[운영체제/OS] L17. CPU Scheduling (1)

CPU Scheduling Goals

 

CPU scheduler must decide:

• 프로세스 실행 시간
• 프로세스들이 실행될 순서

 

User-oriented schdeuling policy goals

: 유저관점에서 스케쥴링의 평가(기준)

• 평균 반응시간 (프로세스 실행시키고 첫번째반응이 일어날 때까지 걸리는 시간)을 최소화한다. 반면 interactive한 유저가 적절한 응답을 받는 수를 최대화한다.
• trunaround time(프로세스 시작 ~ 종료까지, execution time + waiting time) 최소화함
• 평균 응답 시간의 편차 최소화
  • 예측가능성은 중요함 ..
  • 프로세스는 어떤 시스템에 load 되었는지 상관없이 항상 (대략적으로) 같은 시간동안 실행되어야한다.

 

System-oriented schdeuling policy goals

: 시스템관점에서의 스케쥴링의 평가

• Throughput(단위시간동안 해치우는 일의 양)이 최대
• 프로세스 활용률(CPU 사용시간 백분율) 극대화 - 최대한 많이 활용되도록

Q. CPU활용도 → 프로세스 많이 실행할수록 값이 올라가나요 ?
A. ㅇㅇ 참고로 스케쥴러가 중간중간 돌아가는 시간은 빼야한다 (유저 프로세서가동작할 때 필요한 걸 CPU 활용도라고 함 )

 

Other system-oriented scheduling policy goal

: 정서적인 것들

• Fairness : OS나 user로부터 가이드가 없는 경우 프로세스는 동일하게 취급되어야하며 어떤 프로세스도 (서비스가 무한히 거부되는)기아상태에 빠지면 안됨 ~~ !
• Balance resources → 한쪽에 부하되는 리소스를 쓰지 않음 !! : 시스템의 모든 리소스(CPU, 메모리, 디스크, I/O)를 사용 중으로 유지
• 부하가 높은 리소스를 충분히 사용하지 않는 프로세스를 선호

---

** 스케쥴링의 종류와 평가 (위에서 배운걸로 하나씩 배우고 평가해보자 )

 

출처 : Topcit essencial

이건 시험준비 자료에서 본건데.. 같이 보면 좋을 것 같아서 넣어두었다 ! 

 

FCFS (Non-preemptive: run till done !)

• Non-preemptive (비선정)
• Response time - 프로세스 실행 시간에 큰 차이가 있다면 느리다
  • long → short 순서면 short엄청 기다려야함
  • CPU bound 프로세스 → I/O bound 프로세스 순서면 ‘convoy effect’ 발생 ** convoy effect : CPU 사용시간이 긴 프로세스에 의해 사용시간이 짧은 프로세스들이 오래 기다리는 현상 → 엄마 CPU보다 새끼 CPU에게 먼저 일 시키기 !!
• Throughput - not emphasized
• Fairness - 짧은 프로세스와 I/O bound 프로세스는 패널티가 있음
• Starvation - 스택 순서대로 건너뛰지 않으니 일어나지 않음
• Overhead - minimal(스케쥴러가 머리 안씀~~ )

📄 ** Preemptive vs Non-Preemptive scheduling

Non-preemptive scheduling - 스케줄러는 이때만 실행 !
1. 프로세스가 러닝에서 블락상태로 전이될 때(이때 CPU는 빈 상태)
2. 프로세스가 종료되었을 때

Preemptive schedular - 스케쥴러는 거의 언제나 실행 !
이럴때도 실행됨
- 프로세스가 생성될 때
- 블락된 프로세스가 레디상태가 될 때
- 타이머 인터럽트가 발생했을 때
오버헤드는 증가하지만, 긴 프로세스가 CPU를 독점하지 못하게 한다!
system call(ex. 파일읽기)을 처리하는 동안 or inconsistent 상태에서 OS 커널을 선점해서는 안됨 !

❎  사용자 프로세스 간에 공유된 데이터를 inconsistent 상태로 유지할 수 있음 !
**커널은 세마포 처리를 안한다 . (CPU 하나일때 )

 

Round-Robin

뺑뺑이 돌리겠다! , FCFS 성질 남아있음

• Policy
  • fixed time slice(타임 퀀텀)을 정의함
  • 레디 큐의 첫번째에서 프로세스를 정한다
  • 최대한 한 타임슬라이스동안 돌려주고, 그 사이 프로세스가 완수되지 않으면 레디 큐의 마지막으로 넣어줌
  • 타임 슬라이스가 끝나기 전, 프로세스가 끝나거나 블락된다면, 레디큐의 첫번째 프로세스를 고르고 최대한 한 타임슬라이스 돌려 … (반복)
  • 이걸 구현하기를 주기적인 interval타이머
• Implementing using :
  • 주기적인 간격으로 인터럽트하는 Hardware timer
  • FIFO 레디 큐 (tail에 넣고, head에서 빼고)

Round-Robin Example

Ex1 → 거꾸로 돌리면 Ex 2

EX 1 - EX 2 

 

평가 ㄱㄱ

Round-Robin Evaluation

• Preemtive(타임퀀텀주고 짤라)
• Responsetime - 짧은 프로세스에게 유리함
  • Long 프로세스는 다른 시간 슬라이스를 위해 n*q 타임유닛을 기다려야할수도 ..
    • n = 다른 프로세스의 수 & q = 타임 슬라이스의 길이
• Throughput - time slice에 달려있음
  • (타임 퀀텀) 넘 작아 : context switches가 너무 많아 = os overhead가 너무 커
  • 넘 커 : FCFS랑 비슷해
• Fairness : I/O bound 프로세스(full time slice를 사용하지 않는)에 패널티
• Starvation - not possible : 번갈아가며 돌려서 없음
• Overhead - 낮아

---

Shortest-Job-First(SJF)

• Policy :
  • 다음번 CPU burst가 가장 작은 프로세스를 선택하고 이 프로세스를 non-preemptive하게 실행시킨다 ( termination되거나 blocking될 때 까지)
  • 동점인 경우, FCFS을 사용하여 동점 해제
• Difficulty : 다음번 CPU burst의 길이를 결정하는 것이 어려움 ..
  • Approximation : 과거 프로세스의 수행과 예측에 기반하여 런타임 수행시간 (length)의 길이를 예측

SJF Example

• average waiting time

SJF Evaluation

• Non-preemptive
• Response time - 짧은 프로세스에게는 좋음
  • 긴 프로세스는 많은 짧은 프로세스가 끝날 때까지 기다려야한다
  • Provably optimal - 주어진 프로세스 set에서평균 대기시간을 최소화함
• Throughput - high
• Fairness - 긴 프로세스에게 패널티있음
• Starvation - 긴 프로세스에 있을 수 있음
• Overhead - 높음(CPU burst time을 측정하고 기록함)

 

---

[참고 및 출처]

 

한국항공대학교 「컴퓨터 운영체제」 강의 자료