CPU 스케줄링

• 운영체제가 프로세스들에게 합리적으로 CPU 자원을 배분하는 것
• 각 프로세스에는 우선순위가 존재
  • 우선순위는 PCB에 명시되어 있음(PRI)
    
    

• 우선순위가 높은 프로세스가 더 빨리, 많이 실행
• I/O-bound Process, CPU-bound Process
  • I/O-bound Process: 입출력 작업을 중심으로 하는 프로세스 → 입출력을 위한 waiting 상태에 더 많이 머무름
  • CPU-bound Process: cpu의 연산 등의 작업을 중심으로 하는 프로세스

스케줄링 큐

• 프로세스의 상태와 관련지어 생각해 볼 것

• ready queue, waiting queue

  • ready queue
    • CPU를 사용하고 싶은 프로세스들이 들어가는 큐
    • 프로세스가 처음 시스템에 들어오면 ready queue로 들어감
    • 준비 및 CPU 할당을 기다림
    • linked list로 구현됨
      • ready queue의 header는 리스트의 첫 pcb를 가리킴
      • 각 pcb는 다음 pcb를 가리키는 포인터를 포함
  • waiting queue
    • I/O 장치를 사용하기 위해 waiting된 프로세스들이 들어가는 큐
    • waiting queue 순서
      1. I/O 작업이 완료되면 waiting queue에서 작업이 완료된 PCB를 찾는다.
      2. 해당 PCB를 ready 상태로 변경
      3. 해당 PCB를 waiting queue에서 제거
      4. ready queue로 이동

• 큐에 삽입된 순서로 실행하되, 우선순위가 높은 프로세스를 먼저 실행

  
  

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

선점형 스케줄링(Preemptive Scheduling)

• 프로세스가 CPU 자원을 할당받아 사용하고 있더라도, 운영체제가 CPU 자원을 빼앗아 다른 프로세스에 할당할 수 있는 방식
• 현재 대부분 운영체제의 스케줄링 방식
• 어느 한 프로세스의 자원 독점을 막는다
• context switching 과정에서 오버헤드

비선점형 스케줄링(Non-Preemptive Scheduling)

• 프로세스가 CPU 자원을 할당받아 사용하고 있을 때, 운영체제가 CPU 자원을 빼앗을 수 없는 스케줄링 방식
• context switching 오버헤드가 선점형 스케줄링보다 적다
• 계속 기다려야 하므로 모든 프로세스가 골고루 자원 사용 불가

CPU 스케줄링 알고리즘

스케줄링 기준

• CPU utilization(cpu 이용률)
• Throughput(처리량)
• Turnaround time(총처리 시간)
• Waiting time(대기 시간)
  • ready queue에서 대기하면서 보낸 시간
• Response time(응답 시간)
  • 하나의 요구를 제출했을 때, 첫 번째 응답이 돌아오는 시간

CPU utilization, throughput이 클수록,
turnaround time, waiting time, response time이 적을수록 바람직하다.
→ 읽어보면 당연한 말!

FCFS - First Come First Served

• ready queue에 삽입된 순서대로 프로세스를 처리
  • 따라서 non-preemptvie
• convey effect 발생 가능성
  • convey effect: CPU를 오래 사용하는 프로세스가 먼저 도착하면, 다른 모든 프로세스는 무작정 기다려야 한다.

SJF - Shortest Job First

• ready queue의 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 것 우선으로
  • non-preemptive
• CPU 이용 시간이 같을 시, FCFS 스케줄링
• waiting time이 최소

RR - Round Robin

• FCFS와 유사하지만 time slice 개념 추가
  • time slice: 프로세스가 CPU를 사용할 수 있는 정해진 제한 시간
  • 정해진 time slice만큼 시간 동안 돌아가며 CPU를 사용함
  • 프로세스가 완료되지 않았다면, queue의 맨 뒤에 삽입
• context switching 발생
  

SRT - Shortest Remaining Time

• preemptive한 SJF 스케줄링
• SJF + RR
  • 정해진 time slice만큼 CPU를 사용하되, 다음 프로세스는 남아 있는 작업 시간이 가장 짧은 프로세스 선택

Priority Scheduling

• 우선순위에 따라 스케줄링
• 우선순위가 같을 시 FCFS 순서로 처리
• 우선순위가 높은 프로세스만 계속해서 실행됨
• starvation 현상 발생
  • ready queue에 먼저 삽입되었음에도 실행이 연기될 수 있음
• starvation을 방지하기 위한 aging 기법
  • 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 것

Multilevel Queue Scheduling

• priority scheduling의 발전된 형태
• 우선순위별로 ready queue를 여러 개 사용
• 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 모두 처리한 후 그다음 우선순위의 큐를 처리
• 큐별로 여러 time slice 사용 가능
• 큐별로 여러 cpu scheduling 알고리즘 사용 가능
• 마찬가지로 starvation 현상 발생

Multilevel Feedback Queue Scheduling

• 프로세스들이 큐 사이를 이동할 수 있는 Multilevel Queue Scheduling

• CPU를 오래 사용하는 프로세스는 점차 우선 순위가 낮아진다.

• 프로세스가 큐 사이를 이동할 수 있으므로, 낮은 우선순위에서 오래 대기한 프로세스는 점차 우선순위가 높은 큐로 이동한다. → starvation 방지

• 구현이 복잡하다.

• 가장 일반적인 CPU 스케줄링

• multilevel feedback queue의 parameter 요소들

  • 큐의 개수
  • 각 큐의 스케줄링 알고리즘
  • 높은 우선순위 큐로 이동하기 위한 method
  • 낮은 우선순위 큐로 이동하기 위한 method
  • 프로세스가 처음 들어왔을 때 어떤 큐로 갈지 결정하는 method
  • 등등
  
  

---

Reference

혼자 공부하는 컴퓨터구조+운영체제
공룡책