단기, 중기 ,장기 스케줄링
장기 스케줄링
- 프로세스가 cpu에 의해 실행될 수 있는 자격을 부여할지 말지를 결정
중기 스케줄링
- 프로세스 이미지 전부 혹은 일부가 주 메모리에 올라올 수 있는 자격을 부여할지 말지 결정
단기 스케줄링
- cpu에 의해 실행될 다음 번프로세스로 어떤 프로세스를 선택할지를 결정
- ready 상태를 많이 만들어서 cpu가 일하도록 만든다.
Workload assumptions
workload
- 일련의 프로세스들이 실행하는 상황
- 프로세스가 얼마나 cpu를 차지하는지
가정(비현실적)
- 각 작업은 동일한 시간동안 실행
- 모든 작업은 같은 시간에 도착
- 각 작업은 시작되면 완료될때까지 실행
- 모든 작업은 cpu만 사용(io 없다고 가정)
- 각 작업 실행 시간은 알려져 있다고 가정
평가 기준
- Turn around time(반환 시간)
- 작업완료시간 - 작업 도착 시간
- Fairness
- 공정성은 성능고 ㅏ상충되는 스케줄링 기준
- Response time
- 시스템으로부터 첫번째 응답이 온 시간
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
스케줄 함수 호출 시기
- TIME QUENTUM - 주어진시간 지났을 때
- I/O 요청
- 스스로 수행 종료 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 |
'Operating System' 카테고리의 다른 글
[Operating System] 공평한 스케줄러 (0) | 2022.12.28 |
---|---|
[Operating System] MLFQ Multi-level Feedback Queue Scheduling (2) | 2022.12.28 |
[Operating System] 프로세스 실행 (0) | 2022.12.19 |
[Operating System] 프로세스 (0) | 2022.12.19 |
[Operating System] 운영체제란? (0) | 2022.12.19 |