[운영체제] 3강 - 프로세스 스케줄링

✅ 1. 프로세스 스케줄링

(1) 프로세스 스케줄링 이란?

• 프로세스 스케줄링: 프로세스가 여러 개인 경우에 프로세스 처리순서를 결정하는 것을 의미함.

(2) 프로세스 스케줄링 단계

• 작업 큐: 시스템에 작업이 들어오면 큐에 프로세스 작업들이 쌓이게 됨.
• ** 쉽게말해, 보조기억장치에 작업 큐에서 대기하고 있기 때문에 메모리를 차지하지 않고 대기하는 상태를 의미한다. **
• 상위단계 스케줄링: 프로세스들 중에서 어떤 프로세스를 메모리에 적재 할 지 결정하는 단계임. (내부 스케줄링 알고리즘 동작)
• 준비 큐: 상위단계 스케줄링의 승인 결정에 의해 프로그램이 메모리에 로드되는데, 그 결과로 준비 큐에 프로세스가 쌓임.
• 하위단계 스케줄링: 준비 큐에 들어와 있는 프로세스들 중에 CPU를 점유 할 프로세스를 결정하는 단계임.
• 중간단계 스케줄링: 시스템에 너무 많은 프로세스가 올라와서 메모리가 부족해질 때, 운영체제가 프로세스들을 대기시킴.
• ** 쉽게 말해, 실행 중에 프로세스가 갑자기 메모리를 많이 쓰거나 새로운 프로세스가 계속 들어오면 메모리가 꽉 찰 수 있는데, 이때 메모리 부족으로 시스템이 뻗는 것을 방지하기 위함임. **
• 핵심은 하위단계 스케줄링이며, 나머지 시스템은 운영체제에 따라서 존재 할 수도 안 할 수도 있음.

• 하위단계 스케줄링: 준비 큐에 들어와 있는 프로세스들 중 CPU를 점유 할 프로세스를 결정하는 단계이며, 이곳에서 사용이 되는 스케줄러 알고리즘들이 "CPU 스케줄러 알고리즘" 들임.
• 디스패처: 운영체제 내부의 코드 기능이며, CPU 스케줄러가 선택한 프로세스에게 CPU 제어권을 실제로 넘겨주는 운영체제의 실행 모듈이다. 즉, CPU 스케줄링 알고리즘에 따라 실행 될 프로세스가 결정이 되면, 이후에 디스패처가 해당 프로세스 CPU 제어권을 넘겨 처리 시켜줌.

(3) 스케줄링 기본 목표

• 스케줄링의 기본 목표는 공정성과 균형이며, 이러한 목표를 통해 스케줄링 알고리즘을 구성 할 수 있음.
• 공정성: 모든 프로세스가 공정하게 CPU 제어권을 받도록 유도를 해줘야하는 원칙으로 보면 됨.
• 균형: 모든 하드웨어들 간의 자원이 놀지 않고 골고루 바쁘게 돌아가도록 만드는 것을 의미함.

(4) 운영체제의 유형에 따른 스케줄링의 목표

[ 일괄처리 운영체제 ]

• 프로세스들을 모아놓고 한 번에 처리하는 운영체제이다.
• 처리량의 극대화: 프로세스들을 한 번에 처리하기 때문에, 처리량을 높이는 것을 목표로 가지고 있음.
• 반환시간의 최소화: 현재 처리되는 프로세스에 모든 자원과 시간을 투자해 최대한 빨리 끝낼 수 있도록 반환시간을 최소화 하는 것을 목표로함.
• CPU 활용의 극대화: 프로세스들이 빨리 처리 될 수 있도록 CPU 활용을 극대화 하는것이 목표임.

[ 시분할 운영체제 ]

• 프로세스들이 아주 짧은 시간만 CPU를 점유해 프로세스를 번갈아가면서 실행되는 운영체제를 의미함.
• 빠른 응답시간: 프로세스들이 번갈아 수행되기 때문에 응답시간을 최소화 시켜 여러 프로세스들이 동시에 잘 작동되도록 하는 것을 목표로 삼고 있음.
• 과다한 대기시간 방지: 특정 프로세스의 처리 시간이 길수록 다른 프로세스들은 대기를 오래해야하는데, 공정성의 문제가 되므로, 과다한 대기시간에 대한 방지를 목표로 삼고 있음.

[ 실시간 운영체제 ]

• 정해진 시간 안에 반드시 작업을 끝내는 것을 보장하도록 설계된 운영체제를 의미함.
• 처리기한 맞춤: 프로세스 하나의 작업 완료가 정해진 시간 내에 반드시 처리됨을 목표로 삼고 있음.

(5) 스케줄링 정책

• 스케줄링 정책이란, 운영체제가 한정된 시스템 자원을 여러 프로세스나 스레드에게 어떤 순서로, 얼마나 오랫동알 할당할지 결정하는 규칙이며, 크게 선점 스케줄링, 비선점 스케줄링으로 나뉨.

(6) 스케줄링 정책 - 선점 스케줄링 정책

• 실행 중인 프로세스가 있을 때, 특정 우선순위 등의 조건에 따라서 시간이 할당됨에도 불구하고 CPU 를 뻣어가는 방식임.
• ** 즉, 높은 우선순위의 프로세스를 우선 처리해야 하는 경우에 유용한 방식임. **
• 실시간, 시분할 시스템에서 사용이 되며, 문맥 교환에 따른 오버헤드가 발생 할 수 있음.
• 즉, 문맥 교환이 빠르게 잘 실행되도록 운영체제가 만들어져 있어야 함.

• 문맥: 해당 프로세스의 레지스터 값 또는 상태 등을 문맥이라 하며, 이러한 문맥은 PCB에 저장이 됨.
• 문맥 교환: context switching 이라고 하며, CPU가 현재 실행하고 있는 프로세스의 문맥을 PCB에 저장하고 다른 프로세스가 수행이 된 후 이전의 PCB를 통해 문맥을 복원하는 작업을 함.

(7) 스케줄링 정책 - 비선점 스케줄링 정책

• 비선점 스케줄링 정책은 사용중인 CPU를 뺏을 수 없는 정책을 의미함.
• 쉽게 말해, 실행이 시작된 프로세스는 준비상태로 전이는 시키지 못하지만, 대기상태나 종료상태로는 전이가 될 수 있음.
• 정확히는 I/O 입출력 등의 작업으로인해 스스로 CPU를 내려놓고 대기 상태로 가는건 가능하지만 타의에 의해서는 불가능함.
• 문맥 교환이 따로 없어 오버헤드는 발생하지 않지만, 프로세스간의 대기 상태가 길어질 수 있음.

(8) 프로세스의 평가 기준

• ** 운영체제의 스케줄링 성능을 평가할 때 핵심이 되는 두 가지 지표를 의미한다. **
• 평균대기시간: 프로세스가 준비 큐에 도착한 후, CPU를 할당받기 위해 기다린 시간의 총합을 의미함.
• 평균반환시간: 프로세스가 준비 큐에 도착한 시점부터 모든 실행을 마치고 종료될 때까지 걸린 전체 시간을 의미함.
• 두개다 모든 프로세스의 대기 시간 또는 반환 시간의 합계를 프로세스의 개수로 나눈 값임.
• ** 또한, 이 두가지의 지표 모두 "낮을수록" 좋은 스케줄링이라고 판단을 함. **

• A 프로세스의 대기시간은 준비큐에 머문 시간인 0~2 = 2가 될 것이다.
• A 프로세스의 반환시간은 준비큐에 머문 시간 + 처리 된 후 반환 시간인 0~4 = 4가 될 것이다.
• B 프로세스의 대기시간은 준비큐에 머문 시간인 1~4 = 3가 될 것이다.
• B 프로세스의 반환시간은 준비큐에 머문 시간 + 처리 된 후 반환 시간인 1~7 = 6이 될 것이다.
• ** 즉, 평균대기시간은 A프로세스, B프로세스의 대기 시간을 더한 값이 2+3 에 2를 나누면 2.5를 얻을 수 있음. **
• ** 평균반환시간도 마찬가지로 A, B 프로세스 반환시간 4+6 / 2 = 5 를 얻을 수 있음. **

---

✅ 2. 스케줄링 알고리즘

(1) FCFS 스케줄링

• First-Come First-Served: 먼저 들어온 프로세스의 작업을 먼저 처리를 해주는 방식임.
• 비선점 방식: 프로세스가 CPU를 할당 받으면 스스로 대기 상태로 가지 않는 이상 CPU를 계속해서 점유하고 있는 상태임.
• 준비 큐에 도착한 순서에 따라서 디스패처가 디스패치를 해줌.

• A,B,C,D 프로세스가 순서대로 준비 큐에 들어왔다고 가정하면, A를 우선적으로 수행하고 다음 B,C,D 순으로 프로세스를 CPU가 처리를 하게 됨.

• 장점: 간단한 큐 자료구조로 스케줄링 알고리즘을 구현 할 수 있음.
• 단점: 비선점 방식이다 보니, 짧은 프로세스가 긴 프로세스를 기다릴 수 있으며, 이중에서 중요한 프로세스가 나중에 수행될 가능성이 존재함. 또한, 프로세스들의 도착순서에 따라 평균반환시간이 크게 변할 수 있음.
• 그렇기 때문에 시분할 운영체제, 실시간 운영체제에는 적합하지 않은 방식임.

(2) SJF 스케줄링

• Shortest Job First: 가장 짧게 처리할 수 있는 프로세스를 먼저 처리해주는 방식임.
• 비선점 방식: 프로세스가 CPU를 할당 받으면 스스로 대기 상태로 가지 않는 이상 CPU를 계속해서 점유하고 있는 상태임.
• ** 일반적으로 과거 프로세스 사용 데이터를 기반으로 한 통계적 예측으로 짧은 것을 판단함. **

• 비선점 방식이므로, A 프로세스가 CPU를 점유하게 되고, 준비 큐에 B -> C가 들어온 상태에서 만약 C가 더 짧게 처리를 할 수 있을 것 같다고 판단(CPU 사이클 수가 적은 것)이 되면 우선순위를 높여서 넣어주게 되고, D도 마찬가지로 C보다는 길기 때문에 다음에 넣어지지만 B 보다는 CPU 사이클이 짧기 때문에 B보다 우선순위가 높아짐.

• 장점: 일괄처리 환경은 애초에 프로세스의 작업들을 모아놓고 처리를 하기 때문에 해당 프로세스가 얼마나 걸릴지 어느정도는 예상을 할 수 있음. 그렇기 때문에 일괄처리 환경에서 구현하기가 쉬움.
• 단점: 먼저 처리할 프로세스의 CPU 시간을 정확하게 예상할 수 없으며, 가장 긴 프로세스는 평생 수행이 안될 가능성이 있음.

(3) SRT 스케줄링

• Shortest Remaining Time: 스케줄링은 준비 큐에서 기다리는 프로세스 중 남은 실행시간이 가장 짧다고 예상되는 것을 먼저 디스패치하는 선점 방식의 알고리즘이다.
• 쉽게말해, SJF 는 비선점 방식이지만, 여기에 선점 방식으로만 바꾼 방식임.

• A가 가장 먼저 준비 큐에 도착 한 뒤 2만큼 수행을 하면, A의 CPU 사이클 5가 남게 된다.
• 이후로 B가 준비 큐에 도착하면 A(5) B(4) 사이클이 적은(남은 실행시간이 더 짧은) B가 수행이 되게 된다.
• 이때, B가 또 2만큼 수행이 된다고 가정하면, A(5), B(2) 가 될 것이다.
• 이후 C가 준비 큐에 도착하면 A(5), B(2), C(1) 이기 때문에 C가 먼저 수행이 될 것이다. ( 반복 )

• 장점: SJF와 다르게 선점 방식이다 보니 평균대기시간이나 평균반환시간에서 효율적임.
• 단점: SJF 방식과 동일하게 실제로 프로세스의 CPU 시간을 예상할 수 없으며, 선점 방식 자체는 문맥 교환이 빈번하게 일어날 수 있기 때문에 SJF(비선점) 보다 오버헤드가 클 수 있음.

(4) RR 스케줄링

• Round Robin: 선점 방식이며, 준비 큐에 도착한 순서대로 디스패치를 하지만 정해진 시간 할당량이 존재함.
• 즉, 시간 할당량에 따라서 실행이 제한이 되며, 시간 할당량 안에 종료하지 못한 프로세스는 준비 큐의 마지막에 배치됨.
• 또한, 자의로 넘어가는것이 아닌 타의로 넘어가는 것이므로, 준비 큐(준비상태)로 돌아가게 되는 것임.
• 일반적으로 가장 널리 사용이 되는 방식임.

• 1. A 프로세스 준비 큐에서 디스패치를 통해 CPU 시간 할당량 4만큼 수행 됨.
• 2. 해당 과정에서 준비 큐에 B 프로세스와 C프로세스가 들어온 상태임.
• 3. A 프로세스가 4만큼 수행 한 뒤 아직 3만큼의 수행을 해야 하므로, 준비 큐 마지막에 들어가고 다음 B 프로세스가 수행 됨.
• ** 위와 같이 선점 방식에 최대한 공평하게 프로세스에 CPU 할당하는 방식이 RR 스케줄링 알고리즘임. **

• 장점: CPU를 독점하지 않고 공평하게 이용 할 수 있으며, 가장 일반적으로 많이 사용되는 방식임.
• 단점: 시간 할당량이라는 기준이 너무 크면 FCFS 스케줄링과 동일하게 작동할 수 있다는 문제가 있으며, 시간 할당량이 반대로 너무 작으면 문맥 교환이 빈번하게 발생하기 떄문에 오버헤드가 커질 수 있음.

(5) HRN 스케줄링

• Highest Response Ratio Next: 준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치 해주는 방식.
• 응답비율: 해당 프로세스의 예상 실행시간이 짧거나, 대기시간이 길수록 응답비율이 커지며, 해당 응답비율이 커질수록 해당 프로세스의 우선순위가 높아지는 느낌이라고 보면 됨.
• 비선점 방식임.

• B의 예상 실행시간: CPU 사이클 수를 예상 실행시간으로 볼 수 있으므로, 4임.
• B의 대기시간: 2~7 = 5
• 응답비율: 4/5 + 1 = 2.25 (B의 응답비율)
• B = 2.25, C = 4, D = 1.67 이므로, 응답비율이 가장 높은 C가 제일 먼저 준비 큐에서 나와 CPU를 할당 받고 실행 됨.

• 장점: SJF 스케줄링의 긴 프로세스는 항상 오래 대기한다는 단점을 응답비율을 추가함으로써, 나중에 들어오는 짧은 프로세스보다 먼저 디스패치가 가능해진다는 장점이 있음.
• 단점: 이 또한 실제로 예상 프로세스 수행 시간(CPU 시간)을 예상할 수 없음.

(6) 다단계 피드백 큐 스케줄링

• Multilevel Feedback Queue: 입출력 중심의 프로세스와 연산 중심의 프로세스를 구분하여 시간 할당량을 부여하는 방식이며, 쉽게 말해 입출력 중심의 프로세스는 시간 할당량을 조금 주고, 연산 중심 프로세스는 시간 할당량을 길게 주는 느낌의 방식이라고 보면 됨.
• 다단계 피드백 큐 스케줄링은 선점 방식이며, Round Robin 방식을 확장한 버전이라고 생각하면 됨.
• 기본 구성: 다단계 피드백 큐는 여러 개의 큐로 구성이 되어있으며, 각 큐는 서로 다른 우선순위와 시간 할당량을 가지고 있음.
• 동적 이동: 프로세스가 주어진 시간 할당량을 모두 사용하면, 우선순위가 한 단계 낮은 큐로 강등되며, 반면 I/O 발생 등으로 시간을 다 쓰지 않고 CPU를 반납하면 우선순위가 유지되거나 상향될 수 있음.
• 큐별 알고리즘: 보통 상위 큐는 Round Robin(RR)을 사용하고, 가장 하위 큐는 First-Come First-Served(FCFS) 방식을 사용함.
• 반환 시간 최적화: 실행 시간이 짧은 프로세스를 먼저 처리하여 전체적인 대기 시간을 줄임.
• 응답 시간 최소화: 대화형 프로세스(I/O가 잦은 작업)를 우선적으로 처리하여 사용자 경험을 높임.

• I/O 위주 프로세스는 자발적으로 CPU를 반납하고 대기상태에 자주 머무르기 때문에 높은 우선권을 가짐.
• 즉, CPU 점유에 대한 높은 우선권을 가지고 있다는 의미임.
• 연산 위주의 프로세스는 CPU 우선권이 낮아지지만, 시간 할당량이 그만큼 계속해서 늘어남.
• 즉, 더 많은 시간동안 CPU를 사용 할 수 있다는 특징이 있음.

(7) 스케줄링 알고리즘 관계

• FCFS -> 시간할당량 부여 -> RR 방식이 됨.
• RR -> 다단계로 만듦 -> 다단게 큐 방식
• SJF(가장 짧은 예상 시간의 프로세스 우선순위) -> 선점 방식으로 변경 -> SRT
• SJF -> 대기 시간이 길어질 수 있는 문제 해결 -> HRN(대기 시간이 긴 것 등을 토대로 우선순위 부여)