버스트
프로세스의 실행은 CPU에 의해 명령어가 실행되는 것과, 입출력장치를 통한 작업을 기다리는 것을 반복하는 것이다. 이때, CPU에 의해 명령어가 실행되는 동안의 시간을 CPU 버스트라고 하고, 입출력 작업을 수행하는 동안의 시간을 IO 버스트라고 한다.
일반적으로 CPU 버스트는 매우 짧다. 아래 그래프는 일반적인 프로세스의 실행부터 종료까지 발생한 CPU 버스트의 빈도를 나타낸 그래프다. 물론, 프로세스마다 이런 그래프는 다 다르게 나타난다. 연산이 위주인 프로세스는 더 긴 CPU 버스트를 보일 것이다. 어쨋든 이런 분포는 스케줄링 알고리즘을 선택하는데 중요한 기준이 된다.
스케줄링 알고리즘 기초
스케줄링은 아래 4가지 상황에서 발생한다.
1.
실행중인 프로세스가 실행 상태에서 대기 상태로 전환될 때. (입출력 발생, 자식 프로세스 종료 대기 등)
2.
프로세스가 실행 상태에서 준비 완료 상태로 전환될 때. (인터럽트 발생)
3.
프로세스가 대기 상태에서 준비 완료 상태로 전환될 때. (입출력 종료)
4.
실행중인 프로세스가 종료될 때.
1번과 2번 상황에선 스케줄링이 무조건 발생한다. 그런데, 2번과 3번 상황의 경우 현재 실행중인 프로세스를 그대로 수행할 수 있는 상황이기 때문에 스케줄링이 발생하지 않아도 된다.
선점 스케줄링
2번과 3번 상황 중 적어도 어느 하나의 상황이 발생했을 때 스케줄링이 일어나는 알고리즘.
선점 스케줄링은 결국, 현재 실행중인 프로세스를 강제로 일시중지하고 다른 프로세스를 실행하는 것이다. 따라서 여러 프로세스가 공유하는 자원을 일시중지 대상인 프로세스가 접근하고 있다면 공유자원에 대한 프로세스간의 동기화문제를 해결해야 한다. 가령 일시 중지 대상의 프로세스가 공유 자원에 쓰기 작업을 하는 도중에 일시중지되고, 다른 프로세스가 이를 읽게 된다면 잘못된 상태의 공유 자원을 읽게 될 수 있다. 같은 이치로 모든 프로세스가 공유하는 커널영역의 어떤 변경을 유발하는 시스템 콜을 수행중인 프로세스를 일시중지하게 되면 문제가 발생할 수 있다. 따라서, 선점 스케줄링을 지원하려면 운영체제는 이런 문제가 발생하지 않도록 신경써야 한다.
비선점 스케줄링
1번과 4번 상황이 발생했을 때만 스케줄링이 일어나는 알고리즘.
스케줄링 알고리즘의 성능 판단 기준
•
CPU 이용률(CPU utilization): 전체 시스템 가동 시간에 대한 CPU가 연산을 하고 있는 시간의 비율.
•
처리량(Throughput ): 단위 시간당 완료된 프로세스의 개수.
•
총처리 시간(Turnaround time) : 특정 프로세스를 실행하는데 걸리는 시간. 메모리에 들어가기 위해 기다리며 소비한 시간, 준비 완료 큐에서 대기한 시간, CPU에서 실행하는 시간, 그리고 입/출력 시간을 합한 시간.
•
대기 시간(Waiting time): 특정 프로세스가 준비 완료 큐에서 대기하면서 보낸 시간의 합.
•
응답 시간 (Response time): 하나의 요구를 제출한 뒤 첫 번째 응답이 나올 때까지의 시간. 입출력 장치의 속도에 제한된다.
성능 판단 방법
1.
결정론적 모델링 : 프로세스의 정보들을 미리 정해 그 집합에 대한 성능 분석을 하는 방법. ⇒ 실제로는 실행할 프로세스가 날마다 바뀌기 때문에 사용하기 힘든 방법이다.
2.
큐잉 모델링 : CPU 버스트와 IO 버스트를 측정및 추정하여 그 분포를 이용해 수학적인 분석을 하는 방법 ⇒ 결국 실제 시스템의 근사치일 뿐이다.
3.
시뮬레이션 : 코드 짜서 시뮬레이션 하는 방법 ⇒ 비용이 비싸다
스케줄링 알고리즘
FIFO 스케줄링
CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는 알고리즘. 준비 완료 큐가 일반적인 큐다.
이 방식은 아주 간단하지만, 평균 대기 시간이 매우 길 수 있다. 먼저 CPU를 요청한 프로세스가 긴 CPU 버스트를 가지는 프로세스라면, 나중에 CPU를 요청한 프로세스가 짧은 CPU 버스트를 가지고 있어도 오래 대기해야 한다.
0초에 거의 동시에 준비 완료 큐에 도착한 세 프로세스의 CPU 버스트가 다음과 같다고 하자.
•
P1 : CPU 버스트 24
•
P2 : CPU 버스트 3
•
P3 : CPU 버스트 3
P1 , P2, P3 순서로 CPU를 요청했다면 프로세스의 평균 대기 시간은 (0 + 24 + 27) / 3 = 17 이다.
FIFO 스케줄링 - CPU 버스트가 큰 프로세스가 먼저 도착한 경우
만약, P2, P3, P1 순서로 CPU를 요청했다면 프로세스의 평균 대기 시간은 (0 + 3 + 6) / 3 = 3 이다.
FIFO 스케줄링 - CPU 버스트가 작은 프로세스가 먼저 도착한 경우
결국, 짧은 CPU 버스트를 가지는 여러 프로세스가 긴 CPU 버스트를 가지는 프로세스를 기다리게 되어 CPU와 입출력 장치의 이용률이 떨어지게 된다.
SJF 스케줄링
CPU 버스트가 짧은 프로세스가 먼저 CPU에 할당된다. 이때, 프로세스의 전체 길이가 아니라, 다음 CPU 버스트가 가장 짧은 프로세스를 먼저 CPU에 할당한다.
이 방식은 각 프로세스의 평균 대기 시간이 최소임이 보장된다. FIFO 알고리즘의 예시에서, CPU 버스트가 큰 프로세스에 먼저 CPU가 할당되면 평균 대기 시간이 늘어나는 것을 보았다. 반대로 CPU 버스트가 낮은 프로세스에 먼저 CPU가 할당되면 평균 대기시간이 줄어든다. 따라서, 매 시점 가장 CPU 버스트가 짧은 프로세스에 할당된다면 평균 대기 시간이 최소가 된다.
다음 CPU 버스트를 정확히 알 수 없기 때문에 엄밀한 SJF 스케줄링은 이론상 가능한 알고리즘이다.
실제로 다음 CPU 버스트를 정확히 알 수 없으니 이를 예측해야 한다. 이전 CPU 버스트를 통해 다음 CPU 버스트를 예측할 수 있다.
이를 재귀적으로 정리하면
이므로, 오래된 CPU 버스트일수록 가중치가 작아진다.
선점형과 비선점형을 모두 생각할 수 있다.
한 프로세스를 실행하는 동안 다른 프로세스가 준비완료 큐에 도착할 수 있다. 그리고, 현재 실행중인 프로세스의 남은 CPU 버스트보다 새로 도착한 프로세스의 CPU 버스트가 더 짧을 수 있다. 선점형 SJF 알고리즘이라면 이 경우 스케줄링이 동작할 것이지만, 비선점형 SJF 알고리즘이라면 스케줄링이 동작하지 않을 것이다.
우선순위 스케줄링
프로세스에 특정 우선 순위를 부여해 이를 기준으로 스케줄링 하는 알고리즘이다. SJF 알고리즘은 이 우선순위의 기준을 다음 CPU 버스트가 가장 짧은 것으로 하는 경우다. (= SJF 알고리즘은 우선순위 알고리즘의 특별한 경우다.)
우선순위의 기준은 다양한 것을 사용할 수 있다. 내부적으로 어떤 측정 가능한 양을 사용할 수도 있고, 프로세스의 중요성이나 프로세스의 실행을 위해 필요한 자원 등의 외부적인 기준을 사용할 수도 있다.
SJF 알고리즘과 마찬가지로 선점형과 비선점형 모두 가능하다.
한 프로세스를 실행하는 동안 다른 프로세스가 준비완료 큐에 도착할 수 있다. 그리고, 현재 실행중인 프로세스의 우선순위보다 새로 도착한 프로세스의 우선순위가 더 높을 수 있다. 선점형 알고리즘이라면 이 경우 스케줄링이 동작할 것이지만, 비선점형 알고리즘이라면 스케줄링이 동작하지 않을 것이다.
무한히 대기하는 프로세스가 생길 가능성이 있다. ⇒ 노화 기법으로 해결
만약, 특정 프로세스의 우선순위가 매우 낮게 설정될 경우, 매번 다른 프로세스에 밀려 실행되지 않을 수 있다. 이를 방지하기 위해 오래 대기하고 있는 프로세스의 우선순위를 점진적으로 올려주는 노화 기법을 적용할 수 있다.
라운드 로빈(RR) 스케줄링
FIFO 알고리즘에 추가적으로 주어진 시간 할당량 이내에서만 CPU를 사용하고 선점되는 방식이다.
FIFO 알고리즘에서와 마찬가지로 가장 먼저 CPU 요청을 한 프로세스가 CPU에 할당된다. 이후 미리 정해진 시간 할당량이 지나거나 CPU 버스트가 끝나면 스케줄링이 발생한다.
구체적인 예를 들면, 시간 할당량이 10 인 RR 알고리즘에서, P1의 CPU 버스트가 13 이라면, 10 만큼만 CPU를 사용하다가 선점되어 다음 프로세스 P2가 CPU를 할당받고, P1은 준비완료 큐의 맨 끝에 추가된다. 나중에 P1의 차례가 되면 남은 CPU 버스트인 3만큼만 CPU를 사용하고 다음 프로세스로 차례가 넘어간다.
시간 할당량의 크기에 따라 RR 알고리즘의 성능이 극명하게 갈린다.
시간 할당량이 어떤 프로세스의 CPU 버스트도 그보다 클 정도로 충분히 작다면, 시간 할당량이 n인 RR 알고리즘은 n개의 실제 CPU 성능의 1/n인 가상 CPU를 사용하는 것이다. 그러나, 이 경우 문맥 교환이 자주 발생하게 되므로 이로 인한 오버헤드가 커져 스케줄링 성능이 줄어든다. 반대로 시간 할당량이 어떤 프로세스의 CPU 버스트도 그보다 작을 정도로 충분히 크면 그것은 FIFO와 같다. 이런 이유로 시간 할당량은 문맥 교환 시간보다 크면서도 CPU 버스트의 80%정도만 시간 할당량보다 작을 정도로만 커야 한다.
다단계 큐 스케줄링
여러 개의 준비 완료 큐를 사용하는 우선순위 알고리즘이다. 각 프로세스는 그 특성에 따라 하나의 큐에 영구적으로 할당된다. 여러 준비 완료 큐 사이의 우선순위도 고려되어야 한다.
이 방식에서는 두가지 관점의 우선순위가 고려되어야 한다. 하나는 같은 큐 내에서 다음 스케줄링 대상이 되는 프로세스를 선정하는 우선순위이고, 다른 하나는 여러 큐 사이에서 어떤 큐에 다음 스케줄링 대상이 되는 프로세스를 선정하는 권한을 줄지 결정하는 우선순위이다.
또한, 여러 개의 큐에 어떤 기준으로 프로세스를 할당할 것인지도 고려되어야 한다. 예를 들어 시스템 응용프로그램이 포함되는 시스템 프로세스 큐, 실시간으로 사용자와 소통하는 실시간 프로세스 큐, 한번에 대량의 데이터를 일괄적으로 사용하는 배치 프로세스 큐 등으로 나눌 수 있다. 이는 철저히 구현하기 나름이다.
큐의 우선순위와 프로세스를 큐에 할당하는 기준을 복합적으로 고려해 각 큐마다 다른 알고리즘을 적용할 수 있다. A 큐에 속한 프로세스가 모두 동일하게 실행되는 것을 보장해야 된다면 RR 알고리즘을 사용할 것이다. 한편, B 큐에 속한 프로세스들은 CPU 버스트가 매우 짧은 입출력 위주의 프로세스라면 FIFO 알고리즘을 사용할 수 있다.
큐 사이의 우선순위를 구현하는 방법은 각 큐에 절대적인 우선순위를 부여해 상위 우선순위의 큐에 프로세스가 존재하면 하위 큐의 프로세스는 계속 대기하게 할 수도 있고, 마치 RR 알고리즘에서 프로세스에 시간 할당량을 주는 것 처럼 각 큐에 시간 할당량을 주는 방법도 있다. 이 경우 큐마다 시간 할당량이 다를 수 있다.
다단계 피드백 큐 스케줄링
프로세스가 큐 사이의 이동을 허용하는 다단계 큐 스케줄링
다단계 큐 스케줄링에서 프로세스가 하나의 큐에만 고정적으로 할당된다면, 프로세스를 어떤 큐에 할당해야 하는지 결정하는 오버헤드가 적지만, 융통성이 적게 된다. 프로세스가 실행중에 예측 불가능한 요인에 따라 그 특성이 변경 될 수 있고, 우선순위가 낮은 큐에 들어간 프로세스가 너무 오래 대기할 수도 있다. 이를 해결하기 위해 프로세스가 큐 사이의 이동을 가능하게 한 것이다. 예를 들어 프로세스가 CPU를 너무 많이 사용한다면 더 낮은 우선 순위의 큐로 이동시켜 다른 프로세스가 CPU를 사용할 수 있도록 하고, 반대로 CPU를 너무 적게 사용한다면 더 높은 우선순위의 큐로 이동시켜 CPU를 사용할 수 있도록 할 수 있다.
이 분류의 알고리즘을 서술하려면 다음 5가지 기준을 설명해야 한다.
1.
큐의 개수
2.
각 큐를 위한 스케줄링 알고리즘
3.
한 프로세스를 높은 우선순위의 큐로 이동시키는 시기를 결정하는 방법
4.
한 프로세스를 낮은 우선순위의 큐로 이동시키는 시기를 결정하는 방법
5.
프로세스가 처음 들어갈 큐를 결정하는 방법
다중 처리기 스케줄링
접근 법
비대칭 다중 처리(AMP)
하나의 주 처리기가 스케줄링, 입출력 처리 등 모든 시스템 활동을 결정하게 하고, 다른 처리기들은 사용자 코드만 처리하게 하는 방법.
쉽게 말해 하나의 주 처리기가 다른 처리기가 실행할 명령을 할당하는 방법이다. 따라서 자원의 공유를 고려하지 않아도 되지만, 주 처리기가 느리면 다른 처리기를 낭비하는 상황이 생긴다.
대칭 다중 처리(SMP)
여러 처리기가 독자적으로 스케줄링을 하는 방식.
이 방식은 각 처리기가 저마다 준비 완료 큐에 있는 프로세스를 독자적으로 선정해 프로세스를 실행한다. 이 방식에서 모든 처리기가 공통된 준비완료 큐를 공유할 수도 있고, 저마다 다른 준비완료 큐를 가지고 있을 수도 있다. 각 처리기가 공통된 자원을 공유하므로 이를 처리하는 동기화가 고려되어야 한다. 예를 들어 준비완료 큐를 공유한다면 한 프로세스를 여러 처리기가 동시에 선택하면 안되고, 프로세스가 실행되지 않고 있는데 큐에서 사라지는 상황이 발생하면 안된다.
대칭 다중 처리에서 고려할 사항들
처리기 친화성
프로세스가 특정 처리기에서만 실행되도록 하는 경향성. 캐시의 재작성 비용을 아끼기 위한 것.
각 처리기에는 저마다 캐시 메모리를 가지고 있다. 이 캐시 메모리를 통해 특정 프로세스를 실행하기 위해 필요로 하는 데이터를 더 빠르게 가져올 수 있다. 그런데, 프로세스가 다른 처리기로 넘어간다면 기존 처리기의 캐시 메모리는 무효화되어야 하고, 새 처리기의 캐시 메모리는 다시 채워져야 한다.
따라서, 한 프로세스는 같은 처리기에서 수행하는 것이 캐시를 다시 작성하는 비용을 아끼는 것이다. 그리고 이 비용은 꽤 크다. 무조건 같은 처리기에서 수행하게 하는 것은 강한 친화성, 같은 처리기에서 수행하는 것을 노력하지만 보장하지 않는 것을 약한 친화성이라 한다.
부하 균등화
여러 처리기를 사용하는 것의 장점을 살리기 위해 각 처리기가 균등한 부하를 가지게 하는 것.
부하가 하나의 처리기에만 집중된다는 것은 다른 처리기가 쉬고있다는 것을 의미한다. 처리기는 비싸기 때문에 처리기가 쉬고 있는 것은 나쁘다. 따라서, 각 처리기의 부하가 균등하도록 해야 한다.
여러 처리기가 공통의 준비완료 큐를 공유한다면, 특별한 부하 균등화처리를 하지 않아도 알아서 부하가 균등하게 분산된다. 처리기가 즉시 준비완료 큐에서 프로세스를 선택할 것이기 때문이다. 반면, 각 처리기가 각자의 준비완료 큐를 가지고 있다면 부하 균등화가 필요하다.
부하 균등화는 Push 방식과 Pull 방식으로 구현된다.
•
Push 방식 : 특정 태스크가 각 프로세스의 부하를 검사해 바쁜 처리기에서 다른 처리기로 프로세스를 이주시키는 것
•
Pull 방식 : 한가한 처리기가 바쁜 처리기를 기다리는 프로세스를 가져온다.
부하 균등화는 처리기 친화성과 상충된다. 둘 중 무엇을 우선해야 하는지 절대적인 규칙은 없다.
대칭적 다중 쓰레딩
처리기가 자신을 논리적인 처리기 2개로 나누는 것. 각 논리 처리기는 저마다의 레지스터를 가지고, 인터럽트에 대한 책임을 가지지만, 캐시 메모리와 버스를 공유한다. 인텔의 하이퍼 쓰레딩이 이를 구현한 것이다.
운영체제가 서로 다른 쓰레드를 서로 다른 물리적 처리기에서 실행될 수 있도록 스케줄링 하는 것이 더 유리하다.
