[운영체제] CPU 스케줄링

CPU 스케줄링: 운영체제의 CPU 배분 방법

CPU 스케줄링 알고리즘: CPU 스케줄링 절차

CPU 스케줄러: CPU 스케줄링 알고리즘을 결정하고 수행하는 운영체제의 일부분

 

실행의 문맥이 있다면 모두 스케줄링의 대상

프로세스뿐만 아니라 스레드도 CPU의 스케줄링 대상이다.

* 실행의 문맥을 가지고 있는 모든 것을 스케줄링할 수 있기 때문

---

우선순위

운영체제는 프로세스별 우선순위(priority)를 판단하여 PCB에 명시하고, 우선순위가 높은 프로세스에 CPU의 자원을 더 빨리, 많이 할당한다.

사용자가 일부 프로세스의 우선순위를 높일 수도 있다.

ps 명령어를 통해 프로세스의 우선순위를 확인할 수 있다.

 

운영체제는 CPU활용률(CPU utilization)과 같은 고려 요소를 고려하여 우선순위를 할당한다.

운영체제는 높은 CPU 활용률을 유지하기 위해 기본적으로 입출력 작업이 많은 프로세스의 우선순위를 높게 유지

• CPU 활용률: 전체 CPU의 가동 시간 중 작업을 처리하는 시간의 비율
• CPU 버스트(CPU burst): 프로세스가 CPU를 이용하는 작업
• 입출력 버스트(I/O burst): 입출력장치를 기다리는 작업

 

프로세스마다 입출력장치를 이용하는 시간과 CPU를 이용하는 시간의 양에 차이가 있다.

주로 머무르는 상태가 달라서 모든 프로세스가 동일한 시간의 빈도로 CPU를 사용하는 것은 합리적이지 않다.

입출력 집중 프로세스와 CPU 집중 프로세스가 동시에 CPU의 자원을 요구했다면, 입출력 집중 프로세스를 가능한 빨리 실행시켜 끊임없이 입출력 장치를 작동시킨 다음, CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 합리적

입출력장치가 입출력 작업을 완료 전에 입출력 집중 프로세스는 대기 상태가 되므로, 입출력 집중 프로세스를 먼저 처리 후 다른 프로세스를 실행시켜 CPU 활용률을 높일 수 있다. 따라서 입출력 집중 프로세스는 일반적으로 CPU 집중 프로세스보다 우선순위가 높다.

• 입출력 집중 프로세스(I/O bound Process)
  • 입출력 작업이 많은 프로세스
  • 비디오 재생이나 디스크 백업 작업을 담당하는 프로세스
  • 실행 상태보다 입출력을 위한 대기 상태에 더 많이 머무름

• CPU 집중 프로세스(CPU bound Process)
  • CPU 작업이 많은 프로세스
  • 복잡한 수학 연산이나 그래픽 처리 작업을 담당하는 프로세스
  • 대기 상태보다 실행 상태에 더 많이 머무름

---

스케줄링 큐 (Scheduling Queue)

CPU를 이용하고 싶은 프로세스의 PCB와 메모리로 적재되고 싶은 프로세스의 PCB, 특정 입출력장치를 이용하고 싶은 프로세스의 PCB를 큐에 삽입하여 줄 세우는 것

자료구조 관점에서 큐는 본래 선입선출 구조를 따르지만, 스케줄링에 사용되는 큐가 반드시 선입선출일 필요는 없다.

• 준비 큐(ready queue)
  • CPU를 이용하고 싶은 프로세스의 PCB가 서는 줄
  • 준비 상태인 프로세스의 PCB는 준비 큐의 마지막에 삽입되어 CPU를 사용할 차례를 기다린다.
• 대기 큐(waiting queue)
  • 대기 상태에 접어든 프로세스의 PCB가 서는 줄
  • 주로 입출력 작업을 수행 중일 경우, 대기 큐에서 대기 상태로 입출력 완료 인터럽트를 기다리게 된다.
  • 같은 입출력장치를 요구한 프로세스들은 같은 대기 큐에서 기다린다.

운영체제는 큐에 삽입된 순서대로 실행하되, 우선순위가 높은 프로세스로부터 먼저 실행한다.

실행되는 프로세스가 할당받은 시간을 모두 소모할 경우(타이머 인터럽트를 받을 경우), 준비 큐로 다시 이동하고, 실행 도중 입출력 작업을 수행하는 등 대기 상태로 접어들어야 할 경우 대기 큐로 이동하게 된다. 

입출력이 완료되어 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾고, 이 PCB를 준비 상태로 변경한 뒤 큐에서 제거되고, 해당 PCB는 준비 큐로 이동

---

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

스케줄링은 기본적으로 프로세스의 실행이 끝나면 이루어진다.

프로세스가 종료되지 않았음에도 실행 도중 스케줄링이 수행되기도 한다.

실행 도중 스케줄링이 이루어지는 경우

1. 실행 상태에서 입출력 작업을 위해 대기 상태로 전환될 때 (입출력 작업)

2. 실행 상태에서 타이머 인터럽트가 발생해 준비 상태로 변경될 때 (타이머 인터럽트)

 

선점형 스케줄링(preemptive scheduling): 입출력 작업 + 타이머 인터럽트

현재 어떤 프로세스가 CPU를 할당받아 사용하고 있더라도, 운영체제가 프로세스로부터 CPU 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링

언제든 더 급한 프로세스가 끼어들어 CPU를 사용할 수 있으므로 한 프로세스의 CPU 독점을 막고 여러 프로세스에 골고루 CPU 자원을 배분할 수 있다.

context switching시 오버헤드가 발생할 수 있다.

비선점형 스케줄링(non-preemptive scheduling): 입출력 작업

어떤 프로세스가 CPU를 사용하고 있을 때 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없는 스케줄링 방식

context switching 횟수가 적어 오버헤드가 적다.

어떤 프로세스가 CPU를 사용 중이라면 당장 CPU를 사용해야 하는 프로세스라도 무작정 기다려야 한다.

---

CPU 스케줄링 알고리즘

운영체제가 프로세스에 CPU를 배분하는 방법

선입 선처리 스케줄링(FCFS, First Come First Serve): 비선점형

단순히 준비 큐에 삽입된 순서대로 먼저 CPU를 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식

프로세스들이 기다리는 시간이 매우 길어질 수 있다.

convoy effect(호위 효과): 먼저 삽입된 프로세스의 오랜 실행 시간으로 인해 나중에 삽입된 프로세스의 실행이 지연되는 문제

최단 작업 우선 스케줄링(SJF, Shortest Job First): 비선점형

준비 큐에 삽입된 프로세스 중 CPU를 이용하는 시간의 길이가 가장 짧은 프로세스부터 먼저 실행하는 스케줄링 방식

기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 최소 잔여 시간 우선 스케줄링을 통해 선점형으로 구현될수도 있다.

라운드 로빈 스케줄링(Round Robin): 선점형

큐에 삽입된 프로세스들이 삽입된 순서대로 CPU를 이용하되, 정해진 타임슬라이스만큼만 CPU를 이용하는 스케줄링 방식

프로세스가 정해진 시간을 모두 사용하고도 완료되지 않으면 context switching이 발생해 다시 큐의 맨 뒤에 삽입

선업 선처리 스케줄링 + 타임 슬라이스(Time Slice)

타임 슬라이스 (Time Slice)

• 프로세스가 CPU를 사용할 수 있는 최대 시간 단위를 지정
• 프로세스가 지정된 시간을 모두 사용하거나 작업이 끝나면, CPU를 다른 프로세스에게 할당
• 타임 슬라이스가 끝난 후 프로세스가 완료되지 않았을 경우, 컨텍스트 스위칭 (Context Switching)이 발생하며, 해당 프로세스는 큐의 맨 뒤로 이동

최소 잔여 시간 우선 스케줄링(SRT, Shortest Remaining Time): 선점형

SJF (Shortest Job First)와 RR (Round Robin)의 특징을 결합한 스케줄링 방식
남아 있는 실행 시간이 가장 짧은 프로세스를 우선적으로 실행하며, 새로운 프로세스가 도착할 때마다 작업을 중단하고 비교

컨텍스트 스위칭의 오버헤드와 긴 프로세스의 기아(starvation) 문제가 발생할 수 있다.

• 기아(starvation): 운영체제의 자원 관리나 스케줄링에서 발생하는 문제로, 특정 프로세스나 스레드가 무기한으로 필요한 자원을 할당받지 못하는 상태

우선순위 스케줄링(Priority): 선점형, 비선점형

프로세스에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 방식

우선순위가 낮은 프로세스는 우선순위가 높은 프로세스로 인해 계속해서 실행이 연기될 수 있다.

프로세스의 기아(starvation) 문제가 발생할 수 있다.

이를 해결하기 위해 aging을 적용하여, 오랫동안 대기한 프로세스의 우선순위를 높여서 계속 기다리는 프로세스를 없앤다.

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

우선순위 스케줄링의 발전된 형태

우선순위별로 여러 개의 준비 큐를 사용하는 스케줄링 방식

우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리하고, 우선순위가 가장 높은 큐가 비면, 그 다음으로 우선순위가 높은 큐에 있는 프로세스를 처리

프로세스들이 큐 사이를 이동할 수 없어서 우선순위가 낮은 프로세스의 작업이 계속해서 연기될 수 있다. (starvation 발생 가능)

starvation을 해결하기 위해 다단계 피드백 큐 스케줄링

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

다단계 큐 스케줄링과 비슷하게 동작하지만, 프로세스들이 큐 사이를 이동할 수 있다.

다단계 큐 스케줄링(Multilevel Queue Scheduling)의 단점을 보완하기 위해 설계되었음

 

큐 간 이동

• 프로세스는 실행 시간, 대기 시간 또는 우선순위 변화에 따라 상위 큐 또는 하위 큐로 이동
• 처음에는 높은 우선순위 큐에서 시작하며, 타임 슬라이스를 초과하거나 실행 시간이 길어질수록 낮은 우선순위 큐로 이동

새로운 프로세스

• 새로운 프로세스는 항상 가장 높은 우선순위 큐에 삽입
• 이후 프로세스의 특성에 따라 적절한 큐로 이동

기아(starvation) 방지

• 낮은 우선순위 큐에서 오랫동안 대기한 프로세스는 상위 큐로 이동하도록 설계하여 기아 문제를 해결

---

기아 현상(Starvation)

운영체제의 자원 관리나 스케줄링에서 발생하는 문제로, 특정 프로세스나 스레드가 무기한으로 필요한 자원을 할당받지 못하는 상태를 의미한다.

즉, 어떤 프로세스가 계속해서 실행 기회를 얻지 못해 작업을 진행하지 못하는 상황을 말한다.

기아 발생 원인

우선순위 기반 스케줄링

• 우선순위가 높은 작업이 계속해서 새로 도착하면, 우선순위가 낮은 작업은 실행 기회를 얻지 못함
• 낮은 우선순위 프로세스가 무한 대기 상태에 빠질 가능성

자원 할당 문제

• 특정 프로세스가 필요한 자원을 계속해서 다른 프로세스가 차지하고 있다면, 해당 프로세스는 대기 상태에 빠짐

경쟁 조건

• 여러 프로세스가 한정된 자원을 경쟁할 때, 일부 프로세스가 계속해서 자원을 얻지 못할 수 있음

선점형 스케줄링

• 특정 작업이 자주 선점당하고, 실행 기회가 지속적으로 뒤로 밀리면서 무기한 대기

기아 해결 방법

우선순위 조정 (Priority Aging)

• 시간이 지남에 따라 오래 대기한 프로세스의 우선순위를 점진적으로 높여주는 방식
• 오래 대기한 프로세스가 결국 실행 기회를 얻도록 보장

타임 슬라이스

• 모든 프로세스가 공평하게 CPU를 일정 시간 동안 사용하도록 강제
• 라운드 로빈(Round Robin) 같은 방식에서 기아가 발생하지 않음

자원 예약

• 특정 자원을 필요로 하는 프로세스를 위해 자원을 미리 예약하여 대기 시간을 최소화

페어 쉐어 스케줄링 (Fair Share Scheduling)

• 프로세스나 스레드가 공정하게 자원을 분배받도록 보장하는 방식

기아와 교착 상태의 차이

기아 (Starvation)

• 프로세스가 자원을 기다리지만 할당받을 기회를 얻지 못함
• 자원은 사용 가능하지만, 특정 프로세스에 우선 배정되지 않는 문제

교착 상태 (Deadlock)

• 여러 프로세스가 서로 자원을 점유하고 대기하면서, 자원 할당이 완전히 멈춘 상태
• 모든 관련 프로세스가 멈춰버림