[OS] 프로세스 스케줄링

선점형

- 최소 남은 시간 우선(SRTF)

- 라운드 로빈(RR)

- 우선순위(Priority)

 

비선점형

- 선입선출(FIFO 또는 FCFS)

- 최단시간(SJF)

- 우선순위(Priority)

---

선입선출(FCFS) 스케줄링

• 프로세스 A: 도착 시간 0ms, 실행 시간 3ms
• 프로세스 B: 도착 시간 2ms, 실행 시간 6ms
• 프로세스 C: 도착 시간 4ms, 실행 시간 4ms

• 프로세스 A는 즉시 실행을 시작하여 0ms부터 3ms까지 실행됩니다.
• 프로세스 B는 2ms에 도착했지만, A가 실행을 마친 직후인 3ms에 실행을 시작하여 3ms부터 9ms까지 실행됩니다.
• 프로세스 C는 4ms에 도착했지만, B가 실행을 마친 직후인 9ms에 실행을 시작하여 9ms부터 13ms까지 실행됩니다.

이 예에서 볼 수 있듯이, FCFS 스케줄링은 프로세스의 도착 순서에 따라 CPU 사용 시간을 할당하기 때문에, 대기 시간과 반환 시간은 프로세스의 도착 순서와 실행 시간에 크게 영향을 받습니다. FCFS는 구현이 간단하고 예측 가능하지만, 특정 상황에서는 비효율적일 수 있으며, 특히 CPU 사용 시간이 긴 프로세스가 먼저 도착하는 경우 다른 프로세스의 대기 시간이 길어질 수 있습니다.

 

---

최단시간 SJF 스케줄링

• P1: 실행 시간 8ms
• P2: 실행 시간 4ms
• P3: 실행 시간 2ms
• P4: 실행 시간 1ms

SJF 스케줄링에 따라 프로세스는 P4, P3, P2, P1 순으로 CPU를 할당받게 됩니다. 이 순서는 각 프로세스의 실행 시간이 가장 짧은 순서입니다. 따라서, SJF 스케줄링은 이러한 순서로 프로세스를 선택하여 평균 대기 시간을 최소화합니다.

최소 남은 시간 우선(SRTF)

• 시간 0에서 P1 도착, 실행 시간 8ms
• 시간 1에서 P2 도착, 실행 시간 4ms
• 시간 2에서 P3 도착, 실행 시간 9ms
• 시간 3에서 P4 도착, 실행 시간 5ms

시간 0에서 P1이 시작되지만, 시간 1에 P2가 도착하고 P2의 실행 시간이 P1의 남은 시간보다 짧으므로, CPU는 P1에서 P2로 선점됩니다. 이와 같은 방식으로 시스템은 실행 시간이 가장 짧은 프로세스에게 우선적으로 CPU를 할당하여 전반적인 대기 시간과 반환 시간을 최소화합니다.

 

SJF와 SRTF는 이론적으로 평균 대기 시간을 최소화하는 가장 효율적인 스케줄링 알고리즘입니다. 하지만, 실제로는 각 프로세스의 정확한 실행 시간을 미리 알기 어렵다는 단점이 있습니다. 따라서, 이 알고리즘들은 예측 모델이나 과거의 실행 패턴을 기반으로 한 추정값을 사용하기도 합니다.

---

라운드로빈(Round Robin, RR) 스케줄링

• 타임 슬라이스: 4ms
• P1: 실행 시간 10ms
• P2: 실행 시간 6ms
• P3: 실행 시간 7ms
• P4: 실행 시간 4ms

1. P1이 4ms 동안 실행된 후, 남은 시간은 6ms입니다.
2. P2가 4ms 동안 실행된 후, 남은 시간은 2ms입니다.
3. P3가 4ms 동안 실행된 후, 남은 시간은 3ms입니다.
4. P4가 4ms 동안 실행되고 완료됩니다. (남은 시간 없음)
5. 다시 P1이 4ms 동안 실행되고, 남은 시간은 2ms입니다.
6. P2가 2ms 동안 실행되고 완료됩니다. (남은 시간 없음)
7. P3가 3ms 동안 실행되고 완료됩니다. (남은 시간 없음)
8. 마지막으로 P1이 2ms 동안 실행되고 완료됩니다. (남은 시간 없음)

이 예시에서 볼 수 있듯이, 라운드 로빈 스케줄링은 모든 프로세스가 CPU를 공정하게 사용할 수 있도록 보장합니다. 하지만 타임 슬라이스의 크기 설정이 중요한데, 너무 작으면 컨텍스트 스위칭으로 인한 오버헤드가 증가하고, 너무 크면 라운드 로빈 스케줄링이 비선점형 스케줄링처럼 동작하여 시스템의 반응성이 저하될 수 있습니다.

---

우선순위(Priority) 스케줄링

• 프로세스 A: 우선순위 3, 실행 시간 4ms
• 프로세스 B: 우선순위 1, 실행 시간 2ms
• 프로세스 C: 우선순위 2, 실행 시간 1ms
• 프로세스 D: 우선순위 3, 실행 시간 3ms

선점형 우선순위 스케줄링: A->B->C->D

1. 프로세스 A가 처음에 CPU를 할당받아 실행을 시작합니다.
2. 그러나 프로세스 B가 도착하면, A보다 우선순위가 높기 때문에 A의 실행이 중단되고 B가 실행됩니다.
3. B의 실행이 완료된 후, 다시 가장 높은 우선순위를 가진 대기 중인 프로세스 C가 실행됩니다.
4. C의 실행이 완료된 후, 중단되었던 A의 실행이 재개됩니다.
5. 마지막으로 프로세스 D가 실행됩니다.

비선점형 우선순위 스케줄링: B->C->A->D

1. 프로세스 B가 가장 높은 우선순위를 가지므로, 먼저 CPU를 할당받아 실행됩니다.
2. 다음으로 프로세스 C가 실행됩니다.
3. 우선순위가 동일한 프로세스 A와 D는 도착 순서대로 실행됩니다. 먼저 도착한 프로세스가 먼저 실행됩니다.

우선순위 스케줄링은 특정 작업에 대해 더 높은 우선순위를 부여하여 중요한 작업이 빠르게 처리되도록 할 수 있는 장점이 있습니다. 그러나, 낮은 우선순위의 프로세스가 긴 시간 동안 대기하는 "기아 현상(Starvation)"이 발생할 수 있다는 단점이 있습니다. 이를 해결하기 위해 우선순위가 낮은 프로세스의 우선순위를 시간이 지남에 따라 점진적으로 증가시키는 "우선순위 에이징(Priority Aging)" 기법을 사용하기도 합니다.

---

멀티레벨 큐(Multilevel Queue) 스케줄링

멀티레벨 큐 스케줄링은 프로세스를 여러 개의 큐로 분류하여 관리하는 스케줄링 알고리즘입니다. 이 방식은 프로세스의 우선순위, 작업 유형, 메모리 사용량, 프로세스의 특성 등 다양한 기준에 따라 각기 다른 큐를 할당받게 됩니다. 멀티레벨 큐 스케줄링은 각 큐마다 고유의 스케줄링 알고리즘을 적용할 수 있으며, 큐 사이에는 우선순위가 있어서 높은 우선순위의 큐가 먼저 CPU 시간을 할당받습니다.

멀티레벨 큐(Multilevel Queue) 스케줄링의 구성

멀티레벨 큐 스케줄링 시스템은 일반적으로 다음과 같이 구성됩니다:

• 시스템 프로세스 큐: 운영 체제나 시스템 수준의 작업을 처리하는 프로세스를 위한 큐입니다. 가장 높은 우선순위를 가집니다.
• 대화형 사용자 프로세스 큐: 사용자와의 상호작용을 필요로 하는 프로세스를 위한 큐입니다. 반응 시간이 중요한 작업을 처리합니다.
• 일괄 처리 큐: 사용자 상호작용을 필요로 하지 않는 일괄 처리 작업을 위한 큐입니다. 계산이 많이 필요한 작업을 처리합니다.
• 백그라운드 큐: 유지 보수 작업이나 백업과 같은 낮은 우선순위의 작업을 처리하는 프로세스를 위한 큐입니다.

각 큐는 독립적인 스케줄링 정책을 가질 수 있습니다. 예를 들어, 시스템 프로세스 큐에는 선점형 우선순위 스케줄링을, 일괄 처리 큐에는 선입선출(FCFS) 또는 최단 작업 우선(SJF) 스케줄링을 적용할 수 있습니다.

운영 체제가 다음과 같은 멀티레벨 큐를 가지고 있다고 가정해 봅시다:

1. 시스템 큐: 우선순위 1 (가장 높음)
2. 대화형 큐: 우선순위 2
3. 일괄 처리 큐: 우선순위 3
4. 백그라운드 큐: 우선순위 4 (가장 낮음)

새로운 프로세스가 시스템에 도착하면, 그 프로세스의 특성에 따라 적절한 큐로 분류됩니다. 예를 들어, 시스템 작업은 시스템 큐로, 사용자 상호작용을 요구하는 작업은 대화형 큐로 분류됩니다. CPU 스케줄러는 먼저 시스템 큐의 프로세스에게 CPU를 할당하고, 이 큐가 비어 있을 경우에만 다음 우선순위의 큐에 있는 프로세스에게 CPU를 할당합니다.

이 방식의 주요 장점은 프로세스의 유형과 요구 사항에 따라 다른 스케줄링 정책을 적용할 수 있다는 것입니다. 그러나 프로세스가 한 번 특정 큐에 할당되면 다른 큐로 이동할 수 없다는 단점이 있으며, 이로 인해 특정 큐에서 기아 현상이 발생할 수 있습니다.

---

멀티레벨 피드백 큐(Multilevel Feedback Queue, MFQ) 스케줄링

멀티레벨 피드백 큐(Multilevel Feedback Queue, MFQ) 스케줄링 알고리즘은 멀티레벨 큐 스케줄링을 확장한 형태로, 프로세스가 다른 큐로 이동할 수 있게 함으로써 더 유연한 스케줄링을 가능하게 합니다. 이 알고리즘의 핵심 아이디어는 프로세스의 실행 행위(예: CPU 사용 시간, 입출력 요청 빈도)에 따라 동적으로 우선순위를 조정하는 것입니다. 이를 통해 시스템은 다양한 유형의 작업을 효율적으로 처리할 수 있으며, 공정성과 시스템 반응성을 향상시킬 수 있습니다.

멀티레벨 피드백 큐 스케줄링의 특징

• 다중 큐: 여러 개의 큐가 있으며, 각 큐는 다른 우선순위를 가지고 다른 스케줄링 알고리즘(예: 라운드 로빈, FCFS)을 사용할 수 있습니다.
• 동적 우선순위 조정: 프로세스의 실행 패턴에 따라 프로세스를 더 높거나 낮은 우선순위의 큐로 이동시킵니다.
• 양방향 이동: 프로세스는 시간 할당량을 초과하거나 입출력을 대기하는 등의 이유로 더 낮은 우선순위 큐로 이동할 수 있으며, 일정 시간 동안 CPU를 거의 사용하지 않은 경우 더 높은 우선순위 큐로 승격될 수도 있습니다.

예를 들어 시스템이 세 개의 큐를 가지고 있다고 가정해 봅시다. 각 큐는 다른 타임 슬라이스 크기를 가지는 라운드 로빈 스케줄링을 사용합니다.

• 큐 1: 타임 슬라이스 8ms (가장 높은 우선순위)
• 큐 2: 타임 슬라이스 16ms
• 큐 3: 타임 슬라이스 32ms (가장 낮은 우선순위)

새로운 프로세스는 기본적으로 가장 높은 우선순위인 큐 1에 할당됩니다. 프로세스가 타임 슬라이스 내에 실행을 완료하지 못하면 큐 2로 이동됩니다. 만약 큐 2에서도 타임 슬라이스를 초과하면 큐 3으로 이동됩니다. 프로세스가 큐 3에서 타임 슬라이스를 다 사용하지 않고 다음 상태로 넘어가면 이 프로세스는 다시 높은 우선순위의 큐로 승격될 수 있습니다.

이 시스템은 CPU 집약적인 작업을 자동으로 식별하여 더 낮은 우선순위로 조정하고, 반대로 입출력 집약적인 작업이나 짧은 작업을 더 높은 우선순위로 승격시킴으로써, 다양한 유형의 작업을 효과적으로 처리할 수 있습니다.

 

 

https://m.blog.naver.com/syunjae21/222202539627