[OS] CPU 스케줄링 : 최단 작업 우선 스케줄링, 라운드 로빈 스케줄링

🤷‍♀️ CPU 스케줄링이란?

아나.. 글씨 크기 조절 가능한거 지금앎..

 

• OS는 메모리에 여러 개의 프로세스를 올려놓고, CPU의 가동 시간을 적절히 나누어 각각의 프로세스에게 분배하여 실행하도록 한다.
  현재 실행 중인 프로세스로부터 다른 프로세스로 CPU를 넘겨주어야 때 기다리고 있는 프로세스들 중에 어떤 프로세스를 선택해야 할지에 대한 방식,기준
• 장기 스케줄링 - 어느 작업을 커널에 등록시켜 프로세스로 만들어 줄 것인가
  중기 스케줄링 - 보류 상태의 프로세스들(위에서 등록한 프로세스) 중에서 어느 프로세스에게 메모리를 할당해 줄 것인가
  단기 스케줄링 - 준비 상태의 프로세스들(위에서 할당받은 프로세스) 중에서 어느 프로세스에게 CPU를 할당할 것인가. <- 일반적으로 부르는 스케줄링
• 사용자 관점에서는 응답시간, 시스템 관점에서는 CPU의 처리량과 활용도가 성능 지표가 된다.

 

🏃‍♀️ 최단 작업 우선 스케줄링

 

• SJS(Shortest Job First) 스케줄링, SPN(Shortest Process Next) 스케줄링이라고도 불린다.
• 준비 큐에서 기다리고 있는 프로세스 중에서 가장 짧은(CPU 요구량이 가장 적은) 프로세스를 먼저 실행시켜 준다.
• 프로세스가 자원을 할당받으면 스스로 반납할 때까지 계속 그 자원을 사용하도록 하는 비선점 방식이다.(Nonpreemption) <-> SRT(Shortest Remaining Time) 스케줄링
• 단점 :
  긴 프로세스는 자원을 할당받지 못한 상태에서 짧은 프로세스가 계속해서 도착할 수 있으므로, 무한 대기 현상이 발생할 수 있다.
  각 프로세스들의 크기를 실행 전에 정확히 알 수 없다. 비슷한 환경에서 자주 실행되어 지는 프로세스는 지수 평균으로 추측하여 스케줄링 하기도 한다.

지수 평균 (exponential averaging)

• 예시

프로세스	도착 시간	CPU 요구량(초)
P1	0	10
P2	0.5	5
P3	1	2
P4	1	4

💫 라운드 로빈 스케줄링

 

• TMI : 라운드 로빈의 사전적 의미는 서명한 사람의 순서를 밝히지 않기 위해 원형으로 서명한 항의서 사발통문(沙鉢通文)이다. 즉, 그런 식으로 모든 프로세스의 순서를 공평하게 하자는 식으로 지은 것 같은데... 이건 뇌피셜이다.
• FCFS 스케줄링 기반(First Come First Service, 온 순서대로 실행시키는 비선점방식) 으로 하되,
  각 프로세스는 한 번에 쓸 수 있는 CPU 시간 크기(시간 할당량)이 지나면 시간 종료 인터럽트에 의해 CPU를 뺏기는 선점 방식이다.
• 기본적 라운드 로빈
• 가상(Virtual) 라운드 로빈
  - 기본적 라운드 로빈에서는 입출력 위주의 프로세스는 입출력을 발생시킨 다음, 입출력이 완료되면 바로 준비 큐의 맨 뒤로 돌아간다. 이 때, 시간 할당량이 남아있다면, 그 시간은 보상받지 못한다. 반면, 연산 위주의 프로세스는 시간 할당량을 모두 소진하고 준비 큐로 들어간다.
  - 이 문제를 보완하기 위해 시간 할당량이 남은 입출력을 마친 프로세스들이 들어가는 준비 큐를 따로 하나 둔다. 이 큐의 우선순위는 원래 준비 큐보다 더 높으며, CPU에 시간 할당을 받을 때는 쓰지 못하고 남긴 시간만 준다. 
• CPU를 독점하는 단점은 보완할 수는 있지만, CPU의 선점에 따른 문맥 교환의 오버헤드를 감수해야한다. 
  시간 할당량이 작으면 오버헤드가 너무 커지며, 너무 크면 FCFS와 같아지게 되므로 적절한 시간 할당량을 찾아야 한다.
• 오버헤드에도 불구하고 대화식 시스템이나 시분할 시스템에 적합한 방법으로 알려져있다.
• 예시

프로세스	CPU 요구량(초)
P1	30
P2	8
P3	15
P4	10

 

 

출처

김주균, 「OS? Oh Yes!」, 휴먼싸이언스

https://ko.wikipedia.org/wiki/%EB%B9%84%EC%84%A0%EC%A0%90_%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81

Silbershartz, Galvin andGagne 「Operating System Concepts - 10th Edition」, Wiley