Process Scheduling 1

OS 수업 정리

---

Types of process scheduling

• Long-term scheduling(job scheduler)

  어떤 프로그램을 프로세스로 올릴지 결정(처음 job을 메모리로 올림)

• Medium-term scheduling(swapper)

  디스크의 suspended queue와 메모리의 queued에서의 scheduling

• Short-term scheduling(CPU scheduler)

  메모리 상에 있는 프로세스 중 어떤 프로세스가 프로세서에 의해 실행될 것인지 결정

• I/O scheduling

  어떤 IO request부터 처리할 것인지 결정
  

selection function

다음에 실행될 프로세스를 선택하는 함수
max[W] 따위로 나타낼 수 있으며 들어갈 수 있는 인자들은 다음과 같다.

• W : 총 실행 시간
• e : execution에만 사용된 시간
• s : 총 service 시간

decision mode

preemptive, nonpreemptive 방식으로 나뉨

Scheduling Algorithms

FIFO

가장 기본적인 알고리즘으로, FCFS(first come first served)라고도 불림

• selection function : MAX[W]
• decision mode : 비선점
• 특징
  • 쉬운 구현, 낮은 복잡도, 적은 overhead 가능성, 긴 프로세스들을 잘 다룰 수 있음
  • 짧은 프로세스에서 반환시간이 상당히 길어질 수 있음(process간 fair하지 않다.), convoy effect(큰 프로세스들로 인해 작은 process들이 몰려있는 현상)

SPN(Shortest process next)

작은 프로세스부터 먼저 처리하는 알고리즘으로, SJF(Shrtest job first)라고도 불림

• selection function : min[s]
• decision mode : 비선점
• 특징
  • 짧은 process를 더 잘 다루기 위한 FIFO의 변형 방식(향상된 응답성)
  • long process들의 starvation 가능성(short process가 계속 들어오는 경우)
  • service time이 주어지지 않은 경우 이를 계산해야됨(미래에대한 예측이 필요)
    이것을 계산하기 위해 과거 수행했던 인스턴스들을 이용
    • 산술평균(계산의 overhead를 방지하기 위해 점화식 이용)
      
    • Exponential avg(locality를 반영하는 방식. 가장 최근에 있던 것에 가중치를 높게 설정)
      

Round-Robin

기본적으로 FIFO의 방식을 취하지만, 수행 시간에 제한(q)을 두는 방식

• selection function : constant
• decision mode : 선점
• 특징
  • FIFO보다 short job이 겪는 패널티를 낮춤
  • 모든 프로세스들은 $(n-1)q$ 시간보다 적게 기다림 // q == length of time quantum
  • q가 커지는 경우 FIFO와 유사해지고, 작아지는 경우 context switch overhead가 높아짐

SRT(Shortest remaining time)

SPN의 방식을 따르지만, preemptive. 응답성 측면에서는 optimal하다.

• selection function : min[s-e]
• decision mode : 선점
• 특징
  • SPN에 비해 높은 응답성
  • 매번 s-e를 계산하는 overhead
  • starvation이 일어날 수 있음

HRRN(Highest response ratio next)

응답 비율($R=(q+s)/s$)가 높은 것을 선택하는 방식. 서비스시간과 기다린 시간을 둘 다 고려하는 방식

• selection function : max[(q+s)/s]
• decision mode : 비선점
• 특징
  • starvation을 막을 수 있음(SRT보다 응답성이 떨어짐)
  • s를 계산해야함 overhead

---

여기까지가 중간고사 범위