안녕하딤니카?
저번 글까지 프로세스를 정리했고, 이번 글에서는 CPU 스케줄링에 대해서, 그리고 CPU 스케줄링 알고리즘에 대해 정리해보려고 합니다.
그럼 시~~~작
사실 이 대표 사진을 고르는데 시간을 더 많이 씁니다
블로그 쓰는 시간보다도요
대표사진 아주 중요해
1. CPU 스케줄링과 프로세스 우선순위
CPU 스케줄링이란, 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것을 말합니다.
CPU 스케줄링은 컴퓨터 전체 성능과도 직결되는 아주 중요한 문제입니다. 만약 프로세스들한테 CPU를 제대로 분배를 못 한다면, 꼭 실행되어야 되는 프로세스가 실행이 안 되거나, 당장 급하지 않은 프로세스들이 먼저 실행되는 무질서한 상태가 반복될 수 있습니다.
그렇다면 가장 공정한 CPU 스케줄링은 무엇일까요? 어떻게 해야 모든 프로세스한테 CPU 자원을 아주 공정하게 배분할 수 있을까요? 프로세스 중에서 먼저 손 든 프로세스한테 우선권을 주면 될까요? 사실 이게 언뜻 들으면 가장 합리적인 방식일 것 같지만, 이건 그렇게까지 좋은 방법은 아닙니다.
빨리 처리해야 하는 프로세스가 있고, 천천히 처리해도 되는 프로세스, 즉 프로세스마다 우선순위가 다르기 때문에 이 우선순위를 고려해서 CPU 스케줄링을 해야 합니다. 이 우선순위는 사용자가 직접 정할 수도 있고, 운영체제가 미리 정해둔 우선순위를 따를 수도 있습니다.
예를 들자면, 입출력 작업이 많은 프로세스(입출력 집중 프로세스, IO Bound Process)의 우선순위는 CPU 작업이 많은 프로세스(CPU 집중 프로세스, CPU Bound Process)의 우선순위보다 높습니다. 이는 입출력 집중 프로세스는 입출력 완료까지 대기하는 시간이 계속 발생하기 때문에, 이 대기 상태에는 CPU를 안 쓰니까 CPU 집중 프로세스의 우선순위를 높어서 CPU 집중 프로세스 먼저 작업을 끝내고 그다음에 입출력 집중 프로세스를 처리하는 것입니다.
이렇게 각각의 상황, 프로세스가 요구하는 자원에 맞게 프로세스의 우선순위(priority)를 운영체제가 부여합니다. 이 우선순위는 PCB에 부여합니다.
2. 프로세스 우선순위를 결정하는 방법
2-1. 스케줄링 큐 (준비 큐, 대기 큐)
근데 운영체제가 프로세스의 우선순위를 선정하기 위해서 일일이 모든 프로세스의 PCB를 검사하는 것은 굉장히 비효율적입니다. 컴퓨터에서 동시에 실행되는 프로세스는 굉장히 많은데, 각각의 프로세스별 우선순위를 운영체제가 결정하는 방법이 바로 스케줄링 큐입니다.
스케줄링 큐를 쉽게 풀어서 설명하자면, 운영체제가 특정 자원(메모리, 하드디스크, 입출력 장치 등등)을 쓰고 싶어 하는 프로세스의 줄을 세우는 것입니다. (자료구조에서의 큐는 FIFO이지만, 스케줄링에서의 큐는 반드시 FIFO일 필요는 없습니다.)
이 스케줄링 큐에도 종류가 여러 가지 있습니다. 대표적인 스케줄링 큐의 종류는 준비 큐와 대기 큐가 있습니다.
준비 큐는 CPU를 이용하고자 하는 프로세스들이 서는 줄을 의미합니다. 대기 큐는 입출력 장치를 이용하고자 하는 프로세스들이 서는 줄을 의미합니다. 앞서 CPU의 상태에 대해 정리한 글에서, 준비 상태는 당장이라도 CPU를 할당받을 수 있지만 아직 차례가 되지 않은 상태라고 했고, 대기 상태는 프로세스가 실행 도중 입출력 장치를 사용하는 경우에 되는 상태라고 정리했습니다. 이 준비 큐와 대기 큐도 이러한 CPU의 상태처럼 준비 큐와 대기 큐에 각각의 자원을 원하는 프로세스들이 위치합니다.
대기 큐에 대해서 조금 더 정리해 보자면, 대기 큐에도 같은 장치를 요구한 프로세스들은 같은 큐에서 대기하는 경우가 많습니다. 프린터 입출력 장치를 사용하는 프린터 대기 큐, CD-ROM 입출력 장치를 사용하는 CD-ROM 대기 큐 이런 방식으로요.
2-2. 선점형 스케줄링과 비선점형 스케줄링
어떤 프로세스가 자기 차례가 되어서 CPU를 이용하고 있는데(실행 상태), 다른 프로세스가 와서 너무 급한데 본인이 먼저 CPU를 사용해도 되냐고 합니다. 우리는 이럴 때 두 가지 선택지 중 하나를 고를 수 있습니다.
- 현재 CPU를 사용 중인 프로세스로부터 CPU 자원을 빼앗아서 다른 프로세스에 할당하기 ➡️ 선점형 스케줄링 (Preemptive Schedulig)
- 현재 CPU를 사용 중인 프로세스의 작업이 끝날 때까지 프로세스한테 기다리라고 하기 ➡️ 비선점형 스케줄링 (Non-Preemtive Scheduling)
진짜 쉽게 말하자면, 선점형 스케줄링은 급한 프로세스가 있다면 새치기를 허용하는 거고, 비선점형 스케줄링은 새치기는 무슨 네 차례나 기다리라 한다고 볼 수 있습니다...
선점형 스케줄링의 장점은 어느 한 프로세스의 자원 독점을 막고, 프로세스들에게 골고루 자원을 배분할 수 있습니다. 단점은 그만큼 문맥 교환 과정에서 오버헤드가 발생할 수 있습니다.
비선점형 스케줄링의 장점은 선점형 스케줄링에 비해 문맥 교환에서 발생하는 오버헤드가 적다는 점입니다. 단점은 모든 프로세스가 골고루 자원을 이용하기 어렵습니다.
3. 대표적인 스케줄링 알고리즘
3-1. 비선점형 스케줄링 - 선입 선처리 스케줄링 (FCFS Scheduling)
선입 선처리 스케줄링은 FCFS(First Come First Served)라는 말처럼 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점형 스케줄링입니다. 먼저 CPU를 요청한 프로세스부터 CPU를 할당합니다.
설명만 보면 선입 선처리 스케줄링은 되게 공정한 방식의 스케줄링 알고리즘 같지만, 호위효과라는 부작용을 야기할 수 있는 스케줄링 알고리즘입니다. 호위효과란, 프로세스들이 기다리는 시간이 매우 길어짐을 뜻합니다. 앞에 먼저 처리하고 있는 프로세스의 실행 시간이 길면 길수록 뒤에 기다리는 프로세스의 대기 시간이 그만큼 늦어질 수 있습니다.
3-2. 비선점형 스케줄링 - 최단 작업 우선 스케줄링 (SJF Scheduling)
위에서 선입 선처리 스케줄링이 가지고 있는 호위효과 단점을 방지하는 스케줄링 알고리즘이 최단작업 우선 스케줄링입니다.
최단 작업 우선을 SJF(Shortest Job First)라고 하는데, 영어 뜻을 그대로 풀이하는 것처럼 CPU 사용이 긴 프로세스는 나중에 실행하고, CPU 사용 시간이 짧은 프로세스는 먼저 실행하는 것이 최단 작업 우선 스케줄링입니다.
(최단 작업 우선 스케줄링을 선점형 스케줄링으로도, 비선점형 스케줄링으로도 구현할 수 있지만, 분류는 비선점형 스케줄링으로 합니다.)
3-3. 비선점형 스케줄링 - HRN 스케줄링 (Highest Response Ratio Next Scheduling)
위에서 설명했던 짧은 작업에 유리한 최단 작업 우선(SJF) 스케줄링을 보완한 알고리즘입니다. HRN 스케줄링은 짧은 작업과 대기 시간이 긴 작업의 우선순위를 높입니다. 최단 작업 우선 스케줄링의 단점인 긴 작업과 짧은 작업의 과도한 불평등을 보완합니다. 한 프로세스가 CPU를 사용하면 작업이 완성될 때까지 실행하며, 대기시간이 고려되어 긴 작업과 짧은 작업 사이의 불평등을 어느 정도 완화합니다.
HRN 스케줄링 알고리즘에서 우선순위를 산정하는 공식은 (대기시간 + 서비스시간) / 서비스시간입니다.
3-4. 선점형 스케줄링 - 라운드 로빈 스케줄링 (RR Scheduling)
라운드로빈(Round Robin, RR)이란 순서대로 뭔가를 한 다는 것인데, 여기서 라운드 로빈 스케줄링은 선입 선처리 스케줄링에 타임 슬라이스(time slice)라는 개념이 더해진 스케줄링 알고리즘입니다. 타임 슬라이스란 각 프로세스가 CPU를 사용할 수 있는 정해진 시간이라는 뜻인데, 라운드 로빈 스케줄링은 정해진 타임 슬라이스만큼의 시간 동안 돌면서 CPU를 이용하는 선점형 스케줄링 알고리즘입니다.
라운드 로빈 스케줄링에서 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되, 정해진 시간만큼만 이용합니다. 정해진 시간을 모두 사용했음에도 아직 프로세스가 완료되지 않았다면, 다시 큐의 맨 뒤에 삽입합니다. 여기서 문맥 교환이 이루어집니다.
라운드 로빈 스케줄링에서는 타임 슬라이스의 크기가 중요합니다. 왜냐면 타임 슬라이스의 크기가 너무 커지면, 타임 슬라이스 개념을 더하기 전인 선입 선처리 스케줄링의 방식과 거의 똑같아지기 때문입니다. 그렇게 되면 선입 선처리 스케줄링에서 발생할 수 있는 호위효과가 라운드 로빈 스케줄링에서도 발생할 수 있습니다.
3-5. 선점형 스케줄링 - 최소 잔여 시간 우선 스케줄링 (SRT Scheduling)
최소 잔여 시간 우선 스케줄링은 SRT, SRTF 스케줄링이라고 부르는데, 이건 Shortest Remaining Time (First)를 줄인 것입니다. 이 알고리즘은 최단 작업 우선 스케줄링과 라운드 로빈 스케줄링이 합쳐진 방식인데요, 두 알고리즘을 아래에 다시 정리하자면
- 최단 작업 우선 스케줄링 (SJF 스케줄링) : 작업 시간이 짧은 프로세스부터 처리하는 비선점형 스케줄링 알고리즘
- 라운드 로빈 스케줄링 (RR 스케줄링) : 정해진 타임 슬라이스만큼 돌아가며 사용하는 선점형 스케줄링 알고리즘
입니다. 그래서 이 둘을 합쳐서, 최소 잔여 시간 우선 스케줄링은 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업시간이 가장 적은 프로세스를 선택하는 선점형 스케줄링 알고리즘입니다.
3-6. 비선점형 스케줄링 - 우선순위 스케줄링 (Priority Scheduling)
우선순위 스케줄링이란 프로세스들에게 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행하는 스케줄링 알고리즘입니다. 여기서 우선순위가 같은 프로세스들은 선입 선처리(먼저 준비 큐에 들어가 있는 프로세스부터 실행)로 스케줄링합니다.
(최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링 ⊂ 우선순위 스케줄링)
우선순위 스케줄링 방식이 가지고 있는 단점이 있습니다. 바로 기아 현상(starvation, 또는 아사 현상)입니다. 우선순위 스케줄링은 말 그대로 우선순위가 높은 프로세스 먼저 실행하는 알고리즘이라, 우선순위가 높은 프로세스만 주야장천 실행하고, 우선순위가 낮은 프로세스는 준비 큐에 먼저 삽입되었음에도 불구하고 실행이 연기됩니다. 이 현상을 기아 현상이라고 합니다.
기아현상을 해결할 수 있는 대표적인 기법으로는 에이징(aging)이 있습니다. 에이징은 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식입니다. 대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방식이라 에이징이라는 명칭이 붙었습니다. 에이징 기법을 사용하면 우선순위가 낮은 프로세스도 언젠가는 우선순위가 높아져서 기아 현상을 어느 정도 해결할 수 있습니다.
3-7. 선점형 스케줄링 - 다단계 큐 스케줄링 (Multilevel Queue Scheduling)
다단계 큐 스케줄링은 앞서 설명했던 우선순위 스케줄링의 발전된 형태입니다. 다단계 큐 스케줄링은 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 알고리즘입니다.
우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리하고, 우선순위가 가장 높은 큐가 비어있다면 그다음 우선순위 큐에 있는 프로세스를 처리하는 방식으로 진행합니다.
이렇게 우선순위를 여러 개 두면 좋은 점은 프로세스 유형별로 우선순위를 구분하는 것이 쉬워집니다. 어떤 큐에는 우선순위가 비교적 높아야 하는 입출력 집중 프로세스가 삽입될 수 있고, 또 어떤 큐에는 우선순위가 비교적 낮아도 상관없는 CPU 집중 프로세스가 삽입될 수 있습니다. 그리고 어떤 큐에는 타임 슬라이스를 적게 지정할 수 있고, 다른 큐에는 타임 슬라이스를 크게 지정할 수 있고... 이런 식으로 큐마다 다른 우선순위와 타임 슬라이스로 스케줄링을 할 수 있습니다.
이렇게 큐를 여러 개 두면 또 좋은 점은 큐마다 다른 스케줄링 알고리즘을 적용할 수 있다는 점입니다. 큐별로 어떤 큐에는 라운드 로빈, 어떤 큐에는 SRT 스케줄링 이런 식으로 프로세스 유형별로 적합한 스케줄링 알고리즘을 선택할 수 있는 알고리즘이 바로 다단계 큐 알고리즘입니다.
이런 다단계 큐 스케줄링에도 단점이 있습니다. 바로 우선순위 간 큐간에 프로세스가 이동할 수 없다는 점입니다. 그래서 우선순위가 낮은 큐에 배치된 프로세스는 다시 한번 기아 현상이 발생할 수 있다는 단점이 있습니다.
3-8. 선점형 스케줄링 - 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)
위에서 설명한 다단계 큐 스케줄링의 단점을 보완한 스케줄링 알고리즘이 바로 다단계 피드백 큐 스케줄링입니다. 다단계 피드백 큐 스케줄링은 우선순위별로 준비 큐를 여러 개 사용하는 다단계 큐 스케줄링에서, 큐 간의 이동이 가능한 스케줄링입니다.
다단계 피드백 큐 스케줄링의 실행 방식은 일단 준비 상태인 프로세스를 가장 높은 우선순위 큐에 삽입하고, 그다음에 자기 차례가 되면 CPU를 할당받아서 실행하게 하는데, 여기서 만약 실행이 끝나지 않았다면 다음 우선순위 큐로 이동시켜 실행하게 하도록 스케줄링이 이루어집니다. 이러면 CPU 집중 프로세스는 점점 우선순위가 낮아지고, CPU를 많이 사용하지 않아도 되는 입출력 집중 프로세스의 우선순위는 점점 높아집니다.
정리하자면, 다단계 피드백 큐 스케줄링은 CPU를 많이 이용해야 하는 프로세스일수록 우선순위가 자연스럽게 낮아질 수 있도록, 입출력 집중 프로세스의 우선순위는 상대적으로 높아질 수 있도록 하는 스케줄링 알고리즘입니다.
다단계 피드백 큐 스케줄링에서도 에이징 기법을 적용할 수 있습니다. 예를 들어서, 어떤 프로세스가 CPU를 엄청나게 많이 이용해야 하는데, 타임 슬라이스에 걸려서 우선순위가 계속 낮아져서 한도 끝도 없이 기다리는 기아 현상이 발생한다면, 이 프로세스의 우선순위를 점차 높임으로써 기아 현상을 예방할 수 있습니다.
이 다단계 피드백 큐 스케줄링 알고리즘은 구현은 복잡하지만, 가장 일반적인 형태의 CPU 스케줄링 형태라고 알려져 있습니다.
4. 정리
이번 글에서는 CPU 스케줄링의 개념과 프로세스의 우선순위를 결정하는 방법, 그리고 CPU 스케줄링 알고리즘의 대표적인 것들을 정리해 봤습니다. 내용이 많이 길어지긴 CPU 스케줄링을 원리와 과정 중심으로 접근한다면 좀 더 쉽게 정리할 수 있다는 점을 남기며...
그럼 20000 !
[자료 출처]
강민철, 《혼자 공부하는 컴퓨터 구조+운영체제》, 한빛미디어, 2022
인프런 - 개발자를 위한 컴퓨터공학 1 : 혼자 공부하는 컴퓨터구조 + 운영체제
🍀
좋아하는 것을 계속 좋아하세요!
반드시 행복해집니다
백엔드 개발자가 되고 싶어서 열심히 헤딩 중인 재영입니다 :-)
[Github] https://github.com/chujaeyeong
[E-mail] chujy1224@gmail.com
'Study > 컴퓨터구조, 운영체제' 카테고리의 다른 글
| 교착 상태(데드 락, Dead Lock)에 대해 정리해보자 (0) | 2025.01.11 |
|---|---|
| 프로세스의 동기화, 동기화 기법에 대해 정리해보자 (0) | 2025.01.10 |
| 스레드를 정리해보자 (스레드의 구성 요소, 멀티 스레드, 멀티 프로세스) (1) | 2025.01.07 |
| 프로세스 상태와 계층 구조에 대해 정리해보자 (0) | 2025.01.07 |
| 프로세스의 개요와 PCB, 메모리 영역에 대해 정리해보자 (0) | 2025.01.07 |
