UNIX CPU 스케줄링

■ 시분할 시스템에서의 CPU 할당

 

시분할 시스템에서는 여러 프로세스가 병렬로 실행되며, CPU는 프로세스에 순차적으로 할당되어 프로세스가 실제로 동시에 실행되는 것처럼 보이도록 한다.

 

 

■  스케줄링 알고리즘

- FCFS (First Come First Serve):
  - 프로세스가 도착한 순서대로 CPU를 할당한다.
  - 간단하지만, 선입선출 방식으로 인해 프로세스의 대기 시간이 길어질 수 있다.

- SJF (Shortest Job First):
  - 실행 시간이 가장 짧은 프로세스에게 CPU를 우선 할당한다.
  - 평균 대기 시간을 줄일 수 있지만, 실행 시간이 긴 프로세스는 대기 시간이 길어질 수 있다.

- RR (Round Robin):
  - 각 프로세스에 일정 시간(퀀텀 타임)을 할당하고, 시간이 끝나면 다음 프로세스에게 CPU를 넘긴다.
  - 공평성을 제공하지만, 퀀텀 타임이 너무 짧으면 많은 문맥 교환이 발생할 수 있다.

 

 3. 퀀텀 타임 (Quantum Time)
퀀텀 타임은 프로세스가 CPU를 차지하는 짧은 단위 시간이다. 각 프로세스는 이 시간 동안 CPU를 사용하고, 이후 다음 프로세스에게 CPU를 넘긴다.

 

 4. 다단계 피드백 큐 스케줄링
유닉스 시스템에서는 다단계 피드백 큐 스케줄링을 사용하여 효율적인 프로세스 관리를 구현한다. 

- 다단계 큐: 여러 개의 큐를 사용하며, 각 큐는 서로 다른 우선순위를 가지고 있다.
  - 높은 우선순위 큐: 퀀텀 타임이 짧다.
  - 낮은 우선순위 큐: 퀀텀 타임이 길어진다.

- 우선순위 조정:
  - 새로 도착한 프로세스는 높은 우선순위 큐에 배치된다.
  - 프로세스의 실행 시간이 길어질수록 낮은 우선순위 큐로 이동하게 된다.
  - 이를 통해 CPU 시간을 효율적으로 배분하고, 장기 실행 프로세스에 대한 공평성을 제공한다.

- 공평성:
  - 하위 단계의 큐는 더 긴 퀀텀 타임을 제공하여 프로세스가 충분한 실행 시간을 가질 수 있도록 한다.
  - 다양한 우선순위 큐를 통해 프로세스의 실행 시간과 요구에 따라 적절한 스케줄링이 이루어진다.

ef. 퀀텀 타임 작업 

 

.- 프로세스 \(P1\): 총 12ms의 작업이 필요
- 프로세스 \(P2\): 총 8ms의 작업이 필요
- 프로세스 \(P3\): 총 4ms의 작업이 필요
- 퀀텀 타임: 4ms

 실행 과정:

1. 첫 번째 사이클:
   - \(P1\): CPU를 4ms 동안 할당받아 실행된다. \(P1\)은 4ms의 퀀텀 타임을 모두 사용했지만, 아직 8ms의 작업이 남았다.
   - \(P2\): \(P1\)이 끝나고 \(P2\)가 CPU를 할당받아 4ms 동안 실행된다. \(P2\)는 4ms의 작업을 완료했지만, 4ms의 작업이 더 남았다.
   - \(P3\): \(P2\)가 끝나고 \(P3\)가 CPU를 할당받아 4ms 동안 실행된다. \(P3\)는 4ms의 작업을 모두 완료한다.

2. 두 번째 사이클:
   - \(P1\): 다시 CPU를 할당받아 4ms 동안 실행된다. \(P1\)은 이제 4ms 더 작업을 수행하고, 남은 작업량은 4ms가 된다.
   - \(P2\): \(P1\)이 끝나고 \(P2\)가 다시 CPU를 할당받아 남은 4ms의 작업을 수행하여 모든 작업을 완료한다.
   - \(P3\): \(P3\)는 이미 모든 작업을 완료했으므로 이번 사이클에서 실행되지 않는다.

3. 세 번째 사이클:
   - \(P1\): CPU를 마지막으로 할당받아 남은 4ms의 작업을 완료한다.

 
- \(P1\): 총 12ms의 작업이 필요했기 때문에 3번의 사이클을 거쳐서 작업을 모두 완료
- \(P2\): 총 8ms의 작업이 필요했기 때문에 2번의 사이클을 거쳐서 작업을 완료
- \(P3\): 총 4ms의 작업이 필요했기 때문에 1번의 사이클만으로 작업을 완료

 

 

 

ef. 다단계 피드백 큐

 

다단계 피드백 큐(Multi-level Feedback Queue)는 각 큐 마다 서로 다른 퀀텀 타임(Quantum Time)을 가져 단기 작업은 빨리 처리하고, 장기 작업은 천천히 처리하여 시스템의 효율성과 공평성을 높인다.

 

 다단계 피드백 큐의 동작 원리:

1. 우선순위 큐와 퀀텀 타임:
   - 여러 개의 큐가 있고, 각 큐는 서로 다른 우선순위와 퀀텀 타임을 가진다.
   - 높은 우선순위 큐: 짧은 퀀텀 타임을 가진다.
   - 낮은 우선순위 큐: 긴 퀀텀 타임을 가진다.

2. 프로세스의 이동:
   - 새로운 프로세스: 가장 높은 우선순위 큐에 먼저 배치된다.
   - 퀀텀 타임 초과: 만약 프로세스가 할당된 퀀텀 타임 동안 작업을 완료하지 못하면, 한 단계 낮은 우선순위 큐로 이동한다.
   - 완료되지 않은 작업: 프로세스가 계속해서 작업을 완료하지 못하면, 점점 더 낮은 우선순위 큐로 이동하게 된다.

3. 프로세스의 종료:
   - 프로세스가 CPU에서 충분한 시간을 사용해 작업을 완료하면, 해당 프로세스는 큐에서 제거된다.


 큐 구성:
- 큐 1: 퀀텀 타임 4ms (가장 높은 우선순위)
- 큐 2: 퀀텀 타임 8ms (중간 우선순위)
- 큐 3: 퀀텀 타임 16ms (가장 낮은 우선순위)

 프로세스와 작업량:
- \(P1\): 총 20ms 작업량
- \(P2\): 총 12ms 작업량
- \(P3\): 총 4ms 작업량

 스케줄링 과정:

1. 첫 번째 사이클 (모든 프로세스가 큐 1에서 시작):
   - \(P1\): 4ms 동안 실행되고, 작업량이 16ms 남는다. (큐 2로 이동)
   - \(P2\): 4ms 동안 실행되고, 작업량이 8ms 남는다. (큐 2로 이동)
   - \(P3\): 4ms 동안 실행되고, 모든 작업을 완료한다. (큐에서 제거)

2. 두 번째 사이클 (큐 2):
   - \(P1\): 큐 2에서 8ms 동안 실행된다. 작업량이 8ms 남는다. (큐 3으로 이동)
   - \(P2\): 큐 2에서 8ms 동안 실행된다. 작업을 완료한다. (큐에서 제거)

3. 세 번째 사이클 (큐 3):
   - \(P1\): 큐 3에서 16ms 퀀텀 타임 내에 남은 8ms의 작업을 모두 완료한다. (큐에서 제거)


- \(P1\): 큐 1 → 큐 2 → 큐 3으로 이동하며 작업을 완료한다.
- \(P2\): 큐 1 → 큐 2에서 작업을 완료한다.
- \(P3\): 큐 1에서 작업을 완료한다.

 다단계 피드백 큐의 장점:

- 효율성: 짧은 작업은 빨리 처리하고, 긴 작업은 뒤로 미뤄 시스템 자원을 효율적으로 사용한다.
- 공평성: 모든 프로세스가 CPU 시간을 어느 정도 확보할 수 있도록 한다. 오래 걸리는 작업도 시간이 지나면 긴 퀀텀 타임을 받으므로 충분한 처리 시간을 보장받는다.