[OS] CPU Scheduling 기본 ( 6가지 )

1. 선입선처리 스케줄링 (FCFS) - First Come First Served

 - 이름 그대로 먼저요창한 Process가 CPU를 먼저 할당받는 스케줄링 기법이다.

   ( FIFO Queue를 통해 쉽게 구현이 가능하다. Ready Queue를 그대로 이어받는다. )

 

 - 먼저들어온 Process의 처리시간이 길다면 나머지 Process들의 대기시간이 길어질 수 있다.

   ( 상황에따른 변동폭이 매우 큰편이다. )

 

 - 비선점형 스케줄링 알고리즘이다.

   ( 새로 준비완료된 Process가 이미 CPU를 할당받은 Process의 CPU를 선점할 수 없다. )

 

 

 

---

 

2. 최단 작업 우선 스케줄링 (SJF) - Short Job First

 - 이름 그대로 Burst Time(쉽게말해 수행시간)이 가장적은 Process에게 CPU를 할당한다.

   

Burst Time ?     CPU Burst와 I/O Burst로 나눌 수 있는데, CPU Burst란 말그대로 CPU가 해당 프로세스의 명령을 실행하고 있는 것을 말하고, I/O Burst는 I/O를 요청하고 기다리는 시간을 말한다.   때문에 프로세스마다 CPU Burst위주의 프로세스냐 아니면 I/O Burst위주의 프로세스냐에 따라서 스케줄링 기법을 달리해야한다.  ( 이를 CPU Bound Process, I/O Bound Process 라고 한다. )

 

 - 이 스케줄링기법에서의 어려움은 Process들의 Burst Time을 파악하기 어렵다는 것이다.

   때문에 단기 스케줄링에서는 구현하기에 많은 한계가 있다.

 

 - 해당 스케줄링기법은 선점일수도 비선점일 수도 있다.  Preemitive and Non-Preemitive

   여기서 선점형 SJF의 경우에는 "최소 잔여 시간 우선 스케줄링" 이라고 부르기도 한다.

     ( 이 추가적인 명칭을 보면 어떻게 스케줄링이 진행되는지 파악이 가능하다. ) 

 

---

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

 - 우선순위가 가장 빠른 Process에게 CPU를 할당한다. 우선순위가 같을경우 FCFS 스케줄링 적용.

    ( 우선순위라는건 OS마다 다르며 큰 수가 더 빠른 우선순위일수도 있고 반대로 작은 수가 더 빠른 우선순위일수도 있다. )

 

 - 우선순위 스케줄링도 선점일수도 비선점일 수도 있다.

 

 - 끝까지 파악해봤을 때 우선순위 스케줄링이라는 것은 단독적으로 사용한다기

   보다는 여러가지 스케줄링 기법에 혼용되어 사용되는 것 같다.

 

 - 우선순위 스케줄링의 가장 큰 문제는 우선순위가 느린 Process의 기아현상이 발생할 수 있다는 점이다.

   때문에 우선순위 스케줄링을 사용할 때 반드시 aging 기법과 같은 해결방안을 같이 적용해야 한다.

 

---

4. 라운드로빈 스케줄링 (RR)

 - FCFS 스케줄링 기법에 Preemitive(선점)을 더한 것으로 생각하면 된다.

   시간할당량과 시간조각을 정의해 그 만큼의 CPU Burst를 가졌으면 CPU를 다른 Process에게 넘겨야한다.

      ( 어떻게보면 지금까지의 선점과는 느낌이 조금 다르긴하다. ) 

 

 - 시간할당량은 보통 10~100 밀리초정도이며, 너무 클경우 FCFS와 다를게 없어지고

   너무 작을경우 Context Switch에 의해서 자원손실이 많이 되기 때문에

   적당한 길이의 시간할당량을 정의해서 사용해야한다. 

   ( "시간할당량 x 0.1 = 문맥교환" 이면 CPU는 10%를 문맥교환을 위해서 사용한다고 생각하면 된다. )

 

---

5. 다단계 큐 스케줄링 ( 큐간의 이동 x → 융통성 x )

 - Ready Queue 이외의 다수의 큐를 두어 Process들을 분류한다.

   일반적으로 프로세스들은 메모리 크기, 우선순위, 유형과 같은 특성으로 분류되어 한 개의 큐에 할당된다.

   각 큐는 각기 다른 스케줄링 알고리즘을 사용할 수 있다.

 

 - 이 스케줄링은 가장 최우선되는 Queue가 비지 않는이상 다른 Queue의 Process가

   CPU를 할당받을 기회를 잃는다. 한마디로 Process 의 기아현상이 발생할 수 있다는 것이다.

   이를 해결하기위해 책에서는 Queue마다 CPU할당 시간을 나누는 것을 제시했는데 조금 무식한것 같다.

 

---

6. 다단계 피드백 큐 스케줄링 ( 큐간의 이동 o )

 - 말 그대로 필요에따라 Queue를 이동하여 기아현상을 해결할 수 있다는 것이다.

우선 들어오는 모든 Process들은 Queue-0에 집어넣는다. 그리고 Queue-0에 있는 Process에게 8밀리초의 실행시간을 부여하고 해당 Process의 처리가 남아있다면 Queue-1의 꼬리로 이동시킨다. 이렇게 함으로써 8밀리초 이하의 실행시간을 가진 Process에게 최고의 우선순위 부여. Queue-1은 Queue-0이 완전히 비었을 때 16밀리초의 실행시간을 부여하는 식으로 진행된다.. 참고로 당연하겠지만 Queue-3의 Process가 실행되다가 Queue-0에 Process가 들어오면 선점된다.

 - 다단계 큐 스케줄링에서 기준점이 되는 것은 아래와 같다.

    1. 큐의 개수

    2. 각 큐의 스케줄링 기법

    3. 큐간의 이동 시기

    4. Process가 최초로 들어갈 큐

 

 

반드시 각 스케줄링 기법의 평균 대기시간 및 평균 수행시간을 계산할 줄 알아야한다.
이후에 나오는 실시간 스케줄링쪽에서는 CPU 점유율과 해당 프로세스들이 주어졌을 때,
수행이 가능한지 불가능한지 여부를 판단할 수 있어야한다. 약간의 차이점 ...?