비선점 스케줄링
할당된 프로세스를 CPU에서 강제로 내보낼 수 없으며 프로세스가 작업을 완료하거나 입출력 이벤트 등 인터럽트 발생 시에만 CPU를 반환하여 다른 프로세스가 사용할 수 있게 됩니다. 우선순위에 따라 ready queue 내에 프로세스의 위치가 달라질 수 있습니다.
- 장점 : 복잡한 알고리즘이 필요 없으며 context switch발생이 매우 적으므로 응답 시간이 적습니다.
- 단점 : 공정성이 없으며 대기시간이 높습니다. 또한 우선순위에 의해 무한정 대기가 발생할 수 있으며 시스템에 중요한 작업을 빠르게 해결하지 못할 수 있습니다. 알고리즘에 따라 인터럽트가 발생하더라도 CPU를 반환하지 않는 경우도 있으며 사용 효율이 줄어듭니다.
- 단순 반복 작업에 유리하여 일괄 처리 방식에 적합합니다.
선점 스케줄링
할당된 프로세스가 내보내질 수 있으며 우선순위에 따라 동작하는 스케줄링 기법입니다. 우선순위가 높은 프로세스가 들어오면 현재 프로세스는 preempted 되어 ready queue로 돌아가는 context switch 과정이 진행되고 우선순위가 높은 프로세스가 CPU를 점유하게 됩니다. 우선순위가 높은 프로세스를 빠르게 처리할 수 있으며 주기적으로 인터럽트를 발생 시기는 타이머 인터럽트가 필요합니다.
- 장점 : 우선순위가 높은 프로세스를 빠르게 처리할 수 있으며 비선점 스케줄링에 비하여 대기시간이 적습니다. 적절한 알고리즘을 통해 공정성과 대기시간 최소화, CPU 사용률을 극대화시킬 수 있습니다.
- 단점 : 복잡한 알고리즘이 필요하며 구조 설계가 어렵습니다. 스케줄링 동작에 의해 기본적으로 오버헤드가 있으며 context switch가 자주 발생하므로 응답 시간이 늘어 이 또한 성능에 영향을 미칩니다.
- 멀티프로그래밍 환경, 여러 개의 프로그램이 실시간으로 동작하는 환경에 사용됩니다.
선점 스케줄링의 경우 뒤에서 배울 race condition을 발생시킬 수 있습니다. race condition(경쟁 상태)란 공유 자원에서 여러 개의 조작이 동시에 일어나서 결과에 잘못된 영향을 미칠 수 있는 상태를 의미합니다. 현재 프로세스가 공유 메모리 조작 혹은 공유 장치에 입출력 동작 중 같은 공유 자원을 사용하는 다른 프로세스가 선점하게 되면 원하지 않은 결괏값이 나올 수 있습니다.
경쟁상태 : ko.wikipedia.org/wiki/%EA%B2%BD%EC%9F%81_%EC%83%81%ED%83%9C
경쟁 상태 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 논리 상태에서의 경쟁 상태 공학 분야에서 경쟁 상태(race condition)란 둘 이상의 입력 또는 조작의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 말
ko.wikipedia.org
또한 커널 디자인이 어려워집니다. 시스템 콜 동작 중 선점이 발생하게 되면 커널 동작 처리를 해 주어야 하는데 이는 커널 구조에 악영향을 미칠 수 있습니다. 이를 해결하기 위해 시스템 콜 동작 중 선점은 불가능하도록 만들더라도 실시간 컴퓨팅 환경에서는 좋지 못한 해결책입니다.
우선순위
스케줄링 알고리즘에 따라 우선순위를 활용하여 OS의 효율성을 높일 수 있습니다.
- 내부 정의 : OS가 직접 측정하여 사용하는 우선순위입니다. (Ex. CPU burst, time limit, 등)
- 외부 정의 : OS 외부에서 정의된 우선순위입니다. (Ex. 사용자가 지정한 우선순위, 일반/과금 사용자 등)
정의된 우선순위를 스케줄링에 따라 다르게 사용할 수 있습니다.
- 비선점 스케줄링 : 높은 우선순위를 ready queue 앞쪽에 배치
- 선점 스케줄링 : 높은 우선순위의 프로세스를 강제로 선점해 실행
First-Come, First-served Scheduling (FCFS)
항상 먼저 들어온 작업이 먼저 실행되는 가장 간단한 비선점 스케줄링 알고리즘입니다. 우선순위가 없습니다.
프로세스가 ready queue에 들어오면 해당 프로세스의 PCB는 ready queue의 가장 끝에 연결되어 현재 큐 상태에서 가장 마지막에 실행됩니다.
CPU는 ready queue에서 가장 앞에 있는 PCB를 가져와 프로세스를 실행합니다.
평균 waiting time이 길며 각 프로세스들이 공정하지 않게 실행되며 중요하지 않은 긴 작업이 중요한 짧은 작업을 막을 수 있어 효율적이지 못한 알고리즘입니다.
Convoy Effect : 소요시간이 긴 몇 개의 프로세스 때문에 전체 OS가 느려지는 현상을 의미합니다. 이는 실시간 환경에서 치명적이며 OS의 Utilization을 저하시킵니다.
- 장점 : 구현이 간단하며, context switch가 덜 발생하여 성능이 좋습니다.
- 단점 : Convoy Effect, 공정성, 실시간성 등 문제가 있습니다.
- 단순 반복 작업 등 실시간성이 필요 없는 작업에 유리합니다.
Shortest-Job-First Scheduling (SJF)
현재 ready queue에 존재하는 프로세스 중 가장 짧은 CPU burst time을 가진 프로세스를 먼저 실행합니다.
FCFS에 비하여 평균 waiting time이 많이 줄어듭니다.
SJF 스케줄링 방식은 선점, 비선점 방식 모두 가능합니다.
- 선점 스케줄링(Shortest Remaining time First : SRT) : 현재 실행 중인 프로세스의 남은 CPU burst time이 새로 들어온 프로세스보다 길 경우 현재 프로세스를 중단하고 context switch를 통해 새로 들어온 프로세스를 실행합니다. 이 경우 SRT 스케줄링이라고 부릅니다.
- 비선점 스케줄링 : CPU burst time이 짧은 순으로 ready queue에 연결됩니다.
프로세스에 CPU burst time 우선순위가 부여됩니다. 이 우선순위에 따라 동작하며 프로세스마다 CPU burst time을 알기 어렵기 때문에 빠르게 프로세스를 선택해야 하는 short-term scheduling에서 사용할 수 없습니다.
long-term scheduling에서 주로 이 스케줄링 방식을 사용합니다. short-term에 비해 많은 시간을 사용할 수 있기 때문에 CPU burst time을 예측하거나 계산하여 사용하거나 사용자가 프로세스 제한 시간을 설정하면 이를 사용할 수 있습니다.
CPU burst time 예측 시 주로 Exponential Average 방식을 사용합니다.
Shortest Job First CPU Scheduling with predicted burst time - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
www.geeksforgeeks.org
SJF 알고리즘을 사용하면 계속해서 짧은 시간의 프로세스가 들어오게 되면 긴 프로세스는 계속해서 실행되지 못하는 Starvation 문제가 생깁니다. 이러한 문제를 해결하기 위해 Aging을 사용합니다.
Aging : Ready Queue에 오래 머물러 있으면 시간에 따라 우선순위를 더 부여해주는 방법입니다.
- 장점 : 우선순위에 의해 평균 waiting time이 줄어 동시성이 좋습니다.
- 단점 : Starvation 문제가 일어나며 이는 Aging 알고리즘과 병행하여 해결할 수 있지만 실시간 환경에는 부적합합니다. 또한 SRT 스케줄링의 경우 새로운 프로세스가 도착할 때마다 스케줄링을 새로 해야 하므로 성능이 떨어질 수 있습니다.
- Long-term 스케줄링에 자주 사용됩니다.
Round-Robin Scheduling
실시간, 시간 공유 시스템을 위하여 디자인된 선점 스케줄링 알고리즘입니다. 프로세스를 시간 단위로 CPU에 할당하여 실행하고 이를 통해 실시간성을 구현합니다.
알고리즘을 통해 선정된 프로세스가 일정 시간을 할당받아 수행되고 부여받은 시간이 끝나면 context switch가 일어나 다른 프로세스가 실행됩니다. 이로 인하여 context switch가 많이 발생하여 프로세스 응답 시간은 길어지지만 평균 대기시간은 감소하여 공정성과 실시간성에 유리합니다.
따라서 Time Quantum을 잘 조절하여 평균 대기시간, 응답 시간의 균형을 맞춰야 합니다.
* Time Quantum > context switch time을 항상 만족하여야 합니다.
- 장점 : SJF처럼 예측할 필요 없이 CPU burst time이 무작위인 경우 효율적으로 실시간성을 보장할 수 있습니다. 또한 Time Quantum 단위로 프로세스를 실행하기 때문에 평균 대기 시간이 (프로세스 수 - 1) * Time Quantum을 넘을 수 없습니다. 이로 인하여 공정성이 보장됩니다.
- 단점 : context switch가 자주 발생하며 Time Quantum 크기에 따라 효율성이 많이 달라지게 됩니다.
- Time Quantum 크기를 잘 설정해야 하며 이에 따라 공정성을 보장할 수 있기 때문에 실시간 컴퓨팅 환경에 적합합니다. 대부분의 현대 컴퓨터에서 실시간성을 위해 이 스케줄링 알고리즘이 사용됩니다.
Multilevel Queue Scheduling
프로세스가 각각 클래스로 나누어져 있으며 우선순위가 다 다를 경우 이들을 처리하기 위해 다량의 ready queue를 사용하는 스케줄링 알고리즘입니다.
(시스템, 사용자), (대몬, 서비스, 유저 프로그램) 등의 기준으로 나눌 수 있으며 설계 시 정의된 프로세스 기준으로 나누어집니다.
각 큐는 각각의 알고리즘을 사용할 수 있으며 Time Quantum 또한 다르게 둘 수 있습니다. 큐 간의 우선순위 또한 정의가 가능합니다.
* Multilevel Feedback Queue : 큐가 프로세스가 이동이 가능합니다.
'스터디 > 운영체제' 카테고리의 다른 글
| [운영체제] 좀비 프로세스, 고아 프로세스 (0) | 2021.03.15 |
|---|---|
| [운영체제] 프로세스 생성과 소멸 (0) | 2021.03.15 |
| [운영체제] Scheduling (0) | 2021.01.22 |
| [운영체제] Context Switch (0) | 2021.01.16 |
| [운영체제] 프로세스 (0) | 2021.01.09 |