운영체제와 정보기술의 원리6 CPU 스케줄링

1. CPU 스케줄링의 등장 이유

• 일반 명령 : CPU 내에서 수행되는 명령이나 메모리에 접근하는 명령
• 특권 명령 : 모든 입출력 명령
  
  
• CPU 버스트 : 사용자 프로그램이 직접 CPU를 가지고 수행하는 명령
• I/O 버스트 : 사용자 프로그램 수행 중 I/O 요청이 발생해서 입출력 작업을 수행하는 명령
  
  
• I/O 바운스 프로세스(I/O bound Job) : I/O 요청이 빈번해서 CPU 버스트가 짧게 나타나는 프로세스 (예) 대화형 프로그램
• CPU 바운스 프로세스(CPU bound Job) : I/O 작업이 거의 없고 CPU 버스트가 길게 나타나는 프로세스 (예) 계산 위주의 프로그램

이와 같이 CPU 사용 패턴이 프로그램마다 다르므로, CPU 스케줄링을 통해서 CPU를 효율적으로 사용할 수 있도록 하는 것이 필요하다.

2. CPU 스케줄러

종류
1. 선점형 방식 : 프로세스가 사용하고 있는 CPU를 강제로 빼앗을 수 있는 방법
2. 비선점형 방식 : 프로세스가 사용하고 있는 CPU를 강제로 빼앗을 수 없는 방법. 프로세스가 CPU를 스스로 반납할 때까지 기다려야 한다.

CPU 스케줄러가 필요한 경우
1. I/O 요청 등에 의해 프로세스가 봉쇄 상태로 바뀌는 경우(비선점형)
2. I/O 작업이 완료되어 프로세스가 준비 상태로 바뀌는 경우(선점형)
3. 타이머 인터럽트가 발생해 프로세스가 준비 상태로 바뀌는 경우(선점형)
4. 실행 중인 프로세스가 종료되는 경우(비선점형)

3. 디스패처

디스패처 : CPU 스케줄링에 의해 선택된 프로세스에게 CPU의 제어권을 넘긴다. 이 과정을 문맥교환이라 한다.

4. 스케줄링의 성능 평가

시스템 관점의 성능 평가 지표
- CPU 이용률 : CPU가 일을 한 시간의 비율
- CPU 처리량 : CPU 버스트를 완료한 프로세스의 개수

사용자 관점의 성능 평가 지표
- 소요시간 : 준비 큐에서 기다린 시간과 실제로 CPU를 사용한 시간의 합
- 대기시간 : CPU 버스트 중에서 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합
- 응답시간 : 프로세스가 준비 큐에 들어온 후 첫번째 CPU를 획득하기까지 기다린 시간

5. 스케줄링 알고리즘

선입선출 스케줄링 First-Come First-Served: FCFS
프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식. 먼저 도착한 프로세스의 성격에 따라서 평균 대기시간이 크게 달라진다.
✱ 콘보이 현상 : CPU 버스트가 짧은 프로세스가 긴 프로세스보다 나중에 도착해서 오랜 시간을 기다려야하는 현상

최단작업 우선 스케줄링 Shortest-Job First: SJF
CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식. 선점형 방식(SRTF)과 비선점형 방식이 있는데, 선점형 방식이 평균 대기시간을 가장 많이 줄일 수 있는 방식이 된다.
✱ 기아 현상 starvation : CPU 버스트가 짧은 프로세스가 계속 도착하면 CPU 버스트가 긴 프로세스는 영원히 CPU를 할당받지 못할 수도 있다.

우선순위 스케줄링
우선순위가 가장 높은 프로세스에게 제일 먼저 할당하는 방식. 만약 우선순위를 CPU 버스트 시간으로 정하면 SJF 알고리즘과 동일하게 된다. 기아현상이 발생할 수 있는데, 노화 기법을 사용해서 문제를 해결할 수 있다.
✱ 노화 기법 aging : 기다리는 시간이 길어지면 우선순위를 조금씩 높인다.

라운드 로빈 스케줄링 Round Robin Scheduling
시분할 시스템의 성질을 가장 잘 활용한 스케줄링 방식. 할당시간을 제한하는 방식. 할당시간이 만료되면  타이머 인터럽트를 사용해서 CPU를 회수한다. 시간이 지나면 적어도 하나씩은 완료되기 때문에 비교적 공정한 스케줄링 방식이라 할 수 있다.
✱ 할당시간 Time Quantum : 프로세스가 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간

멀티레벨 큐 Multi-level Queue
준비 큐를 여러 개로 분할해서 관리하는 스케줄링 기법. 큐에 대한 스케줄링 방식에는 고정 우선순위 방식과 타임 슬라이스 방식이 있다.

멀티레벨 피드백 큐 Multilevel Feedback Queue
멀리레벨 큐와 동일하나, 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다.

다중처리기 스케줄링 Multi-processor System Scheduling
CPU가 여러 개인 시스템. 부하균형 매커니즘이 필요하다. 대칭형 다중처리기와 비대칭형 다중처리기가 있다.

실시간 스케줄링 Real-time Scheduling
각 업마다 주어진 데드라인이 있어서 정해진 데드라인 안에 반드시 작업을 처리해야하는 방식. 경성(hard) 실시간 시스템과 연성(soft) 실시간 시스템 방식이 있다.
✱ EDF(Earlist Deadline First) 스케줄링 방식 : 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 방식.