[운영체제] Ch2.4. Scheduling

• Ready 상태에 있는 프로세스 중 누구에게 CPU를 할당할것인가에 대한 정책
• Batch 시스템이냐 - TimeSharing 시스템이냐에 따라 다름
• Context Switching Overhead를 고려해야한다.
  • user mode => kernel mode 모드 스위칭
  • 현재의 상태정보 저장
  • 주소공간 (memory map) 정보 저장
  • 다음에 실행할 프로세스 선택 (스케쥴링)
  • PCB에 저장되어 있는 데이터 리로딩
  등, 꽤 많은 일이 context switch 사이에 일어난다!!

Process Behavior

• CPU를 사용하는 패턴에 따라
  • a) Compute Bound : CPU 연산의 비중이 높은 프로세스
  • b) I/O Bound : I/O 연산의 비중이 높은 프로세스
• CPU의 성능에 따라 상대적으로 결정된다.

 

When to Schedule

• 새 프로세스가 생성된 경우 : fork()로 새 프로세스가 ready queue에 들어갔을 때
• 프로세스가 exit한 경우
• 프로세스가 block된 경우
• I/O Interrupt가 발생한 경우

Clock Interrupt

OS가 interrupt를 주기적으로 걸어서,

• 리소스 관리하는 루틴을 계속 수행시킨다.
• 한 프로세스가 CPU Quantum을 초과하는지 계속 감지한다
• 해당 프로세스가 Quantum을 초과하면 unschedule (압수)

Two categories of scheduling

• NonPreemptive : 알아서 끝낼때까지 CPU를 계속 쓰게 해주는 것
  주로 Batch System에서 사용
• Preemptive : 프로세스마다 CPU 점유 시간 (CPU Quantum)에 제한을 건다.
  Clock Interrupt를 통해 확인한다.
  주로 Timesharing System에서 사용

 

Three Environments for Scheduling

1. Batch System (일괄 처리)

• job을 operator에게 넘겨주고 일이 끝나면 결과값을 받는 것 (상호작용 x)
• Non-preemptive - Context Switch Overhead의 빈도를 줄인다.
• preemptive 알고리즘을 사용한다면, Quantum의 크기를 매우 크게 잡는다.
• Troughput (단위 시간당 처리하는 job의 수)
• Turnaround Time (operator에게 job을 주고 결과를 받기까지의 소요 시간)
• CPU Utilization : CPU가 항상 바쁘게 움직여야 함

2. Interactive System

• 무조건 preemptive 알고리즘 사용 (Time sharing)
• 한 프로세스가 Quantum을 초과하면 unschedule
• Response Time : 요청에 대한 응답 시간
• Proportionality : 10개에 10초면, 100개는 100초

3. Real time System

• 프로세스가 처리되는 Deadline을 맞춰야 함
• 얼마동안 써야하냐 - 같은 스케쥴이 다 정해져 있기 때문에 preemptive-nonpreemptive가 중요하지 않음. 상관없다.
• Meeting Dealines : 데드라인을 맞춰야함
• Predictability : 일정 수준 이상의 서비스 품질이 유지되어야 함 (스트리밍 같은거)

 

Scheduling 스케쥴링

• Time Scale의 크기에 따라
  • Long Term : 몇개까지 Ready 상태로 둘 수 있게 할것인가 (너무 많이 넣어도 메모리 문제)
  • Short Term : Ready 상태에 있는 프로세스 중 CPU를 할당할 프로세스를 선정한다.
• Starvation : Ready queue에 있는 어떤 프로세스가 스케쥴링 알고리즘에 따라 선택을 못받고 계속 뒤로 밀려나는 것.

1. FCFS

• First come first served
• create된 순서대로 프로세스를 처리하는 방식 (선입선출)
• 대체로 non-preemptive (context switch 오버헤드 적음)
• Starvation이 없다. 언젠가 무조건 처리되니까.
• 문제점
  • 평균 Turnaround Time이 커질 가능성이 있음

 

2. SJF

• Shortest Job First
• CPU를 제일 조금 쓸 것 같은 애를 먼저 처리하는 것

• 문제점
  • 실제로는 CPU Burst Time을 알 수 없다.
  • 모든 Job들이 동시에 요청된 경우에만 최적의 성능을 발휘한다.
• 문제 예시
  • A, B, C, D, E = 2, 4, 1, 1, 1 (CPU Burst Time)
  • A,B는 0초에 / C,D,E는 3초에 동시 요청됨

 

3. SRTN

• Shortest Remain Time Next
• SJF의 preemptive 버전
• 매 클락마다 주기적으로 멈추고 스케쥴링을 다시 한다.
• 현재 필요한 CPU Burst 중 가장 작은 걸 찾아서, 그 job을 먼저 처리한다.
• 새로 들어온 짧은 job이 혜택을 많이 봄

 

4. Round Robin

• Ready Queue 맨 앞에 있는 애부터 수행, 정해진 Quantum을 넘어가면 맨 뒤로 보내버린다.
• Preemptive (퀀텀 있으면 preemptive인것)
• Starvation이 없다 (기본적으로 FCFS이기 때문에)
• 보통 원형 큐로 구현 (포인터만 옮기면 바로 큐 맨뒤로 옮기는게 되니깐)
• 문제점 : 적당한 Quantum 값을 찾기 힘들다
  • Quantum의 값이 작으면 : Context Switch가 자주 일어나 overhead 커짐
  • Quantum의 값이 크면 : Response Time이 커진다 (결국 그냥 FCFS와 비슷해지니까)

5. Priority Scheduling

• job들에게 우선순위를 부여함 (같은 애들끼리는 FCFS나 RR 같은 다른 알고리즘 사용)
• Static Assignment : 정적으로 우선순위 부여
• Dynamic Assignment : 동적으로
  • I/O Bound Process에게 더 높은 우선순위를 준다 (보통은 Quantum을 다 쓰기 전에 끝내니까)
  • 우선순위 : 1/𝑓 (𝑓 : 해당 프로세스가 quantum 중 사용한 시간의 비율)
    Ex. q:10 중에 2만큼만 사용하고 I/O 요청으로 인해서 block 되였다면 : 1/ (2/10) = 5
• 문제점 : 역시 Starvation
  • 오래 기다릴 수록 우선순위를 증가시켜준다
  • 같은 우선순위 애들끼리는 RR (아래 예시)

6. Multiple Queues

• 여러 큐가 있고, 각 큐마다 다른 알고리즘을 적용
• 프로세스들은 큐 사이를 옮겨다닐 수 있음
• 위 Priority Scheduling도 이것 중 하나인가???
• Multi Level Feedback Queues (MLFQ)
  • 각 큐마다 다른 job type을 가짐 (Batch냐.. Interactive냐.. CPUbound..)
  • 그에 맞는 Quantum을 정해두고 맞는 큐로 찾아 들어가는 구조인듯 (Feedback을 통해)

7. Guaranteed Scheduling

• ratio (실제 CPU 사용한 시간 / 할당된 시간)가 작은 job 먼저
• 다른 애들과 비율이 똑같아질때까지 계속 제일 작은거 실행하다가.. 계속 계산해가며 갱신

8. Lottery Scheduling

• Job마다 티켓을 주고, 스케쥴러가 랜덤하게 티켓을 뽑는다. 해당 번호를 갖고있는놈이 수행됨
• 각 프로세스마다 갖고 있는 티켓의 개수가 다르겠지 (확률게임)
• Highly Response : 새로 큐에 들어온 프로세스도 바로 CPU를 받을 가능성이 있음
• Ticket Exchanging : 동일한 Task를 수행하는 애들끼리 티켓을 주고 받을 수 있음
• Propotional Scheduling : 특정 비율로 할당하는 경우에 적합 (Frame Rate이 10, 20, 25인 3개의 Job이 있는 경우, 전체 Ticket 55개를 10개, 20개, 25개로 분배하면 된다)

9. Fairshare Scheduling

• Process 단위로 CPU를 할당하는 것이 아닌, Process를 구동하는 User들에게 공평하게 CPU를 할당하는 것이다.

 

Real-Time Systems

Real time 시스템에서는 Response, Turnaround Time보다는 데드라인이 중요하다.

• Periodic : Event가 Regular하게 발생되는 경우를 의미한다. (Event란, CPU를 할당하여 처리해야 하는 일을 의미한다.)
• Aperiodic : Event가 불규칙적으로 발생되는 경우를 의미한다. Dead-Line을 충족시키기 어렵다.