Scheduling
Processes(P1, P2,…..,Pn)을 위해 CPU가 일을 해야하는데, 프로세스들을 어떻게 병렬적으로, 순차적으로 처리할건지 스케쥴을 짜줘야한다. 목표는 CPU가 멈춰있는 시간이 최소화되도록 하는것
→ Scheduling Algorithm의 탄생 및 발전의 이유
장점
•
프로세서(CPU) 이용률 증가
•
프로세서(CPU) 처리율 증가
•
작업 응답시간 최소화
스케쥴링(of CPU)
•
어느 시점에, 어느 프로세스에 자원을 할당할 것인가를 결정
•
프로세서 스케쥴링
•
인터럽트 처리, 오류 처리, 시스템 콜 → 스케쥴링 불필요
목적
1.
골고루 CPU를 쓰게 하겠다
2.
CPU의 활용도를 높이겠다
•
자원 할당 공정성 보장
•
단위시간당 처리량 최대화
•
적절한 응답시간 보장
•
오버헤드 최소화
•
실행 대기 방지
•
우선순위
•
Preemptive(선점) VS Non-Preemptive(비선점)
Preemptive
•
우선순위 높은 프로세스가 선점
•
CPU 활용도 효율적
•
대기시간 및 응답시간 감소
•
유연
•
특정 시간동안 CPU 할당
•
오버헤드 존재
◦
프로세스가 변경될때, 교체되는 프로세스에 대한 정보들(PCB의 교체라던지)에 의해 필연적인 준비시간이 발생
Non-Preemptive
•
실행중인 프로세스 종료시까지 대기 필요
•
CPU 활용도 비효율적
◦
CPU연산이 필요한 경우말고도,
I/O burst라던지 다른 연산을 하는 경우도 많은데도 다른 프로세스가 진행되지 못 함
•
대기시간 및 응답시간 증가
◦
P2는 P1이 끝날때까지 기다려야함
•
엄격
•
프로세스 종료or대기 상태 될때까지 프로세스에 CPU 할당
•
오버헤드 X
•
스케쥴링을 위한 비용 감소
•
높은 처리량
•
간단함
Dispatcher
CPU의 통제를 단기 스케쥴러에 의해 선택된 프로세스에게 넘깁니다(by DIspatcher module)
통제권 전달에는 다음 과정을 포함합니다
•
Context Switching
•
UserMode로 Switch
•
프로그램을 재시작하기 위해
프로그램 안의 적절한 위치로 jumping
Scheduling Criteria
1.
CPU 활용
a.
CPU clock frequency
b.
한번의 사이클 당 여러개의 명령어 VS 한개의 명령어가 여러번의 사이클
2.
처리량
a.
단위시간당 완료된 프로세스 개수
b.
단위시간당 여러개의 프로세스 VS 한 프로세스당 여러개의 단위시간
3.
Turnaround Time
a.
프로세스 제출시간과 완료시간 간격
i.
Queue wait, CPU execution, I/O time
4.
Waiting Time
a.
큐 대기 시간
5.
Response Time
a.
Minimum response time
프로세스 제출 후 첫번째 응답이 나온느 시간 간격
6.
프로세스 속성
a.
어느 것을 먼저 고려할 것인가? : 입출력 위주 VS 연산 위주
b.
입출력 위주 : 기억장치 / 입출력장치와의 데이터 이동에서의 시간소요
7.
시스템 속성
a.
일괄처리(처리량), 대화형(응답시간)
8.
프로세스 활용 목적
a.
응용프로그램의 성격
총 처리 시간 VS 응답시간
시스템 입장에서의 성능
•
CPU 이용률
•
처리량
사용자 입장에서의 성능
•
대기시간
•
응답시간
•
총 처리시간
응답시간
프로세스가 도착한 후,
처음으로 실행되는 시간
EX) 2초에 도착하여 6초에 처음 실행이 시작되는 경우 → 응답시간 == 4초
Turnaround / Wait Time
Throughput
FCFS Scheduling
Non-Preemptive
Simplest Scheduling Algorithm
Context Switching이 필요없는 경우에 가장 적합한 스케쥴링 방식(두 활동 프로그램에게 할당할 메모리가 충분하지 않은 경우)
Convoy Effect란,
긴 프로세스가 짧은 프로세스보다 순위가 높은 경우, 대기시간이 너무 길어지는 효과를 말합니다
FCFS Orders
•
Best Turnaround Time → CPU 버스트가 가장 짧은 것을 먼저 실행할때
•
Worst Turnaround Time → CPU 버스트가 가장 긴 것을 먼저 실행할때