운영체제 공룡책

[운영체제 공룡책] 5장 CPU Scheduling

studyingalone 2024. 12. 14. 18:28
728x90

5.1 Basic Concepts

  • 단일 CPU 코어가 있는 시스템에서는 한 번에 하나의 프로세스만 실행할 수 있다.
  • 멀티프로그래밍의 목적은 CPU 사용률을 최대화하기 위해 항상 일부 프로세스를 실행하는 것

5.1.1 CPU – I/O Burst Cycle

  • 프로세스 실행 사이클: CPU 실행(CPU burst)과 I/O 대기(I/O burst)가 번갈아 발생. 마지막 CPU burst는 프로세스 종료 요청으로 끝남.
  • CPU burst 분포: 짧은 CPU burst가 많고 긴 CPU burst는 드물며, 분포는 지수적 또는 초지수적.
    • I/O 중심 프로그램: 짧은 CPU burst가 많음.
    • CPU 중심 프로그램: 긴 CPU burst가 적음.
  • 스케줄링 중요성: 이러한 분포를 고려해 CPU 스케줄링 알고리즘을 구현해야 함.

Alternating sequence of CPU and I/O bursts.

5.1.2 CPU Scheduler

  • 역할: CPU가 유휴 상태가 되면 준비 큐에 있는 프로세스 중 하나를 선택해 CPU를 할당.
  • 준비 큐 구현 방식: FIFO, 우선순위 큐, 트리, 비정렬 연결 리스트 등 다양.
  • 프로세스 제어 블록(PCB): 준비 큐에서 프로세스 정보를 관리.

Histogram of CPU-burst durations

5.1.3 Preemptive and Nonpreemptive Scheduling

  • 스케줄링 시점:
    1. 프로세스가 실행 상태에서 대기 상태로 전환될 때 (예: I/O 요청).
    2. 프로세스가 실행 상태에서 준비 상태로 전환될 때 (예: 인터럽트 발생).
    3. 프로세스가 대기 상태에서 준비 상태로 전환될 때 (예: I/O 완료).
    4. 프로세스가 종료될 때.
  • 스케줄링 유형:
    • 비선점형(Nonpreemptive): 시점 1, 4에서만 발생하며, 프로세스가 CPU를 스스로 놓을 때까지 유지.
    • 선점형(Preemptive): 시점 2, 3에서도 스케줄링 가능. 대부분의 현대 OS는 선점형 알고리즘 사용.
  • 선점형 스케줄링의 문제:
    • 경쟁 상태(Race Condition): 공유 데이터가 일관되지 않은 상태가 될 위험.
    • 커널 설계: 선점형 커널은 뮤텍스 락 등으로 데이터 보호 필요.
  • 비선점형 커널: 간단하지만 실시간 컴퓨팅 지원에 부적합.

5.1.4 Dispatcher

  • 역할: CPU 스케줄러가 선택한 프로세스에 CPU 제어권을 넘김.
    • 기능:
      1. 프로세스 간 컨텍스트 전환.
      2. 사용자 모드로 전환.
      3. 사용자 프로그램의 실행 위치로 점프.
  • 디스패처 지연: 컨텍스트 전환 시간이며, 빠를수록 효율적.

5.2 Scheduling Criteria

CPU 스케줄링 알고리즘 선택 시 고려해야 할 기준

  • CPU 활용률(CPU Utilization): CPU를 가능한 한 바쁘게 유지해야 함. 실제 시스템에서는 40%~90% 사이를 목표로 함.
  • 처리량(Throughput): 단위 시간당 완료된 프로세스 수.
  • 반환 시간(Turnaround Time): 프로세스 제출부터 완료까지 걸린 시간.
    • 준비 큐 대기 시간 + CPU 실행 시간 + I/O 작업 시간의 합.
  • 대기 시간(Waiting Time): 준비 큐에서 대기한 총 시간.
  • 응답 시간(Response Time): 요청 제출 후 첫 응답이 생성되기까지 걸린 시간.

5.3.1 First-Come, First-Served Scheduling

FCFS(First-Come, First-Served) 스케줄링 알고리즘은 가장 단순한 CPU 스케줄링 알고리즘으로, 먼저 요청한 프로세스가 먼저 CPU를 할당받는 방식

  • 구현 방식: 프로세스는 준비 큐(ready queue)에 도착하면 큐의 끝에 추가되고, CPU는 큐의 맨 앞 프로세스에 할당
  • 특징:
    • FIFO 큐를 사용하여 관리.
    • 비선점형(non-preemptive): 한 번 CPU를 할당받으면 작업이 끝날 때까지 반환하지 않음.
  • 장점: 코드가 단순하고 이해하기 쉬움.
  • 단점:
    • 평균 대기 시간 증가 가능성: 프로세스 도착 순서와 CPU 실행 시간에 따라 대기 시간이 크게 달라질 수 있음.
      • 예:
        • 순서(P1, P2, P3): 평균 대기 시간 = 17ms
        • 순서(P2, P3, P1): 평균 대기 시간 = 3ms

5.3.2 Shortest-Job-First Scheduling

Shortest-Job-First(SJF) 스케줄링 알고리즘은 각 프로세스의 다음 CPU 버스트 시간을 기준으로 CPU를 할당하는 방식이다. 다음 CPU 버스트가 가장 짧은 프로세스가 먼저 실행.

  • 기본 개념:
    • SJF는 최적화된 알고리즘으로, 주어진 프로세스 집합에서 평균 대기 시간이 최소가 된다.
    • FCFS와 비교: SJF는 더 짧은 CPU 버스트를 먼저 실행하여 평균 대기 시간을 줄입니다.
  • 예시:
    • 프로세스: P1(6ms), P2(8ms), P3(7ms), P4(3ms)
    • SJF 스케줄: P4 → P1 → P3 → P2 (평균 대기 시간 7ms)
    • FCFS 스케줄: 평균 대기 시간 10.25ms

  • 단점:
    • 다음 CPU 버스트를 알 수 없기 때문에 예측 방법 필요.
    • 예측 방법: 이전 CPU 버스트의 지수 평균을 사용해 다음 버스트를 예측.
    • 예측 공식: τn+1 = α tn + (1 - α) τn, 여기서 α는 최근 정보의 가중치.
  • 선점형 및 비선점형:
    • 선점형 SJF(Shortest-Remaining-Time-First, SRTF): 새로운 프로세스가 도착할 때, 현재 실행 중인 프로세스의 남은 시간보다 짧은 CPU 버스트를 가진 프로세스를 실행.
    • 비선점형 SJF: 실행 중인 프로세스가 끝날 때까지 기다림.
  • 예시 (선점형):
    • 프로세스: P1(8ms), P2(4ms), P3(9ms), P4(5ms)
    • 결과 Gantt 차트: P1 → P2 → P4 → P1 → P3
    • 평균 대기 시간: 6.5ms (선점형), 7.75ms (비선점형)

5.3.3 Round-Robin Scheduling

Round-Robin(RR) 스케줄링 알고리즘은 FCFS와 비슷하지만 선점 기능이 추가된 알고리즘이다. 각 프로세스는 고정된 시간 단위인 타임 퀀텀(time quantum)만큼 CPU를 할당받고, 그 후에는 다른 프로세스로 전환.

  • 동작 원리:
    • 준비 큐(ready queue)를 순차적으로 순회하며 각 프로세스에 최대 1 타임 퀀텀만큼 CPU를 할당.
    • 프로세스가 CPU 버스트를 마치기 전에 타임 퀀텀이 다 되면, 프로세스는 대기 큐 뒤로 밀리고, 다음 프로세스가 실행됩니다.
    • 타임 퀀텀의 길이는 일반적으로 10~100ms
  • 예시:
    • 프로세스: P1(24ms), P2(3ms), P3(3ms)
    • 타임 퀀텀: 4ms
    • Gantt 차트: P1 → P2 → P3 → P1 → P1 → P1 → P1 → P1
    • 평균 대기 시간: 5.66ms

5.3.4 Priority Scheduling

Priority Scheduling은 각 프로세스에 우선순위를 할당하고, CPU는 가장 높은 우선순위를 가진 프로세스에 할당되는 스케줄링 알고리즘. 우선순위가 동일한 프로세스는 FCFS(선입선출) 방식으로 처리. SJF는 우선순위가 CPU burst의 길이에 비례하는 특별한 형태로, CPU burst가 짧을수록 우선순위가 높다.

  • 우선순위 정의:
    • 내부 정의: 시스템 자원(예: CPU와 I/O 사용 비율, 메모리 요구량 등)을 기준으로 우선순위 결정.
    • 외부 정의: 외부 요인(예: 중요도, 자금 등)에 따라 우선순위가 결정.
  • 선점 및 비선점:
    • 선점형: 우선순위가 높은 프로세스가 새로 도착하면, 현재 실행 중인 프로세스를 중단하고 CPU를 선점.
    • 비선점형: 새로 도착한 프로세스는 대기 큐에 추가되며, 현재 실행 중인 프로세스는 완료될 때까지 실행.
  • 문제점 - 기아(Starvation):
    • 우선순위가 낮은 프로세스는 계속해서 높은 우선순위의 프로세스에 의해 CPU를 선점당할 수 있음.
    • 해결 방법: Aging(나이가 든 프로세스의 우선순위 증가) 기법을 사용하여 대기 중인 프로세스가 실행될 수 있도록 함.
  • 우선순위 + Round-Robin:
    • 동일 우선순위 프로세스들은 Round-Robin 방식으로 처리하여, 공정성을 유지하고 기아를 방지할 수 있음.

예시:

  • 프로세스와 우선순위:
    • P1(4ms, 우선순위 3), P2(5ms, 우선순위 2), P3(8ms, 우선순위 2), P4(7ms, 우선순위 1), P5(3ms, 우선순위 3)
  • Gantt 차트: P4 → P2 → P3 → P2 → P3 → P2 → P3 → P1 → P5 → P1 → P5

 

 

5.4 Thread Scheduling

스레드 스케줄링은 사용자 수준 스레드와 커널 수준 스레드의 스케줄링 방식에 차이가 있습니다. 대부분의 현대 운영 체제에서는 커널 수준 스레드가 스케줄링됩니다. 사용자 수준 스레드는 스레드 라이브러리에서 관리되며, 운영 체제는 이를 알지 못합니다. 사용자 스레드는 궁극적으로 커널 스레드에 매핑되어 실행됩니다.

  1. 경쟁 범위(Contents Scope):
    • 프로세스 경쟁 범위(PCS): 사용자 스레드가 동일 프로세스 내에서 경쟁합니다. 사용자 스레드는 스레드 라이브러리에서 관리되며, LWP(경량 프로세스)를 통해 커널 스레드에 매핑됩니다. 우선순위에 따라 스케줄링됩니다.
    • 시스템 경쟁 범위(SCS): 커널 수준에서 모든 스레드가 경쟁합니다. 일대일 모델을 사용하는 시스템(예: Windows, Linux)은 SCS를 사용하여 스레드를 CPU에 할당합니다.

5.5 Multi-Processor Scheduling

5.5.1 Approaches to Multiple-Processor Scheduling

  1. 비대칭 다중 처리(SMP):
    • 단일 서버 접근법: 모든 스케줄링, I/O 처리 등은 하나의 프로세서(마스터 서버)가 담당하고, 나머지 프로세서는 사용자 코드만 실행.
    • 장: 간단
    • 단: 병목 현상이 발생할 수 있다.
  2. 대칭 다중 처리(SMP):
    • 각 프로세서가 자체 스케줄링: 모든 프로세서가 자신의 스케줄러를 가지고, 각 프로세서가 준비 큐를 검사하여 실행할 스레드를 선택
    • 이 방식에는 두 가지 전략:
      1. 공유 준비 큐: 모든 스레드가 하나의 큐에서 관리되며, race condition을 방지하기 위해 락을 사용해야 한다. 이게 성능 저하를 일으킬 수 있다.
      2. 개별 준비 큐: 각 프로세서가 자신만의 큐에서 스레드를 선택하므로 성능 문제를 방지할 수 있다. 이 방법은 캐시 메모리 사용 효율성을 높이고, 각 프로세서가 작업을 분배할 수 있게 한다.

Organization of ready queues

5.5.2 Multicore Processors

 

  • 현대 시스템은 멀티코어 프로세서를 사용하며, 하나의 물리적 칩에 여러 코어가 존재. 각 코어는 OS에서 독립적인 논리 CPU로 인식됨.
  • 멀티코어 시스템은 각 CPU가 별도의 칩에 있는 시스템보다 더 빠르고 전력 효율이 높음.

 

메모리 스톨과 멀티스레딩

  • 메모리 스톨: 프로세서가 메모리에서 데이터를 가져오는 동안 대기하는 상황. 주로 캐시 미스로 인해 발생.

Memory stall

  • 이를 해결하기 위해 멀티스레딩 기술이 도입됨. 한 스레드가 대기 중일 때 다른 스레드가 실행되도록 설계.
  • 칩 멀티스레딩(CMT): 각 코어에 여러 하드웨어 스레드를 할당하여 코어 사용률을 높임.

 

 

Chip multithreading

 

 

멀티스레딩 방식

  • Coarse-Grained 멀티스레딩: 메모리 스톨 같은 지연 이벤트 발생 시 스레드를 전환. 전환 시 파이프라인 플러시로 인해 비용이 큼.
  • Fine-Grained 멀티스레딩: 명령어 경계에서 스레드를 전환. 전환 비용이 낮고 효율적.

Multithreaded multicore system

 

 

2단계 스케줄링

  • 1단계(OS 스케줄링): OS가 어떤 소프트웨어 스레드를 논리 CPU에서 실행할지 결정.
  • 2단계(하드웨어 스케줄링): 코어가 어떤 하드웨어 스레드를 실행할지 결정.

Two levels of scheduling

 

 

5.5.3 Load Balancing

로드 벨런싱(Load Balancing)의 필요성

  • SMP(대칭 멀티프로세싱) 시스템에서 모든 프로세서의 작업 부하를 균형 있게 유지해야 멀티프로세서의 이점을 최대한 활용 가능함
  • 부하가 불균형하면 일부 프로세서는 유휴 상태가 되고, 다른 프로세서는 과부화와 긴 대기큐를 가지게 됨

로드 벨런싱의 목적

  • 작업 부하를 모든 프로세서에 고르게 분배

※ 공통 실행 큐를 사용하는 시스템에서는 필요하지 않음

➡️ 프로세서가 유휴 상태가 되면 즉시 공통 큐에서 스레드를 가져오기 때문

 

로드 밸런싱 방식

  • 푸시 마이그레이션(push migration): 특정 작업이 주기적으로 각 프로세서의 부하를 점검하고, 불균형이 발견되면 작업을 덜 바쁜 프로세서로 이동시켜 부하를 분산.
  • 풀 마이그레이션(Pull migration): 유휴 상태의 프로세서가 과부하 상태의 프로세서에서 대기 중인 작업을 가져옴.
  • 이 두 방식은 독립적으로 작동하지 않고, 일반적으로 병행하여 구현.

로드 벨런 방식

 

  • 모든 큐에 스레드 수를 균등하게 맞추는 방식.
  • 모든 큐에 스레드 우선순위를 균등하게 분배하는 방식.

 

 

5.6 Real-Time CPU Scheduling

 

  • 소프트 실시간 시스템(Soft real-time systems): 실시간 프로세스가 우선순위를 가지지만, 언제 스케줄링될지는 보장하지 않음.
  • 하드 실시간 시스템(Hard real-time systems): 작업이 엄격한 기한(Deadline) 내에 반드시 처리되어야 함. 기한을 초과하면 처리가 무의미.

5.6.1 Minimizing Latency

 

  • 실시간 시스템은 이벤트 기반으로 작동하며, 발생한 이벤트에 신속히 반응해야 함.
  • 이벤트 지연(event latency): 이벤트가 발생한 시점부터 처리되기까지 소요되는 시간

 

Event latency

 

주요 지연 유형:

  1. 인터럽트 지연(Interrupt latency): CPU가 인터럽트를 처리하기 시작하기까지 걸리는 시간.
  2. 디스패치 지연(Dispatch latency): 프로세스를 중단하고 새로운 프로세스를 시작하는 데 걸리는 시간.

 

 

인터럽트 지연 (Interrupt latency)

  • 인터럽트가 도착한 시점부터 인터럽트 서비스 루틴(ISR)이 실행되기까지의 시간.
  • 최소화 전략:
    • 커널 데이터 구조를 업데이트할 때 인터럽트를 비활성화하는 시간을 최소화.
    • 하드 실시간 시스템에서는 지연 시간이 반드시 유한하고 예측 가능해야 함.

Interrupt latency

 

 

디스패치 지연(Dispatch latency)

  • 스케줄링 디스패처가 기존 프로세스를 중단하고 새로운 프로세스를 실행하는 데 소요되는 시간.
  • 디스패치 지연의 구성 요소:
    1. 충돌 단계:
      • 커널에서 실행 중인 프로세스의 선점.
      • 낮은 우선순위 프로세스가 높은 우선순위 프로세스에 필요한 자원을 해제.
    2. 디스패치 단계:
      • 높은 우선순위 프로세스를 CPU에 스케줄링.
  • 최소화 전략:
    • 선점 가능한 커널(preemptive kernel) 도입.
    • 하드 실시간 시스템에서는 마이크로초(µs) 단위로 측정.

 

 

Dispatch latency

 

5.6.2 우선순위 기반 스케줄링 (Priority-Based Scheduling)

 

  • 특징: 실시간 시스템은 우선순위 기반 알고리즘과 선점(preemption)을 지원해야 함.
    • 선점 지원: 높은 우선순위 프로세스가 준비 상태가 되면 실행 중인 프로세스를 중단시킴.

Periodic task

  • 위 그림은 시간에 따른 주기적 프로세스의 실행
  • 프로세스의 마감일(deadline) 또는 비율 요구 사항에 따라 우선 순위를 할당할 수 있다.
  • 프로세스가 스케줄러에게 마감일을 알려야 함
  • 다음 스케줄러는 승인 제어 알고리즘이라는 기술을 사용하여 두 가지 중 하나를 수행 
    1. 프로세스를 승인하여 프로세스가 제시간에 완료되도록 보장
    2. 마감일까지 작업을 서비스할 수 없다고 보장할 수 없는 경우 요청을 불가능하다고 거부

5.6.3 비율-단조 스케줄링 (Rate-Monotonic Scheduling, RMS)

  • 특징:
    • 우선순위 정적 할당: 짧은 주기를 가진 작업이 높은 우선순위를 가짐.
    • 선점 가능.
  • 장점:
    • 최적성 보장: 정적 우선순위 기반 알고리즘 중 가장 효율적.
  • 한계: 높은 CPU 사용률(94% 등)에서는 모든 작업의 기한 준수를 보장하지 못할 수 있음.

 

P2에 P1보다 더 높은 우선순위를 할당

Scheduling of tasks when P2 has a higher priority than P1

  • 그림에서 볼 수 있듯이 P2가 먼저 실행을 시작하고 35번째에 완료.
  • 이 시점에서 P1이 시작되어 55시간에 CPU 버스트를 완료
  • 그러나 P1의 첫 번째 기한이 50번째 시간이었으므로 스케줄러로 인해 P1이 기한을 놓쳤다.

 

P1에 P2보다 높은 우선순위를 할당하는 속도 단조 스케줄링을 사용

Rate-monotonic scheduling

  • P1이 먼저 시작하여 시간 20에 CPU 버스트를 완료하여 첫 번째 기한을 충족
  • P2는 이 시점에서 실행을 시작하여 시간 50까지 실행
  • 이때 아직 CPU 버스트에 5밀리초가 남아있지만 P1에 의해 선점
  • P1은 시간 70에 CPU 버스트를 완료하고, 이 시점에서 스케줄러가 P2를 다시 시작
  • P2는 시간 75에 CPU 버스트를 완료하여 첫 번째 기한을 충족
  • P1이 다시 스케줄링되는 시간 100까지 시스템은 유휴 상태

5.6.4 가장 빠른 기한 우선 (Earliest-Deadline-First, EDF) 스케줄링

  • 특징:
    • 우선순위를 동적으로 조정: 기한이 빠를수록 높은 우선순위 부여.
    • 주기적 작업뿐만 아니라, 비주기적 작업도 지원.
    • 이론적 최적성: CPU 사용률 최대 100%까지 활용 가능.
  • 한계:
    • 문맥 전환 및 인터럽트 처리로 인해 실제로는 100% 달성 불가.

 

  • :
    • 주기 p1 = 50, 처리 시간 t1 = 25t
  • :
    • 주기 , 처리 시간 .

 

 

  • 초기 실행:
    • 이 더 빠른 기한(50)을 가지므로 높은 우선순위로 먼저 실행.
    • 실행 후 실행.
  • 기한 기반 우선순위 조정:
    • 가 기한(80)에 가까워질 때 우선순위가 높아져, 의 선점을 막고 실행 완료.
    • 결과적으로 모든 작업이 기한을 준수.

 

 

 

 

728x90
반응형

'운영체제 공룡책' 카테고리의 다른 글

[운영체제 공룡책] 7장 동기화 예제  (0) 2025.01.15
[운영체제 공룡책] 6장 Synchronization Tools(동기화 도구)  (1) 2025.01.02
[운영체제 공룡책] 4장 Threads &Concurrency  (1) 2024.11.26
[운영체제 공룡책] 3장 ProcessManagement  (4) 2024.11.20
[운영체제 공룡책] 2장 Operating - System Structures  (4) 2024.11.13

'운영체제 공룡책'의 다른글

  • 현재글[운영체제 공룡책] 5장 CPU Scheduling

관련글

티스토리툴바