[CS] 혼공컴운 Chapter 11. CPU 스케줄링

11-1 CPU 스케줄링 개요

운영체제가 프로세스들에게 공정하고 합리적으로 CPU자원을 배분하는 것을 CPU 스케줄링이라고 한다.

프로세스 우선순위

• 프로세스의 중요도에 따라 운영체제가 우선순위(priority)를 부여.
• 우선순위가 높은 프로세스는 대표적으로 입출력 작업이 많은 프로세스.
• 입출력 작업을 완료하기 전까지 입출력 집중 프로세스는 대기 상태가 되므로, 다른 프로세스가 CPU를 사용할 수 있기 때문.

 

스케줄링 큐

• 각 프로세스의 PCB에 부여된 우선순위에 따라 CPU를 사용할 수 있도록 줄을 세우는 것이 스케줄링 큐(scheduling queue)
• 대표적인 큐로 준비 큐(ready queue: CPU를 이용하고 싶은 프로세스들이 서는 줄)와 대기 큐(waiting queue: 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄)가 있다.

 

선점형 스케줄링

• 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식 -> 자원 독점 불가능
• 운영체제에 의해 인터럽트가 걸려 비자발적으로 준비 큐로 이동될 수 있다.
• 비선점에 비해 프로세스 간 문맥 교환이 자주 발생하기 때문에 이로 인한 오버헤드가 발생할 수 있다.
• 하지만 어떤 한 프로세스가 CPU를 오랫동안 독점하는 현상을 방지할 수 있으므로 비선점보다 더 나은 서비스를 제공한다.

 

비선점형 스케줄링

• 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식 -> 자원 독점 가능
• 모든 프로세스가 골고루 자원을 사용할 수 없다.

 

11-2 CPU 스케줄링 알고리즘

스케줄링 알고리즘 종류

• FCFS(First Come First Served): 준비 큐에 삽인된 순서대로 CPU를 할당. 비선점형
• RR(Round-Robin): 정해진 타임 슬라이스(CPU를 사용할 수 있는 정해진 시간)만큼의 시간동안 CPU를 할당. 선점형
• SJF(Shortest Job First): 예상 CPU 사용 시간이 짧은 프로세스를 먼저 실행. 비선점형
• SRT(Shotest Remaining Time): SJF와 RR을 합친 스케줄링 방식. 선점형
• 우선순위(Priority Scheduling): 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 알고리즘. 우선순위가 낮은 프로세스는 실행이 계속 연기되어 기아(starvation) 현상에 빠질 수 있음. 따라서 에이징(aging)이라는 기법을 통해 시간 흐름에 따라 우선순위를 증가시켜 기아 현상 방지.
• Multilevel Feedback: 우선순위별 준비 큐를 여러 개 사용하는 스케줄링 알고리즘으로, 프로세스가 정해진 타임 슬라이스 동안 해당 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐로 삽입되어 CPU를 오래 사용해야 하는 프로세스는 점차 우선순위가 낮아짐. 또한 낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시키는 에이징 기법을 적용하여 기아 현상을 예방.

Multilevel Feedback Scheduling

 

다양한 스케줄링 정책들의 특징

실제 예를 통한 스케줄링 정책들의 비교