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

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