- 스케줄링 대상은 Ready Queue에 있는 프로세스들
- 대부분의 OS에서는 우선순위 알고리즘이나 Round Robin 혼합해서 사용한다고 함
비선점형 스케줄링
: 어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나(State: terminated) 입출력 요구가 발생하여 자발적으로 중지(State: waiting(blocked))될 때까지 계속 실행
- 순서대로 처리되어 공정성 있음
- 응답 시간을 예상 가능.
- 선점 방식보다 스케줄러 호출 빈도가 낮고 context switch로 인한 오버헤드가 적음
- 사용자 개입 없이 순서대로 처리해야 할 곳에 적절
- CPU 사용시간이 긴 하나의 프로세스가 있을 때 여러 프로세스가 기다리게 되고, 처리율이 떨어질 수 있음.
FCFS(First Come First Served)
- CPU 사용시간 긴 프로세스가 전체 처리율을 낮출 수 있음
SJF(Shortest Job First)
- CPU 시간 짧은 프로세스 선 할당
- starvation: 프로세스가 긴 프로세스는 영원히 CPU 할당 못 받음
선점형 스케줄링
: 어떤 프로세스가 CPU를 할당받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있다.
- 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있음
- 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합
- 긴급한 프로세스 제어 가능
- OS가 CPU를 선점하고 있다가 프로세스의 요청이 있을 때 할당
RR(Round Robin) - 실제 사용
- 각 프로세스를 10ms~ 100ms의 시간 단위로 분할해 돌아가면서 수행하는 알고리즘. 시간이 지나면 선점당하고 ready queue의 가장 뒤로 간다. 이 알고리즘은 FCFS를 시분할 선점 형태로 변형한 기법 이라고 볼 수 있다.
- 대화형 운영체제에 적합한데 그 이유는, 실제로 대화형 운영체제에서는 I/O 작업이 CPU 시간보다 길기 때문이다. IO작업이 빈번하므로 CPU를 빠르게 교체하며 유휴시간을 효율적으로 사용할 수 있다. 현대 운영체제는 대부분 대화형 운영체제이기 때문에 이 알고리즘을 채택
- CPU 사용시간이 랜덤한 프로세스들에 효율적
- 프로세스 교체 시 context save
대화형 운영체제(시분할 운영체제)
- 사용자의 입력(키보드, 마우스 등 입력장치)에 대해 컴퓨터가 결과를 출력(모니터)해준다. 이러한 방식으로 컴퓨터 시스템과 대화하듯 작업을 처리.
- 대화형이기 때문에 커널에 의한 I/O 작업이 CPU 시간보다 길다.
- 리눅스, 윈도우, MS-DOS 등 대부분의 현대 운영체제
Priority Scheduling
- 우선순위 높은 프로세스에게 우선 할당(우선순위 정수로 표현)
- 비선점형으로 구성할 수도 있음.
다단계 큐 스케줄링
- Ready Queue를 여러개의 큐로 분리
- 큐 사이에 우선순위를 부여
- 각 큐는 각각 다른 스케줄링 알고리즘 가질 수 있음
- 다단계 피드백 큐 스케줄링: 프로세스들이 큐를 갈아 탈 수도 있음
SRTF(Shortest Remaining Time First)
- 새로운 프로세스 도착할 때마다 새로운 스케줄링 이루어짐 - 따라서 CPU 사용시간을 측정 불가
- SJF를 선점형으로 바꾼 것
- 여전히 starvation
Reference)
https://ko.wikipedia.org/wiki/%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81_(%EC%BB%B4%ED%93%A8%ED%8C%85)
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS#cpu-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%9F%AC