5-1. CPU Scheduling 1

5-1. CPU Scheduling 1

CPU and I/O Bursts in Program Execution, CPU-burst Time의 분포, CPU Scheduler & Dispatcher, Scheduling Algorithms, Scheduling Criteria, FCFS(First- Come First-Served), SJF(Shortest-Job-First), Example of Non-Preemptive SJF, Example of Preemptive SJF, 다음 CPU Burst Time의 예측, Exponential Averaging, Priority Scheduling, Round Robin(RR), Example: RR with Time Quantum = 20, Turmaround Time Varies With Time Quantum

 

CPU Scheduling

1. 비선점형 (일단 줬으면, 강제로 뺏지않는 경우)
2. 선점형 (강제로 빼았는 경우) > timer 이용!

Scheduling Criteria (성능 척도)

1. 시스템 입장에서의 성능 척도 (CPU하나로 최대한 많은 일을 하면 좋은 거!)
   1. CPU utilization(이용률) : 전체 시간 중 CPU가 놀지않고 일한 비율 (CPU는 가능한 바쁘게 일을 시켜라)
   2. throughput(처리량) : 주어진 시간 동안에 몇개의 일을 처리했는가
2. 프로그램 입장에서의 성능 척도 (CPU를 빨리 얻어서 빨리 끝나면 좋은 거!)
   1. Turnaround time(소요시간, 반환시간) : CPU를 쓰러 들어와서 다 쓰고 나갈때까지 걸린 시간
   2. Wating time(대기 시간) : CPU를 쓰고자 하더라도 하나밖에 없기때문에 ready queue에서 기다리는 시간
   3. Response time(응답 시간) : Ready queue에 들어와서 처음으로 CPU를 얻기까지 걸린 시간
   정리를 하자면, Ready queue에 들어와서 기다리는것은 wating time, 기다렸다가 얻기까지는 Response time, 기다렸다가 얻었다가 쓰고 나가는것까지 통틀어 하는 것은 Turnaround time

Scheduling Algorithms

• FCFS (First-Come First-Served) : 먼저 온 순서대로 처리 (비선점형 스케쥴링 (일단얻으면 끝날때까지처리)) (그렇게 효율적인진 않음 )
  • Convoy effect : short process behind long process (앞에 긴 프로세스 때매 서비스를 오랫동안 못받는.... 큐에서 오래 기다리는 !!!!)
• SJF(Shortest-Job-First) : CPU를 짧게 쓰는 프로그램한테 CPU를 먼저주는 알고리즘
  • Two schemes:
    • Nonpreemptive : 빼앗기지 않고 다 끝낸 다음에 가장 짧은 job이 CPU 를 얻음
    • preemptive : 짧은 job이 CPU 점유하고 있는 와중에 더 짧은 job이 오면 CPU 를 빼앗김.
  • Shortest-Remaining-Time-First라고도 불림 (CPU를 줬다가도 더 짧은 친구가 도착하면 뺐을 수 가 있기에 )
  • SJF is optimal : premmptive 방식!
  • 2가지 문제점!!
    1. Starvation(기아현상) : 극단적으로 CPU사용시간이 짧은 것을 선호함. CPU사용시간이 긴 프로세스는 영원히 서비스를 못 받을 수 있음
    2. CPU사용 시간을 미리 알 수 없다는게 문제
• Priority Scheduling (우선순위 스케쥴링) : 우선순위가 제일 높은 CPU에게 주겠다
  • Two schemes:
    • Nonpreemptive : 일단 줬으면, 더 높은 애가 도착해도 기다려!
    • preemptive : 우선순위가 높은 프로세스한테 CPU줬는데, 더 높은 우선순위 오면 빼앗어서 줌
  • 우선순위는 정수로 표현되는데, 숫자가 작을수록 우선순위가 높은것!
  • Problem!
    • Starvation(기아현상)
  • Solution!
    • Aging(노화) : 아무리 우선순위가 낮은 것이라도 시간이 지나면 우선순위를 조금씩 높여주자
• Round Robin (RR)
  • 현대적으로 라운드로빈에 기반함
  • CPU를 줄때는 할당시간을 셋팅해서 주고, 할당시간이 끝나면 타이머 인터럽트가 걸려서 CPU를 빼앗기고, (선점형)!!
  • 좋은점 : 응답시간이 빨라짐
  • n개의 프로세스가 ready queue에 있고, 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다. 즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.