[Operating System] 스케줄링

단기, 중기 ,장기 스케줄링

장기 스케줄링

• 프로세스가 cpu에 의해 실행될 수 있는 자격을 부여할지 말지를 결정

중기 스케줄링

• 프로세스 이미지 전부 혹은 일부가 주 메모리에 올라올 수 있는 자격을 부여할지 말지 결정

단기 스케줄링

• cpu에 의해 실행될 다음 번프로세스로 어떤 프로세스를 선택할지를 결정
• ready 상태를 많이 만들어서 cpu가 일하도록 만든다.

Workload assumptions

workload

• 일련의 프로세스들이 실행하는 상황
• 프로세스가 얼마나 cpu를 차지하는지

가정(비현실적)

• 각 작업은 동일한 시간동안 실행
• 모든 작업은 같은 시간에 도착
• 각 작업은 시작되면 완료될때까지 실행
• 모든 작업은 cpu만 사용(io 없다고 가정)
• 각 작업 실행 시간은 알려져 있다고 가정

평가 기준

1. Turn around time(반환 시간)
   1. 작업완료시간 - 작업 도착 시간
2. Fairness
   1. 공정성은 성능고 ㅏ상충되는 스케줄링 기준
3. Response time
   1. 시스템으로부터 첫번째 응답이 온 시간

Preemption vs Non Preemption

preemtion

• 다른 프로세스가 이미 차지하고있던 cpu를 빼앗는 행위

non preemtion

• 자신이 이미 cpu차지하고있으면 다른 프로세스에 넘겨주지 않는 것을 의미

종류

First In First Out (FIFO) / First Come First Service (FCFS)

• 큐를 이용한 non-preemption 방식이다. 대기시간 기준으로 스케줄링을 수행한다.
• 간단하고 용이하다.
• 단점 Convey effect(호위병 효과)
  • 실행시간이 짧은데 늦게들어왔다는 이유로 나중에 실행되어 평균반환,응답 시간이 길어짐
  • 늦게시작됐다는이유로 매우 긴시간 대기 - convoy effect

평균 반환 시간 (끝난 시간 - 처음 들어온 시간)

 

평균 응답 시간 (시작시간 - 들어온 시간)

Shortest Job First (SJF) / Shortest Process Next (SPN)

• non-preemption 방식이다.
• 먼저 들어온 순서보다는 task 의 소요시간을 기준으로 스케줄링한다.
• convoy effect 해결

평균 반환 시간

평균 응답 시간

• 평균 응답,반환시간이 줄어듬
• 단점으로 Starvation effect 가 발생함
• 짧은 시간이 소요되는 task들을 모두 기다리다가 무한정 기다리게 되는 상황 starvation effect

Shortest Time-to-Completion First (STCF) / Shortest Remaining Time (SRT)

• preemption이다.
• 이미 작업 수행하던 프로세스가 중단될 수 있다.
• 새로운 프로세스가 들어올 경우, 현재 수행중인 프로세스의 잔여 시간보다 새로들어온 프로세스의 수행시간이 짧을 경우에 preemption한다.
• 평균 반환시간

• 평균 응답 시간

• b가 끝난후 9time을 보면 cde 중에 선택을 해야한다. 각각의 time

Round Robin (RR) / Time Slicing

• preemption
• 일정시간마다 돌아가면서 공정하게 스케줄링 하려고한다.
• 들어온 순서대로 큐에 넣고 큐에서 pop을 해 새로운 프로세스를 선택한다.
• 수행이 끝났음에도 남아있는 작업이있으면 다시 큐에 삽입한다.
• 평균 반환시간

• 평균 응답 시간

Incorporating I /O

• I/O 를 고려하는 스케줄링이다. I/O 수행중에는 CPU를 사용하지 않는다. 해당기간 CPU를 휴식시키지 않고 다르프로세스를 실행한다.
• IO 요청이 있으면 IO 마칠때 까지 해당 프로세스는 SLEEP(BLOCK) 됨.
  • IO 마치면 인터럽트 : BLOCK → READY

스케줄 함수 호출 시기

1. TIME QUENTUM - 주어진시간 지났을 때
2. I/O 요청
3. 스스로 수행 종료 exit()

Scheduling 선택 함수 preemption 응답 시간 문맥 교환 비용 유리한 process Starvation

Scheduling	선택 함수	preemption	응답 시간	문맥 교환 비용	유리한 process	Starvation
FIFO/FCFS	max[w]	non-preemption	길 수 있음	최소	연산 많은 process	X
SJF/SPN	min[s]	non-preemption	연산 적을수록 짧음	커질 수 있음	짧은 process	O
STCF/SRT	min[s-e]	preemption	짧음	커질 수 있음	연산 적은 process	O
HRRN	max((w+s)/s)	non-preemption	짧음	커질 수 있음	다소 공정	X
RR	상수	preemption	연산 적을수록 짧음	최대	모두에게 공정	X