Operating System.6 Processor Scheduling 1

기본 용어

• Burst(time)
  • CPU Burst : CPU가 특정 프로세스의 연산을 실행하는 시간
  • I/O Burst : Burst : CPU가 I/O를 기다리는 시간
• CPU-I/O Burst Cycle

• 각 프로세스의 실행 동작은 CPU 실행과 I/O 대기의 순환으로 이루어져 있다.

• Types of processes or Program behavior
  • CPU (or processor) bound
    • I/O Blocking을 당하기 이전에 Long CPU Burst를 가진 프로세스
  • I/O bound - I/O Blocking을 당하기 이전에 Short CPU Busrt를 가진 프로세스

Types of Scheduling

• 운영 체제에서는 다양한 종류의 스케줄링이 사용되며, 각 스케줄링은 시스템의 성능과 효율성을 높이기 위해 서로 다른 역할을 한다.
• 대표적인 스케줄링 종류로는 Long-term 스케줄링, Medium-term 스케줄링, Short-term 스케줄링, 그리고 I/O 스케줄링이 있다.

1. Long-term 스케줄링 (장기 스케줄링) :

   • 장기 스케줄링은 프로세스를 메모리에 로드하는 시점을 결정하는 스케줄링이다.
   • 시스템에 제출된 작업들 중에서 어떤 프로세스를 메모리에 할당하여 Ready 상태로 전환할지 결정한다.
   • 프로세스의 우선순위, 메모리 요구사항, I/O 요구사항 등을 고려하여 결정한다.
   • 메모리와 다른 시스템 자원의 활용도를 높이는 것이 목적이다.
   • 시스템의 전체적인 성능과 처리량에 영향을 미친다.
   • 일반적으로 배치 처리 시스템에서 사용되며, 대화형 시스템에서는 잘 사용되지 않는다.

• 즉, 새로운 프로세스가 만들어졌을 때 결정

1. Medium-term 스케줄링 (중기 스케줄링):

   • 중기 스케줄링은 메모리에 로드된 프로세스를 일시적으로 메모리에서 제거하거나 다시 메모리에 로드하는 결정을 하는 스케줄링이다.
   • 프로세스의 상태를 메모리와 디스크 사이에서 전환합니다. (Swapping)
   • 메모리 부족 상황에서 일부 프로세스를 디스크로 스왑 아웃하여 메모리 공간을 확보한다.
   • 스왑 아웃된 프로세스는 필요할 때 다시 메모리로 스왑 인되어 실행을 재개할 수 있다.
   • 메모리 관리와 밀접한 관련이 있으며, 가상 메모리 시스템에서 주로 사용된다.

• CPU 자원을 관리해줘야 할 때 사용

1. Short-term 스케줄링 (단기 스케줄링):

   • 단기 스케줄링은 Ready 상태의 프로세스 중에서 다음에 실행할 프로세스를 선택하는 스케줄링아다.
   • CPU 스케줄러라고도 불리며, 가장 빈번하게 발생하는 스케줄링이다.
   • 프로세스에 CPU를 할당하고 실행 순서를 결정한다.
   • 스케줄링 알고리즘(FCFS, SJF, Priority, Round-Robin 등)을 사용하여 프로세스를 선택한다.
   • 프로세스의 특성과 시스템의 목적에 따라 적절한 알고리즘을 선택한다.
   • 시스템의 응답 시간, 처리량, 자원 활용도 등에 직접적인 영향을 미친다.

• Process Switch가 필요한 시점에 순서를 결정.

1. I/O 스케줄링:
   • I/O 스케줄링은 입출력 장치와 관련된 요청을 처리하기 위한 스케줄링이다.
   • 프로세스가 I/O 작업을 요청할 때, I/O 스케줄러는 요청의 순서와 우선순위를 결정한다.
   • 디스크 스케줄링 알고리즘(FCFS, SSTF, SCAN, C-SCAN 등)을 사용하여 디스크 액세스 순서를 최적화한다.
   • I/O 장치의 활용도를 높이고, 프로세스의 대기 시간을 최소화하는 것이 목적이다.
   • 시스템의 전체적인 성능과 응답 시간에 영향을 미친다.

• 이러한 스케줄링은 운영 체제 내에서 상호 작용하며 시스템의 성능과 효율성을 결정한다.
• Long-term 스케줄링은 시스템 전체의 자원 활용도를 고려하고, Medium-term 스케줄링은 메모리 관리를 담당하며, Short-term 스케줄링은 CPU 할당을 결정한다.
• I/O 스케줄링은 입출력 장치의 효율적인 사용을 보장한다.

Scheduling Criteria(평가 척도)

• User Oriented
  • Turnaround time : 프로세스 제출부터 완료까지의 시간 간격
  • Response time : 대화형 프로세스의 경우 요청 제출부터 응답 수신이 시작될 때까지의 시간
  • Deadlines
• System Oriented
  • Throughput : 단위 시간 당 처리량
  • Processor utilization: 전체 시간 대비 CPU가 사용된 시간 비율
  • Fairness : 프로세스들은 동일하게 취급되어 처리되어야 한다는 검

컴퓨터의 목적별 중요 기준

• Super computer : 주로 방대하고, 긴 실행 작업을 수행하기 때문에 Throughput과 CPU utilization이 중요하다.
• Server Computer for Cloud server : 서버에 들어온 작업들이 동등한 CPU 자원 할당량을 받아야 하기 때문에 Fairness가 중요하다
• Personal Computer : user oriented한 성능 개선이 중요하다, I/O 작업이 빈번하게 발생한다.
• Embedded system or Real-time : 실시간으로 빠른 처리를 해야 하기 때문에 deadline이 중요하다.

Selection Function(선택 함수)

• ready 상태인 프로세스들 중에서 다음에 실행되어야할 프로세스를 결정하는 함수.
• 선택 함수는 우선순위, 자원의 필요량, 프로세스의 실행 특성에 기반하여 선택을 한다.
  • 실행의 특징 3가지
    • 기다린 시간(w)
    • 자원을 받아 수행한 시간(s)
    • 예상 종료 시간(e)
    • 에를 들어 FCFS 방식은 max[w]를 기준으로 프로세스를 선택한다.

CPU 점유 방식

• Non-Preemptive(비선점 스케줄링)
  • 프로세스가 CPU를 할당받으면 작업을 완료하거나 자발적으로 CPU를 반환할 때까지 CPU를 점유한다.
  • 한 프로세스가 CPU를 점유하고 있을 때, 다른 프로세스는 CPU를 강제로 빼앗을 수 없다.
  • 프로세스의 응답 시간이 길어질 수 있으며, 긴 작업을 수행하는 프로세스가 CPU를 독점할 가능성이 있다.
  • 구현이 간단하고 문맥 교환(Context Switch) 오버헤드가 적다.
  • FCFS(First-Come, First-Served) 스케줄링, Shortest-Job-First(SJF) 스케줄링 등이 대표적인 비선점 스케줄링 알고리즘이다.
• Preemptive(선점 스케줄링)
  • 스케줄러가 프로세스의 실행을 중단시키고 다른 프로세스에게 CPU를 할당할 수 있다.
  • 높은 우선 순위의 프로세스가 도착하거나, 할당된 시간 조각(Time Slice)이 만료되면 현재 실행 중인 프로세스를 중단 시킬 수 있다.
  • 스케줄러에 의해 프로세스의 실행이 제어되며, 프로세스는 언제든 CPU를 뺏길 수 있다.
  • 시분할 시스템에서 주로 적용되며, 응답 시간을 줄이고 대화형 시스템에 적합하다.
  • 문맥 교환 오버헤드가 발생할 수 있지만, 프로세스 간의 공평한 CPU 공유와 빠른 응답 시간을 제공한다.
  • Round-Robin(RR) 스케줄링, Priority 스케줄링 등이 대표적인 선점 스케줄링 알고리즘이다.

FIFO(First In, First Out)

• 프로세스가 도착한 순서대로 CPU를 할당받는 비전점(Non-preemptive) 스케줄링 알고리즘이다.
• 간단하고 직관적이며, 먼저 도착한 프로세스가 먼저 실행되는 공평성을 가진다.
• 동작 원리
  1. 프로세스들은 도착한 순서대로 준비 큐(ready queue)에 삽입된다.
  2. cpu는 현재 실행 중인 프로세스가 완료되거나 대기 상태로 전환될 때까지 해당 프로세스를 실행한다.
  3. 현재 프로세스가 완료되면, 준비 큐에서 가장 앞에 있는 프로세스가 CPU를 할당받고 실행된다.
  4. 이 과정은 준비 큐가 비어있을 때까지 반복된다.
• 특징
  • 간단하고 구현이 쉬우며, 문맥 교환(Context Switch) 오버헤드가 적다.
  • 평균 대기 시간(Average Waiting Time)이 길어질 수 있다. 특히, 긴 작업을 수행하는 프로세스가 먼저 도착할 경우 후속 프로세스들의 대기 시간이 길어진다.
  • 응답 시간(Response Time)이 느릴 수 있다.
  • 중요한 프로세스라도 먼저 도착한 프로세스가 완료될 때까지 기다려야 한다.
  • Convey Effect(호위 효과)가 발생할 수 있다.
    • Convey Effect : 긴 작업을 수행하는 프로세스 뒤에 짧은 작업을 수행하는 많은 프로세스들이 대기하는 현상
• 사용하기 적합한 상황
  • 프로세스의 도착 순서가 중요한 경우에 사용될 수 있다.
  • 작업 부하가 균등하고 프로세스의 실행 시간이 비슷한 경우에 적합하다.
  • 대기 시간보다 처리량(Throughput)이 중요한 배치 처리 시스템에서 사용될 수 있다.(CPU bound process)
• 즉 selection function = max(w), Non-preemptive

FIFO 에시

• Turnaround time(Terminate Time - Arrive Time)
  • A : 3
  • B : 7
  • C : 9
  • D : 12
  • E : 12
• Average Turnaround time : 8.6

Shortest Process Next(SPN, 혹은 SJF:Shortest Job First)

• 실행시간이 가장 짧은 프로세스부터 CPU를 할당하는 비선점(Non-Preemptive) 스케줄링 알고리즘이다.
• 이 알고리즘은 평균 대기 시간을 최소화 하는 것을 목표로 한다.
• 동작 원리
  1. 프로세스들은 도착한 순서대로 준비 큐(Ready Queue)에 삽입된다.
     • 스케줄러는 준비 큐에 있는 프로세스들의 실행 시간을 에측하거나 알고 있다고 가정한다.
  2. CPU는 현재 실행 중인 프로세스가 완료되면, 준비 큐에서 실행 시간이 가장 짧은 프로세스를 선택하여 CPU를 할당한다.
  3. 선택된 프로세스는 실행을 완료할 때까지 CPU를 점유한다.
  4. 프로세스가 완료되면, 다시 준비 큐에서 실행 시간이 가장 짧은 프로세스를 선택하여 실행한다.
• SPN 스케줄링의 특징
  • 실행 시간이 짧은 프로세스를 우선적으로 실행하여 평균 대기 시간을 최소화 한다.
  • 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스들이 모두 완료될 때까지 기다려야 할 수 있다.
  • 프로세스의 실행시간을 정확히 알아야 하는 것이 어려울 수 있다.(실행 시간을 에측하는 기술이 필요하다)
  • 기아 현상(Starvation)이 발생할 수 있다.
    • Starvation : 실행 시간이 긴 프로세스는 계속해서 후순위로 밀릴 수 있다.
• SPN 스케줄링이 유용한 상황
  • 작업 부하가 주로 짧은 프로세스로 구성되어 있는 경우에 효과적이다.
  • 대화형 시스템보다는 일괄 처리(Batch processing)시스템에 적합하다.
  • 프로세스의 실행 시간을 에측할 수 있는 경우에 사용될 수 있다.
• 한계점
  • 실행 시간이 긴 프로세스가 무한정 대기할 수 있는 기아 현상이 발생할 수 있다.
  • 프로세스의 실행 시간을 정확히 예측하는 것이 어려울 수 있다.
  • 새로 도착한 프로세스의 실행 시간이 현재 실행 중인 프로세스보다 짧더라도, 선점되지 않으므로 응답 시간이 늘어날 수 있다.
• 한계점 극복을 위한 방안들
  • 기아 현상을 방지하기 위해 에이징(Aging) 기법을 사용하여 오래 기다린 프로세스의 우선순위를 높이는 방법
  • 실행 시간 예측을 위해 과거 실행 기록을 활용하거나, 사용자로부터 실행 시간 정보를 입력받는 방법
  • 선점형 SPN 스케줄링(Shortest Remaining Time Next, SRTN)을 사용하여 새로 도착한 짧은 프로세스에게 CPU를 선점하도록 하는 방법
• 실제 서비스에서는 실행 시간 예측의 어려움과 기아 현상 등의 문제로 인해 다른 스케줄링 알고리즘과 함께 사용된다.
• selection function = min[s]

Shortest Process Next(SPN) 예시

• Turnaround time
  • A : 3
  • B : 7
  • C : 11
  • D : 14
  • E : 3
• Average Turnaround time : 7.6
• 동일한 수행 시간을 요구하는 프로세스들이 들어올 경우 FIFO 방식이 더 좋은 성능을 보여줄 수도 있다.

Shortest Remaining Time Next(SRTN 혹은 SRT)

• 선점형(Preemptive) 스케줄링 알고리즘이다.
• SPN 스케줄링의 변형으로, 현재 실행 중인 프로세스의 남은 실행 시간보다 더 짧은 실행 시간을 가진 새로운 프로세스가 도착하면 현재 프로세스를 선점하고 새로운 프로세스에게 CPU를 할당한다.
• 동작 원리
  1. 프로세스들은 도착한 순서대로 준비 큐(Ready Queue)에 삽입된다.
  2. 스케줄러는 준비 큐에 있는 프로세스들의 남은 실행 시간을 예측하거나 알고 있다고 가정한다.
  3. CPU는 현재 실행 중인 프로세스의 남은 싲ㄹ행 시간과 준비 큐에 있는 프로세스들의 실행 시간을 비교한다.
  4. 준비 큐에 있는 프로세스 중 남은 실행 시간이 현재 실행 중인 프로세스의 남은 실행 시간보다 짧은 프로세스가 있다면, 현재 프로세스를 선점하고 해당 프로세스에게 CPU를 할당한다.
  5. 선택된 프로세스는 실행을 완료하거나, 더 짧은 실행 시간을 가진 새로운 프로세스가 도착할 때까지 CPU를 점유한다.
  6. 프로세스가 완료되면, 다시 준비 큐에서 남은 실행 시간이 가장 짧은 프로세스를 선택하여 실행한다.
• 특징
  • 선점형 알고리즘이므로, 현재 실행 중인 프로세스의 남은 실행 시간보다 더 짧은 실행 시간을 가진 프로세스가 도착하면 선점이 발생한다.
  • 평균 대기 시간과 평균 반환 시간(Turnaround Time)을 최소화 하는 것을 목표로 한다.
  • 새로 도착한 프로세스의 실행 시간이 현재 실행 중인 프로세스보다 짧은 경우, 빠른 응답 시간을 제공할 수 있다.
  • Context Switch 오버헤드가 발생할 수 있다.
  • 프로세스의 남은 실행 시간을 정확히 예측해야 하는 것이 어려울 수 있다.
  • Starvation이 발생할 가능성이 있다.(긴 실행 시간을 가진 프로세스는 계속해서 선점 당할 수 있다)
  • Turnaround Time 측면에서 optimal하다.
• 유용한 상황
  • 대화형 시스템이나 실시간 시스템에서 빠른 응답 시간을 제공하기 위해 사용될 수 있다
  • 작업 부하가 주로 짧은 프로세스로 구성되어 있는 경우 효과적이다.
• 한계점
  • 프로세스의 남은 실행 시간을 정확히 예측하는 것이 어려울 수 있다.
  • 잦은 문맥 교환이로 인한 오버헤드가 발생할 수 있다.
  • 긴 실행 시간을 가진 프로세스가 무한정 대기하는 기아 현상이 발생할 수 있다.
• 한계점을 해결하기 위한 방안
  • SPN(SJF)과 동일
• Selection Function = min(S-E)
• Exponential average : 실행 시간 예측 방법
  • 과저의 실행 시간들 중에 최근 실행 시간들에 높은 가중치를 두고 계산하는 방법

SRTN 예시

• Turnaround Time
  • A : 3
  • B : 13
  • C : 4
  • D : 14
  • E : 2
• Average turnaround time : 7.2

Highest Response Ratio Next(HRRN)

• 비선점형(Non-preemptive) 스케줄링 알고리즘으로, 각 프로세스의 응답률(Response Ratio)을 기준으로 우선 순위를 할당하여 CPU를 할당하는 방식이다.
  • 응답률은 프로세스의 대기 시간과 실행 시간을 고려하여 계산된다.
• 동작 원리
  1. 프로세스들은 도착한 순서대로 준비 큐(Ready Queue)에 삽입된다.(이쯤되면 이 과정은 말 안해도 다들 아실 것 같다. ㅡ.ㅡ)
  2. 각 프로세스의 응답률을 계산한다
     • 응답률 = (대기 시간 + 실행 시간) / 실행 시간
     • 대기 시간은 프로세스가 준비 큐에서 대기한 시간을 의미한다
     • 실행 시간은 프로세스의 예상 실행 시간 또는 실제 실행 시간을 의미한다.
  3. 응답률이 가장 높은 프로세스에게 CPU를 할당한다.
  4. 할당받은 프로세스는 실행을 완료할 때까지 CPU를 점유한다.
  5. 프로세스가 완료되면, 다시 준비 큐에 있는 프로세스들의 응답률을 계산하고 가장 높은 응답률을 가진 프로세스에게 CPU를 할당한다.
• 특징
  • 비선점형 방식이다
  • 프로세스의 대기 시간과 실행 시간을 모두 고려하여 응답률을 계산한다.
  • 대기 시간이 길어질수록 응답률이 높아지므로, 오래 기다린 프로세스에게 우선순위를 부여한다.
  • 실행 시간이 짧은 프로세스와 대기 시간이 긴 프로세스 사이의 균형을 유지할 수 있다.
  • 기아 현상(Starvation)을 방지할 수 있다.
    • 대기 시간이 길어질수록 응답률이 높아지므로 오래 기다린 프로세스는 결국 CPU를 할당받게 된다.
• 유용한 경우
  • 대기 시간과 실행 시간을 모두 고려하여 프로세스에 공정한 기회를 제공하고자 할 때 사용될 수 있다.
  • 긴 작업과 짧은 작업이 혼재되어 있는 시스템에서 효과적이다.
  • 기아 현상을 방지하면서도 시스템의 전반적인 성능을 향상 시키고자 할 때 사용될 수 있다.
• 한계점
  • 프로세스의 실행 시간을 예측해야 하므로, 정확한 예측이 어려울 수 있다.
  • 프로세스의 실행 시간이 매우 길 경우, 다른 프로세스들의 대기 시간이 길어질 수 있다.
  • 비선점형 알고리즘이므로, 긴급한 프로세스가 도착하더라도 현재 실행 중인 프로세스를 선점할 수 없다.
• HRRN 스케줄링은 SJF(Shortest Job First) 스케줄링과 유사하지만, 대기 시간을 고려하여 기아 현상을 방지한다는 점에서 차이가 있다.
• 또한, 응답률 계산에서 실행 시간과 대기 시간을 모두 고려하므로 보다 공정한 스케줄링을 제공할 수 있다.
• Selection Function = Max[(w+s)/s]

HRRN 예시

• Turnaround time
  • A : 3
  • B : 7
  • C : 9
  • D : 14
  • E : 7
• Average turnaround time : 8.0

Round-Robin

• 선점형 스케줄링 알고리즘으로, 각 프로세스에 동일한 시간 할당량(Time Quantum 혹은 Time Slice)을 부여하고 순환적으로 CPU를 할당하는 방식이다.
• 할당된 시간 동안 CPU를 사용하고 시간이 만료되면 다음 프로세스에게 CPU를 넘겨준다.
• 동작 원리
  1. 시간 할당량(Time Quantum)을 정의한다. 이는 각 프로세스가 한 번에 CPU를 사용할 수 있는 시간을 나타낸다.
  2. 프로세스들은 도착한 순서대로 준비 큐에 삽입된다.
  3. 준비 큐의 첫 번째 프로세스에게 CPU를 할당하고, 할당된 시간 동안 실행한다.
  4. 할당된 시간이 만료되면 타이머 인터럽트가 발생하고, 현재 실행 중인 프로세스는 준비 큐의 끝으로 이동한다.
  5. 준비 큐의 다음 프로세스에게 CPU를 할당하고, 할당된 시간 동안 실행한다.
  6. 프로세스가 할당된 시간 내에 실행을 완료하면 종료되고, 그렇지 않으면 준비 큐의 끝으로 이동한다.
  7. 준비 큐가 비어있을 때까지 이 과정을 반복한다.
• 특징
  • 선점형 알고리즘이므로, 시간 할당량이 만료되면 프로세스는 선점되고 다음 프로세스에게 CPU를 넘겨준다.
  • 각 프로세스는 동일한 시간 할당량을 받으므로, CPU 사용 기회가 공평하게 분배된다.
  • 시간 할당량이 작을수록 Context Switch가 빈번하게 발생하여 오버헤드가 증가할 수 있다.
  • 시간 할당량이 클수록 응답시간이 길어진다.(FIFO 방식과 유사해진다)
  • 시간 할당량이 작아지면 SPN이랑 비슷해진다
  • 프로세스의 실행 시간이 시간 할당량보다 큰 경우, 여러 번 선점되어 실행될 수 있다.
• 유용한 상황
  • 시분할 시스템(Time-sharing System)에서 사용자 간의 공평한 CPU 사용을 보장하고자 할때 사용된다.
  • 대화형 시스템에서 빠른 응답 시간을 제공하기 위해 사용될 수 있다.
  • 프로세스의 특성이 다양하고 실행 시간을 예측하기 어려운 경우에 효과적이다.
• 한계점
  • 시간 할당량의 크기에 따라 성능이 좌우된다.(적절한 시간 할당량을 선택하는 것이 중요하다)
  • 프로세스의 실행 시간이 시간 할당량보다 큰 경우, 여러 번 선점되어 Context Switch 오버헤드가 발생할 수 있다.
  • 프로세스의 특성을 고려하지 않고 동일한 시간 할당량을 뷰여하므로, 최적의 성능을 보장하지는 않는다.
• RR 스케줄링은 시분할 시스템에서 널리 사용되며, 사용자 간의 공평한 CPU 사용과 빠른 응답 시간을 제공하는 것을 목표로 한다.
• 시간 할당량의 크기는 시스템의 특성과 요구사항에 따라 적절히 선택되어야 한다.

Round-Robin 예시

• Turnaround Time
  • A : 4
  • B : 16
  • C : 13
  • D : 14
  • E : 7
• Average turnaround time : 10.8

Round-Robin 심화 예시

• 짧은 것들은 앞으로 땡겨지는 경향이 생긴다.
• 또한 Time Slice가 작아질 수록 Response Time이 좋아진다.
• Turnaround time 이건 무조건 좋아지는건 아니다.

• I/O 입출력이 있는 경우

  • Two process

    • A : Run for 10 ms then wait for I/O for 50ms
    • B : No waiting(CPU-intensive)

  

• time slice가 작으면 long process가 불리하다.
• response time 증가, 유틸리티 증가

Virtual Round Robin

• I/O bound process에 유리한 점 추가 : I/O Request에 의해 Time slice를 다쓰지 못하고 blocking되면 다음번에 유리한 queue에 들어감.

Multi-Level Feedback Queue(MLFQ)

• Multi-Level Feedback Queue (MLFQ) 스케줄링은 다단계 피드백 큐를 사용하여 프로세스를 스케줄링하는 방법이다.

• MLFQ는 우선순위가 다른 여러 개의 준비 큐(Ready Queue)를 사용하며, 프로세스의 특성에 따라 동적으로 우선순위를 조정한다.

• MLFQ 스케줄링의 주요 목적

  • 프로세스의 특성에 따라 적응적으로 우선순위를 할당하여 시스템의 응답성과 처리량을 향상시키는 것이다.
  • I/O 바운드 프로세스와 CPU 바운드 프로세스를 구분하여 효과적으로 스케줄링하는 것이다.
  • 사용자 상호작용을 개선하고 시스템의 전반적인 성능을 향상시키는 것이다.

• MLFQ 스케줄링의 동작 원리

  1. 우선순위가 다른 여러 개의 준비 큐를 생성합니다. 일반적으로 우선순위가 높은 큐부터 낮은 큐 순으로 배치된다.
  2. 프로세스는 처음에 가장 높은 우선순위의 큐에 할당된다.
  3. 각 큐마다 다른 타임 슬라이스(Time Slice)를 할당합니다. 우선순위가 높은 큐는 짧은 타임 슬라이스를, 우선순위가 낮은 큐는 긴 타임 슬라이스를 할당받는다.
  4. 프로세스는 할당된 타임 슬라이스 동안 실행됩니다. 타임 슬라이스가 만료되면 프로세스는 현재 큐에서 제거되고 우선순위가 한 단계 낮은 큐로 이동한다.
  5. 프로세스가 I/O 작업을 수행하거나 자발적으로 CPU를 양보하면, 해당 프로세스는 원래 있던 큐로 이동한다.
  6. 우선순위가 높은 큐에 프로세스가 없는 경우, 우선순위가 낮은 큐에서 프로세스를 선택하여 실행한다.
  7. 이 과정은 모든 프로세스가 종료될 때까지 반복된다.

• MLFQ 스케줄링의 특징

  • I/O 바운드 프로세스는 I/O 작업 후에 높은 우선순위의 큐로 이동하므로 빠른 응답 시간을 보장받을 수 있습니다.
  • CPU 바운드 프로세스는 점진적으로 낮은 우선순위의 큐로 이동하므로 장기 실행 프로세스의 기아 현상을 방지할 수 있습니다.
  • 동적 우선순위 조정을 통해 시스템의 응답성과 처리량을 향상시킬 수 있습니다.
  • 우선순위가 높은 큐에서 짧은 타임 슬라이스를 사용하므로 대화형 프로세스에 적합합니다.
• 고려사항
  • 큐의 개수, 각 큐의 타임 슬라이스, 우선순위 조정 기준 등을 적절히 설정해야 합니다.
  • 우선순위 변경으로 인한 오버헤드가 발생할 수 있습니다.
  • 프로세스의 특성을 정확히 파악하고 적절한 피드백을 제공해야 효과적입니다.

MLFQ 스케줄링은 프로세스의 특성을 고려하여 적응적으로 우선순위를 조정함으로써 시스템의 응답성과 처리량을 향상시키는 것을 목표로 합니다. 실제 시스템에서는 MLFQ의 변형이나 다른 스케줄링 알고리즘과의 조합을 통해 최적의 성능을 얻을 수 있습니다.