정의
단일 처리기 시스템에서는 한 순간에 하나의 프로세스만 실행될 수 있다.
즉, 나머지 프로세스는 CPU가 자유상태가 될 때까지 무기한 대기해야 한다.
다중 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행중인 프로세스가 존재하도록 하는 데 있다. (항상 CPU가 일하고 있도록)
❗❗❗❗❗
따라서 운영체제는 CPU를 점유한 프로세스에 대기가 발생할 때마다 그 프로세스로부터 CPU를 회수해서 다른 프로세스에게 할당하는 “스케줄링”을 시도한다.
CPU 스케줄링 용어
CPU 버스트, 입/출력 버스트
프로세스 실행은 CPU 실행과 입/출력 대기의 사이클로 구성된다.
CPU가 필요할 때는 CPU를 집중적으로 사용하다가 입/출력 요청이 발생할 때는 CPU는 잠시 쉬고 입/출력을 대기하게 된다.
프로세스 실행 시...
1) 프로세스가 실행되면 최초에는 CPU 버스트로 시작해서 CPU를 집중적으로 사용한다.
2) 그러다가 입/출력 요청이 발생하면 입/출력 버스트로 교체되고, 이후 입출력이 끝나면 다시 CPU 버스트가 실행된다.
3) 이후에는 이 두 버스트가 반복적으로 발생하는 패턴을 보인다.
입/출력 중심의 프로그램은 전형적으로 긴 입/출력 버스트와 짧은 CPU 버스트를 가지는 편이고,
CPU 지향 프로그램은 전형적으로 짧은 입/출력 버스트와 긴 CPU 버스트를 가지는 편이다.
❗❗❗❗❗
따라서 CPU-입/출력 버스트 분포를 파악해서 CPU 스케줄링 알고리즘을 선택해야 한다.
CPU 스케줄러
CPU 할당을 기다리는 프로세스들이 모여 있는 준비 완료 큐는
선입선출 큐, 우선순위 큐, 순서가 없는 연결 리스트 등으로 구현되어 있다.
입/출력 버스트 등에 의해 CPU가 유휴 상태가 될 때마다, 운영체제는 준비 완료 큐에 있는 프로세스 중 하나를 선택해서 실행해야 한다.
❗❗❗❗❗
이를 수행하는 것이 단기 스케줄러(CPU 스케줄러) 이다.
PCB
준비 완료 큐에 있는 레코드들은 프로세스 제어 블록(PCB) 형태로 존재한다.
PCB란 해당 프로세스 상태, 다음에 실행할 명령어의 주소, 프로세스 우선순위, 프로세스와 연관된 입/출력 장치 등에 대한 다양한 프로세스 정보를 수록한 블록이다.
❗❗❗❗❗
프로세스가 CPU 버스트로 시작해서 CPU를 사용하다가 입/출력 요청이 발생하면 입/출력을 하기 위해 CPU가 잠깐 유휴 상태가 되고 이 때 운영체제가 준비 완료 큐에 들어 있는 프로세스 중 하나를 선택해서 실행하게 된다. 이러한 작업을 “CPU 스케줄러”가 한다.
선점 스케줄링(Preemptive Scheduling)
특정 프로세스에 CPU가 할당되어 사용되는 도중
-
실행되는 프로세스보다 우선 순위가 높은 프로세스가 준비 완료 큐에 들어왔을 경우
-
현재 프로세스가 아직 작업을 마치지 못했는데 자신에게 주어진 CPU 점유 시간을 다 채웠을 경우
현재 프로세스에게 CPU를 할당할 것인지
아니면
다음 프로세스에게 넘겨줄 것인지를 결정하는 것에 따라
“선점/비선점 스케줄링”을 구분한다.
(다음 프로세스에게 넘겨주는 것을 선점형 스케줄링이라고 한다)
디스패처
디스패처는 CPU 스케줄러의 결정에 의해 선택된 프로세스에게 CPU를 넘겨주는 모듈이다.
구체적인 디스패처의 역할은 다음과 같다.
- 문맥 교환(Context Switching)
- 사용자 모드로 전환
- 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치 이동
위와 같은 작업을 수행하면서 소모하는 시간 -> 디스패치 지연(dispatch latency)
CPU 스케줄링 기준
CPU 스케줄링 알고리즘은 모두 서로 다른 특징을 가지고 있는데, 특정 상황에서 더 나은 스케줄링 알고리즘을 선택하기 위해 아래의 기준을 바탕으로 성능을 비교할 수 있다.
-
CPU 이용률(CPU Utilization)
CPU가 사용되는 정도 -
처리량(Throughput)
단위 시간당 완료된 프로세스의 개수(작업량) -
총 처리 시간(Turnaround time)
한 프로세스를 실행하는 데 소요된 시간
프로세스 완료 시간에서 프로세스 제출 시간을 뺀다.
준비 완료 큐에서 대기한 시간, CPU에서 실행하는 시간, 입/출력 시간 등을 포함한다. -
대기 시간(Waiting time)
프로세스가 준비 완료 큐에서 대기하면서 보낸 시간의 합 -
응답 시간(Response time)
대화식 시스템(interactive)을 위한 기준
응답이 시작되는 데까지 걸리는 시간
❗❗❗❗❗
효율적인 스케줄링을 위해서는CPU 이용률과 처리량은 최대화
총 처리 시간, 대기 시간, 응답 시간은 최소화하는 것이 바람직하다.
CPU 스케줄링 알고리즘
선입 선처리 스케줄링(First-Come, First-Served Scheduling, FCFS 스케줄링)
CPU를 먼저 요청한 프로세스가 CPU를 먼저 할당 받는다.
즉, 준비 완료 큐에 들어온 순서대로 프로세스를 할당받는다.
CPU가 자유 상태가 되면 준비 완료 큐의 가장 앞에 있는 프로세스에게 CPU를 할당하고,
준비 완료 큐는 가장 앞에 위치한 프로세스를 제거한다.
즉, 선입선출(FIFO) 큐로 관리된다.
비선점형 스케줄링 기법이다.
장점
- 구현이 간단하다.
단점
- 최소 평균 대기 시간을 보장하지 않는다.
- 하나의 긴 프로세스가 CPU를 점유할 경우 모든 다른 프로세스들이 CPU 양도를 기다리는 호위효과(convoy effect)가 발생하게 된다.
-> 이는 CPU와 장치 이용률을 저하시킨다.
최단 작업 우선 스케줄링(Shortest-Job-First Scheduling, SJF 스케줄링)
가장 작은 CPU 버스트를 가진 프로세스가 CPU를 먼저 할당받는다.
단, 두 프로세스가 동일한 길이의 다음 CPU 버스트를 가질 경우에는 FCFS 스케줄링을 사용한다.
선점형, 비선점형 스케줄링을 모두 적용할 수 있다.
장점
- 최소 평균 대기 시간을 보장하므로 평균 대기 시간을 기준으로 스케줄링 기법을 비교한다면 “최적의 스케줄링 기법”이다.
단점
- 다음 CPU 버스트 길이를 미리 파악하기가 어렵다.
우선순위 스케줄링(Priority Scheduling)
각 프로세스는 특정 기준에 의해 우선순위가 부여되고 이 기준에 의해 우선순위가 가장 높은 프로세스가 CPU를 먼저 할당 받는다.
단, 우선순위가 같은 프로세스들은 FCFS 스케줄링을 적용한다.
SJF 스케줄링 역시 우선순위 스케줄링의 한 종류라고 볼 수 있다.
우선순위의 기준으로는
시간 제한, 메모리 요구, 열린 파일의 수, 평균 입/출력 버스트의 평균 CPU 버스트의 비율, 프로세스의 중요도, 비용, 정치적인 요인
등이 있다.
선점형, 비선점형 스케줄링을 모두 적용할 수 있다.
-
선점형 스케줄링을 적용할 경우
준비 완료 큐에 새로운 프로세스가 들어오면
현재 진행 중인 프로세스와 우선순위를 비교해서
우선순위가 더 높은 프로세스가 CPU를 선점한다.
-
비선점형 스케줄링을 적용할 경우
현재 진행 중인 프로세스를 계속 진행하되
새로 들어온 높은 우선순위의 프로세스는 준비 완료 큐의 머리 부분에 삽입한다.
장점
- 우선순위를 고려할 수 있다.
단점
- 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 문제(무한 봉쇄, indefinite blocking) 혹은 기아 상태(starvation)가 발생할 수 있다.
단점 해결 방법
- aging: 오랫동안 대기하는 프로세스들의 우선순위를 점진적으로(특정 시간마다) 증가시켜주는 기법(노화, aging)을 적용할 수 있다.
라운드 로빈 스케줄링(Round-Robin Scheduling)
사전에 CPU 시간 할당량(time quantum) 또는 시간 조각(time slice)를 설정하고, 한 프로세스에게 지정된 시간 할당량만큼의 CPU 점유 시간을 부여하는 스케줄링 기법이다.
시간 할당량만큼 CPU를 점유한 프로세스에게는 인터럽트가 발생하도록 타이머를 설정한 후, 프로세스를 디스패치한다.
시분할 시스템을 위해 설계된 기법이다.
이 때, 준비 완료 큐는 선입선출(FIFO) 큐로 관리한다.
선점형 스케줄링 기법이다.
프로세스는 주어진 시간 할당량 이내에 작업을 완료할 수도 있고 완료하지 못할 수도 있다.
이 때는 다음과 같이 처리하면 된다.
-
프로세스의 CPU 버스트 < 시간 할당량
프로세스가 종료된 이후 자신이 자발적으로 CPU를 방출한다. -
프로세스의 CPU 버스트 > 시간 할당량
타이머가 끝나고 인터럽트가 발생되면 Context Switching이 일어나고 실행하던 프로세스는 준비 완료 큐의 꼬리에 위치한다.
장점
- 프로세스가 n개 존재하고 각 프로세스 당 시간 할당량이 q라고 가정한다면, 각 프로세스는 다음 시간 할당까지 최대 (n – 1) * q 이상을 대기하지 않음을 보장할 수 있다.
단점
- 시간 할당량의 크기 설정에 따라 알고리즘의 성능이 크게 영향을 받게 된다.
+ 시간 할당량이 지나치게 크면 선입 선처리 스케줄링 기법과 같아질 수 있다.
+ 시간 할당량이 지나치게 작으면 Context Switching 오버헤드가 커져서 총 처리 시간(Turnaround time)이 증가한다.
다단계 큐 스케줄링(Multilevel Queue Scheduling)
준비 완료 큐를 다수의 별도의 큐로 분류해서 각 큐마다 제각각의 스케줄링 알고리즘을 적용하는 방법이다.
프로세스는 포어그라운드(foreground, 대화형) 프로세스와 백그라운드(background, 일괄처리) 프로세스로 구분될 수 있다.
일반적으로 대화형 시스템을 위해 포어그라운드 프로세스가 우선순위를 가지는 경우가 많다.
따라서 프로세스의 메모리 크기, 프로세스의 우선순위, 프로세스 유형, 프로세스 특성에 따라 각각의 프로세스는 특정 큐에 할당될 수 있다.
단, 프로세스는 큐 간 이동할 수 없다.
각 큐는 낮은 우선순위의 큐보다 절대적인 우선순위를 가진다. 또한, 큐들 사이에 시간을 나누어 CPU를 사용하기도 한다.
선점형 스케줄링 기법이다.
다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)
다단계 큐 스케줄링에서 프로세스가 큐들 사이를 이동하는 것을 허용한 방법이다. (다단계 큐 스케줄링 기법에서 큐 간 프로세스 이동을 가능하게 한 것)
특정 프로세스가 CPU를 너무 많이 점유할 경우, 해당 프로세스를 낮은 우선순위 큐로 이동시킬 수 있다.
또한, 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위 큐로 이동(노화, aging)시킬 수 있다.
역시 각 큐는 낮은 우선순위의 큐보다 절대적인 우선순위를 가지고 큐들 사이에 시간을 나누어 CPU를 사용할 수도 있다.
선점형 스케줄링 기법이다.
다중 처리기 스케줄링(Multiple-Processor Scheduling)
위에서 정리한 CPU 스케줄링 기법은 단일 처리기 시스템 아래에서 하나의 CPU를 어떻게 스케줄링할 것인지를 결정한 것이다. 하지만 CPU가 여러 개라면 여러 개의 CPU를 여러 프로세스에게 할당해야 하는 더 복잡한 문제가 발생하게 된다.
그렇기 때문에 다중 처리기 시스템이 CPU 스케줄링 시 고려해야 하는 부분은 단일 처리기 시스템과는 다르다.
다중 처리기 시스템에서의 스케줄링 결정 대상
-
비대칭 다중 처리(asysmmetric multiprocessing)
주 서버라는 하나의 처리기가 모든 스케줄링 결정을 내린다.다른 서브 처리기들은 주 서버의 결정에 따라 사용자의 코드만을 수행한다.
주 서버 처리기만 시스템 자료 구조에 접근하므로 자료 공유로 인한 문제가 발생하지 않는다.
-
대칭적 다중 처리(symmetric multiprocessing, SMP)
각 처리기가 독자적으로 스케줄링을 한다.각 처리기는 공통의 준비 완료 큐에서 프로세스를 선택할 수도 있고, 자신만의 독자적인 준비 완료 큐를 구성할 수도 있다.
다중 처리기가 공동의 시스템 자료 구조에 접근하므로 자료 공유 문제를 고려해야 한다.
또한, 공통의 준비 완료 큐를 사용할 경우 다중 처리기가 공통된 프로세스를 선택하지 않도록 조심해야 한다.
다중 처리기 시스템에서의 스케줄링 쟁점
1. 처리기 친화성(Processor Affinity)
프로세스가 여러 처리기로 이동하게 될 경우 캐시 메모리를 채우고 비우는 오버헤드가 발생한다.
따라서 한 처리기에서 다른 처리기로의 이주를 피하고, 대신 같은 처리기에서 프로세스를 실행시키려고 하는 현상을 보이는 데 이 현상을 처리기 친화성이라고 한다.
2. 부하 균등화(Load Balancing)
모든 처리기 사이의 부하가 고르게 배분되도록 하는 것을 말한다.
대칭적 다중 처리 시스템에서 여러 처리기를 최적으로 활용하기 위해서는 부하 균등화가 잘 이루어져야 한다.
부하 균등화는 대칭적 다중 처리 시스템의 각 처리기가 공통의 준비 완료 큐가 아닌 자기 자신만의 큐를 가지고 있을 때 적용 가능하다.
한 처리기가 과부하 상태일 때 여유로운 처리기로 프로세스를 이동시키는 것을 push, 여유로운 처리기에서 과부하 처리기의 프로세스를 이주시키는 것을 pull이라고 한다.
단, 부하 균등화는 위에서 소개한 처리기 친화성과 상충되므로 사전에 부하 불균형 상태에 대한 적절한 정의가 이루어져야 한다.
3. 대칭적 다중 스레딩(Symetric Multithreading)
대칭적 다중 처리 시스템은 다수의 물리적인 처리기를 제공하는 것을 이야기한다.
이와 달리 동일한 물리 처리기 상에 다수의 논리적인 처리기를 제공해서 다수의 스레드가 동시에 실행되도록 하는 것을 대칭적 다중 스레딩(SMT, 하이퍼스레딩 기술(hyperthreading technology))이라고 한다.
논리적인 처리기는 하나의 물리적인 처리기 내부에 여러 개 존재할 수 있다.
이 논리적인 처리기들은 캐시 메모리, 버스 등과 같은 자신이 속한 물리적인 처리기의 자원을 공유하며 사용한다
