아래 내용들은 양희재 교수님의 운영체제 강의를 듣고 정리한 내용입니다.

1. Shortest-Job-First (1)

• Example: AWT = (3+16+9+0)/4 = 7 msec
  – cf. 10.25 msec (FCFS)

• Provably optimal

• Not realistic; prediction may be needed

• 프로세스 중 bust time가 가장 짧은 값을 먼저 올림.

• 근데 burst time을 예측 하기 힘듬, 이상적이으로 대기 시간이 가장 적지만 현실에서 불가능하다.
  (도착시간도 모두 다름)

2. Shortest-Job-First (2)

• Preemptive or Nonpreemtive
• cf. Shortest-Remaining-Time-First (최소잔여시간 우선)
• Example
  

Preemptive: AWT = (9+0+15+2)/4 = 26/4 = 6.5 msec

• 잔여시간이 작은거 부터, 우선순위로 계산함.
• preemtive 예제 : 자기보다 긴급한 프로세스가 오면 쫒겨남
• ready queue에서 대기하는 프로세스중 짧은 걸 올림.
• 하지만, 램에 도착한 시간이 다르니까, 램 동작시간 - 도착한시간 을 해줌

Nonpreemptive: 7.75 msec

3. Priority Scheduling (1)

• Priority : typically an integer number (우선순위의 정수가 주어진다.)
• Low number represents high priority in general (Unix/Linux)
• Example
  – AWT = 8.2 msec
  

• 모두 동시에 도착했다고 가정해보자

4. Priority Scheduling (2)

• 어떤 기준으로 우선순위를 정할까?

Priority

• Internal: time limit, memory requirement, i/o to CPU burst, …
• 내부적인 이유 : 타임 시간이 짧은것, 메모리 연산이 짧은것 우선, i/o가 길고 cpu가 짧은거면 cpu가 빨리 연산을 처리할수 있음으로 우선처리
• External: amount of funds being paid, political factors, …
• 외부적인 이유 : 정치적인 요인! 서버 컴퓨터를 예제로 든다면, 돈많이 내는 쪽에 우선순위를 내어줌, 입시나 게임 프로그램 중 입시쪽 프로그램에 더 비중을 많이 두게 설정 가능.(반대로도 가능햇으면..좋을텐데)
• Preemptive or Nonpreemptive(둘다 가능)

Problem

• Indefinite blocking: starvation (기아)
• 만약 우선순위가 낮을때 프로그램이 계속 들어온다면, 아무리 일찍들어왔어도 실행되지 못할 문제가 생길수 있다.
  – Solution: againg
• 대체 방법으로 레디큐에서 계속 기다리고 있으면 우선순위를 차츰 올려주는 형태로 해결해 줄 수 잇다. 이를 aging 이라 함.

Round-Robin (1)

• Time-sharing system (시분할/시공유 시스템)
  사진 과 같이 일정 Time quantum 마다 다른 프로세스를 불러옴
• Time quantum 시간양자 = time slice (10 ~ 100msec)
• Preemptive scheduling
• Example

• 4msec마다 시간마다, 프로세스가 바뀌는 예제
  – Time Quantum = 4msec
  – AWT = 17/3 = 5.66 msec
  

Round-Robin (2)

• Performance depends on the size of the time quantum
  – ∆ → ∞ FCFS : 타임권텀이 무한대면 fcfs랑 동일함.
  – ∆ → 0 Processor sharing (* context switching overhead) : 스위칭이 매우 빈번하게 일어나서 프로세스가 동일하게 일어나는거 처럼 보임.(문제는 pcb에 저장하고 불러오는과정이 너무 빈번하게 일어나서 cpu효율이 줄어듬)

• Example: Average turnaround time (ATT)
  – ATT = 11.0 msec (∆ = 1), 12.25 msec (∆ = 5)
  

• ∆ = 1, ∆ = 5 타임퀀텀 1 초일때는 11.0평균 대기시간을 가지고, 타임퀀텀 5일때는 12.25의 평균 대기시간을 가짐.

아래사진 p1 = 6임

average waiting time : average turarount time
대기 타임은 대기 시간을 계산 : 턴어라운드는 끝나는대 걸리는 시간