Scheduling

CPU 스케줄러(프로세스 스케줄러)

프로세스를 스케줄링하기 위한 Queue에는 세 가지 종류가 존재한다.

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

각각의 Queue에 프로세스들을 넣고 빼주는 스케줄러에도 크게 세 가지 종류가 존재한다.

장기 스케줄러(Long-term scheduler or job scheduler)

                      “ 어떤 프로세스를 ready queue에 넣을 것인가? “

메모리는 한정되어 있어 많은 프로세스들이 한꺼번에 메모리로 올라올 경우, 대용량 메모리(디스크)에 임시로 저장된다. 이 pool에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 Ready Queue로 보낼지 결정하는 역할을 한다.
- 메모리와 디스크 사잉의 스케줄링을 담당
- 프로세스에 memory(및 각종 리소스)를 할당(admit)
- Degree of Multiprogramming 제어(실행중인 프로세스의 수 제어)
- 프로세스의 상태 new -> ready(in memory)

• 메모리에 프로그램이 너무 많이 올라가거나 너무 적게 올라가도 성능이 좋지 않은 것이다. 참고로 time sharing system에서는 장기 스케줄러가 없다. 그냥 곧바로 메모리에 올라가 ready 상태가 된다.

단기 스케줄러(Short-term scheduler or CPU scheduler)

                         “ 어떤 프로세스에게 CPU를 할당할 것인가? “

CPU와 메모리 사이의 스케줄링을 담당한다. Ready queue에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정하고 프로세스에 CPU를 할당(scheduler dispatch)한다.

• 프로세스의 상태
  ready -> running -> waiting -> ready

중기 스케줄러(Medium-term scheduler or Swapper)

                               “ 메모리에 적재된 프로세스 수 관리 “

• 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아낸다(Swapping). 프로세스에게서 메모리를 할당 해제하고 degree of Multiprogramming을 제어한다. 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러이다.
• 프로세스의 상태
  ready -> suspended
  • Suspended(Stopped) : 외부적인 이유로 프로세스의 수행이 정지된 상태로 메모리에서 내려간 상태를 의미한다. 프로세스 전부가 디스크로 Swap out 된다. Blocked 상태는 다른 I/O 작업을 기다리는 상태이므로 스스로 Ready 상태로 돌아갈 수 있지만 이 상태는 외부적인 이유로 suspending 되었기 때문에 스스로 돌아갈 수 없다.

스케줄링의 목적

• 공평성 : 모든 프로세스가 자원을 공평하게 배정받아야하며 자원 배정 과정에서 특정 프로세스가 배제되어서는 안된다.
• 효율성 : 시스템 자원이 놀지 않도록 스케줄링하고 남은 자원을 사용하려는 프로세스에게 우선권을 주어야한다.
• 안정성 : 우선순위를 사용해 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유 또는 파괴하려는 프로세스로부터 자원을 보호해야 한다.
• 확장성 : 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 한다.
• 반응 시간 보장 : 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 생각하므로 시스템은 적절한 시간 내에 프로세스 요구에 반응해야 한다.
• 무한 연기 방지 : 특정 프로세스의 작업이 무한히 연기되어서는 안된다.

스케줄링 평가 척도

1. CPU Utilization(이용률) : 전체 시간 중 CPU가 놀지 않고 일한 시간
2. Throughput(처리량) : 단위 시간당 처리량, CPU가 얼마나 많은 일을 했는가
3. Turnaround Time(소요시간, 반환시간) : CPU 사용한 시간 + 기다린 시간
4. Waiting Time(대기시간) : 프로세스가 Ready Queue에서 기다린 전체 시간의 합
5. Response Time(응답시간) : 프로세스가 Ready Queue에 들어가서 최초로 CPU할당 받기까지의 시간

오버헤드 , 기아현상, 반환시간, 대기시간은 낮추고 처리량, 사용률, 응답 시간은 높인다.

선점 vs. 비선점

• 선점 스케줄링 : 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 OS가 CPU를 강제로 뺴앗을 수 있는 스케줄링 방식(시분할, 대화형 시스템에서 사용), 문맥 교환이 잦아 오버헤드가 크다.
  • 우선순위 스케줄링, RR, Multilevel queue, Multilevel-feedback queue
    • Multilevel queue : 작업을 여러 종류의 큐로 나누어 큐마다 다른 time quantum 할당
    • Multilevel-feedback queue : Multilevel에서 time quantum을 채우면 다음 level로 내려감
• 비선점 스케줄링 : 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식(배치 시스템에서 사용), 기다리는 프로세스가 많아 처리율이 떨어진다.
  • FCFS, SJF

1. FCFS(First Come First Served)

먼저 온 순서대로 처리하는 방식이다.

• 비선점형(Non-preemptive) 스케줄링 : 일단 CPU를 잡으면 CPU burst가 완료될 때까지 CPU를 반환하지 않는다. 할당되었던 CPU가 반환될땜만 스케줄링이 이루어진다.
• Convoy effect : 소요시간이 긴 프로세스가 먼저 도달해 효율성을 낮추는 현상이 발생한다.

2. SJF(Shortest Job First)

다른 프로세스가 먼저 도착했어도 CPU burst time이 짧은 프로세스에게 선 할당한다. Ready Queue에서 대기 중인 프로세스 중에서 CPU 소요 시간이 가장 짧은 프로세스를 우선으로 하는 방식이다.

• starvation : 효율성을 추구하는게 가장 중요하지만 특정 프로세스가 지나치게 차별받으면 안되는 것이다. 이 스케줄링은 극단적으로 CPU 사용이 짧은 job을 선호한다. 그래서 사용 시간이 긴 프로세스는 거의 영원히 CPU를 할당받을 수 없게 된다.
• 다음 CPU Burst의 길이를 결정하는 방법
  CPU 수행 될 때에는 프로세스가 얼만큼의 CPU burst를 갖는지 미리 알 수 없다.

3. SRTF(Shortest Remaining Time First)

새로운 프로세스가 도착할 땜마다 새로운 스케줄링이 이루어진다.

• 선점형(Preemptive) 스케줄링 : 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 갖는 새로운 프로세스가 도착하면 CPU를 뺏긴다.
• starvation
• 새로운 프로세스가 도달할 때마다 스케줄링을 다시하므로 CPU burst time(CPU 사용시간)을 측정할 수가 없다.

4. Priority Scheduling

우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링이다. 우선순위는 정수로 표현되고 작은 숫자가 우선순위가 높다.

• 선점형 스케줄링 방식 : 더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU를 선점한다.
• 비선점형 스케줄링 방식 : 더 높은 우선순위의 프로세스가 도착하면 ready queue의 head에 넣는다.
• 무기한 봉쇄(Indefinite blocking or starvation) : 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스를 CPU가 무기한 대기하는 상태
  • 해결책으로 aging 기법이 있으며, 아무리 우선순위가 낮은 프로세스라도 오래 기다리게 된다면 우선순위를 높여준다.

5. Round Robin

각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖는다.

• 할당 시간이 지나면 프로세스는 선점 당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
• RR은 CPU 사용 시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적이다.
• RR이 가능한 이유는 프로세스의 context를 save할 수 있기 때문이다.
• Response time이 빨라진다.
• n개의 프로세스가 ready queue에 있고 할당시간이 q(time quantum)인 경우 각 프로세스는 q 단위로 CPU 시간의 1/n을 얻는다. 즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.

문제점

• q→$\infty$ : FIFO(FCFS), 응답 시간이 떨어지게 된다.
• q→$0$ : context switch가 늘어나게 되어 오버헤드가 발생한다.(CPU utilization 하락)
• Rule of thumb : CPU burst의 80% 정도를 포함할 수 있도록 q를 설정해야 한다.

6. Multi-Level Queue

Ready queue를 여러 개로 분할한다.

• foreground(interactive) : 사용자와 소통 중심
• background(batch - no human interaction)

각 큐는 독립적인 스케줄링 알고리즘을 갖는다.

• foreground : Round Robin
• background : FCFS

Queue에 대한 스케줄링이 필요하다.

• Fixed priority scheduling(고정 우선순위 방식)
  고정적으로 우선순위를 부여하여 우선순위가 높은 큐를 먼저 serve하고 우선순위가 낮은 큐는 우선순위가 높은 큐가 비었을 때 serve하게 된다.
  즉, 전위 큐와 후위 큐를 사용하는 방식에서 전위 큐에 있는 프로세스에게 우선적으로 CPU가 할당되고, 전위 큐가 비어 있는 경우에 후위 큐에 있는 프로세스에게 CPU가 할당 된다.
  Starvation 가능성
• Time slice(타임 슬라이스)
  각 큐에 CPU time을 적절한 비율로 할당
  80%는 foreground(RR), 20%는 background(FCFS)

문제점

프로세스를 어느 큐에 삽입할 것인지, 전위 큐가 계속 차있는 상태라면 후위 큐에 있는 프로세스들은 계속 CPU를 할당받지 못하게 된다.(Starvation)
→ 각 큐에 CPU 할당시간을 적절한 비율로 할당한다. (Multilevel Feedback Queue)

7. Multi-Level Feedback Queue (MLFQ)

멀티 레벨 피드백 큐는 CPU를 기다리는 프로세스를 여러 큐에 줄세운다는 측면에서 멀티큐와 동일하지만 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다.
Aging 방식이 여기서도 적용되는데, 우선순위가 낮은 큐에서 오래 기다린 프로세스를 우선순위가 높은 큐로 올려주는 방식이다.

특징

• 프로세스들의 다양한 성격을 반영해 구현 가능
• 프로세스가 다른 큐로 이동 가능
• Aging 사용

멀티 레벨 피드백 큐를 정의하는 파라미터
1. 큐의 수
2. 각 큐의 스케줄링 알고리즘
3. 프로세스를 상위 큐로 올리는 기준
4. 프로세스를 하위 큐로 내리는 기준
5. 프로세스가 CPU 할당받으려 할 때 들어갈 큐를 정하는 기준

✌🏻대체적으로 CPU burst가 높은 프로세스는 우선순위가 낮게 평가되고, 낮은경우 우선순위가 높게 평가된다.

멀티레벨 피드백 큐 vs 멀티레벨 큐

멀티레벨 피드백 큐는 비교적 복잡하지만 유연성이 뛰어나고 SJF 알고리즘처럼 Turnaround time에 최적화 되어있다. (q를 보고 우선순위를 예측하고 변경하게 되는데, 짧은 프로세스가 먼저 돌게 해주므로 Average Turnaround time을 줄일 수 있다.) interactive process가 먼저 수행되므로 응답 시간도 줄어든다.