📌 스케줄링 알고리즘
비선점형 알고리즘은 프로세스가 CPU를 할당받으면 작업이 끝날 때까지 CPU를 놓지 않기 때문에 효율이 떨어져서 지금은 거의 사용되지 않습니다. 선점형 알고리즘은 시분할 시스템을 고려하여 만들어진 알고리즘으로, 어떤 프로세스가 CPU를 할당 받아 실행 중이라도 운영체제가 CPU를 강제로 빼앗을 수 있습니다.
1. 스케줄링 알고리즘의 선택 기준
어떤 스케줄링 알고리즘이 효율적인지 파악하려면 평가 기준이 있어야 합니다.
- CPU 사용률 : 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법입니다.
- 처리량 : 단위 시간당 작업을 마친 프로세스의 수로, 이 수치가 클 수록 좋은 알고리즘입니다.
- 대기 시간 : 대기 시간은 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간으로, 이 시간이 짧을수록 좋습니다.
- 응답 시간 : 응답 시간은 프로세스 시작 후 첫 번째 또는 반응이 나올 때까지 걸리는 시간으로, 이 시간 역시 짧을수록 좋습니다.
- 반환 시간 : 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간입니다. 반환 시간은 대기 시간과 실행 시간을 더한 값입니다.
CPU 알고리즘의 효율성을 평가할 때 사용률과 처리량은 계산하기가 어려워 주로 대기 시간, 응답 시간, 반환 시간을 계산합니다.
스케줄링 알고리즘의 성능을 비교할 때는 주로 평균 대기 시간을 봅니다.
평균 대기 시간을 알고리즘의 절대적인 성능을 보여주는 지표로 보지 말고, 알고리즘이 어떻게 작동하는지 파악하는 도구 정도로만 생각하면 좋을 것 같습니다.
2. FCFS 스케줄링
동작 방식
FCFS(First Come First Served) 스케줄링은 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식으로, 선입선출 스케줄링이라고도 합니다.
초기의 일괄 작업 시스템에서 사용되던 FCFS 스케줄링은 프로세스가 큐에 도착한 순서대로 실행되며 비선점형 방식이기 때문에 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있습니다. 게다가 큐가 하나라 모든 프로세스의 우선순위가 동일합니다.
FCFS는 FIFO(First In First Out) 라고도 하는데, 일반적으로 FIFO는 큐를 가리키는 말이기 때문에 이와 구분하기 위해 스케줄링 알고리즘에서는 FCFS라고 부릅니다.
성능
FCFS 스케줄링의 성능을 평균 대기 시간으로 평가해보려면, 평균 대기 시간은 작업을 시작할 때까지 전체 프로세스가 대기한 시간의 평균값으로, 시스템의 모든 프로세스가 작업을 요청하여 실제로 작업을 시작할 때까지 기다린 시간을 합한 후 프로세스의 수로 나누어 구합니다.
평가
FCFS 스케줄링 알고리즘은 단순하고 공평하지만, 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다리느라 시스템의 효율성이 떨어집니다. 이러한 문제를 콘보이 효과(convoy effect) 또는 호위 효과라고 합니다. 컨베이어 벨트에 작업물이 한 줄로 늘어서 있을 때 앞의 작업이 오래 걸려서 뒤의 작업이 지연되는 현상과 같습니다.
3. SJF 스케줄링
동작 방식
SJF(Shortest Job First) 스케줄링은 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식으로, 최단 작업 우선 스케줄링이라고도 합니다.
SJF 스케줄링에서는 프로세스에 CPU를 배정할 때 시간이 오래 걸리는 작업이 앞에 있고 간단한 작업이 뒤에 있으면 그 순서를 바꾸어 실행합니다.
성능
평가
SJF 스케줄링은 작은 작업을 먼저 실행하기 때문에 시스템의 효율성이 좋아집니다. 이러한 장점에도 불구하고 SJF 스케줄링은 다음과 같은 이유로 사용하기가 어렵습니다.
-
운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵습니다.
현대의 프로세스는 사용자와 빈번하게 상호작용하기 때문에 프로그램 종료 시간을 파악하기 어렵습니다.
-
SJF 알고리즘은 공평성에 위배됩니다.
작업 시간이 길다는 이유만으로 계속 뒤로 밀린다면 공평성이 현저하게 떨어집니다.
공평성 위배 문제는 에이징(나이 먹기) (aging)으로 완화할 수 있습니다. 에이징은 프로세스가 양보할 수 있는 상한선을 정하는 방식입니다. 프로세스가 자신의 순서를 양보할 때마다 나이를 한살씩 먹어 최대 몇 살까지 양보하도록 규정하는 방식입니다.
4. HRN 스케줄링
동작 방식
HRN(Highest Response Ratio Next) 스케줄링은 SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘으로, 최고 응답률 우선 스케줄링이라고도 합니다. SJF 스케줄링은 프로세스의 실행 시간이 판단 기준이기 때문에 항상 적은 시간을 사용하는 프로세스에 우선권이 주어지지만, HRN 스케줄링은 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링하는 방식입니다.
성능
HRN 스케줄링은 우선순위를 정할 때 대기 시간을 고려함으로써 아사 현상을 완화합니다.
평가
HRN 스케줄링은 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려하여 아사 현상을 완화합니다. 그러나 여전히 공평성이 위배되어 많이 사용되지는 않습니다.
5. 라운드 로빈 스케줄링
동작 방식
'순환 순서 방식'으로 번역되는 라운드 로빈(RR, Round Robin) 스케줄링은 한 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업을 하다가 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식입니다. 선점형 알고리즘 중 가장 단순하고 대표적인 방식으로, 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행됩니다.
라운드 로빈 스케줄링은 FCFS 스케줄링과 유사한데, 차이점은 각 프로세스마다 CPU를 사용할 수 있는 최대 시간, 즉 타임 슬라이스가 있다는 것입니다.
성능
라운드 로빈 스케줄링 같은 선점형 방식에서는 프로세스가 CPU를 일정 시간 동안 사용한 후 다른 프로세스에 넘겨주어야 하므로 앞의 긴 작업을 무작정 기다리는 콘보이 효과가 줄어듭니다.
평가
앞서 계산한 FCFS 스케줄링의 평균 대기 시간과 라운드 로빈 스케줄링의 평균 대기 시간을 비교해 보면 미세하게 라운드 로빈 스케줄링이 앞섭니다. 그러나 라운드 로빈 스케줄링이 FCFS 스케줄링보다 평균 대기 시간이 적다고 단정할 수는 없습니다.
이처럼 라운드 로빈 스케줄링과 FCFS 스케줄링의 평균 대기 시간이 같다면 라운드 로빈 스케줄링이 더 비효율적인 알고리즘입니다. 라운드 로빈 스케줄링 같은 선점형 방식에서는 문맥 교환 시간이 추가되기 때문입니다. 문맥 교환 시간을 고려하여 라운드 로빈 스케줄링의 평균 대기 시간을 산출하면 앞의 계산 값보다 좀 더 크게 나옵니다.
6. SRT 우선 스케줄링
동작 방식
SRT(Shortest Remaining Time) 스케줄링은 SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식으로 최소 잔류 시간 우선 스케줄링이라고도 합니다. SRT 스케줄링은 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남은 작업 시간이 가장 적은 프로세스를 선택합니다.
성능
평가
SJF 스케줄링과 SRT 스케줄링의 평균 대기 시간을 비교해 보면 SRT 스케줄링의 평균 대기 시간이 짧습니다. 하지만 SRT 스케줄링은 좋은 알고리즘이 아닙니다. 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야 하므로 SJF 스케줄링에는 없는 작업이 추가됩니다. 또한 SRT 스케줄링은 SJF 스케줄링과 마찬가지로 운영체제가 프로세스 종료 시간을 예측하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 않습니다.
7. 우선순위 스케줄링
동작 방식과 성능
프로세스는 중요도에 따라 우선순위를 갖는데 이러한 우선순위를 반영한 스케줄링 알고리즘이 우선순위 스케줄링입니다.
우선순위는 비선점형 방식과 선점형 방식에 모두 적용할 수 있으므로 우선순위 스케줄링도 비선점형과 선점형 방식으로 모두 구현할 수 있습니다.
- (비선점형 방식) SJF 스케줄링
- (비선점형 방식) HRN 스케줄링
- (선점형 방식) SRT 스케줄링
- 고정 우선순위 알고리즘
- 변동 우선순위 알고리즘
평가
우선순위 스케줄링은 준비 큐에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스에 먼저 CPU를 할당하므로 공평성을 위배하고 아사 현상을 일으킨다는 문제가 있습니다. 또한 프로세스의 우선순위를 매번 바꿔야 하기 때문에 오버헤드가 발생하여 시스템의 효율성이 떨어집니다.
따라서 우선순위는 시스템의 효율성보다 프로세스의 중요도에 따라 정해집니다.
8. 다단계 큐 스케줄링
다단계 큐(MLQ, Multi-Level Queue) 스케줄링은 우선순위에 따라 준비 큐를 여러 개 사용하는 방식입니다. 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입됩니다.
다단계 큐 스케줄링은 우선순위에 따라 다양한 스케줄링이 가능한 선점형 방식입니다. 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스보다 먼저 작동할 수 있을 뿐더러 우선순위에따라 타임 슬라이스를 조절하여 작업 효율을 높일 수도 있습니다.
다단계 큐 스케줄링에서는 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에 하위 큐 프로세스의 작업을 할 수 없습니다. 우선순위가 높은 프로세스 때문에 우선순위가 낮은 프로세스의 작업이 연기되는데, 이러한 문제를 해결하기 위해 제안된 것이 다단계 피드백 큐 스케줄링입니다.
9. 다단계 피드백 큐 스케줄링
다단계 피드백 큐(MLFQ, Multi-Level Feedback Queue) 스케줄링은 우선순위가 낮은 프로세스에 불리한 다단계 큐(MLQ) 스케줄링의 문제점을 보완한 방식입니다. 다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링과 기본 형태가 같아 우선순위를 가진 여러 개의 큐를 사용합니다. 하지만 다단계 큐 스케줄링은 각 단계의 큐에 라운드 로빈 방식을 사용하고 우선순위에는 변화가 없는 데 반해, 다단계 피드백 큐 스케줄링은 CPU를 사용한 후 프로세스의 우선순위가 낮아집니다. CPU를 사용한 후의 프로세스는 원래의 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어갑니다.
다단계 피드백 큐 스케줄링에서는 프로세스가 CPU를 한 번씩 할당 받아 실행될 때마다 프로세스의 우선순위를 낮춤으로써, 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화합니다.
다단계 피드백 큐 스케줄링의 또 다른 특징은 우선순위에 따라 타임 슬라이스의 크기가 다르다는 것입니다.
결국 다단계 피드백 큐 스케줄링에서 마지막 큐에 있는(우선순위가 가장 낮은) 프로세스는 무한대의 타임 슬라이스를 얻습니다. 무한대의 타임 슬라이스를 얻는다는 것은 프로세스가 실행상태에 들어가면 CPU를 빼앗기지 않고 끝까지 작업을 마친다는 의미입니다. 그러므로 다단계 피드백 큐 스케줄링에서 마지막 큐는 들어온 순서대로 작업을 마치는 FCFS 스케줄링 방식으로 동작합니다.
다단계 피드백 큐 스케줄링은 오늘날 운영체제가 CPU 스케줄링을 할 때 일반적으로 사용하는 방식입니다.
📌 인터럽트 처리
1. 인터럽트의 개념
오늘날의 프로그래밍에서는 버튼이 눌렸는지 안 눌렸는지 주기적으로 확인하는 대신 버튼이 눌리면 프로세스에 알려주는데 이를 이벤트 드리븐(event driven)이라고 합니다. 하지만 다양한 입출력 장치가 개발되어 운영체제가 모든 입출력을 관리하기 어려워지자 이벤트 드리븐 방식과 마찬가지로 입출력을 요청하고 입출력이 완료되면 이벤트를 발생시켜 이 사실을 알리게 되었는데, 이를 인터럽트라고 합니다.
2. 동기적 인터럽트와 비동기적 인터럽트
인터럽트는 프로세스가 실행 중인 명령어로 인해 발생하는 동기적 인터럽트(synchronous interrupt)와 실행 중인 명령어와 무관하게 발생하는 비동기적 인터럽트(asynchronous interrupt)로 나눌 수 있습니다.
3. 인터럽트 처리 과정
시스템에는 많은 인터럽트가 존재하고 각각의 인터럽트에는 고유 번호, 즉 인터럽트 번호가 있습니다. 윈도우에서는 이 번호를 IRQ라고 하며, 시스템에 인터럽트가 발생하면 IRQ로 인터럽트를 식별합니다.
인터럽트는 한순간에 여러 개가 동시에 발생하기도 합니다. 이렇게 동시에 발생하는 인터럽트를 하나로 묶어서 처리하는 개념이 인터럽트 벡터입니다.
인터럽트 벡터에는 각 인터럽트를 처리하는 함수가 연결되어 있습니다. 해당 인터럽트가 발생하면 어떤 일을 처리할 것인지가 이 함수에 정의되어 있는데 이를 인터럽트 핸들러(interrupt handler)라고 부릅니다.
4. 인터럽트와 이중 모드
사용자 프로세스는 시스템 호출을 요청한 후 대기 상태로 전환되고 커널 프로세스는 요청받은 작업을 처리합니다. 즉 사용자 모드에서 커널 모드로 전환되는데, 이와 같이 운영체제가 두 모드를 전환하며 일을 처리하는 것을 이중 모드(dual mode)라고 합니다.
사용자가 커널 모드로 진입하는 경우는 두 가지입니다. 하나는 시스템 호출을 사용한 경우, 다른 하나는 인터럽트를 발생시킨 경우입니다. 시스템 호출에 의해 커널 모드로 진입하는 것은 사용자 프로세스가 원해서 진입하는 것이기 때문에 자발적(voluntary)이지만 인터럽트에 의해 커널 모드로 진입하는 것은 비자발적(non-voluntary)입니다. 어떤 프로세스가 인터럽트를 발생시켰다는 것은 잘못된 명령을 수행하여 동기적 인터럽트가 발생한 것이므로 프로세스가 강제 종료됩니다. 그러므로 사용자 프로세스가 자발적으로 커널 모드에 진입할 수 있는 유일한 수단은 시스템 호출입니다.
