✅ 스케줄링

✔ 자원을 어떤 시점에 어느 프로세스에게 할당할지 결정하는 것.

• 스케줄링 방법에 따라 프로세서(CPU)를 할당받을 프로세스를 결정한다.
• 따라서 스케줄링은 시스템 성능에 영향을 미친다.

💎 목표

✔ 공평성 : 모든 프로세스가 자원을 공평하게 배정 받아야 하며, 특정 프로세스가 배제되면 안된다.
✔ 효율성 : 시스템 자원을 놀리는 시간 없이 스케줄링 해야한다.
✔ 안정성 : 우선순위를 사용하여 중요한 프로세스가 먼저 처리되도록 해야한다.
✔ 반응 시간 보장 : 적절한 시간 안에 프로세스의 요구에 반응해야 한다.
✔ 무한 연기 방지 : 특정 프로세스의 작업이 무한히 연기되면 안된다.

🔧 시스템에 따른 목표

Batch System

가능하면 많은 일을 수행하도록 스케줄링. 시간(time)보단 처리량(throughout)이 중요.

Interactive System

빠른 응답시간(response time). 적은 대기시간(waiting time).

Real-time System

기한(deadline) 맞추기. 시간 제약 조건을 만족.

📈 스케줄링 평가 척도

CPU Utilization(프로세서 이용률)

• CPU가 사용되는 비율.

Throughput(처리양)

• 단위시간당 처리한 작업의 수.

Turnaround Time(반환시간 or 소요시간)

• 프로세스의 처음 시작 시간부터 모든 작업을 끝내고 종료하는데 까지 걸린 시간.

Waiting Time(대기 시간)

• CPU를 할당받기 위해 큐에서 기다린 시간.

Response Time(응답 시간)

• Interactive System에서의 입력에 대한 반응 시간.

✅ 선점 / 비선점 스케줄링

🔄 선점 스케줄링

프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU의 사용권을 선점할 수 있는 경우 회수할 수 있는 방식.

✔ 우선순위가 높은 프로세스를 빠르게 처리할 수 있다.
✔ 처리 시간이 매우 긴 프로세스가 CPU 사용을 독점하는 것을 막을 수 있다.
✔ 잦은 Context Switching으로 오버헤드가 많이 발생한다.
✔ 빠른 응답 시간을 요구하는 시스템에서 사용한다.
✔ 처리시간 예측이 어렵다.

💥 선점 스케줄링 종류

Priority Scheduling

• 우선순위를 부여하여 우선순위가 높은 순서대로 처리
• 우선순위가 낮은 프로세스가 무한정 기다리는 Starvation 문제가 생길 수 있다.

SRTF (Shortest Remaning Time First)

• 가장 짧은 실행 시간을 요구하는 프로세스에게 CPU를 할당한다.
• 현재 CPU를 할당받은 프로세스의 남은 처리 시간이 새로 추가된 프로세스의 실행시간보다 길 경우 CPU를 빼앗긴다.
• SJF 알고리즘을 선점 형태로 변경한 기법

Round Robin

• 큐에 먼저 들어온 프로세스에게 CPU를 할당한 후, 할당된 시간(Time Quantum or Time Slice)동안 실행한다.
• 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 큐의 가장 뒤에 배치된다.
• FCFS 알고리즘을 선점 형태로 변경한 기법
• 할당 시간이 크면 FCFS와 같아지고 작으면 Context Switching이 잦아져 오버헤드가 증가한다.

Multilevel-Queue (다단계 큐)

• 프로세스를 여러 그룹으로 분류하여 그룹에 따라 각기 다른 큐를 이용하는 기법
• 우선순위가 낮은 큐들이 실행 못하는 것을 방지하고자 각 큐마다 다른 할당 시간을 설정한다.
• 우선순위가 높은 큐는 할당 시간을 작게, 우선순위가 낮은 큐는 할당 시간을 크게

Multilevel-Feedback-Queue (다단계 피드백 큐)

• 특정 그룹의 큐에 들어간 프로세스가 다른 큐로 이동할 수 있도록 다단계 큐 방식을 개선한 기법

🔔 Aging 기법

프로세스가 자원을 할당받지 못하고 기다린 시간에 비례하여 우선 순위를 높여 빠르게 자원을 할당받도록 하는 기법. 무한연기, Starvation 문제를 해결하기 위한 기법이다.

🔄 비선점 스케줄링

프로세스가 CPU를 점유하고 있다면 종료나 I/O등의 이벤트가 있을 때까지 이를 뺏을 수 없는 방식.

✔ 모든 프로세스에 대한 요구를 공정하게 처리한다.
✔ 배치 시스템에 적합하다.
✔ 처리시간 예측이 쉽다.

💥 비선점 스케줄링 종류

FCFS (First Come First Served)

• 큐에 도착한 순서에 따라 차례로 CPU를 할당하는 방식.

SJF (Shortest Job First)

• 실행시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 방식.
• FCFS보다 평균 대기 시간이 짧다.

HRN (Hightest Response-ratio Next)

• 우선순위를 계산하여 점유 불평등을 보완한 방법.
• 실행시간이 긴 프로세스에게 불리한 SJF 기법의 단점 보완.
• 우선순위 = (대기시간 + 실행시간) / 실행시간

✅ 프로세스 상태

• 생성(new) : 프로세스가 막 생성된 상태.
• 준비(ready) : 프로세스가 CPU 할당을 기다리는 상태.
• 실행(running) : 프로세스가 실행 중인 상태.
• 대기(waiting) : 프로세스가 event를 기다리는 상태.
• 종료(terminated) : 프로세스의 실행이 완료된 상태.

⏰ 프로세스의 상태 전이

• 승인 (Admitted) : 프로세스 생성이 가능하여 승인됨.

• 스케줄러 디스패치 (Scheduler Dispatch) : 준비 상태에 있는 프로세스 중 하나를 선택하여 실행시키는 것.

• 인터럽트 (Interrupt) : 예외, 입출력, 이벤트 등이 발생하여 현재 실행 중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리하는 것.

• 입출력 또는 이벤트 대기 (I/O or Event wait) : 실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우, 입출력/이벤트가 모두 끝날 때까지 대기 상태로 만드는 것.

• 입출력 또는 이벤트 완료 (I/O or Event Completion) : 입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것.

💛 참고 :
https://www.crocus.co.kr/1373
https://velog.io/@ss-won/OS-CPU-Scheduling-Algorithm
https://colomy.tistory.com/120