CPU Scheduling [Priority & Round Robin]

• 비선점형 스케줄링(Non-preemptive Scheduling) :  - 프린트 
  - 어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실행되도록 보장한다. 
  - 순서대로 처리되는 공정성이 있고 다음에 처리해야 할 프로세스와 관계없이 응답 시간을 예상할 수 있으며 선점 방식보다 스케줄러 호출 빈도 낮고 문맥 교환에 의한 오버헤드가 적다. 
  - 일괄 처리 시스템에 적합하며, CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로, 처리율이 떨어질 수 있다는 단점이 있다.
  
  

• 선점형 스케줄링(Preemptive Scheduling) :         - 보통의 OS
  - 어떤 프로세스가 CPU를 할당받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있다.
  - 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있다. 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세서를 제어할 수 있다.
  - '운영 체제가 프로세서 자원을 선점'하고 있다가 각 프로세스의 요청이 있을 때 특정 요건들을 기준으로 자원을 배분하는 방식이다.

FIFO - FCFS - RR(Round Robin)

FCFS 스케줄링(First Come, First Served Scheduling)

가장 간단한 CPU 스케줄링 알고리즘이다. 이 방법에서는 CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다. FIFO 큐로 쉽게 구현하고 관리할 수 있다. 

그러나 이 알고리즘 하에서 프로스세스들의 평균 대기 시간은 가끔 대단히 길 수 있다. 시간 0에 도착한 다음의 프로세스 집합을 생각해보자.(CPU 버스트 시간 단위는 밀리초이다)

일반적으로 FCFS 스케줄링 정책 하에서 평균 대기시간은 최소가 아니며, CPU 버스트 시간이 크게 변할 경우 평균 대기시간도 상당히 변한다.

=> 시간에 상관없이 들어온 순서대로 처리하는 스케쥴링 ( 대기시간이 너무 길 수 있다. )

그래서~ 최단 작업 우선 스케줄링(Shortest Job First Scheduling)

평균 대기 시간을 최소화하기 위해 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식의 CPU 스케줄링 알고리즘으로 평균 대기시간을 최소로 만드는 걸 최적으로 두고 있는 알고리즘

=> CPU burst가 긴 프로세스 실행 못하는 Starvation 문제가 있고, 이걸 구현하기가 현실적으로 불가능하다.

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

시분할 시스템을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Quantum)로 CPU를 할당하는 방식의 CPU 스케줄링 알고리즘이다.

보통 시간 단위는 10 ms ~ 100 ms 정도이다. 시간 단위동안 수행한 프로세스는 준비 큐의 끝으로 밀려나게 된다. 문맥 전환의 오버헤드가 큰 반면, 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리하다.

라운드 로빈은 사발통문과 마찬가지로 사람의 이름을 순서대로 적는 것이 아니라 원형으로 적어 조직의 서열을 숨기는 서명 방식이다.

** RR 정리 **

- FCFS에서 짧은 프로세스가 피해보는 현상 완화방법
  : 시간을 정해놓고 프로세스가 일정 시간 이상을 넘어가는 순간 실행을 강제로 중단시킴
-프로세스 실행시간측정방법
  : 클럭(clock) 인터럽트(또는 타이머 인터럽트)
  : 클럭인터럽트는 일정간격으로 주기적으로 발생
-시간할당량(time slicing)기법이라고 함

우선순위 스케줄링(Priority Scheduling)

우선순위는 내부적 또는 외부적으로 정의될 수 있다. 내부적으로 정의된 우선순위는 프로세스의 우선순위를 계산하기 위해 어떤 측정 가능한 양들을 사용한다. 예를 들어 시간제한, 메모리 요구, 열린 파일 수, 평균 I/O 버스트의 평균 CPU 버스트에 대한 비율 등이 우선순의의 계산에 사용된다. 외부적 우선순위는 프로세스의 중요성, 지불되는 비용 등 운영체제 외부적 기준에 의해 결정된다.

우선순위 스케줄링 알고리즘의 주요 문제는 

1. 무한봉쇄(indefinite blocking)  -  aging 기법 사용.
2. 기아상태(starvaion)    

부하가 과중한 컴퓨터 시스템에서는 높은 우선순위의 프로세스들이 꾸준히 들어와서 낮은 우선순위의 프로세스들이 CPU를 얻지 못하게 될 수 있는데, 이때 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 발생한다. 낮은 우선순위의 프로세스들을 무한히 봉쇄하는 문제에 대한 한 해결 방안은노화(aging)으로, 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 기법이다.