본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 Chapter 11. CPU 스케쥴링 부분을 읽고 정리한 내용입니다.

CPU 스케쥴링이란?

• 프로세스들에게 공정하게 합리적으로 CPU 자원을 배분하는 것
• 제대로 안되면 반드시 실행되어야 할 프로세스들이 실행되지 못하거나 당장 급하지 않은 프로세스들만 주로 실행되는 등 무질서한 상태가 발생할 수도 있음

프로세스 우선순위

• 아주 단순하게 생각해 봤을 때 CPU를 사용 요청을 먼저 보낸 프로세스들을 순서대로 CPU 이용하게 하는 방법
• 합리적인 방식같지만 좋은 방식은 아님
  • 단순히 FIFO 형태로 CPU를 이용하면 비효율적으로 대기 시간이 길 수 있음
  • 또한 프로세스 마다 우선순위가 다르기 때문

일반적인 프로세스가 실행되는 과정

• 대부분의 프로세스들은 CPU와 입출력장치를 모두 사용하며 실행됨 → 실행/대기 상태 반복
  • 예를들어 워드 프로세서에서 CPU를 이용해 명령어 실행, 사용자로부터 입력받은 내용을 보조기억장치에 저장, CPU를 사용하여 명령어를 실행, 사용자가 입력한 내용을 화면에 출력

• 프로세스 종류마다 입출력장치를 이용하는 시간과 CPU를 이용하는 시간의 양에 차이가 있음
  • I/O bound process: 비디오 재생이나 디스크 백업 작업을 담당하는 프로세스와 같이 입출력 작업이 많은 프로세스 (실행상태보다 입출력을 위한 대기 상태에 더 많이 머무름)
  • CPU bound process: 복잡한 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스와 같이 CPU 작업이 많은 프로세스 (대기 상태보다 실행 상태에 더 많이 머무름)

• I/O bound process와 CPU bound process가 동시에 CPU 자원을 요구한 경우
  • I/O bound process를 빨리 실행시켜 입출력 장치를 끊임없이 작동시켜 대기 상태가 되면 CPU bound process에 집중적으로 CPU를 할당하는 것이 더 효율적
    ⇒ 이를 위해 운영체제는 프로세스마다 priority를 부여 (PCB에 명시)

참고) 프로세스의 우선순위를 확인할 수 있는 명령어

$ ps -el
  UID   PID  PPID        F CPU PRI NI       SZ    RSS WCHAN     S             ADDR TTY           TIME CMD
    0     1     0     4004   0  46  0 411466656  19712 -      Rs                  0 ??        12:30.24 /sbin/launchd
    0   146     1     4004   0  31  0 410161104   1776 -      Ss                  0 ??         0:00.01 /usr/libexec/iou
    0   298     1     4004   0  31  0 410536368  41248 -      Ss                  0 ??        10:18.55 /usr/libexec/log
    0   299     1     4004   0   4  0 410397920   2368 -      Ss                  0 ??         0:00.22 /usr/libexec/smd
    0   300     1     4004   0  31  0 410401168   8080 -      Ss                  0 ??         0:53.46 /usr/libexec/Use
    0   302     1     4004   0  20  0 410160192   1024 -      Ss                  0 ??         0:05.09 /System/Library/
    0   303     1  1004004   0  50  0 410516816   7200 -      Ss                  0 ??         7:27.37 /System/Library/

• PRI 컬럼이 process 의 priority 우선순위를 의미

스케쥴링 큐

• PCB에 우선순위가 적혀 있다고 하지만 CPU를 사용할 다음 프로세스를 찾기 위해 운영체제가 모든 프로세스의 PCB를 순회하는건 비효율적
• 또한 새로운 프로세스들이 언제든 생길 수 있음

⇒ 스케쥴링 큐를 구현해 모든 프로세스들을 줄세워 관리
* 자료 구조 관점에서 큐는 FIFO이지만 스케쥴링 큐는 반드시 FIFO일 필요는 없음

크게 Ready queue와 Waiting queue가 있음

• Ready queue: CPU를 이용하고 싶은 프로세스들이 서는 줄
• Waiting queue: 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄
  
  

• 준비 상태에 있는 프로세스들의 PCB는 준비 큐의 마지막에 삽입 되어 CPU를 사용할 차례를 기다림
• 운영체제는 큐에 삽입된 순서대로 프로세스들을 하나씩 꺼내어 실행하되, 그 중 우선순위가 높은 프로세스를 먼저 실행

• 대기 상태에 있는 프로세스도 같은 장치를 요구한 프로세스들은 같은 대기 큐에서 기다림
• 입출력이 완료되어 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾아 준비 상태로 변경한 뒤 waiting queue에서 제거하고 ready queue로 이동

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

• 선점: ‘남보다 앞서서 차지함’을 의미

선점형 스케쥴링(preemptive scheduling)

• 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케쥴링 방식
• 프로세스마다 정해진 시간만큼 CPU를 사용하고 정해진 시간을 모두 소비하여 타이머 인터럽트가 발생하면 운영체제가 해당 프로세스로부터 CPU자원을 뺏은 후 다음 프로세스에 할당하는 방식

장점 & 단점

• 장점: 더 급한 프로세스가 언제든 끼어들어 사용할 수 있고 자원을 골고루 배분할 수 있음
• 단점: context switch 과정에서 오버헤드 발생

비선점형 스케쥴링(Non-preemptive scheduling)

• 하나의 프로세스가 자원을 사용하고 있으면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없는 스케쥴링 방식을 의미 → 하나의 프로세스가 자원 사용을 독점

대부분의 운영체제는 선점형 스케쥴링 방식을 사용

CPU 스케쥴링 알고리즘

스케쥴링 알고리즘의 종류

선입 선처리 스케쥴링 (FCFS 스케쥴링)

• First Come First Served Scheduling 으로 단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케쥴링 방식
• 공정해 보이지만 때때로 프로세스들이 기다리는 시간이 매우 길어질 수 있음

프로세스 A, B, C가 순서대로 준비 큐에 삽입된 상태

• 프로세스 C는 2ms동안 CPU에서 실행되기 위해 22ms라는 긴 시간을 기다려야 함 ⇒ convoy effect (호위효과)

convoy effect를 막기 위해서는 단순히 실행시간이 짧은 프로세스를 먼저 실행하면 됨 ⇒ 최단 작업 우선 스케쥴링

최단 작업 우선 스케쥴링 (Shortest Job First Scheduling)

• 기본적으로 비선점형 스케쥴링 알고리즘으로 분류되지만, 선점형으로 구현될 수도 있음

라운드 로빈 스케쥴링(Round robin scheduling)

• 선입 선처리 스케쥴링에 타임 슬라이스라는 개념이 더해진 스케쥴링 방식

* 타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미

• 큐에 삽입된 순서대로 프로세스들을 실행하되 정해진 시간만큼 사용
• 정해진 시간 내에 프로세스가 완료되지 못하면 다시 큐의 맨 뒤로 삽입됨

예시

• ready queue에 process A, B, C 순서로 삽입되어 있는 경우
• 타임슬라이스: 4ms
  
  

• 타임 슬라이스의 크기가 중요
  • 크면 들어온 순서대로 process를 처리하기 때문에 선입 선처리 스케쥴링과 차이가 없음
  • 작으면 context switch가 자주 발생해 CPU에 부담

최소 잔여 시간 우선 스케쥴링 (Shortest Remaining Time)

• 최단 작업 우선 스케쥴링 + 라운드 로빈 스케쥴링
• 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스는 남은 작업 시간이 가장 적은 프로세스를 선택

우선순위 스케쥴링(Priority scheduling)

• 프로세스들에 우선순위를 부여하고 높은 우선순위를 가진 프로세스부터 실행하는 스케쥴링 알고리즘
  • 우선순위가 같은 프로세스들은 선입 선처리로 스케쥴링

발생할 수 있는 문제

Starvation 현상: 우선순위가 높은 프로세스를 우선하여 처리하는 방식이기에 우선순위가 낮은 프로세스는 ready queue에 먼저 삽입되었음에도 불구하고 계속해서 실행이 연기될 수 있음

⇒ 방지하기 위한 대표적인 기법으로 에이징(aging)이 있음

• 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

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

• 우선순위 스케쥴링의 발전된 형태로 우선순위별로 준비 큐를 여러 개 사용하는 스케쥴링 방식
• 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어있으면 그 다음 우선순위 큐에 있는 프로세스들을 처리

• 큐별로 다양한 스케쥴링을 적용해서 효율적으로 처리 가능
• 단점은 기본적으로 프로세스가 큐 간의 이동이 안되서 우선순위가 낮은 큐에 있는 프로세스는 실행되지 않는 starvation 현상이 발생할 수 있음

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

• 큐 간의 이동이 가능한 다단계 큐 스케쥴링
• 우선순위가 가장 높은 큐에 삽입되어 프로세스가 실행되다가 타임 슬라이스 동안 실행을 다 못 끝내면

• 다음 우선순위 큐에 삽입되고, 결국 CPU를 오래 사용해야 하는 프로세스는 점차 우선순위가 낮아짐

• 즉 CPU-bound process는 자연스레 우선순위가 낮아지고, I/O Bound process는 자연스레 우선순위가 높은 큐에서 실행이 끝남
• 낮은 우선순위 큐에서 너무 오래 기다리는 프로세스는 에이징 기법을 적용해 starvation 현상을 예방할 수 있음
• 구현이 복잡하지만 CPU 스케쥴링의 가장 일반적인 알고리즘 형태로 알려짐

참고

1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"