[OS] 스케줄러

프로세스 상태

프로세스를 스케줄링 하기 위한 Queue 의 3가지 종류

• Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합
• Ready Queue : 현재 메모리 내에 있으면서 CPU 를 잡아서 실행되기를 기다리는 프로세스의 집합
• Device Queue : Device I/O 작업을 대기하고 있는 프로세스의 집합

스케줄러

• 장기스케줄러(Long-term scheduler or job scheduler)
  • New → Ready. 시작 프로세스 중 어떤 것들을 ready queue로 보낼지 결정
  • 메모리와 디스크 사이의 스케줄링을 담당.
  • 프로세스에 memory(및 각종 리소스)를 할당(admit)
  • degree of Multiprogramming 제어(실행중인 프로세스의 수 제어)
• 단기스케줄러(Short-term scheduler or CPU scheduler)
  • CPU 와 메모리 사이의 스케줄링을 담당.
  • Ready Queue 에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정.
  • 프로세스에 CPU 를 할당(scheduler dispatch)
  • 프로세스의 상태 ready -> running -> waiting -> ready
• 중기스케줄러(Medium-term scheduler or Swapper)
  • 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄 (swapping)
  • 프로세스에게서 memory 를 deallocate. 빼앗는다.
  • degree of Multiprogramming 제어
  • 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러.
  • 프로세스의 상태ready -> suspended
  • Process state - suspended: 외부적인 이유로 프로세스의 수행이 정지된 상태로 메모리에서 내려간 상태를 의미한다. 프로세스 전부 디스크로 swap out 된다. blocked 상태는 다른 I/O 작업을 기다리는 상태이기 때문에 스스로 ready state 로 돌아갈 수 있지만 이 상태는 외부적인 이유로 suspending 되었기 때문에 스스로 돌아갈 수 없다. -> 중기 스케줄러에 의해 생겨난 상태.

Blocked: 자신이 요청한 event가 만족되면 Ready
Suspended: 외부에서 resume해 주어햐 Active

Scheduling Criteria

• CPU utilization (이용률)
  - 사장님 입장에서 주방장이 놀지 않고 일한 비율
• Throughput (처리량)
  - 단위 시간 당 몇명의 손님이 다녀갔는지
• Turnaround time (소요 시간, 반환 시간)
  - 손님의 입장에서 주문하고 음식을 다 먹고 나가기까지의 시간
• Waiting time (대기 시간)
  - 모든 음식을 기다린 시간
• Response time (응답 시간)
  - 첫 음식이 나오기까지 걸리는 시간

CPU 스케줄러

대상: Ready Queue 에 있는 프로세스
목적: cpu 사용효율 극대화

• FCFS(First Come First Served)
  • 먼저 온 순서대로 처리.
  • 비선점형(Non-Preemptive) 스케줄링
  • 문제점
    • convoy effect: 소요시간이 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상이 발생한다.
• SJF(Shortest - Job - First)
  • 다른 프로세스가 먼저 도착했어도 CPU burst time 이 짧은 프로세스에게 선 할당
  • 비선점형(Non-Preemptive) 스케줄링
  • 문제점
    • Starvation(기아 현상): CPU 사용시간이 긴 프로세스는 영원히 CPU를 사용하지 못할수 있음
    • CPU 사용시간을 미리 알수 없음 → SJF 는 CPU 사용시간을 알아야 가능
      • 과거의 CPU burst time 을 이용해서 추정
• SRTF(Shortest Remaining Time First)
  • 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
  • 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU 를 뺏긴다.
  • 선점형 (Preemptive) 스케줄링. 선점형 SJF scheduling
  • 문제점
    • starvation(기아 현상)
• Priority Scheduling
  • 우선순위가 제일 높은 프로세스에게 CPU를 할당 (보통 정수값으로 표현, 대부분 정수중에서 작은 정수가 우선순위가 높다고 표현)
    
  • 선점형(Preemptive) 스케줄링 방식
    • 더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU 를 선점한다.
  • 비선점형 스케줄링(Non-Preemptive) 방식
    • 더 높은 우선순위의 프로세스가 도착하면 Ready Queue 의 Head 에 넣는다.
  • 문제점
    • starvation
    • 무기한 봉쇄(Indefinite blocking)
  • 해결책!
    • aging: 아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여주자.
• Round Robin
  • 선점형 FCFS with time quantum(할당 시간, 10 to 100 milliseconds)
  • circular queue: 할당 시간이 지나면 프로세스는 선점당하고 ready queue 의 제일 뒤에 가서 다시 줄을 선다.
  • RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적
  • RR이 가능한 이유는 프로세스의 context 를 save 할 수 있기 때문이다.
  • 장점
    • 응답시간 response time이 빨라진다.
    • 다른 스케줄링처럼 예측 할 필요도 없다.
  • 주의할 점
    • time quantum이 너무 커지면 FCFS와 같아진다.
    • 또 너무 작아지면 스케줄링 알고리즘의 목적에는 이상적이지만 잦은 context switch 로 overhead 가 발생한다.
    • 그렇기 때문에 적당한 time quantum을 설정하는 것이 중요하다.
• Combine RR and Priority scheduling

Multilevel Queue

Multi-Level Feedback Queue

Multi-Processor Scheduling

Real-time Scheduling

Thread Scheduling