Computer Science Basics/운영체제

OS - 4. CPU Scheduling

타자치는 문돌이 2024. 4. 23. 04:46

CPU는 Multi Programming을 통해 효율을 극대화한다.

Single Core CPU는 한 번에 하나의 프로세스만 실행할 수 있기 때문에 CPU Scheduling을 통해 CPU가 실행할 프로세스를 적절히 정해줘야 한다.

프로세스의 실행은 CPU 실행과 I/O 대기의 사이클로 이루어져 있다.
보통 I/O Bound Process는 CPU 실행이 짧고 잦으며, I/O 대기가 길고, CPU Bound Process는 CPU 실행이 길고 적다.
컴퓨터가 실행하는 대부분의 작업은 I/O Bound Process이다.

CPU Scheduler

CPU Scheduler는 메모리에서 다음에 실행할 프로세스를 선택한 뒤, 프로세스가 준비되면 CPU에 프로세스를 할당한다.


프로세스의 상태 변화 그림을 다시 보면,
CPU Scheduler는

  1. Running -> Waiting (I/O가 필요할 때)
  2. Running -> Ready (Interrupt가 일어났을 때)
  3. Waiting -> Ready (I/O 작업이 끝났을 때)
  4. Terminated

일 때 Scheduling Decision을 내리고, 프로세스의 상태를 변화시킨다.
1, 4의 이유로만 Scheduling Decision이 일어날 때, 우리는 Scheduling Scheme이 Non-preemptive (Cooperative)하다고 한다.
이외의 상황에서 Scheduling이 일어난다면, Preemptive 하다고 한다.

Dispatcher

CPU Scheduler가 다음 프로세스를 정하면, Dispatcher는 CPU의 주도권을 다음 프로세스에 넘기는 역할을 한다.
Dispatcher는

  • Context Switch
  • User Mode로 전환
  • 프로세스 재시작 때 올바른 위치에서 시작할 수 있도록 조절

하는 역할을 한다.

Dispatcher가 프로세스를 중단하고 다른 프로세스를 실행하는 데까지 걸리는 시간을 Dispatch Latency라고 하며, 이 시간은 짧으면 짧을수록 작업 속도가 빨라져 최대한 짧아야 한다.

CPU Scheduling Algorithm

Criteria

알고리즘처럼 CPU Scheduling Algorithm도 평가 기준이 존재한다.

  • CPU Utilization : CPU가 최대한 바쁘게 일해야 한다.
  • Throughput : Time Unit 당 끝나는 프로세스의 개수 -> 많을수록 좋다.
  • Turnaround Time : 특정 프로세스가 Ready Queue 대기부터 종료될 때까지 걸리는 시간 -> 짧을수록 좋다.
  • Waiting Time : Ready Queue에서 대기한 시간 -> 짧을수록 좋다.
  • Response Time : Ready Queue 대기부터 첫 응답까지의 시간 (종료 X) -> 짧을수록 좋다.

주로 이 값들의 평균값을 보고 효율성을 계산하나 상황에 따라서 특정 값이 효율성이 더 중요한 경우도 있고, 특히 Interactive System에서는 평균 Response Time을 줄이는 것 보다 Response Time의 분산을 줄이는 것이 더 효율적인 경우도 있다.

FCFS Scheduling

First-Come First-Served Scheduling에서 CPU는 들어온 순서대로 프로세스를 처리한다.
이 경우 특별한 경우가 없다면 I/O 대기나 종료로만 프로세스가 종료되는 Non-Preemptive Scheduling이다.
매우 단순하고 구현하기도 쉽다.

Convoy Effect

위 예시의 Average Waiting Time을 계산하면 (0 + 24 + 27) / 3 = 17이다.

같은 프로세스가 다른 순서가 들어온 경우를 생각해 보자.

이 경우 Average Waiting Time은 (6 + 0 + 3) / 3 = 3이다.
P1이 조금 늦게 들어오기만 해도 Average Waiting Time이 14나 줄어든다.
이렇게 긴 CPU-Bound 프로세스 뒤에 짧은 I/O Bound 프로세스가 대기하게 되면 I/O 프로세스는 CPU-Bound 프로세스가 끝날 때까지 긴 시간을 대기하여 전체적인 성능이 저하되는 비효율적인 상황이 일어난다. 이런 현상을 Convoy Effect라고 한다.

SJF Scheduling

CPU Burst가 가장 짧은 프로세스 먼저 처리하는 방법이다.
SJF를 구현하는 방법은 두 가지가 있는데

  • Non-Preemptive : 실행 중인 프로세스는 더 짧은 프로세스가 들어오더라도 실행을 끝내고 다음 프로세스를 실행한다.

  • Preemptive : 실행 중인 프로세스가 남은 시간보다 더 짧은 프로세스가 들어온다면, 프로세스를 중단하고 더 짧은 프로세스를 실행한다. Shortest Remaining Time First라고도 한다.

SJF는 가장 짧은 Average Waiting Time을 가지는 효율적인 알고리즘이다.
그런데 다음 프로세스의 실제 Burst Time은 구하기 매우 어렵다. Exponential Averaging이라는 방법으로 예측할 뿐이다.

Priority Scheduling

Priority Scheduling은 프로세스의 우선순위 개념을 추가해 우선순위가 더 높은 프로세스를 먼저 처리하는 방법이다.
마찬가지로 중간에 새 프로세스가 들어왔을 때 중단하느냐의 여부로 두 가지 방법으로 구현할 수 있다.
SJF도 어떤 측면에서는 Priority가 Burst Time인 Priority Scheduling이라고 할 수 있다.

우선순위가 높은 프로세스가 계속해서 들어오면 어떻게 될까?
우선순위가 낮은 프로세스가 영영 실행되지 못할 수도 있다. 이런 문제를 Starvation이라고 한다.
이런 문제는 프로세스의 우선순위를 시간이 지남에 따라 조금씩 증가시키는 Aging을 통해 해결할 수 있다.

Robin-Round Scheduling

RR Scheduling에서 각 프로세스는 Time Quantum이라는 짧은 CPU Time 단위를 가진다. 이 짧은 시간만큼 프로세스를 실행하고 다시 Ready Queue에 돌아간다.
짧은 시간이 지나면 프로세스의 상태에 상관없이 중간에 Scheduler가 프로세스를 종료하는 Preemptive Scheduling이다.

q가 너무 크면 사실상 FCFS와 다를 게 없다.
q가 너무 작으면, 정작 프로세스 실행 시간보다 Context Switch가 시간이 더 걸릴 수도 있다.
주로 SJF보다 Average Turnaround Time은 길지만 Response Time은 짧다.

 

Multilevel Queue Scheduling

Multilevel Queue에서는 Ready Queue 두 개를 사용한다.
각 Queue는 고유한 Scheduling Algorithm을 가진다.
두 Queue끼리의 우선순위는 다양한 방법으로 조정한다.

  • Fixed Priority : 무조건 A Queue는 B보다 우선
  • Time Slice : CPU Time의 80%는 A Queue가, 20%는 B가 사용

Multilevel Feedback Queue Scheduling

Queue를 여러 개 사용하는데, 프로세스가 Queue를 이동할 수 있다.
다양한 알고리즘으로 구현할 수 있는데, 아래는 그 예시 중 하나이다.

  1. Q1에 들어가 8ms의 Time Quantum만큼 실행된다.
  2. 아직 끝나지 않았으면 Q2로 이동한다.
  3. Q2에서 16ms의 Time Quantum만큼 실행된다.
  4. 아직 끝나지 않았으면 Q3로 이동한다.
  5. Q3에서는 Q1과 Q2가 비었다면 FCFS로 프로세스를 처리한다.

Multi Processor의 Scheduling

Multi Processor의 CPU Scheduling은 더욱 복잡하다.
크게 두 가지 시나리오를 생각할 수 있다.

  • Asymmetric Multiprocessing : 한 프로세서가 Master 프로세서가 되어 나머지 프로세서를 관리한다. Master는 다른 프로세서에 프로세스를 할당하거나 데이터 구조를 제어하고, CPU Scheduling, I/O 등을 처리한다.
  • Symmetric Multiprocessing (SMP) : 프로세서는 공통된 Ready Queue에서 프로세스를 꺼내가거나, 프로세서 별로 다른 Ready Queue를 사용한다. Scheduler는 두 프로세서가 같은 프로세스를 실행하지 않도록 관리한다.

다음 내용들은 SMP와 관련된 내용이다.

Load Balancing

여러 프로세서가 있는데 한 프로세서에 프로세스가 쏠리면 비효율적이다.
Load Balancing은 프로세서가 각자의 Ready Queue를 가지고 있을 때, 여러 프로세서의 Workload를 고르게 하기 위한 방법이다.

  • Push Migration : 프로세서가 바쁘면 여유로운 프로세서에 Task를 보낸다.
  • Pull Migration : 프로세서가 여유로우면 바쁜 프로세서에서 Task를 가지고 온다.

두 방식이 동시에 사용될 수도 있다.

Processor Affinity

프로세서가 프로세스를 실행하다가 Interrupt로 Ready Queue로 갔다가 다시 실행될 때, 어느 프로세서한테 가는 것이 효율적일까?
캐시가 있다면 실행하던 프로세서한테 가는 것이 더 효율적일 것이다.
Processor Affinity는 이런 상황을 대비해 한 프로세서에서 실행 중이던 프로세스는 같은 프로세서에 배정해 주는 방법이다.

Processor Affinity를 반드시 지켜 다른 프로세서에 할당되는 것을 막는 Hard Affinity와 가능하다면 같은 프로세서에 할당하되, 여유가 안 되면 다른 프로세서에 보내는 Soft Affinity가 있다.

 

 

OS - 0. Index

저작자표시 비영리 변경금지