프로세스 스케줄링
- 스케줄링이란 프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업을 뜻하며, 대기 시간은 최소화하고 최대한 공평하게 처리하는 것을 목적으로 합니다.
- 메모리에 여러 개의 프로세스를 올려놓고(다중 프로그래밍), CPU의 가동시간을 적절히 나누어(시분할) 각각의 프로세스에게 분배하여 실행되도록 합니다.
- 프로세스 스케줄링이란 CPU를 사용하려고 하는 프로세스들 사이의 우선순위를 관리하는 일입니다. 처리율과 CPU 이용률을 증가시키고 오버헤드/응답시간/반환시간/대기시간을 최소화시키기 위한 기법입니다. 즉, CPU가 쉬지 않고 계속 열심히 일할 수 있도록 효율적인 계획을 잡아주는 것입니다.
- 스케줄링에서는 아래와 같이 장기, 중기, 단기 단위가 있습니다.
- 장기 (Long-term Scheduling)
- 어떤 프로세스가 시스템의 자원을 차지할 수 있도록 할 것인가를 결정하여 아래 준비(ready) 상태 큐로 보내는 작업을 의미합니다.
- 상위 스케줄링이라고도 하며, 작업 스케줄러에 의해 수행됩니다.
- 수행 빈도가 적고, 느립니다.
- 즉, 어떤 프로세스를 커널에 등록할 것인가를 정하는 것입니다.
- 중기(Middle-term Scheduling)
- 어떤 프로세스들이 CPU를 할당받을 것인지 결정하는 작업을 의미합니다.
- CPU를 할당받으려는 프로세스가 많을 경우 프로세스를 일시 대기(wating)시킨 후 활성화해서 일시적으로 부하를 조절합니다.
- Swap In/Out 결정(메모리 부족 시 Swap Out, 남으면 Swap In)합니다.
- 즉, 어떤 프로세스에게 메모리를 할당할 것인가를 정하는 것입니다.
- 단기(Short-term Scheduling)
- 프로세스가 실행되기 위해 CPU를 할당받는 시기와 특정 프로세스를 지정하는 작업을 의미합니다.
- 프로세서 스케줄링, 하위 스케줄링이라고도 합니다.
- 프로세서 스케줄링 및 문맥 교환은 프로세서 스케줄러에 의해 수햅됩니다.
- 자주 수행되고 빠릅니다.
- 즉, 어떤 프로세스에게 CPU를 할당할 것인가를 정하는 것입니다.
- 장기 (Long-term Scheduling)
- 프로세스는 아래 5가지 상태 중 하나를 가집니다.
- 생성(Create) : 프로세스가 생성되는 중입니다.
- 실행(Running) : 프로세스가 프로세서를 차지하여 명령어들이 실행되고 있습니다.
- 준비(Ready) : 프로세스가 프로세서를 사용하고 있지는 않지만 언제든지 사용할 수 있는 상태로, CPU가 할당되기를 기다리고 있습니다.
- 대기(Waiting) : 프로세스가 입출력 완료, 시그널 수신 등 어떤 사건을 기다리고 있는 상태를 말합니다.
- 종료(Terminated) : 프로세스의 실행이 종료되었습니다.
- 여기서 준비 큐는 준비(Ready) 상태에 있는 프로세스들을 모아놓은 큐(Queue)입니다.
- 운영체제는 CPU 스케줄러를 통해 준비 큐에 있는 프로세스 중 한 프로세스를 골라 다음에 실행시킵니다.
- 운영체제가 프로세스를 프로세서에 할당하는 것을 디스패치(Dispatch)라고 합니다.
- 스케줄링 알고리즘 평가 기준은 아래와 같습니다.
- CPU 이용률 : 전체 시스템 시간 중, CPU가 작업을 처리하는 시간의 비율
- 처리량 : CPU가 단위 시간 당 처리하는 프로세스의 갯수
- 총 처리 시간 : 프로세스가 시작해서 끝날 때까지 걸린 시간
- 대기시간 : 프로세스가 준비완료 큐에서 대기하는 시간의 총합
- 응답시간 : 대화식 시스템에서 요청 후 첫 응답이 오기까지 걸린 시간
- 프로세서 스케줄링의 기법은 적용 시점에 따라 크게 선점(Preemptive)형과 비선점(Non-Preemptive)형으로 구분합니다.
- CPU 스케줄링의 결정 시점(적용 시점)은 다음과 같은 프로세스의 상태 변화가 있을 때입니다.
- 수행 → 대기 (비선점, 선점)
- 수행 → 준비 (비선점)
- 대기 → 준비 (비선점)
- 수행 → 종료 (비선점, 선점)
프로세서 스케줄링 기법
비선점(Non-Preemptive)
- 어떤 프로세스가 CPU를 할당받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 실행되도록 보장합니다.
- 순서대로 처리되는 공정성이 있고 다음에 처리해야 할 프로세스와 관계없이 응답 시간을 예상할 수 있으며 선점 방식보다 스케줄러 호출 빈도가 낮고
문맥 교환에 의한 오버헤드가 적습니다. - 일괄 처리 시스템에 적합하며, CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로 처리율이 떨어질 수 있다는 단점이 있습니다.
- 비선점 기법으로는 아래와 같은 종류들이 존재합니다.
- FCFS 스케줄링 (First Come First Serve Scheduling)
- CPU를 먼저 요청한 프로세스가 먼저 CPU를 배정받는 스케줄링 방법입니다.
- P1(24ms), P2(3ms), P3(3ms) 프로세스가 있다고 가정했을 때, CPU 스케줄링 결과는 다음과 같이 표현됩니다.
- 가장 간단한 방식이지만, 평균 대기 시간(Average Waiting Time)을 생각해 보았을 때, (P1(0) + P2(24) + P3(27)) / 3 = 17ms 입니다. P3의 우선순위가 가장 높았다면 의미없는 대기 시간을 줄일 수 있습니다.
- 이런 식으로, 다른 모든 프로세스들이 커다란 한 프로세스가 끝날 때까지 계속 기다리는 현상을
Convey Effect라고 합니다.Convey Effect는 CPU와 장치들의 사용률을 낮추기 때문에 되도록이면 지양해야 합니다.
- SPN (Shortest Process Next) / SJF(Shortest Job First) 스케줄링
- 준비 큐에서 기다리고 있는 프로세스 중에서 가장 CPU 요구량이 적은 것을 먼저 실행시켜 주는 방식입니다.
- 평균 응답 시간을 최소화할 수 있으나, 실행 시간이 긴 프로세스가 CPU를 할당받지 못하고 계속해서 대기하는 무한 대기 현상이 발생할 수 있습니다.
- HRRN (Highest Response Ratio Next) 스케줄링
- 준비 큐에 있는 프로세스들 중에서 응답률(Response Ratio = (대기시간 + CPU 요구량) / CPU 요구량)이 가장 높은 프로세스에게 높은 우선순위를 주는 방식입니다.
- SPN과 SRT 방식의 약점인 수행 시간이 긴 프로세스의 무한 대기 현상을 방지하기 위한 기법입니다.
선점(Preemptive)
- 어떤 프로세스가 CPU를 할당받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있습니다.
- 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있습니다.
- 빠른 응답시간을 요구하는 대화식 시스템에 적합합니다.
- 운영체제가 프로세서 자원을 선점하고 있다가 각 프로세스의 요청이 있을 때, 특정 요건들을 기준으로 자원을 배분하는 방식입니다.
- 선점 기법으로는 아래와 같은 종류들이 존재합니다.
- 라운드 로빈 (Round-Robin/RR) 스케줄링
- FCFS 스케줄링을 기반으로 하여 CPU를 할당하되, 각 프로세스는 한 번에 쓸 수 있는 CPU 시간 크기(시간 할당량)이 지나면 시간 종료 인터럽트에 의해 CPU를 뺏기게 되는 방식입니다.
- 주로 우선순위 스케줄링(Priority Scheduling)과 결합해 프로세스의 시간 할당량을 조절하는 방식으로 활용합니다.
- 단, FCFS 스케줄링에서 프로세스 하나가 CPU를 독점하는 단점을 방지하지만, Context Switch의 오버헤드를 감수해야 합니다.
- SRT (Shortest Remaining Time) 스케줄링
- 준비 큐에서 완료까지 남은 CPU 요구량이 가장 짧은 것을 먼저 실행시켜주는 방식입니다.
- 실행 도중 남은 실행 시간이 더 적은 프로세스가 준비 큐에 들어올 경우, 현재 실행 중인 것을 중단하고 새 프로세스에게 CPU를 할당합니다.
- 다단계 큐 (Multi-level Queue) 스케줄링
- 프로세스들의 우선순위 개수 만큼의 큐가 필요합니다.
- 프로세스들은 자신의 우선순위 값에 해당하는 큐에 들어가게 되며, 우선순위가 낮은 하위 단계 큐의 작업은 실행 중이더라도 상위 단계 큐에 프로세스가 도착하면 CPU를 뺏깁니다.
References
'Computer Science > 운영체제' 카테고리의 다른 글
| 문맥교환(Context-Switching) (0) | 2021.03.23 |
|---|---|
| 동기와 비동기 (0) | 2021.03.23 |
| 교착상태와 기아상태 (0) | 2021.03.23 |
| Process와 Thread (0) | 2021.03.23 |
