티스토리 뷰
CPU 스케줄링 알고리즘
CPU 스케줄링 알고리즘은 다양하고 운영체제마다 다른 알고리즘을 사용하고 있다. 아래는 7가지 알고리즘에 대한 설명이다.
선입 선처리 스케줄링
선입 선처리 스케줄링은 FCFS 스케줄링이라고 불린다. 이는 준비 큐에 삽입된 순서대로 프로세스를 처리하는 비선점형 스케줄링 방식이다. 공정해 보이지만, 프로세스들이 기다리는 시간이 길어질 수 있다.
A 프로세스가 15ms 실행 동안 B 프로세스는 15ms를 대기하고, B 프로세스가 5ms 실행 동안 C 프로세스는 1ms를 실행하기 위해 15ms+5ms를 대기하게 된다. 위 스케줄링의 평균 대기 시간은 (20+15+0) / 3 대략 12초 정도 걸린다.
최단 작업 우선 스케줄링
앞서 FCFS 스케줄링의 단점을 방지할려면 CPU 사용 시간이 긴 프로세스는 나중에 실행하고, CPU 사용 시간이 짧은 프로세스는 먼저 실행하면 된다. 기본적으로 비선점형 스케줄링으로 분류되며, 이를 최단 작업 우선 스케줄링이라고 하고 SJF 스케줄링이라고 한다.
위의 SJF 스케줄링은 실행 시간이 짧은 프로세스 부터 실행되며 C 프로세스가 1ms 실행 동안 B 프로세스는 1ms 대기하고, B 프로세스가 5ms 실행 동안 C 프로세스는 1ms+5ms만 대기하면 된다.
라운드 로빈 스케줄링
라운드 로빈 스케줄링 스케줄링은 RR 스케줄링이라고 하며, 선입 선처리(FCFS) 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식이다. 타임 슬라이스란 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미한다. 즉 정해진 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링이다. 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입된다. 이때 문맥 교환이 발생한다.
RR 스케줄링은 타임 슬라이스 크기가 중요하다. 타임 슬라이스 크기가 지나치게 크면 FCFS 스케줄링과 다를 바 없고, 반대로 지나치게 작으면 문맥 교환이 발생하는 비용이 커 CPU는 프로세스를 처리하는 일보다 프로세스를 전환하는 데 사용하게 된다.
최소 잔여 시간 우선 스케줄링
최소 잔여 시간 우선 스케줄링은 SRT 스케줄링이라고 하며, 최단 작업 우선(SJF) 스케줄링과 라운드 로빈(RR) 스케줄링을 합친 스케줄링이다. 즉, 작업 시간이 짧은 프로세스를 먼저 실행하며 타임 슬라이스 크기만큼 우선적으로 실행하는 방식이다.
우선순위 스케줄링
우선순위(Priotity) 스케줄링은 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 사진 프로세스 부터 실행하는 스케줄링이다. 우선순위 대로 실행 되는데 만약 우선순위가 높은 프로세스가 큐에 들어오면 그 프로세스가 바로 실행하게 된다. 다만, 큐에 우선순위가 높은 프로세스가 계속 들어오게 되면 낮은 프로세스들은 연기가 되어 기아 현상이 발생하게 된다. 이를 방지하기 위해 에이징이 있는데 오랫동안 대기한 프로세스의 우선순위를 높이는 방식이다.
다단계 큐 스케줄링
다단계 큐 스케줄링 MLQ 스케줄링이라 하며 앞서 우선순위(Priority) 스케줄링의 발전된 형태이다. MLQ 스케줄링은 우선순위별로 준비 큐를 여러 개 사용하는 방식이다. 다단계 큐 하에서는 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고 비어 있으면 그다음 우선순위 큐에 있는 프로세스들을 처리한다.
위의 큐를 여러 개 두면 프로세스를 우선순위를 구분하여 실행하는 것이 편리하다. 또한 큐별로 타임 슬라이스를 여러 개 지정할 수도 있고, 큐마다 다른 스케줄링 알고리즘을 사용할 수 있다. 다만 우선순위가 높은 큐에 프로세스가 계속 들어온다면 우선순위가 낮은 큐에 있는 프로세스는 연기될 여지가 있다.
다단계 피드백 큐 스케줄링
다단계 피드백 큐 스케줄링은 다단계 큐(MLQ) 스케줄링의 발전된 형태이다. MLQ 스케줄링은 프로세스들이 큐 사이를 이동할 수 없다. 이런 방식대로면 우선순위가 낮은 프로세스는 계속 연기될 여지가 있으며 기아 현상이 발생할 수 있다. 이를 보완한 스케줄링이 다단계 피드백 큐(MLFQ) 스케줄링이다. 보완한 것은 프로세스들이 큐 사이를 이동할 수 있다는 것이다.
위의 그림에서 프로세스가 타임슬라이스 만큼 실행한다고 가정하였다. 그런데 만약 프로세스가 해당 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐에 삽입되어 실행된다. 그리고 해당 큐에서 실행이 끝나지 않는다면 프로세스는 또 다음 우선순위 큐에 삽입된다. 즉 CPU를 오래 사용하는 프로세스의 우선순위는 낮아지게 된다.
위의 그림에서 실행을 못 끝낸 프로세스가 다음 우선순위로 내려갔다. 이렇게 프로세스가 못 끝낸 상태로 우선순위가 내려간다면 낮은 우선순위에 있기 때문에 큐에 오래 기다리게 되는데 우선순위가 높은 큐로 이동시키는 에이징 기법을 적용하여 기아 현상을 예방할 수 있다. MLFQ 스케줄링은 CPU 이용 시간이 길면 낮은 우선순위로 이동시키고, 낮은 우선순위에서 오래 기다린다면 높은 우선순위 큐로 이동시키는 스케줄링이다.
정리
- 선입 선처리(FCFS) 스케줄링: 준비 큐에 삽입된 순서대로 CPU를 할당
- 최단 작업 우선(SJF) 스케줄링: 준비 큐에 삽입된 프로세스들 중 CPU 사용 시간의 길이가 가장 짧은 프로세스부터 CPU를 할당
- 라운드 로빈(RR) 스케줄링: 정해진 시간만큼만 돌아가며 CPU를 할당
- 최소 잔여 시간 우선(SRT) 스케줄링: 최단 작업 우선(SJF) 스케줄링과 라운드 로빈(RR) 스케줄링을 합친 스케줄링
- 우선순위(Priority) 스케줄링: 가장 높은 우선순위의 프로세스에 CPU를 할당
- 다단계 큐(MLQ) 스케줄링: 우선순위 별로 다단계 큐에 프로세스를 삽입하여 우선순위가 높은 큐에 CPU를 할당
- 다단계 피드백 큐(MLFQ) 스케줄링: 다단계 큐(MLQ) 스케줄링의 발전된 형태이며, 프로세스가 큐 사이를 이동할 수 있는 스케줄링
본 포스팅은 “혼자 공부하는 컴퓨터 구조 + 운영체제/강민철 저”를 읽고 학습한 내용을 정리한 것
'CS > 운영체제' 카테고리의 다른 글
| <운영체제> 멀티프로세스와 멀티스레드 이란? (0) | 2026.01.09 |
|---|