이 글은 혼자 공부하는 컴퓨터 구조+운영체제 교재와 강의를 참고하여 정리한 글입니다. 오타나, 잘못된 내용이 있으면 언제든지 알려주세요! 감사합니다.😊
CPU 스케줄링
CPU 스케줄링 개요
모든 프로세스는 CPU를 필요로 하고 모든 프로세스는 먼저 CPU를 사용하고 싶어 한다. 이런 프로세스들에게 공정하고 합리적으로 CPU 자원을 할당하기 위해 운영체제는 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 기다리게 할지 결정한다.
- 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것을 CPU 스케줄링(CPU scheduling)이라 한다.
- CPU 스케줄링은 컴퓨터 성능과 직결되는 아주 중요한 문제이다.
프로세스 우선순위
프로세스들에게 공정하게 CPU를 배분하려면 어떻게 해야 할까?
단순히 생각하면 CPU를 사용하고 싶다고 먼저 요청한 프로세스 순서대로 CPU를 이용하게 하는 방법이 있다.
하지만 이는 좋은 방법이 아니다. 왜냐하면 프로세스마다 우선순위가 다르기 때문이다. 즉, 빨리 처리해야 하는 프로세스가 있기 때문이다.
참고: CPU를 사용하는 작업을 CPU 버스트(CPU burst)라고 하고, 입출력장치를 기다리는 작업을 입출력 버스트(I/O burst)라 부른다. 즉 프로세스는 일반적으로 CPU 버스트와 입출력 버스트를 반복하며 실행된다.
- 입출력 작업이 많은 프로세스를 입출력 집중 프로세스(I/O bound process)라고 한다.
- 입출력 집중 프로세스는 실행 상태보다는 입출력을 위한 대기 상태에 더 많이 머무른다.
- CPU 작업이 많은 프로세스를 CPU 집중 프로세스(CPU bound process)라고 한다.
- CPU 집중 프로세스는 대기 상태보다는 실행 상태에 더 많이 머무른다.
- 입출력 집중 프로세스의 우선순위는 CPU 집중 프로세스의 우선순위보다 높다.
- 왜 그럴까? 대부분의 프로세스들은 CPU와 입출력장치를 모두 사용하며 실행된다. 즉, 프로세스는 실행 상태와 대기 상태를 반복하며 실행된다.
- 그런데 프로세스 종류마다 입출력장치를 이용하는 시간과 CPU를 이용하는 시간의 양에는 차이가 있다.
- 비디오 재생, 디스크 백업 작업을 담당하는 프로세스는 입출력 작업이 많다.
- 복잡한 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스는 CPU 작업이 많다.
CPU 집중 프로세스는 CPU를 많이 사용해야 하고, 입출력 집중 프로세스는 그렇지 않은데 모두 동일한 빈도로 CPU를 사용하는 것은 비합리적이다. 다음 예시를 보자.
- 입출력 집중 프로세스와 CPU 집중 프로세스가 동시에 CPU 자원을 요구했다고 가정하자.
- 이 경우 입출력 집중 프로세스를 가능한 한 빨리 실행시켜 입출력장치를 끊임없이 작동시키고, 그다음 CPU 집중 프로세스에 CPU를 할당하는 것이 더 효율적이다.
- 입출력장치가 입출력 작업을 완료하기 전까지는 입출력 집중 프로세스는 어차피 대기 상태가 될 예정이기 때문에 입출력 집중 프로세스를 먼저 처리해 버리면 다른 프로세스가 CPU를 사용할 수 있기 때문이다.
- 모든 프로세스가 CPU를 차례대로 돌아가며 사용하는 것보다 각각의 상황에 맞게 CPU를 배분하는 것이 더 효율적이다.
따라서 운영체제는 상황에 맞게, 그리고 프로세스의 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 하기 위해 프로세스마다 우선순위를 부여한다.
- 운영체제는 각 프로세스의 PCB에 우선순위를 명시하고, PCB에 적힌 우선순위를 기준으로 먼저 처리할 프로세스를 결정한다.
- 우선순위가 높은 프로세스는 더 빨리, 더 자주 실행된다.
스케줄링 큐 (scheduling queue)
PCB에 우선순위가 적혀 있지만, CPU를 사용할 다음 프로세스를 찾기 위해 운영체제가 일일이 모든 프로세스의 PCB를 찾는 것은 비효율적이다. CPU 자원에만 국한된 상황이 아니고 메모리에 적재되고 싶어 하는 프로세스, 특정 입출력장치와 보조기억장치를 사용하길 원하는 프로세스도 여러 개 있을 수도 있다. 그래서 운영체제는 프로세스들에게 '줄을 서서 기다릴 것'을 요구한다.
- 프로세스들을 모두 줄 세우고, 운영체제는 이 줄을 스케줄링 큐 (scheduling queue)로 구현하고 관리한다.
참고: 큐는 선입선출 자료구조이지만, 스케줄링에서의 큐는 반드시 선입선출 방식일 필요는 없다.
운영체제가 관리하는 대부분의 자원은 큐로 관리된다. 그래서 운영체제가 관리하는 줄, 즉 큐에는 다양한 종류가 있는데 대표적인 큐로는 준비 큐와 대기 큐가 있다.
- 준비 큐(ready queue)는 CPU를 이용하고 싶은 프로세스들이 서는 줄을 의미한다. 즉 CPU를 이용하기 위해 기다리는 줄이다.
- 준비 상태에 있는 프로세스들의 PCB는 준비 큐의 마지막에 삽입되어 CPU를 사용할 차례를 기다린다.
- 프로세스마다 우선순위가 다르기 때문에 운영체제는 우선순위가 높은 프로세스를 먼저 실행한다. 즉, 같은 큐 내에서도 우선순위별로 처리된다.
- 자기 차례가 된 프로세스는 디스패치돼서 CPU를 할당받아 실행 상태가 된다.
- 자기 실행 차례가 끝나면, 타이머 인터럽트가 발생하면 다시 준비 상태에 접어든다. 즉, 준비 큐에 삽입이 된다.
- 대기 큐(waiting queue)는 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄을 의미한다. 즉 입출력장치를 이용하기 위해 기다리는 줄이다.
- 컴퓨터에는 여러 가지 입출력장치들이 연결되어 있는 것처럼, 대기 큐도 또한 여러 개 있다.
- 이러한 여러 개의 대기 큐는 입출력장치별로 있는 경우가 많다. 즉, 같은 장치를 요구한 프로세스들은 같은 큐에서 대기하게 된다.
- 입출력이 완료되어 입출력 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾고, 이 PCB 상태를 대기 상태에서 준비 상태로 변경한 뒤 대기 큐에서 제거한다.
- 그 후 해당 PCB는 준비 큐로 이동한다.
선점형과 비선점형 스케줄링
어떠한 프로세스가 CPU를 잘 사용하고 있는데 갑자기 다른 급한 프로세스가 CPU를 지금 당장 사용하길 원한다면 어떻게 해야 할까?
이럴 경우 두 가지 선택지가 존재한다.
- 선점형 스케줄링(preemptive scheduling)
- 비선점형 스케줄링(non-preemptive scheduling)
선점형 스케줄링 (preemptive scheduling)
- 선점은 '남보다 앞서서 차지함'을 의미한다.
- 선점형 스케줄링은 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 우선순위가 더 높은 프로세스에 할당할 수 있는 스케줄링 방식을 말한다.
- 즉, 어느 하나의 프로세스가 자원 사용을 독점할 수 없는 스케줄링 방식이다.
- 프로세스마다 정해진 시간만큼 CPU를 사용하고, 정해진 시간을 모두 사용해 타이머 인터럽트가 발생하면 운영체제가 해당 프로세스부터 CPU 자원을 빼앗아 다음 프로세스에 할당하는 방식은 선점형 스케줄링의 일종이다.
- 선점형 스케줄링은 다음과 같은 장단점이 존재한다.
- 장점: 어느 한 프로세스의 자원 독점을 막고 프로세스들에게 골고루 자원을 배분할 수 있다.
- 단점: 그만큼 문맥 교환이 많이 발생하기 때문에 문맥 교환 과정에서 오버헤드가 발생할 수 있다.
비선점형 스케줄링 (non-preemptive scheduling)
- 비선점형 스케줄링은 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식을 말한다.
- 즉, 하나의 프로세스가 자원 사용을 독점할 수 있는 스케줄링 방식이다.
- 비선점형 스케줄링은 다음과 같은 장단점이 존재한다.
- 장점: 선점형 스케줄링에 비해 문맥 교환이 덜 발생하기 때문에 문맥 교환 과정에서 발생하는 오버헤드가 적다.
- 단점: 모든 프로세스가 골고루 자원을 이용하기 어렵다.
CPU 스케줄링 알고리즘
CPU 스케줄링 알고리즘의 종류는 매우 다양하고, 운영체제는 저마다 서로 다른 스케줄링 알고리즘을 사용하고 있다.
중요한 것은 각 스케줄링 알고리즘에 사용된 '아이디어'이지, '용어'가 아니다.
즉, CPU 스케줄링 알고리즘의 아이디어인 작동방식과 장단점을 기억하자.
스케줄링 알고리즘의 종류
CPU 스케줄링 알고리즘의 종류는 매우 다양하지만, 일곱 가지 CPU 스케줄링 알고리즘에 대해 알아보자.
- 선입 선처리 스케줄링 (FCFS 스케줄링)
- 최단 작업 우선 스케줄링 (SJF 스케줄링)
- 라운드 로빈 스케줄링 (RR 스케줄링)
- 최소 잔여 시간 우선 스케줄링 (SRT 스케줄링)
- 우선순위 스케줄링 (priority 스케줄링)
- 다단계 큐 스케줄링 (Multilevel queue 스케줄링)
- 다단계 피드백 큐 스케줄링 (Multilevel feedback queue 스케줄링)
선입 선처리 스케줄링
- 선입 선처리 스케줄링은 FCFS (First Come First Served) 스케줄링으로도 불린다.
- 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링 방식이다.
- 즉, CPU를 먼저 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식이다.
선입 선처리 스케줄링방식은 가장 공정해 보이지만 큰 부작용을 야기할 수 있다.
- 프로세스 A, B, C가 순서대로 준비 큐에 삽입되었다고 가정하자.
- 이럴 경우 프로세스 C는 고작 2ms를 실행하기 위해 22ms(17ms + 5ms)라는 긴 시간을 기다려야 한다.
- 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용이 존재한다. 이 부작용을 호위 효과(convoy effect)라 한다.
이러한 호위 효과를 방지하기 위해서는 어떻게 해야 할까? 단순히 생각하면 CPU 사용 시간이 긴 프로세스는 나중에 실행하고, CPU 사용시간이 짧은 간단한 프로세스를 먼저 실행하면 된다.
최단 작업 우선 스케줄링
- 최단 작업 스케줄링은 SJF (Shortest Job First) 스케줄링으로도 불린다.
- 최단 작업 스케줄링은 준비 큐에 삽입된 프로세스들 중 CPU 이용 시간이 가장 짧은 프로세스부터 실행하는 스케줄링 방식이다.
- 즉, CPU 사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식이다.
- 최단 작업 우선 스케줄링은 기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 선점형으로 구현될 수도 있다.
- 선점형 최단 작업 우선 스케줄링이 최소 잔여 시간 우선 스케줄링이다.
- 실행시간이 짧은 C와 B부터 실행하면 C는 더 이상 기다릴 필요가 없고, B는 2ms, A는 7ms만 기다리면 된다.
라운드 로빈 스케줄링
- 라운드 로빈 스케줄링은 RR(Round robin) 스케줄링으로도 불린다.
- 라운드 로빈 스케줄링은 선입 선처리 스케줄링에 타임 슬라이스(time slice)라는 개념이 더해진 스케줄링 방식이다.
- 타임 슬라이스란 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미한다.
- 즉, 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링이다.
- 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되 정해진 시간만큼만 CPU를 이용한다.
- 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입한다. 이때 문맥 교환이 발생한다.
- 타임 슬라이스가 4ms인 라운드 로빈 스케줄링을 한다고 가정하자.
- A는 4ms만큼 실행했는데 아직 완료되지 않았기 때문에 문맥 교환이 발생한다.
- B는 3ms만큼만 실행하면 된다. 굳이 타임 슬라이스 전체를 쓸 필요 없다. 프로세스 B를 완료하고 문맥 교환이 발생한다.
- C도 A와 마찬가지로 4ms만큼 실행했는데 아직 완료되지 않았기 때문에 문맥 교환이 발생한다.
- 라운드 로빈 스케줄링에서는 타임 슬라이스 크기가 매우 중요하다.
- 타임 슬라이스가 지나치게 클 경우에는 사실상 선입 선처리 스케줄링과 다를 바가 없기 때문에 호위 효과가 생길 수도 있다.
- 타임 슬라이스가 지나치게 작을 경우에는 문맥 교환에서 발생하는 오버헤드 때문에 CPU의 부담이 커지게 된다.
최소 잔여 시간 우선 스케줄링
- 최소 잔여 시간 우선 스케줄링은 SRT(Shortest Remaining Time) 스케줄링으로도 불린다.
- 최소 잔여 시간 우선 스케줄링은 최단 작업 우선 스케줄링과 라운드 로빈 알고리즘을 합친 스케줄링 방식이다.
- 최단 작업 우선 스케줄링은 작업 시간이 짧은 프로세스부터 처리하는 스케줄링 방식이다.
- 라운드 로빈 알고리즘은 정해진 타임 슬라이스만큼 돌아가며 사용하는 스케줄링 방식이다.
- 즉, 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스를 선택한다.
우선순위 스케줄링
- 우선순위 스케줄링은 프로세스들에게 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 방식이다.
- 만약, 우선순위가 같은 프로세스들이 있다고 하면 선입 선처리로 스케줄링이 된다.
- 최단 작업 우선 스케줄링 방식이나, 최소 잔여 시간 우선 스케줄링 방식은 넓은 의미에서 우선순위 스케줄링의 일종으로 볼 수 있다.
- 최단 작업 우선 스케줄링은 작업 시간이 짧은 프로세스에 높은 우선순위를 부여하는 방식으로 볼 수 있기 때문이다.
- 최소 잔여 시간 우선 스케줄링은 남은 시간이 짧은 프로세스에 높은 우선순위를 부여하는 방식으로 볼 수 있기 때문이다.
우선순위 스케줄링 방식은 근본적인 문제, 부작용을 가지고 있다.
- 우선순위 스케줄링의 근본적인 문제점은 기아(starvation) 현상이다.
- 기아 현상은 우선순위가 높은 프로세스를 우선하여 처리하여 우선순위가 낮은 프로세스는 (준비 큐에 먼저 삽입되었음에도 불구하고) 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기될 수 있다.
- 즉, 우선순위가 낮은 프로세스의 실행은 계속 뒤로 밀리고, 우선순위가 높은 프로세스만 주구장창 실행되는 것이다.
이러한 기아 현상을 해결하기 위해서는 어떻게 해야 할까?
- 기아 현상을 방지하기 위한 대표적인 기법으로 에이징(aging)이 있다.
- 에이징은 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식이다.
- 즉, 대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법이다.
- 우선순위가 낮아도 언젠가는 우선순위가 높아진다.
다단계 큐 스케줄링
- 다단계 큐 스케줄링은 Multilevel queue 스케줄링으로도 불린다.
- 다단계 큐 스케줄링은 우선순위 스케줄링의 발전된 형태로, 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식이다.
- 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리한다.
- 만약 우선순위가 가장 높은 큐가 비어 있으면 그다음 우선순위 큐에 있는 프로세스를 처리한다.
- 이렇게 큐를 여러 개 두면 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편한다.
- 어떤 큐에는 CPU 집중 프로세스가 삽입된다. (우선순위가 비교적 높아야 함)
- 어떤 큐에는 입출력 집중 프로세스가 삽입된다. (우선순위가 비교적 낮아도 상관없음)
- 또한 큐별로 타임 슬라이스를 여러 개 지정할 수 있고, 큐마다 다른 스케줄링 알고리즘을 사용할 수 있다.
- 어떤 큐에서는 타임 슬라이스를 크게, 어떤 큐에서는 타임 슬라이스를 작게 사용한다.
- 어떤 큐에는 선입 선처리 스케줄링을 사용하고, 어떤 큐에서는 라운드 로빈 스케줄링을 사용한다.
이러한 다단계 큐 스케줄링에도 문제점이 있다.
다단계 큐 스케줄링에서는 기본적으로 프로세스가 큐간의 이동이 불가능하다.
따라서, 우선순위가 낮은 프로세스는 계속해서 우선순위가 낮은 큐에서만 머무를 수밖에 없어 기아 현상이 발생한다.
이러한 다단계 큐 스케줄링에서의 기아 현상을 어떻게 해결할까?
다단계 피드백 큐 스케줄링
- 다단계 피드백 큐 스케줄링은 Multilevel feedback queue 스케줄링으로도 불린다.
- 다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링의 발전된 형태이다.
- 큐 간의 이동이 가능한 다단계 큐 스케줄링이다.
- 다단계 큐 스케줄링에서는 기본적으로 큐간의 이동이 불가능하여 우선순위 낮은 프로세스는 계속해서 실행이 연기되는 문제점이 발생한다. 즉, 기아 현상이 발생할 수 있다.
- 새로 준비 상태가 된 프로세스가 있다면 우선 우선순위가 가장 높은 우선순위 큐에 삽입되고 일정 시간(타임 슬라이스) 동안 실행된다.
- 만약 프로세스가 해당 큐에서 실행이 끝나지 않았다면 다음 우선순위 큐에 삽입되어 실행된다.
- 그리고 또 해당 큐에서 실행이 끝나지 않았다면 또 다음 우선순위 큐에 삽입되어 실행된다.
- 결국, CPU를 오래 사용해야 하는 프로세스는 점차 우선순위가 낮아진다.
- 즉, 자연스럽게 CPU를 비교적 많이 사용해야 하는 CPU 집중 프로세스들은 우선순위가 낮아지고, CPU를 비교적 적게 사용하는 입출력 집중 프로세스들은 우선순위가 높아진다.
- 다단계 피드백 큐 스케줄링에서도 에이징 기법을 적용할 수 있다.
- 낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시키는 에이징 기법을 적용해 기아 현상을 해결할 수 있다.
- 즉, 다단계 피드백 큐 스케줄링은 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동시킬 수 있는 알고리즘이다.
- 다단계 피드백 큐 스케줄링은 구현이 복잡하지만, 가장 일반적인 CPU 스케줄링 알고리즘이다.
'Computer Science > 운영체제' 카테고리의 다른 글
| [운영체제] 교착 상태 (0) | 2023.05.25 |
|---|---|
| [운영체제] 프로세스 동기화 (0) | 2023.05.13 |
| [운영체제] 파이썬으로 프로세스와 스레드 다루기 (0) | 2023.05.02 |
| [운영체제] 프로세스와 스레드 (0) | 2023.05.02 |
| [운영체제] 운영체제의 큰 그림 (0) | 2023.04.23 |
