CPU 스케쥴링 (운영체제)

‘혼자 공부하는 컴퓨터구조+운영체제 - 강민철’ 책을 참고하여 작성한 포스트입니다.

---

CPU 스케줄링(CPU scheduling) 이란?

모든 프로세스는 CPU를 필요로 한다. 운영체제가 이러한 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것.

프로세스 우선순위

• 우선순위가 높은 프로세스 일수록 더 빨리 처리해주어야 하는 프로세스이다.
• 프로세스를 종류마다 CPU를 이용하는 시간의 양에는 차이가 있다.
• CPU를 이용하는 작업을 CPU 버스트(CPU burst) 라고 하고, 입출력장치를 기다리는 작업을 입출력 버스트(I/O burst) 라고 하는데,
• CPU 버스트가 많은 프로세스를 CPU 집중 프로세스 라고 하며, 입출력 버스트가 많은 프로세스를 입출력 집중 프로세스 라고 한다.
• 입출력 집중 프로세스를 가능한 한 빨리 실행시켜 대기 상태로 보내고, CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 효율적일 것!
• 이렇게 각각의 상황에 맞게 CPU를 배분할 수 있도록 운영체제는 프로세스마다 우선순위를 부여한다.

스케줄링 큐

• 운영체제가 매번 모든 PCB의 우선순위를 검사하여 먼저 자원을 이용할 프로세스를 결정하는 것은 효율적이지 않다.
• 그래서 운영체제는 스케줄링 큐(scheduling queue) 를 구현하고 프로세스들을 큐에 삽입하여 관리한다.
• 대표적으로 준비 상태에 들어간 프로세스들이 삽입되는 준비 큐(ready queue)와 대기 상태에 들어간 프로세스들이 삽입되는 대기 큐(waiting queue)가 있다.
• 운영체제는 준비 큐에서 우선순위가 높은 프로세스를 pop해 실행한다.
• 입출력이 완료되어 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾아 해당 PCB를 대기 큐에서 꺼내 준비 큐로 삽입한다.

선점형과 비선점형 스케줄링

선점형 스케줄링(preemptive scheduling)

• 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식
• 타이머 인터럽트가 발생했을 때 운영체제가 해당 프로세스로부터 CPU 자원을 빼앗아 다음 프로세스에 할당하는 방식이 한 예다.
• 프로세스의 자원 독점을 막고 골고루 자원 배분이 가능하지만, 문맥 교환 과정에서 오버헤드가 발생 가능하다.

비선점형 스케줄링(non-preemptive scheduling)

• 한 프로세스가 자원을 사용하고 있을 때 그 프로세스가 종료되거나 스스로 대기 상태에 들어가기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식.
• 문맥 교환 과정에서 발생하는 오버헤드가 적지만, 당장 자원을 사용해야 하는 상황에서도 무작정 기다릴 수밖에 없는 단점이 있다.

스케줄링 알고리즘

스케줄링 알고리즘 종류는 매우 다양하고 운영체제마다 제각각이다. 여기서 언급하는 알고리즘들은 ‘아이디어’이지 ‘용어’가 아니다!

선입 선처리 스케줄링

• FCFS 스케줄링(First Come First Served Scheduling) 이라고도 불린다.
• 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식이다.
• 앞 선 프로세스의 처리 시간이 너무 길면 뒤의 처리 시간이 짧은 프로세스가 긴 시간을 기다려야 되는 호위 효과(convoy effect) 현상이 발생할 수 있다.

최단 작업 우선 스케줄링

• 준비 큐 안의 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식.
• SJF 스케줄링(Shortest Job First Scheduling) 이라고도 부른다.
• 일반적으로 비선점형 스케줄링 방식으로 분류한다.
• 선점형 스케줄링 방식으로 구현하면 선점형 최단 작업 우선 스케줄링 이라고 한다.

라운드 로빈 스케줄링

• 라운드 로빈 스케줄링(round robin scheduling) 은 선입 선처리 스케줄링에 타임 슬라이스 개념이 더해진 스케줄링 방식이다.
• 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링 방식이다.
• 시간 내 프로세스가 완료되지 않으면 다시 준비 큐 맨 뒤에 삽입되며 이때 문맥 교환이 발생한다.
• 타임 슬라이스 크기 설정이 매우 중요하다. 너무 크면 선입 선처리 스케줄링과 비슷해서 호위 효과가 발생할 수 있고, 너무 작으면 문맥교환이 너무 자주 일어나 오버헤드?

최소 잔여 시간 우선 스케줄링

• SRT 스케줄링(Shortest Remaining Time) 이라고도 부른다.
• 최단 작업 우선 알고리즘과 라운드 로빈 알고리즘을 합친 스케줄링이다.
• 정해진 타임 슬라이스 크기 만큼 CPU를 사용하되, 다음 CPU를 사용할 프로세스는 남은 작업 시간이 가장 적은 프로세스가 선택된다.

우선순위 스케줄링(priority scheduling)

• 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하되, 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링된다.
• 우선순위가 높은 프로세스들에 의해 우선순위가 낮은 프로세스의 실행이 계속 연기되는 기아(starvation)현상이 발생할 수 있다.
• 이를 방지하기 위한 기법으로 에이징(aging) 이 있다. 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식이다.

다단계 큐 스케줄링(multilevel queue scheduling)

• 우선순위 별로 준비 큐를 여러 개 사용하는 스케줄링 방식.
• 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리한다.
• 큐 별로 프로세스 종류를 다르게 할 수도 있고, 타임 슬라이스 지정 등 다른 스케줄링 알고리즘 적용도 가능하다.

다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)

• 다단계 큐 스케줄링에서 기아 현상이 나타날 수 있는데 이를 보완한 스케줄링 방식이다.
• 타임 슬라이스 동안 프로세스 실행 후 완료 되지 않으면 더 낮은 우선순위 큐에 삽입되어 실행된다.
• 즉, CPU 집중 프로세스들은 자연스럽게 우선순위가 낮아지고, CPU를 비교적 적게 사용하는 입출력 집중 프로세스들은 자연스레 우선순위가 높은 큐에서 실행이 끝난다.
• 에이징 기법으로 오래 기다리는 프로세스는 더 높은 우선순위 큐에 삽입한다.
• 가장 구현이 복잡하지만, 가장 일반적인 CPU 스케줄링 알고리즘이다.

정리

• CPU 스케줄링은 공정하고 합리적으로 CPU 자원을 배분하는 방법
• 프로세스는 우선순위를 가지고 있고, 이는 PCB에 명시된다.
• 운영체제는 호율적인 스케줄링을 위해 스케줄링 큐를 사용한다.
• 준비 큐는 CPU 할당을 기다리는 프로세스들을 위한 큐
• 대기 큐는 입출력장치를 기다리는 프로세스들을 위한 큐
• 선점형 스케줄링은 프로세스가 이용 중인 자원을 뺏을 수 있다
• 비선점형 스케줄링은 그렇지 않다.

선입 선처리 스케줄링 알고리즘은 준비 큐에 삽입된 순서대로 CPU를 할당한다
최단 작업 우선 스케줄링 알고리즘은 준비 큐에 삽입된 프로세스들 중 CPU 사용 시간의 길이가 가장 짧은 프로세스부터 CPU를 할당한다
라운드 로빈 스케줄링 알고리즘은 정해진 시간만큼만 돌아가며 CPU를 할당한다
우선순위 스케줄링 알고리즘은 가장 높은 우선순위를 가진 프로세스에 CPU를 할당한다
다단계 피드백 큐 스케줄링 알고리즘은 프로세스들이 큐 사이를 이동할 수 있는 다단계 큐 스케줄링이다.