프로그래밍/운영체제(OS)

[KOCW] 반효경 운영체제 강의 정리 - 5. CPU Scheduling 1

병인 2022. 5. 12. 22:03

CPU and I/O Bursts in Program Execution

  • CPU만 연속적으로 쓰는 단계 : CPU burst
  • I/O를 실행하는 단계 : I/O burst

CPU-burst Time의 분포

  • 여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케줄링이 필요하다
    • Interactive job에게 적절한 response 제공 요망
    • CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

프로세스의 특성 분류

  • 프로세스는 그 특성에 따라 다음 두 가지로 나눔
    • I/O-bound process
      • CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
      • (many short CPU bursts)
    • CPU-bound process
      • 계산 위주의 job
      • (few very long CPU bursts.)

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 완료 후 인터럽트)
    4. Terminate
  • 1, 4에서의 스케줄링은 nonpreemptive(=강제로 빼앗지 않고 자진 반납)
  • 다른 스케줄링은 preemptive(=강제로 빼앗음)

Scheduling Criteria

  • 성능 척도(Performance Index)
    • 시스템 입장
      • CPU utilization(이용률)
        • CPU가 일한 시간 / 전체 시간
        • CPU를 가능한 바쁘게 일을 시켜라
      • Throughput(처리량)
        • 주어진 시간 동안 작업을 완료한 양
- 프로세스 입장
    - Turnaround time(소요시간, 반환시간)
        - Ready Queue에서 기다린 시간 + Running Time + (선점형 스케줄링에서 CPU를 뺏겨 대기한 시간)
    - Waiting time(대기 시간)
        - Ready Queue에서 기다린 시간 + (선점형 스케줄링에서 CPU를 뺏겨 대기한 시간)
    - Response time(응답 시간)
        - Ready Queue에 들어와서 처음으로 CPU를 얻기까지의 시간

Scheduling Algorithms

FCFS (First-Come Fist-Served)

  • 프로세스 도착 순서대로 처리한다.
  • 비선점형 스케줄링

  • Waiting Time : P1 = 0, P2 = 24, P3 = 27
  • Average Waiting Time = (0 + 24 + 27) / 3 = 17

  • Waiting Time : P1 = 6, P2 = 0, P3 = 3
  • Average Waiting Time = (6 + 0 + 3) / 3 = 3
  • Convoy effect : 짧은 프로세스가 긴 프로세스 뒤에 있는 현상

SJF (Shortest-Job-First)

  • 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용
  • CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
  • Two schemes
    • Nonpreemptive
      • 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(preemption) 당하지 않음
    • Preemptive
      • 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
      • Shortest-Remaining-Time-First (SRTF)이라고도 부른다
  • SJF는 최적이다.
    • 주어진 프로세스들에 대해 minimum average waiting time을 보장

  • 단점
    • Starvation(기아 현상)
    • CPU Burst Time의 예측이 불가
      • 추적(estimate)만 가능
      • 과거의 CPU burst time을 이용해서 추정
        • exponenitial Averaging

Priority Scheduling

  • 우선순위가 높은 프로세스에게 CPU 할당
  • SFJ는 일종의 Priority Scheduling이다
    • Priority = CPU Burst Time
  • 문제
    • Startvation(기아 현상) : 우선순위가 낮은 프로세스는 영원히 프로세스를 얻지 못할 수 있다.
  • 해결
    • Aging : 대기하는 프로세스가 시간이 지날수록 우선순위를 높여줌

Round Robin(RR)

  • 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐(일반적으로는 10~100ms)
  • 할당 시간이 지나면 프로세스는 선점(preempted)당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다
  • n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다
    • 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
  • 성능
    • q가 클 경우 ==> FCFS
    • q가 적을 경우 ==> context switch 오버헤드가 커진다.

q가 20일 경우

  • 일반적으로 SJF보다 average turnaround time이 길지만 response time은 더 짧다.

 

 

출처 : http://www.kocw.net/home/cview.do?lid=5488703b25305c37

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