CPU 스케줄링

다중 프로그래밍

다중프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는 데 있다. 한 프로세스가 입출력하고 있을 때 다른 포르세스가 대기하고 있다면 CPU입장에서는 엄청난 낭비가 발생하는 것이다. 그래서 어떤 프로세스가 대기하고 있을 때 CPU에 다른 프로세스를 할당해주어서 CPU가 항상 실행중인 프로세스를 갖게 해주는 것이다. 

 

CPU 스케줄러

CPU가 유휴 상태가 될 때마다, 운영체제는 준비 완료 큐에 있는 프로세스들 중에서 하나를 선택해 running 상태로 만드는 것이다. 즉 여기서 CPU가 선택되는 방법에 대해서 배울 것입니다. 

 

스케줄링

CPU 스케줄링 결정 과정

 

1. 한 프로세스가 running 상태에서 waiting 상태가 될 때 

 

2. 프로세스가 running 상태에서 ready 상태가 될 때 

 

3. 프로스가 waiting 상태에서 ready 상태가 될 때 

 

4. 프로세스가 종료할 때 

 

상황 1, 4의 경우에는 스케줄링 면에서 선택의 여지가 없다. 즉 새로운 프로세스가 반드시 선택되어야 한다. 

 

이런 상황을 비선점 스케줄링이라고 한다. 그렇지 않으면 보통은 선점 스케줄링이라고 한다. 

 

디스패처

디스패처는 CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈이다. 아래와 같은 작업을 실행한다. 

 

• 문맥 교환
• 사용자 모드로 전환
• 사용자 프로그램의 적절한 위치로 이동

디스패처는 모든 프로세스의 문맥 교환시에 호출되므로 가능한 빨리 수행되어야한다. 다른 프로세스가 실행되는 때 까지 걸리는 시간을 디스패치 지연이라고 한다. 

 

스케줄링 알고리즘

스케줄링 알고리즘은 CPU 이용률과 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소하하는 것이다. 

 

선입 선처리 스케줄링(FCFS 스케줄링) - 비선점 스케줄링

CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다. 선입 선처리 정책의 구현은 선입선출 큐로 쉽게 관리할 수 있다. 

 

즉 큐에서 한개씩 꺼내서 CPU에 할당해준다. 하지만 모든 프로세스들이 하나의 긴 프로세가 종료될 때 까지 기다리는 것은 매우 비효율적이다. 이를 호위효과(convey effect)라고 부른다. 

 

최단 작업 우선 스케줄링(SJF 스케줄링) - 선점, 비선점 둘다 가능

이 알고리즘은 프로세스를 선택할 때 가장 실행시간이 짧은 프로세스를 선택해서 run시킨다. 

 

SJF 스케줄리의 경우 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균 대기 시간을 가진다. 하지만 프로세스의 실제 실행 시간이 짧은 경우를 확인하기 어렵기 때문에 단기 CPU 스케줄링의 경우에는 구현하기 어렵다. 

 

만약 새로운 프로세스가 큐에 도착했을 때 두가지의 경우에 놓인다 현재 실행중인 프로세스들 보다 시간이 적으면 뺐을 수도 있고 아니면 종료될 때 까지 기다렸다가 선택되어 실행될 수 있다. 

 

뺐으면 이를 선점형 종료 될 때 까지 기다린 후 실행되면 이를 비선점형이라고 한다. 

 

우선순위 스케줄링(priority 스케줄링) - 선점, 비선점 둘다 가능

CPU는 가장 우선순위가 높은 프로세스를 할당하고 우선순위가 같은 경우에는 FCFS 스케줄링된다. SJF의 경우에는 단순히 CPU의 실행시간이 가장 중요한 우선순위로 선택된 것이다. 

 

우선순위는 내부적 외부적으로 정의될 수 있다. 

 

내부적은 시간 제한, 메모리 요구, 열린 파일의 수, 평균 입출력 버스트의 평균 CPU 버스트에 대한 비율 등의 우선순위의 계산에 사용된다. 

 

외부적은 프로세스의 중요성, 컴퓨터 사용을 위해 지불되는 비용의 타입과 양 등에 의해 결정된다. 

 

선점형일 때는 큐에 현재 실행되고 있는 프로세스보다 더 높은 순위의 프로세스가 들어오면 교체된다. 

 

비선점형일 때는 현재 실행중인 프로세스가 끝날 때까지 기다린 후 큐에서 우선순위가 높은 프로세스를 고른다. 

 

우선순위 스케줄링의 문제점은 무한 봉쇄 또는 기아현상이다. 즉 우선순위가 낮은 프로세스들은 영원히 실행되지 못할 수 있다는 의미이다. 

-> 해결방법은 우선순위가 낮은 프로세스를 점진적으로 우선순위를 증가시켜서 나중에는 실행될 수 있게 만든다. 

 

라운드 로빈 스케줄링(Round-Robin 스케줄링) - 선점형

시분할을 위해 설계되었다. FCFS 스케줄링이랑 비슷하지만 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가된다. 

 

이 스케줄링은 시간할당량을 정해준다. 해당 시간할당량 만큼 실행되었지만 아직 완료하지 못한 경우 다시 남은 양만큼 준비 완료 큐에 들어가게 만든다. 

 

하지만 시간 할당량 보다 실행 시간이 적은 경우에는 바로 종료되고 프로세스가 교환된다. 추가되는 경우에도 가차없이 프로세스가 교환된다.  그래서 라운드 로빈 스케줄링을 선점형 스케줄링이라고 한다. 

 

시간 할당량은 적당히 정해야한다. 

 

너무 많이 할당할 경우 FCFS와 크게 비슷하지 않게 되고 너무 적게 할당할 경우에도 너무 많은 문맥교환을 야기해서 좋지 않다. 

 

다단계 큐 스케줄링(Multilevel Queue 스케줄링)

여러 개의 큐를 만들어서 포그라운드 프로세스들은 백그라운드 프로세스들보다도 높은 우선순위를 가질 수 있다. 그리고 각 큐는 서로 다른 스케줄링 알고리즘을 가질 수 있다. 큐와 큐사이에 스케줄링도 반드시 있어야 하며 일반적으로 고정 우선순위의 선점형 스케줄링으로 구현된다. 

다단계 큐 스케줄링

하지만 이와 같은 경우에 높은 우선순위의 큐에서 프로세스들이 비지 않으면 아래의 프로세들은 기회가 오지 않아서 기아, 무한 봉쇄의 문제가 발생한다.

 

다단계 피드백 큐(Multilevel Feedback Queue 스케줄링)

다단계 큐에 비해서 큐간의 이동을 허용한다. 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위 큐로 이동한다. 낮은 우선순위 큐에서 너무 오래 대기하는 경우에는 높은 우선순위 큐로 이동할 수 있다.

 

 

일반적으로 다단계 피드백 큐 스케줄러는 다음의 매개변수에 의해 정의된다. 

 

• 큐의 개수
• 각 큐를 위한 스케줄링 알고리즘
• 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
• 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
• 프로세스가 들어갈 큐를 결정하는 방법

큐 스케줄러의 정의에 의하면 이 스케줄링 알고리즘은 가장 일반적인 CPU 스케줄링 알고리즘이다. 그렇지만 모든 매개변수들의 값을 선정하는 특정 방법이 필요하기 때문에 또한 가장 복잡한 알고리즘이다. 

 

다중 처리기 스케줄링

이전에 논의는 단일 처리기를 가진 시스템에서 CPU를 스케줄 하는 문제에 주안점을 두었다. 그렇지만 여러 개의 CPU가 사용 가능하다면 부하 공유가 가능해진다. 

 

다중 처리기 스케줄링에 대한 접근 방법

CPU 스케줄링에 관한 한 가지 해결방법은 주 서버(master)라는 하나의 처리기에 여러개(slave)를 붙여서 코드를 실행한다. 이를 비대칭 다중 처리라고 한다. 

 

대칭 다중처리를 사용하는 방법은 각 처리기가 동등하게 os를 갖고 독자적으로 스케줄링한다. 지금 Windows, Linux, Mac Os X 등의 현대 운영체제들은 SMP(대칭 다중 처리)를 지원한다. 

 

처리기 친화성(Processor Affinity)

프로세스가 특정 처리기에서 실행 중 다른 특정 처리기로 옮길 때 캐시를 비우고 다시 캐시를 채우는 비용이 많이 드는 연산이 발생한다. 

하지만 SMP의 경우에는 다른 처리기의 이주를 피하고 대신 같은 처리기에서 프로세스를 실행시키려고 한다. 

 

운영체제가 동일한 처리기에서 프로세슬 실행시키려고 노력하는 정책을 가지고 있지만 보장하지 않을 때 연성 친화성을(soft affinity)를 가진다. 

 

강성 친화성을 지원하는 시스템을 지원하는 시스템 호출을 제공하는데 이 시스템 호출을 통해 프로세스는 자신이 실행될 처리기 집합을 명시할 수 있다. 

UMA: 메모리 접근시간이 균등하다.

 

NUMA: 메모리 접근시간이 비균등하다.

 

Load Balancing

Load Balancing의 경우에는 SMA에서 하나의 처리기가 부화되면 연산을 바쁘지 않는 다른 처리기로 분배해서 실행시키게 만드는 것을 의미한다. 

 

pull 이주: 쉬고 있는 처리기가 바쁜 처리기에 대기하고 있는 프로세스를 가져온다. 

 

push 이주: 특정 태스트가 주기적으로 각 처리기의 부하를 검사하고 만일 불균형 상태로 밝혀지면 과부화인 처리기에서 덜 바쁜 처리기로 옮긴다. 

 

다중코어 프로세서 

다수의 물리 처리기를 제공함으로서 다수의 스레드를 동시에 실행되게 한다. 하지만 최근에는 하나의 칩안에 여러개의 코어를 만드는 다중코어 프로세서를 이용한다. 이러한 다중코어 프로세서도 운영체제 입장에서는 각 코어가 물리적인 처리기 처럼 보이게된다. 

 

다중코어 프로세서를 이용한 SMP는 더 빠르고 저전력을 소모한다. 

 

연산을 진행하기 전에 필요한 데이터가 없음으로써 메모리 멈춤현상이 발생할 수 있다. 

 

거친 다중스레딩

 

스레드가 메모리 멈춤과 같은 긴 지연시간을 가진 사건이 발생할 때까지 한처리기에서 수행된다. 긴 지연시간을 발생하게 되면 다른 스레드를 실행하게 된다. 이 경우 명령어 파이프 라인이 사라져야 하기 때문에 다른 스레드로 옮기는데 큰 비용이 발생한다.

 

세밀한 다중 스레딩

 

명령어 사이클의 경계와 같이 정밀한 시점에서 스레드 교환이 일어난다. 

 

다중 코어 프로세서는 사실상 두 단계의 스케줄링이 필요하다. 

 

1. 소프트웨어 스레드가 각 하드웨어 스레드에서 실행되어야 하는지를 운영체제가 결덩해야 하는 것이 한 단계이다. 

 

2. 각 코어가 어떤 하드웨어 스레드를 실행시킬 지 지정해야한다. 

 

실시간 CPU 스케줄링

연성 실시간 시스템

 

중요한 프로세스가 스케줄되는 시점에 관해 아무런 보장을 하지 않는다. 오직 중요 프로세스가 그렇지 않은 프로세스들에 비해 우선권을 가진 것만 보장한다.

 

경성 실시간 시스템

 

엄격한 요구조건을 만족시켜야한다. 태스크는 반드시 마감시간까지 서비스를 받아야 하며 마감시간이 지난 이후에 서비스를 받는 것은 서비스를 전혀 받지 않은 것과 동일한 결과를 낳는다.