프로세스 스케줄러란?
💡 한정적인 메모리를 여러 프로세스가 효율적으로 사용할 수 있도록 다음 실행 시간에 실행할 수 있는 프로세스 중에 하나를 선택하는 역할
스케줄링 큐 Queue
프로세스가 실행될때 스케쥴링 큐 방식으로 실행되는데 이게 뭐냐면 실행 될 프로세스가 여러 개 있으면 하나만 실행되고 나머지는 CPU가 자유로워질 때까지 대기하는 것으로 선입선출의 방식을 따릅니다.
큐의 종류
- 작업 큐(Job Queue) - 메모리 할당을 대기 중인 프로세스들
- 준비 큐(Ready Queue) - CPU 할당을 대기 중인 프로세스들
- 장치 큐(Device Queue) - 입출력 자이 할당을 대기 중인 프로세스들
실행 방식
- 프로세스가 시스템에 들어가면 이들은 잡 큐에 넣어져. 잡큐는 시스템에서 모든 프로세스들이 존재하는 곳입니다.
- 메인메모리에 거주하는 프로세스들은 레디 큐라고 불리우는 리스트에서 실행되기를 기다리고 대기
- 큐는 보통 링크드 리스트로 저장되고 레디 헤더는 포인터를 포함하는데, 이 포인터는 리스트에서 PCB의 처음과 끝을 가르킵니다.
- 각 PCB는 포인터 필드를 포함하고 있는데, 이는 레디 큐에 있는 다음 PCB를 가르킵니다.
여기서 PCB란 프로세스 제어 블록(Process Control Block)으로 프로세스에 대한 모든 정보가 모여있습니다. 특히 PCB안에는 프로세스의 상태, 프로세스 번호(PID), 해당 프로세스의 program counter(pc), register값, MMU정보, CPU점유 시간 등이 포함되어 있습니다.
CPU는 한 프로세스가 종료될 때까지 수행하는 것이 아니라 여러 프로세스를 중간 중간에 바꿔가면서 수행합니다. 따라서 CPU는 수행중인 프로세스를 나갈 때, 이 프로세스의 정보를 어딘가에 저장하고 있어야 다음에 이 프로세스를 수행할 때 이전에 수행한 그 다음부터 이어서 작업할 수 있습니다.
이러한 정보를 저장하는 곳이 PCB.
위 그림처럼 프로세스들은 스케쥴러 알고리즘에 따라 여러 queue 사이를 옮겨다니며 작업을 수행
스케줄링 종류
스케줄링 종류는 크게 선점과 비선점으로 나누어집니다.
선점 스케줄링(Preemptive Scheduling)
운영체제의 판단에 따라 현재 실행 중인 프로세스를 강제로 중단시키고, CPU 스케쥴리을 수행
장점
- 우선순위가 높은 프로세스에 빠른 응답시간 보장
단점
- 프로세스간 문맥교환이 자주 발생
- Starvation 발생 가능
!기아 현상(Starvation)
계속해서 우선순위가 높은 프로세스(burst time이 짧은)가 먼저 실행되어 먼저 도착했어도 우선순위가 낮은 프로세스(burst time이 긴)가 게속해서 CPU를 할당받지 못하는 현상
선점인 녀석들 - SRT, RR, Priority Scheduling, Multilevel Scheduling
비선점 스케줄링(Nonpreemptive Scheduling)
현재 실행 중인 프로세스가 자발적으로 CPU 사용을 중단하는 경우에만 CPU 스케줄링을 수행하는 방법입니다. 실행중인 프로세스가 종료되거나(Running→Terminated) 외부 장치 입출력 요청 시(Running→Waiting) 프로세스가 스스로 CPU 사용을 중단하고, 자신의 상태를 변경합니다.
장점
- 모든 프로세스에 대한 공정한 처리
- 문맥교환으로 인한 오버헤드가 적음
단점
- burst time이 긴 프로세스에 의해 burst time이 짧은 프로세스가 기다리는 현상이 생길 수 있음
비선점인 녀석들 - FIFO, SJF
스케줄링 알고리즘
1) FIFO(First Come First Served)
- 비선점형 스케줄링 방식
- 가장 간단한 스케줄링 기법으로 , 먼저 대기 큐에 들어온 작업에게 CPU를 먼저 할당
- 큐를 이용해 쉽게 구현 가능
- FCFS(First Come First Served)라고도 함
2) SJF(Shortest Job First)
- 비선점형 스케줄링 방식
- 최단작업 우선. 실행시간이 짧은 프로세스 순서로 CPU를 할당
- Starvation 발생 가능
3) 라운드 로빈(RR, Round Robin)
- 선점형 스케줄링 방식
- FIFO 스케줄링 기법을 Preemptive(선점형)기법으로 구현한 스케줄링 방법으로, 프로세스는 FIFO형태로 대기 큐에 적재되지만, 주어진 시간 할당량(time slice)안에 작업을 마쳐야 하며, 할당량을 다 소비하고도 작업이 끝나지 않은 프로세스는 다시 대기 큐의 맨 뒤로 되돌아간다.
- 응답시간이 빠르며, 모든 프로세스가 공정하게 CPU를 할당받을 수 있음을 보장
- 단, CPU 할당 시간(Time Quantum)이 길 경우, FCFS랑 같아짐
4) SRT(Shortest Remaining Time First)
- SJF + RR 형식의 선점형 스케줄링 방식
- 새로 도착한 프로세스를 비롯하여 대기 큐에 남아있는 프로세스의 작업이 완료되기까지의 남아있는 실행시간 추정치가 가장 적은 프로세스에 먼저 CPU 할당
- Starvation 발생 가능
5) 다단계 큐(Multilevel Queue)
- 선점 방식
- Background에서 돌아가는 프로세스와 Foreground의 프로세스에 다른 알고리즘을 적용하는 방식
- 큐 사이에 서로 다른 CPU 할당 시간(Time Quantum)을 적용
- Backgounrd 프로세스에는 FCFS, Foreground는 RR 알고리즘 적용
6) 우선순위 스케줄링(Priority Scheduling)
- 선점과 비선점 두가지 방식에 모두 적용 가능
- 우선순위가 높은 프로세스에 CPU를 먼저 할당
- 기아 현상과 무기한 봉쇄가 발생할 수 있으며 에이징 기법을 통해 해결
! 에이징 기법(Aging)
- 먼저 도착한 프로세스가 나이를 계속 먹으며 우선순위가 올라가는 기법
