[OS] 프로세스 스케줄링 알고리즘

프로세스 스케줄링 목적

• throughput의 증대
• 프로세스에 대한 fairness 유지
• 중요한 프로세스에 대한 우선처리가 가능하도록 함
• 시스템 내 자원의 공평한 할당

CPU 스케줄링 알고리즘을 구현할 때 주의 사항

1. 프로세스의 형태
   1. 일괄처리 (Batch) 형태
   2. 대화형 (TSS)
2. 프로세서의 CPU 사용 비율과 I/O 사용 비율 = Burst
3. 프로세스에게 우선순위를 부여했는지 여부
4. 우선순위가 높은 프로세스에 의해서 선점 or 비선점 프로세스
5. 페이지 부재(page fault)의 발생 빈도

👻 페이지와 페이지 부재 Page Fault
- 페이지
가상 메모리 시스템에서 사용하는 고정 크기의 데이터 블록이다.효율적인 메모리 관리를 위해 가상 메모리 공간을 일정하게 나눈 단위이다.
- 페이지 부재
프로세스가 접근하려는 페이지가 주기억장치에 존재하지 않을 때 발생하는 현상실행하려는 페이지가 주기억장치에 없다면 page fault가 발생하고, 하드디스크에서 가져와야 한다.하드디스크에서 가져오려고 하는데 주기억장치가 꽉 차있다면 주기억장치에서 다른거를 swap out하고 다시 가져와야 한다.
- Thrashing
빈번한 페이지 부재로 인해 시스템의 대부분의 시간이 스왑 작업에 소모되는 상태를 의미한다.

 

---

CPU 스케줄리의 세 가지 유형

1. 장기 스케줄링 (long-term)
2. 중기 스케줄링 (medium-term)
3. 단기 스케줄링 (short-term)

 

1. 단기 스케줄링

분배기 dispatcher라고도 한다.

주기억 장치 내의 준비 상태(ready)에 들어와 있는 프로세스들 중에서 다음에 실행시킬 프로세스를 선택하여

CPU를 할당시켜 주는 일을 담당한다

→ 프로세스가 연기되거나 선점 당하는 경우, 다음에 CPU에 할당시킬 프로세스를 선택해주는 일을 한다.

(=그냥 어떤 상황에서든 CPU 할당 시켜주는 거라고 보면 될 듯)

 

선점 : 더 우선순위가 높은 프로세스에 CPU를 양보하는 것을 의미한다. (=인터럽트 허용)

해당 프로세스가 갖고있는 PCB의 정보 관리와 사용자모드로의 전환 작업도 담당한다. (문맥전환)

---

2. 중기 스케줄러 (Medium-term Scheduler)

중기 스케줄러는 메모리에 적재된 프로세스의 수를 관리하며, 시스템 성능을 최적화하기 위해

프로세스를 스왑 인(Swap In) 또는 스왑 아웃(Swap Out)하는 작업을 수행한다.

→ suspended ready queue, suspended block queue를 주기억장치로 가져오는 일을 담당한다고 보면 됨.

 

역할

1. 메모리 관리:
   • 메모리에 너무 많은 프로세스가 적재되어 시스템 성능이 저하될 경우 일부 프로세스를 디스크의 스왑 영역으로 내보낸다.(Swap Out).
   • 메모리에 여유가 생기면 디스크에 있던 프로세스를 다시 메모리로 가져온다.(Swap In).
2. 우선순위 기반 조정:
   • 우선순위가 낮거나 일정 시간 동안 활성화되지 않은 프로세스를 선택해 메모리에서 제거한다.
3. 프로세스 상태 전환:
   • 준비 상태(Ready)에서 중단 상태(Suspended)로 전환하거나, 중단 상태에서 다시 준비 상태로 복귀시킨다.

특징

• 중기 스케줄러는 장기 및 단기 스케줄링 사이에서 작동하며, 시스템의 안정성을 유지하는 데 중요한 역할을 한다.
• 현대 운영체제에서는 가상 메모리 관리 기술이 발달하면서 중기 스케줄러의 사용이 줄어드는 추세이다.

---

3. 장기 스케줄러 (Long-term Scheduler)

장기 스케줄러는 어떤 프로세스를 준비 큐(Ready Queue)에 넣을지 결정하는 역할을 한다. 이를 통해 시스템에 동시에 실행되는 프로세스의 수를 조절한다. (시작과 끝을 담당한다고 보면 된다.)

역할

1. 프로세스 선택:
   • 디스크에 있는 작업(Job) 중에서 실행할 프로세스를 선택하고, 이를 메모리에 적재하여 준비 큐에 등록한다.
   • I/O 중심 프로세스와 CPU 중심 프로세스의 비율을 조절하여 시스템 자원의 균형을 유지한다.
2. Degree of Multiprogramming 조정:
   • 메모리에 동시에 존재하는 활성 프로세스의 수를 제어하여 시스템 과부하를 방지한다.
3. 프로세스 상태 전환:
   • 새로운(New) 상태에서 준비(Ready) 상태로 전환시킨다.

특징

• 장기 스케줄러는 호출 빈도가 낮으며, 수십 초 또는 수 분 단위로 작동한다.

 

스케줄링 알고리즘

선점 vs 비선점 개념

1️⃣ 비선점
:하나의 프로세스가 직접 반납하기 전까지 다른 프로세스가 CPU를 선점할 수 없는 것

장점

: 할당 받은 순선대로 처리된다는 fairness

: 대기 중인 프로세스에 관계없이 응답 시간 예측 가능

단점 (문제점)

: 기아현상 (starvation) 발생 가능 = CPU 배정받지 못하는 현상

: 무한 대기 발생 가능 - 어떤 프로세스가 오류로 인하여 CPU를 계속 사용하는 경우

2️⃣ 선점 
: 높은 우선순위를 갖는 프로세스에게 CPU를 양보한다.
- 대화형으로 처리되는 시분할 시스템

    → 일정 시간이 지나면 무조건 다른 프로세스에게 CPU의 사용을 양보한다.
- 문맥 교환

    → 선점의 경우, 우선순위 높은애에게 양보하므로, 중단 직전까지 수행한 모든 내용을 보관하여 둔 후, 새로 시작되는 프로세스와 관련된 내용을 시스템에 새로 적재 시켜준다.

    → 문맥 교환은 멀티태스킹 환경에서 필수적인 작업이지만, 오버헤드를 유발하여 시스템 성능에 부정적인 영향을 미칠 수 있다

 

---

비선점 스케줄링

1. FCFS (FIFO) 알고리즘

큐를 활용하여 프로세스 실행 순서 결정

CPU를 차지하면, 그 프로세스가 CPU를 반납할 때까지 다른 프로세스가 CPU를 독점한다.

반환시간 = 대기시간 + CPU 요구 시간

 

- 장점 : 간단하다

- 단점

: 기아현상 발생 가능 & 프로세스의 도착 순서의 영향이 크다.

: 특정 프로세스가 오류? → 계속 사용하는 문제 발생

 

2. SJF (Shortest Job First) 알고리즘 [선점 가능]

실행시간을 예측하여, 짧은 프로그래밍을 먼저 실행한다

장점 : 효율적인 알고리즘 중 하나이다.

단점 : 프로그램의 실행 시간을 예측하기 힘들고, 기아 현상이 발생할 수 있다.

 

3. HRRN (Highest Response Ration Next) 알고리즘

실행시간 (CPU Time,Run Time)과 대기시간 (Wait Time)을 고려하여 스케줄링한다.

처리 우선 순위(응답비율) = (대기시간 + CPU 요구 시간) / CPU 요구 시간

응답 비율이 큰 프로세스부터 실행한다

• CPU Time이 같다면, 대기시간이 큰 프로세스를 먼저 처리한다.
• 대기시간이 같다면, CPU Time이 작은 프로세스를 먼저 처리한다.
• → 당연한 것. 식에 넣어보면 됨.

장점 : SJF에서 발생하는 기아 현상을 줄일 수 있다.

 

4. 우선 순위(Priority) 알고리즘 [선점 + 비선점]

우선 순위가 높은 프로세스를 먼저 처리한다. 우선 순위가 같은 경우에는 FCFS (FIFO)로 한다.

각 프로세스의 우선순위는 내부적 요소 또는 외부적 요소에 의해 정의된다.

- 내부적 우선 순위

기계 내부의 성능에 영향을 미치는 작업 처리의 제한 시간

기억 장소의 요구량

사용되는 파일의 수

평균 CPU 버스트에 대한 평균 I/O 버스트의 비율 고려

 

- 외부적 우선 순위

기계 외적인 요인으로 인한 정책적 배려

시스템 운영의 유연성이 좋지만, 기아 현상이 발생한다.

 

- 동적 우선 순위 

우선 순위가 낮아도 대기 시간이 길면 우선 순위를 높여 준다.

→ 기아 현상 개선이 가능하다

cf. 정적 우선 순위 : 프로세스 생성 시 우선순위를 정한다. 실행 중에는 변하지 않는다.

 

선점에서 우선순위 알고리즘 :
높은 우선순위 프로세스가 도착하면 현재 실행 중인 프로세스를 중단하고 CPU를 할당
비선점에서 우선순위 알고리즘 :
CPU를 할당받은 프로세스는 종료될 때까지 실행된다. 새로운 높은 우선순위 프로세스는 대기한다.

 

📍 비선점에서 우선순위 알고리즘 예시 

5. 기한부(deadline) 스케줄링 알고리즘 [선점도 가능하다]

시스템에 제출된 작업의 최종 처리 시간을 명시하고, 명시된 기한 내에 처리되도록 한다.

→ 실시간 처리 시스템이 적용된다.

 

1. 하드 실시간 시스템

프로세스에 시간 제한을 두고, 시간 내에 처리되도록 CPU를 독점 사용하도록 한다. → 기한을 넘기면 시스템 오류로 간주한다.

2. 소프트 실시간 시스템 

시간적 제약이 다소 약소한 형태이다. 중요한 작업에 대해서는 다른 작업에 비해 높은 우선순위를 부여하여 이 작업이 끝날 때까지 높은 우선 순위를 계속 유지시키는 방식이다.

→ 기한을 넘겨도 결과가 유효할 수 있지만, 중요한 작업이 우선적으로 처리

다른 스케줄링 알고리즘 (RR, 우선순위 등)과 복합적인 사용을 목표로 한다.

 

기한부 알고리즘을 적용 시, 프로세스가 요구하는 자원을 정확히 파악해야 한다.