[운영체제] CPU Scheduling

빈·2022년 1월 19일
OS
1

OS

목록 보기
5/5
post-thumbnail

CPU-burst Time 분포

  • I/O bound job
    • 좌측
    • CPU를 잡고 계산하는 시간 보다 I/O에 많은 시간 필요.
    • 사람하고 상호작용
    • many short CPU bursts
  • CPU bound job
    • CPU 오래씀. I/O 빈도 낮음
    • 계산 위주 job
    • few very long CPU bursts

💥 여러 종류의 job(=process) 섞여 있기 때문에 CPU 스케줄링 필요

  • Interactive job에 적절한 response 제공 요망
  • CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

CPU Scheduler & Dispatcher

  • CPU Scheduler
    • Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스 결정
  • Dispatcher
    • CPU 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘겨주는 역할
    • context switch
  • CPU 스케줄링이 필요한 경우
    1. Running → Blocked (예: I/O 요청하는 시스템콜)
    2. Running → Ready (예: 할당시간 만료 timer interrupt)
    3. Blocked → Ready (예: I/O 완료 후 interrupt. 우선순위가 높을 경우)
    4. Terminate
      ⇒ 1, 4 경우 nonpreemptive (= 강탈 아닌 자진 반납)
      All other scheduling is preemptive (= 강제로 빼앗음)

Scheduling Criteria (CPU 성능 척도)

CPU 입장

  • CPU utilization (이용률)
    • keep the CPU as busy as possible
  • Throughput (처리량)
    • of processes that complete their execution per time unit

PROCESS 입장

  • Turnaround time (소요시간, 반환시간)
    • amount of time to execute a particular process
  • Waiting time (대기 시간)
    • amount of time a process has been waiting in the ready queue
  • Response time (응답 시간)
    • amount of time it takes from when a request was submitted until the first response is produced. not output (for time-sharing enviroment)

CPU 스케줄링 알고리즘

  1. FCFS (First come first served)
    • 먼저 온 순서대로 실행
    • Convoy effect : short process behind long process
  2. SJF (Shortest-Job-First)
    • 각 프로세스와 다음번 CPU burst time을 가지고 스케줄링 활용
    • CPU burst time이 가장 짧은 프로세스를 먼저 스케줄
    • Two schemes
      • Nonpreemptive
        • CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음
      • Preemptive
        • 현재 수행중인 프로세스와 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU 빼앗김
        • 이 방법을 Shortest Remaining Time First (SRTF)라고 부름
    • SJF is optimal
      • 주어진 프로세스들에 대해 minimum average waiting time 보장
    • long process 가 실행되지 못할 수도 있음
    • 다음 CPU burst time 예측
      • 추정(estimate)만 가능
      • 과거의 CPU busrt time을 이용해서 추정 (exponential averaging)
  3. Priority Scheduling
    • A priority number(integer) is associated with each process
    • highest priority를 가진 프로세스에게 CPU 할당 (smallest integer = highest priority)
      • preemptive
      • nonpreemptive
    • SJF 는 일종의 priority scheduling
      • priority = predicted next CPU burst time
    • problem
      • Starvation : low priority processes may never execute
    • solution
      • Aging : as time progresses increase the priority of the process (오래 기다리면 우선순위 높이기)
  4. Round Robin (RR)
    1. 각 프로세스는 동일한 크기와 할당 시간(time quantum)을 가짐
    2. 할당 시간이 지나면 프로세스는 선점 당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다
    3. n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU시간의 1/n을 얻는다 ⇒ 어떤 프로세스도 (n-1)q time unit 이상 대기하지 않음
    4. Performance
      • q large → FCFS
      • q small → context switch 오버헤드가 커짐
    5. 응답시간이 빠름 Response time
  5. Multilevel Queue

    1. Ready Queue를 여러개로 분할

      • foreground (interactive)
      • background (batch-no human interaction)

    2. 각 큐는 독립적인 스케줄링 알고리즘을 가짐

      • foreground - RR
      • background - FCFS

    3. 큐에 대한 스케줄링 필요

      • Fixed priority scheduling
        • serve all from foreground then from background
        • Possibility of starvation
      • Time slice
        • 각 큐에 CPU time을 적절한 비율로 할당
        • Eg., 80% to foreground in RR, 20% to background in FCFS
  6. Multilevel Feedback Queue
    • 예시
      • Three queues:
        1. Q0 - time quantum 8 ms
        2. Q1 - time quantum 8 ms
        3. Q2 - FCFS
      • Scheduling
        1. new job Q0으로 들어감
        2. CPU 할당 시간 8ms 수행
        3. 할당시간 내 수행 끝내지 못하면 Q1으로 내려감
        4. Q1 할당시간 내 수행 못하면 Q2로 내려감
  7. Multiple-Processor Scheduling
    • CPU가 여러개인 경우
    • Homogeneous processor
      1. Queue에 한줄로 세워 각 프로세서가 알아서 꺼내가게 할 수 있음
      2. 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에 문제
    • Load sharing
      1. 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
      2. 별개의 큐 vs 공동 큐 사용
    • Symmetric Multiprocessing (SMP)
      1. 각 프로세서가 각자 알아서 스케줄링 결정
    • Asymmetric Multiprocessing
      1. 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
  8. Real-Time Scheduling
    1. Hard real-time systems
      • 정해진 시간 안에 반드시 끝내도록 스케줄링
    2. Soft real-time systems
      • 일반 프로세스에 비해 높은 우선순위를 갖도록 해야 함
  9. Thread Scheduling
    1. Local Scheduling
      • User level thread(OS가 쓰레드의 존재를 모르고 사용자 프로세스가 알아서 관리)의 경우 사용자 수준의 thread library에 의해 사용자 프로세스가 어떤 thread를 스케줄할지 결정
    2. Global Scheduling
      • Kernel level thread(OS가 쓰레드의 존재를 앎)의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

Algorithm Evaluation

  1. Queueing models
    • 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산
    • 도착율과 처리율
    • 이론적으로 많이 사용
  2. Implementatiln (구현) & Measurement (성능 측정)
    • 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
  3. Simulation(모의 실험)
    • 알고리즘을 모의 프로그램으로 작성 후 trace(input data)를 입력으로 하여 결과 비교

출처

http://www.kocw.net/home/search/kemView.do?kemId=1046323

profile
빈
이전 포스트

[운영체제] Process Management

0개의 댓글