📑 본 글은 <혼공컴운>을 읽고 정리한 글입니다.

1. CPU 스케줄링 개요

운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것

1-1. 프로세스 우선순위

프로세스의 종류

• 입출력 집중 프로세스(I/O bound process)
  • I/O burst : 입출력장치를 기다리는 대기 상태가 많음
• CPU 집중 프로세스(CPU bound process)
  • CPU burst : CPU를 이용하는 실행 상태가 많음

프로세스 우선순위

• 운영체제는 각 프로세스의 PCB에 우선순위를 명시한다.
• PCB에 적힌 우선순위를 기준으로 먼저 처리할 프로세스를 결정한다.
• ex) 입출력 작업이 많은 프로세스 / 백그라운드 프로세스는 우선순위가 높다.
• ex2) CPU bound process / 사용자와 상호작용이 잦은 프로세스는 우선순위가 낮다.

1-2. 스케줄링 큐

스케줄링 큐(scheduling queue)

• 운체가 매번 모든 프로세스의 PCB를 뒤적거리면서 다음 차례 프로세스를 결정하는 것은 비효율.

• 줄을 서시오~ for CPU / 메모리 / 입출력장치

• 준비 큐(ready queue): CPU 쓰고 싶은 프로세스 줄 서라~

  • 준비 상태 프로세스들의 PCB 가 준비 큐의 마지막에 삽입된다.
  • 운체가 준비 큐에서 하나씩 꺼내서 실행하는데, 그중에 우선순위가 높은 프로세스 먼저 실행함

• 대기 큐(waiting queue): 입출력장치 쓰고 싶은 프로세스 줄 서라~

  • 대기 큐에 있다가 입출력 완료되면 완료 인터럽트 건다.
  • 운체는 대기 큐에서 작업 완료된 PCB 찾고, 얘를 준비 상태로 바꾸고 대기 큐 → 준비 큐 이동시킴

1-3. 선점형과 비선점형 스케줄링

선점형 스케줄링(preemtive scheduling) ← 운체 pick!

• 운영체제가 프로세스로부터 자원을 강제로 빼앗아서 다른 애한테 줄 수 있음
• 자원 독점을 막고, 골고루 자원 배분 가능
• context switching에서 오버헤드 발생 가능

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

• 현재 자원을 사용하고 있는 프로세스가 종료되거나 스스로 대기 상태로 가기 전에는 빼앗을 수 없다.
• 컨텍스트 스윗칭! 오버헤드 적다
• 모든 프로세스가 골고루 자원을 사용할 수 없다.

2. CPU 스케줄링 알고리즘

2-1. 스케줄링 알고리즘의 종류

선입 선처리 스케줄링(FCFS : First come first served)

• ready queue에 있는 순서대로 처리; 비선점형
• Convoy effect : 프로세스들이 기다리는 시간이 매우 길어질 수 있다.

최단 작업 우선 스케줄링(SJF : Shortest job first)

• ready queue 중 CPU 이용 시간의 길이가 가장 짧은 프로세스 먼저 실행; 비선점형

라운드 로빈 스케줄링(RR : Round Robin)

• FCFS + 타임 슬라이스(각 프로세스가 CPU를 사용할 수 있는 시간)
• 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU 사용한다; 선점형

최소 잔여 시간 우선 스케줄링(SRT: Shortest remaining time)

• SJF + RR
• 타임 슬라이스 만큼 남아있는 작업 시간이 가장 적은 프로세스 먼저; 선점형

우선순위 스케줄링(Priority)

• 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스 먼저
• 기아 문제(Starvation)

  • 우선순위가 낮은 프로세스는 실행이 계속 연기되어서 기다리고 또 기다림

    ⇒ 에이징(Aging)

  • 오랫동안 대기한 프로세스의 우선순위를 높여줌

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

• 우선순위별로 준비 큐를 여러 개 사용한다; 비선점형
  • 우선순위 높은 큐 먼저 처리 → 그 다음 큐 처리 → …
• 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리하다.
• 기아 현상이 발생할 수 있다.

다단계 피드백 큐 스케줄링(Multilevel feedback queue)← 운체 pick!

• 다단계 큐 스케줄링 + 큐 사이를 이동!; 선점형
  • 새로 온 친구 우선순위 가장 높은 큐에 삽입 & 타임슬라이스 만큼 실행
  • 실행이 그 안에 안 끝나면 다음 우선순위 큐로 보냄
  • 거기에서도 안 끝나? 너 유급.
• CPU를 오래 사용해야하는 프로세스들은 우선순위 자연스레 낮아짐
• 우선순위 낮아서 너무 오래 기다리면 Aging → Starvation 해결 가능
  
  

프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시킨다.

프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 높은 우선순위 큐로 이동시킨다.