chapter 11 CPU 스케줄링

11-1 CPU 스케줄링 개요

프로세스 우선순위

프로세스마다 우선순위가 다른데, 우선순위가 높은 프로세스에는 대표적으로 입출력 작업이 많은 프로세스가 있습니다.

프로세스의 종류를 크게 분류하면 입출력 집중 프로세스 (I/O bound process), CPU 집중 프로세스 (CPU bound process)로 나눌 수 있습니다.

운영체제는 각 프로세스의 PCB에 우선순위를 명시하고, PCB에 적힌 우선순위를 기준으로 먼저 처리할 프로세스를 결정합니다.

스케줄링 큐

운영체제는 프로세스들에 ‘줄을 서서 기다릴 것’을 요구합니다. 이 줄을 스케줄링 큐로 구현하고 관리합니다.

대표적인 큐로 준비 큐 (CPU를 이용하고 싶은 프로세스들이 서는 줄), 대기 큐 (입출력 장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄)

우선순위가 낮은 프로세스들이 먼저 큐에 삽입되어 줄을 섰다고 할지라도 우선순위가 높은 프로세스는 그들보다 먼저 처리될 수 있습니다.

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

선점형 스케줄링 - 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식을 의미합니다.

문맥 교환으로 오버헤드가 발생할 수 있습니다.

비선점형 스케줄링 - 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지는 다른 프로세스가 끼어들 수 없는 스케줄링 방식을 의미합니다.

당장 자원을 사용해야 하는 상황에서도 무작정 기다리는 수 밖에 없습니다.

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

스케줄링 알고리즘의 종류

선입 선처리 스케줄링 (FCFS: First come first served scheduling) - 단순히 준비 큐에 산입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식

예를 들어, A - B - C - D의 순서대로 줄을 섰다면 실행 시간이 어떻든 간에 단순히 A - B - C - D의 순서대로 처리하게 됩니다.

최단 작업 우선 스케줄링 (SJF: Shortest job first scheduling) - CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식

예를 들어, 앞의 프로세스 중 CPU 사용 시간이 짧은 프로세스가 C와 B라면 C - B - A의 순서대로 처리할 수 있습니다.

라운드 로빈 스케줄링 - 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링입니다.

최소 잔여 시간 우선 스케줄링 (SRT: Shortest remaining time scheduling)은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아 있는 작업 시간이 가장 적은 프로세스가 선택됩니다.

우선 순위 스케줄링 - 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘입니다. 하지만 우선순위가 높은 프로세스들에 의해 실행이 계속되어 연기될 수 있습니다. 이를 기아현상이라고 합니다.

이를 방지하기 위한 대표적인 기법으로 에이징이 있습니다.

다단계 큐 스케줄링 - 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식입니다.

다단계 피드백 큐 스케줄링 - 프로세스들이 큐 사이를 이동할 수 있습니다. 이로 인해 낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시키는 에이징 기법을 적용하여 기아 현상을 예방할 수 있습니다.