📍목차
- 스케줄링의 개요
- 스케줄링 시 고려 사항
- 다중 큐
- 스케줄링 알고리즘
- 인터럽트 처리
1️⃣ 스케줄링의 개요
CPU 스케줄러는 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정한다.
여러 프로세스의 상황을 고려하여 CPU와 시스템 자원을 어떻게 배정할지 결정하게 된다.
✔️ 규모별 스케줄링
CPU 스케줄러는 관리의 범주에 따라 고수준, 중간 수준, 저수준 스케줄링으로 나뉘게 된다.
각 수준에 대해 알아보자.
고수준 스케줄링
고수준 스케줄링은 시스템 내의 전체 작업 수를 조절한다.
작업은 1개 이상의 프로세스로 이루어지는 운영체제가 다루는 일의 가장 큰 단위로,
고수준 스케줄링에서는 전체 시스템의 부하를 고려하여 스케줄러가 작업을 승인할지, 거부할지 결정한다.
따라서 고수준 스케줄링의 결정에 따라 멀티프로그래밍 정도. 즉, 시스템의 전체 프로세스 수가 결정된다.
중간 수준 스케줄링
고수준 스케줄링이 전체 프로세스의 수를 조절하더라도, 시스템의 사정에 따라 과부하가 걸릴 수 있다.
중간 수준 스케줄링은 활성화된 프로세스의 수를 조절하여 시스템의 과부하를 막는다.
중지와 활성화를 통해 활성화된 프로세스의 수를 조절하는데, 일부 프로세스를 중지 상태로 옮김으로써 나머지 프로세스의 정상 작동을 지원한다. 이는 프로세스 상태 중 보류 상태에 해당한다.
저수준 스케줄링
고수준 스케줄링과 중간 수준 스케줄링으로 인해 적정량의 프로세스가 원활한 작동을 보장했다면,
저수준 스케줄링은 어떤 프로세스를 준비 상태/실행 상태/대기 상태로 보낼지 결정한다.
오늘날의 CPU 스케줄러는 대부분 중간 수준과 저수준 스케줄링으로 이루어져 있다.
✔️ 스케줄링의 목적
| 목적 | 의미 |
|---|---|
| 공평성 | 모든 프로세스가 자원을 공평하게 배정받아야 한다. |
| 효율성 | 자원이 유휴 시간 없이 사용되어야 한다. |
| 안정성 | 우선순위를 통해 중요 프로세스가 먼저 작동함으로써 자원이 보호되어야 한다. |
| 반응 시간 보장 | 적절한 시간 안에 프로세스의 요구에 반응해야 한다. |
| 무한 연기 방지 | 프로세스의 작업이 무한히 연기되어서는 안 된다. |
2️⃣ 스케줄링 시 고려 사항
✔️ 선점형 스케줄링, 비선점형 스케줄링
선점형 스케줄링
선점형 스케줄링이란, 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 CPU를 빼앗을 수 있는 방식이다.
선점형 스케줄링에서 운영체제는 필요에 따라 실행 중인 프로세스를 중단시키고 새로운 작업을 시작할 수 있다.
대표적인 예로는 인터럽트 처리를 들 수 있는데, CPU가 인터럽트를 받으면 현재 실행 중인 작업을 중단하고 커널을 깨워서 인터럽트를 처리한 후 기존의 작업으로 돌아간다.
선점형 스케줄링은 문맥 교환으로 인해 낭비가 생긴다는 단점이 있으나,
하나의 프로세스가 CPU를 독점할 수 없기 때문에 대화형 시스템이나 시분할 시스템에 적합하다.
비선점형 스케줄링
비선점형 스케줄링이란, 어떤 프로세스가 CPU를 사용하면 종료되거나 대기 상태에 들어갈 때까지 실행된다.
비선점형 스케줄링은 선점형 스케줄링보다 작업량이 적고 문맥 교환으로 인한 낭비가 없으나,
CPU 사용 시간이 긴 프로세스 때문에 CPU 사용 시간이 짧은 프로세스가 계속 기다리게 되어 전체 시스템의 처리율이 떨어진다.
✔️ 프로세스 우선순위
CPU 스케줄러는 프로세스의 우선순위에 따라 실행할 프로세스를 결정하는데,
우선순위가 높다는 것은 더 자주 실행된다는 의미이다.
프로세스는 크게 커널 프로세스와 일반 프로세스로 나뉜다.
커널 프로세스는 일반 프로세스보다 우선순위가 높으며, 커널 프로세스 중에서도 중요도에 따라 우선순위가 다르다.
일반 프로세스도 우선순위가 서로 다른데, 문서 편집기보다 비디오 플레이어의 우선순위를 높게 하는 것이 그 예이다.
문서 편집기의 경우 CPU 연산 속도보다 사람의 타이핑 속도가 훨씬 느려 천천히 실행해도 되지만,
비디오 플레이어는 실시간으로 데이터를 읽어 영상과 소리를 출력해야 하기 때문에 자주 실행되어야 한다.
또한 일반 프로세스는 사용자가 우선순위를 조절할 수 있는데, 대용량 파일 압축이나 디스크 백업과 같이 천천히 해도 되는 프로세스의 우선순위를 낮추는 것이 그 예이다.
✔️ CPU 집중 프로세스, 입출력 집중 프로세스
프로세스는 작업 형태에 따라 CPU 집중 프로세스와 입출력 집중 프로세스로 나뉜다.
CPU 집중 프로세스는 수학 연산과 같이 CPU를 많이 사용하는 프로세스를 의미하고,
입출력 집중 프로세스는 저장장치에서 입출력을 많이 실행하는 프로세스를 의미한다.
CPU 집중 프로세스와 입출력 집중 프로세스가 같이 있을 때는 입출력 집중 프로세스를 먼저 실행하는 것이 효율적이다.
만약 CPU 집중 프로세스가 먼저 실행 상태로 들어가면, 타임 슬라이스를 다 쓸 때까지 다른 프로세스가 CPU를 사용할 수 없기 때문이다.
이때, 입출력 집중 프로세스가 CPU 집중 프로세스보다 먼저 실행되는 것을 사이클 훔치기라고 한다.
✔️ 전면 프로세스, 후면 프로세스
전면 프로세스란 화면에 맨 앞에 놓여 사용자와 상호작용하며 현재 입출력을 사용하는 프로세스이며,
후면 프로세스란 사용자와 상호작용이 없는 프로세스이다.
아래는 전면 프로세스와 후면 프로세스의 예시이다.
브라우저가 전면 프로세스, 문서 편집기가 후면 프로세스가 된다.
전면 프로세스는 사용자의 요구에 빠르게 반응해야하기 때문에, 후면 프로세스보다 우선순위가 높다.
정리
앞서 살펴본 CPU 스케줄링 시 고려 사항을 정리하면 아래와 같다.
- 커널 프로세스 > 일반 프로세스
- 전면 프로세스 > 후면 프로세스
- 대화형 프로세스 > 일괄 처리 프로세스
- 입출력 집중 프로세스 > CPU 집중 프로세스
3️⃣ 다중 큐
✔️ 준비 상태의 다중 큐
CPU 스케줄러는 PCB에 기록된 우선순위가 높은 프로세스를 찾아 CPU를 할당한다.
우선순위가 높은 프로세스를 빠르게 찾기 위해 운영체제는 우선순위에 따라 여러 개의 큐를 만들어 놓고,
프로세스는 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입된다.
큐를 몇 개로 나눌지, 어떤 프로세스에 CPU를 할당할지는 스케줄링 알고리즘에 따라 달라지며,
스케줄링 알고리즘은 아래에서 자세히 알아보자.
프로세스의 우선순위를 배정하는 방식은 고정 우선순위 방식과 변동 우선순위 방식이 있다.
- 고정 우선순위 방식
- 프로세스에 우선순위를 부여하면 끝날 때까지 우선순위가 변하지 않는다.
- 구현이 쉬우나, 시스템의 변화에 대응하기 어려워 작업 효율이 떨어진다.
- 변동 우선순위 방식
- 프로세스의 우선순위가 프로세스 실행 도중에 변하는 방식이다.
- 구현이 복잡하나, 시스템의 효율성이 높아진다.
✔️ 대기 상태의 다중 큐
입출력이 완료되기를 기다리는 대기 상태에서도 다중 큐 방식을 사용한다.
시스템 내에는 여러 종류의 입출력장치가 있기 때문에, 효율을 높이기 위해 같은 장치의 입출력을 기다리는 PCB는 동일한 입출력 큐에 모인다.
대기 상태의 다중 큐는 준비 상태의 다중 큐와 차이가 있는데,
준비 상태에서는 한 번에 하나의 PCB를 꺼내는 반면, 대기 상태에서는 여러 개의 PCB를 꺼내 준비 상태로 옮긴다.
이는 여러 입출력장치가 동시에 끝나는 경우 여러 개의 인터럽트를 한꺼번에 처리하기 위함이며,
여러 인터럽트를 한번에 처리하기 위해 인터럽트 벡터라는 자료구조를 활용한다.
인터럽트 벡터에는 동시에 완료된 입출력 정보와 처리 방법이 담겨있고, 이 정보에 따라 PCB는 모두 준비 상태로 이동한다.
또한, 대기 상태의 다중 큐에서 나중에 들어온 PCB가 먼저 준비 상태로 옮겨 가기도 하는데,
이는 입출력장치가 CPU나 메모리보다 느리기 때문에 작업 속도를 높이기 위해 작업 순서를 바꾸기 때문이다.
4️⃣ 스케줄링 알고리즘
스케줄링 알고리즘은 앞서 언급한 비선점형 알고리즘과 선점형 알고리즘으로 나뉜다.
각 유형별 알고리즘을 알아보기에 앞서, 알고리즘 성능 평가를 위한 기준에 대해 알아보자.
스케줄링 알고리즘 평가 기준
CPU 알고리즘의 효율성을 평가할 때 CPU 사용률과 처리량을 보지만,
이는 계산하기 어려워 주로 대기 시간, 응답 시간, 실행 시간, 반환 시간을 계산하여 평가한다.
- 대기 시간 : 프로세스 생성 후 실행 전까지 대기하는 시간
- 응답 시간 : 프로세스 생성 후 첫 번째 출력이 나오기까지의 시간
- 실행 시간 : 프로세스 시작 후 종료되기까지의 시간
- 반환 시간 : 프로세스 생성 후 종료되기까지의 시간
스케줄링 알고리즘의 성능을 비교할 때는 주로 평균 대기 시간을 본다.
평균 대기 시간은 (모든 프로세스의 대기 시간의 합) (프로세스 수)이다.
🔑 FCFS 스케줄링 (비선점형)
First Come First Serve라는 의미로,
준비 큐에 도착한 순서대로 CPU를 할당한다.
큐를 의미하는 FIFO와 구별하기 위해 FCFS라고 표현할 뿐, 완전히 같은 의미이며 큐에 도착한 프로세스 순서대로 실행된다.
비선점형이기 때문에, 한 번 실행된 프로세스가 끝나야만 다음 프로세스를 실행할 수 있다.
✔️ 콘보이 효과
단순하고 공평하지만, 처리 시간이 긴 프로세스가 실행되면 다른 프로세스는 계속 기다리게 되어 효율이 떨어진다.
이렇게 작업물이 한 줄로 늘어서 뒤의 작업이 지연되는 현상을 콘보이 효과라고 한다.
🔑 SJF 스케줄링 (비선점형)
Short Job First라는 의미로,
실행 시간이 가장 짧은 작업부터 CPU를 할당한다.
간단한 작업을 먼저 실행하여 FCFS 스케줄링의 콘보이 효과를 완화할 수 있으나,
사용자와 상호작용하는 프로세스의 경우 운영체체가 프로세스의 종료 시간을 예측하기 어렵고, 공평성에 위배된다는 이유로 사용되지 않는다.
✔️ 아사 현상
아사 현상이란, 실행 시간이 짧은 작업이 큐에 계속 들어와 실행 시간이 긴 작업이 무한 연기되는 현상이다.
이는 에이징(Aging)로 완화할 수 있다.
에이징은 프로세스가 양보하는 횟수의 상한선을 정하는 방식인데, 이 횟수를 어떤 기준으로 정할 것인지에 대한 문제가 있어 잘 사용하지 않는다.
🔑 HRN 스케줄링 (비선점형)
High Response ratio Next라는 의미로,
대기 시간과 CPU 사용 시간을 고려하여 스케줄링하는 방식이다.
HRN 스케줄링에서 프로세스의 우선순위를 결정하는 기준은 아래와 같다.
이렇게 대기 시간을 고려함을 통해 아사 현상을 완화할 수 있다.
그러나 여전히 CPU 사용 시간을 고려한다는 점에서 공평성이 위배되어 많이 사용되지 않는다.
🔑 라운드 로빈 스케줄링 (선점형)
순환 순서 방식이라는 의미의 Round Robin은,
실행된 프로세스가 타임 슬라이스 내에 완료되지 못하면 준비 큐의 맨 뒤로 들어가는 방식이다.
이는 준비 큐의 맨 앞 프로세스부터 차례대로 실행한다는 점에서 FCFS 스케줄링과 유사한데,
타임 슬라이스 동안만 작업할 수 있다는 점에서 차이가 있다.
또한 선점형 방식에서는 문맥 교환 시간이 추가된다는 점을 고려해야 한다.
🔑 SRT 우선 스케줄링 (선점형)
Shortest Remaining Time이라는 의미로,
남은 작업 시간이 가장 적은 프로세스에 CPU를 할당한다.
이는 비선점형 방식의 SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식이다.
그러나 프로세스의 남은 시간을 주기적으로 계산하고, 아사 현상이 발생한다는 점에서 잘 사용하지 않는다.
🔑 우선순위 스케줄링 (비선점형, 선점형)
준비 큐의 순서를 무시하고, 프로세스에 우선순위를 할당하여 우선순위가 높은 프로세스에 CPU를 할당한다.
우선순위는 비선점형 방식과 선점형 방식에 모두 적용할 수 있으므로, 우선순위 스케줄링도 비선점형과 선점형 방식으로 나뉜다.
또한 위에서 언급한 대로 고정 우선순위 알고리즘과 변동 우선순위 알고리즘으로 나뉜다.
우선순위 스케줄링은 여전히 아사 현상이 발생하며, 프로세스의 우선순위를 바꾸는 경우 오버헤드가 발생하여 효율이 떨어진다.
그러나 우선순위는 시스템의 효율성이 아닌 프로세스의 중요도를 기준으로 정해지는데, 이는 커널 프로세스가 일반 프로세스보다 먼저 실행되어야 한다는 점을 떠올리면 쉽게 이해할 수 있다.
🔑 다단계 큐 스케줄링 (선점형)
우선순위에 따라 준비 큐를 여러 개 사용하는 방식으로, 큐에 삽입되는 것만으로 우선순위가 결정된다.
각 단계의 큐에 라운드 로빈 방식을 사용하며, 우선순위에 변화가 없다.
또한 다단계 스케줄링은 우선순위에 따라 다양한 스케줄링이 가능하다.
빠른 응답이 중요한 전면 프로세스는 타임 슬라이스를 작게하고, 후면 프로세스는 FCFS 방식으로 처리하는 형태가 가능하다.
그러나 우선순위가 높은 상위 큐 프로세스의 작업이 끝날때까지 하위 큐 프로세스의 작업이 지연되는데,
이를 해결하는 방식이 다단계 피드백 큐 스케줄링이다.
🔑 다단계 피드백 큐 스케줄링 (선점형)
CPU를 사용한 후, 프로세스는 원래의 큐로 돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.
다단계 피드백 큐 스케줄링에서는 프로세스가 CPU를 한 번 할당받을 때마다 프로세스의 우선순위가 낮아지며,
이를 통해 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화한다.
물론, 우선순위가 낮아지더라도 커널 프로세스가 일반 프로세스의 큐에 삽입되지는 않는다.
중요한 특징으로, 우선순위에 따라 타임 슬라이스의 크기가 다르다.
이는 우선순위가 낮은 프로세스의 실행 기회를 확대하기 위함이며, CPU를 어렵게 얻은 프로세스가 조금 더 오래 실행되는 형태이다.
결국 우선순위가 가장 낮은 큐의 프로세스는 타임 슬라이스가 무한, 즉 FCFS 스케줄링 방식으로 동작한다.
5️⃣ 인터럽트 처리
과거에는 CPU가 직접 입출력장치에서 데이터를 가져오는 폴링 방식을 사용했으나,
현대 운영체제는 CPU가 입출력을 요청하고 입출력이 완료되면 이벤트를 발생시키는데, 이를 인터럽트라고 한다.
동기적 인터럽트, 비동기적 인터럽트
- 동기적 인터럽트 : 프로세스가 실행 중인 명령어로 인해 발생하는 인터럽트. 사용자 인터럽트라고도 한다.
- 입출력장치에 의한 인터럽트, 프로세스 중단 인터럽트, 메모리 overflow 등으로 인해 발생한다.
- 비동기적 인터럽트 : 하드웨어 오류로 인해 발생하는 인터럽트
✔️ 인터럽트 처리 과정
인터럽트에는 해당 인터럽트가 발생하면 어떤 일을 할지도 정의되어 있다.
즉, 인터럽트 번호와 번호에 붙어 있는 함수로 이루어져 있다.
시스템에는 많은 인터럽트가 존재하기 때문에 각 인터럽트에는 고유 번호가 있고,
동시에 발생하는 인터럽트를 처리하기 위해 인터럽트 벡터를 활용한다.
인터럽트 벡터에는 각 인터럽트를 처리하는 함수가 연결되어 있다.
인터럽트 처리 과정을 정리하면 아래와 같다.
- 인터럽트가 발생하면 현재 실행 중인 프로세스는 일시 정지되고, 재시작을 위해 프로세스 관련 정보를 저장한다.
- 인터럽트의 우선순위를 고려하여 인터럽트 처리 순서를 결정한다.
- 처리할 인터럽트가 결정되면, 인터럽트 벡터에 등록된 함수가 실행되어 해당 함수의 명령을 수행한다.
- 인터럽트 처리를 마치면 일시 정지되었던 프로세스가 재시작하거나 종료된다.
👏 마무리
CPU 스케줄링에 관해 자세히 알아보았다.
이전 포스팅 (1) ~ (3)까지는 OS의 전체적인 그림을 살펴봤다면,
본 포스팅부터는 세부적인 동작 방식에 대해 알아볼 예정이다.
다음 포스팅에서는 프로세스 간 통신에 대해 알아보자.
참고 자료
💕좋아요와 댓글은 큰 힘이 됩니다.💕
