[CS 스터디] 3주차 CPU 스케줄링과 IPC
CPU 스케줄링
선점형 VS 비선점형
CPU 스케줄러는 선점형(Preemptive)과 비선점형(Non-Preemptive)으로 구분할 수 있다.
두 스케줄링은 자원을 빼앗길 수 있느냐 빼앗기지 않느냐에 따라 구분할 수 있다.
먼저, 선점형 스케줄링은 자원을 다른 프로세스에 빼앗길 수 있다.
실행중이던 프로세스가 자원을 빼앗기면 어떻게 될까?
자원이 없으면, 프로세스를 실행할 수 없기 때문에 현재 작업을 저장하게 되고, 이 과정에서 잦은 Context Switching이 발생한다.
또한, 선점형 스케줄링은 응답성이 높다는 장점이 있다.
만약 더 높은 우선순위를 가진 프로세스가 생성된다면, 선점형 스케줄링은 기존 프로세스의 자원을 회수하고, 새로운 프로세스에게 할당할 수 있다.
이렇게 되면, 우선순위가 높은 프로세스는 기다리지 않고 작업을 처리할 수 있게 된다.
그렇기 때문에, 선점형 스케줄링은 Real time system에 적합하다.
비선점형 스케줄링은 반대다. 스스로 자원을 반납하기 전까지는 안 빼앗긴다.
그렇기 때문에, 장단점이 선점형 프로세스와 반대이다.
자원을 빼앗기지 않기 때문에, Context Switching으로 인한 오버헤드가 적고, 반대로 응답성이 낮다는 단점을 가진다.
FCFS (First Come First Served)
FCFS는 대표적인 CPU 스케줄링 중 하나로, 비선점형 스케줄링이다.
이름에서 알 수 있듯, FCFS는 프로세스의 도착 시간(Arrival Time)을 기준으로 작업을 처리한다.
프로세스가 얼마나 긴 실행 시간(Burst Time)을 가지는지, 혹은 우선순위가 높은지 낮은지와 관계 없이 무조건 도착 시간 기준으로 처리한다.
그렇기 때문에, 하나의 프로세스가 실행되기까지 높은 응답시간을 가질 수 있다는 단점이 있다.
또한, FCFS는 도착 시간을 기준으로 프로세스를 실행하기 때문에, 실행 시간이 긴 프로세스가 먼저 도착할 경우, 이후 도착한 모든 프로세스들이 긴 대기 시간을 가지게 되는 Convoy Effect라는 단점을 가진다.
RR (Round Robin)
RR은 FCFS와 다르게 선점형 스케줄링 알고리즘이다.
FCFS와 동일하게 도착시간을 기준으로 실행된다.
다만, RR은 모든 프로세스가 실행될 수 있는 최대 시간인 Time Quantum이 존재한다.
RR에서 모든 프로세스는 최대 시간이 도달하면 무조건 자원을 반납하고, Ready Queue(대기열)의 마지막으로 들어가 자기 차례를 다시 기다린다.
이는 특정 프로세스가 자원을 독점하는 것을 방지한다는 장점이 있지만, 동시에 자원을 반납하고 다시 할당받는 과정에서 높은 Context Switching이 발생한다.
SJF (Shortest Job First)
SJF 혹은 SPN(Shortest Process Next)으로 불리는 스케줄링은, FCFS와 마찬가지로 비선점형 스케줄링 알고리즘이다.
SJF는 실행시간(Burst Time)을 기준으로 실행한다.
예를 들어, 아래와 같이 프로세스가 생성되었다고 가정하자.
| AT | BT | |
| 0 | 0 | 10 |
| 1 | 2 | 4 |
| 2 | 5 | 1 |
FCFS라면, 도착 시간(AT) 기준으로 0 -> 1 -> 2 -> 순서로 실행된다.
이렇게 되면, 2번 프로세스는 1초의 BT를 가짐에도 불구하고, 앞선 프로세스가 종료될때까지 9초를 기다려야 한다.
마찬가지로, 1번 프로세스 또한 실행까지 8초를 기다려야 한다.
반면 SJF는 FCFS와 다르게 실행시간을 기준으로 실행되기 때문에, 새로운 프로세스가 실행되는 시점에서 실행시간이 가장 낮은 프로세스를 먼저 실행한다.
따라서, 위의 표와 같이 프로세스가 실행될 경우, SJF는 0 -> 2 -> 1 순으로 프로세스를 실행한다.
그런데, 실행시간을 기준으로 프로세스를 실행하는 것이 좋은 방법 같지만, 심각한 문제가 있다.
바로 기아 (Starvation)이다.
위의 표처럼 실행이 되고 있다고 가정하자. 만약, 2번 프로세스가 끝나는 시점에 BT가 1인 프로세스 4가 새로 도착다면 어떻게 될까?
2번 프로세스는 프로세스 4보다 큰 실행시간을 가지기 때문에, 4번 프로세스가 먼저 실행되고 2번 프로세스가 실행된다.
그렇다면 아래처럼 프로세스가 도착하면 어떻게 될까?
| AT | BT | |
| 0 | 0 | 10 |
| 1 | 2 | 4 |
| 2 | 5 | 1 |
| 3 | 11 | 1 |
| 4 | 12 | 1 |
| 5 | 13 | 1 |
| 6 | 14 | 1 |
| 7 | 15 | 1 |
| 8 | 16 | 1 |
| 9 | 17 | 1 |
| 10 | 18 | 1 |
| 11 | 19 | 1 |
| 12 | 20 | 1 |
| ... | ... | ... |
0번 프로세스가 10초에 완료되고, 2번 프로세스가 11초까지 작업한다. 11초에 4번 프로세스가 생성되어 12초까지, 5번 프로세스가 13초까지.....
1번 프로세스보다 실행시간이 작은 프로세스가 계속 도착하면서, 1번 프로세스는 계속 밀리게 된다.
이렇게 프로세스가 자원을 할당받지 못해 무한정 대기하는 것을 기아라고 한다.
IPC (Inter-Process Communication)
IPC는 프로세스간 데이터를 공유하기 위한 통신 방법이다.
1주차에서 공부한 것 처럼, 모든 프로세스는 독립적인 메모리 공간을 가진다.
그렇기 때문에, 프로세스간 데이터 공유가 필요할 경우, IPC를 통해 통신하게 된다.
Shared Memory
Shared Memory는 다수의 프로세스가 공유하는 메모리 공간을 구축하여 데이터를 주고받는 방법이다.
하나의 메모리 공간을 공유하기 때문에, 빠르다는 장점이 있으나, 여러 프로세스에서 같은 메모리 공간을 공유하기 때문에 동기화 문제가 발생할 수 있다.
Message Passing
Message Passing은 Shared Memory와 반대로, 데이터를 공유할 필요가 있을 때, 매번 데이터를 주고 받는 방식이다.
메모리 공간을 공유하는 방식이 아니기 때문에, 동기화 문제가 발생하지 않는다.
하지만, 매번 시스템콜을 통해 데이터를 주고 받기 때문에, Shared Memory 기법에 비해 성능이 떨어진다는 단점이 있다.