********************************
##이 글은 제가 공부하고 있는 책을 요약해놓은 것이므로 본문 내용만 봐선 이해가 어려울 수 있습니다.
목차
4. 스케줄링 알고리즘
5. 스케줄링 알고리즘 평가
********************************
4. 스케줄링 알고리즘
-선입선출 스케줄링(FCFS)
프로세스가 준비큐에 도착한 시간 순대로 CPU를 할당하는 방식. 자발적으로 CPU를 반납할 때까지 빼앗지 않는다. 대단히 합리적일 것 같지만 경우에 따라 매우 비효율적인 결과가 초래됨. CPU버스트가 긴 프로세스가 먼저 도착할 경우 뒤의 프로세스들은 CPU버스트가 짧더라도 앞의 프로세스를 모두 기다려야해서 평균 대기시간이 길어짐. 이런 현상을 콘보이 현상(Convoy effect)라고 하며 이는 FCFS의 대표적 단점.
- 최단작업 우선 스케줄링(Shortest-Job First: SJF)
CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식. 평균 대기시간을 가장 짧게하는 최적 알고리즘.
선점형 방식: 준비큐에서 CPU버스트가 가장 짧은 프로세스에게 CPU를 할당했다 하더라도, CPU 버스트가 더 짧은 프로세스가 도착할 경우 CPU를 빼앗아 더 짧은 프로세스에게 부여하는 방식. SJF의 선점형 구현방식을 SRTF(Shortest Remaining Time First)라고도 부름. 프로세스들이 준비큐에 도착하는 시간이 불규칙한 경우 선점형 방식이 평균 대기시간을 최소화하는 최적 알고리즘이 됨.
비선점형 방식: 프로세스가 CPU를 자진반납하기 전까지는 CPU를 빼앗지 않는 방식. 현재 CPU를 점유하고 있는 프로세스가 CPU 버스트를 모두 수행하기 전까지 스케줄링하지 않는다. 준비큐에 한꺼번에 도착하고 그 이후는 따로 도착하지 않는 환경에서는 비선점형 방식과 선점형 방식이 서로 같은 결과를 만들어냄.
SJF에서 현실적으로 어려운 부분은 프로세스의 CPU 버스트 시간을 미리 알수 없는 것. 예측을 통해 버스트 시간을 구한 후 예측치가 가장 짧은 프로세스에게 CPU를 할당하게 된다. n+1번째의 CPU버스트 예측시간: T(n+1) = a*t(n) + (1-a)*T(n). t(n)은 n번째 실제 CPU 버스트 시간, T(n)은 n번째 CPU 버스트의 예측시간, a는 두 요소의 가중치 조절값. 식을 풀어쓰면 다음과 같아짐: T(n+1)= a*t(n) + (1-a)a*t(n-1) + (1-a)^2*a*t(n-2) + ... + (1-a)^j*a*t(n-j) + .... 이 방식은 과거를 통해 미래를 예측하는 데 있어서 더 오래된 과거일수록 그 영향력이 적어지도록 반영.
SJF알고리즘의 치명적 단점: 기아현상(starvation). CPU 버스트가 짧은 프로세스에게만 CPU를 할당할 경우 CPU 버스트가 긴 프로세스는 준비 큐에 줄 서서 무한정 기다려야 하는 문제가 발생함.
- 우선순위 스케줄링(priority scheduling)
우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식. 우선순위값이 작을수록 높은 우선순위. 우선순위를 결정하는 방식은 여러가지가 있는데 CPU버스트 시간을 우선순위값으로 정하면 SJF 알고리즘과 동일해진다.
선점형 방식: 현재 프로세스보다 우선순위가 높은 프로세스가 도착하여 CPU를 선점해서 새롭게 도착한 프로세스에게 할당.
비선점형 방식: 우선순위가 더 높은 프로세스가 도착하더라도 CPU를 자진반납하기 전까진 선점하지 않음.
우선순위 스케줄링에서도 기아현상이 발생할 수 있는데 이를 해결하기 위해 노화(aging) 기법을 사용한다. 기다리는 시간이 길어지면 우선순위를 높여 언젠가는 가장 높은 우선순위가 되도록 하는 방법.
- 라운드 로빈 스케줄링(Round Robin Scheduling)
시분할 시스템의 성질을 가장 잘 활용한 새로운 의미의 스케줄링 방식. 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한됨. 이 시간이 경과하면 CPU를 회수해 준비큐에 줄서있는 다른 프로세스에게 할당. 기존 프로세스는 준비 큐의 제일 뒤로 가 기다리게 됨. 이 시간을 할당시간(time quantum)이라고 한다. 할당시간이 너무 길면 라운드 로빈 스케줄링은 FCFS와 같은 결과가 된다. 너무 짧으면 CPU를 사용하는 프로세스가 빈번하게 교체되어 문맥교환의 오버헤드가 커짐(문맥교환이 빈번해지면 CPU의 이용률이 낮아짐. 문맥교환 오버헤드로 인해 전체 시간 중 일부는 CPU가 작업을 수행하지 못하기 때문). 일반적으로 할당시간을 수십 밀리초 정도로 설정하는데 사람이 느리지 않다고 체감할 정도의 시간 규모에 한번씩은 CPU를 할당받을 수 있도록 정한 시간 규모임. 라운드 로빈 스케줄링은 여러 종류의 프로세스가 같이 실행되는 환경에서 효과적임. n개의 프로세스가 준비큐에 있고 할당시간이 q면 모든 프로세스는 (n-1)q시간 이내에 적어도 한번 CPU를 할당받게 됨. 이는 대화형 프로세스의 빠른 응답시간을 보장할 수 있다는 장점이 있다.
이 스케줄링에서 CPU 버스트가 긴 프로세스에게 특별히 불이익이 가는 것도 아님. 각 프로세스의 대기시간이 그 프로세스의 CPU버스트 시간에 비례하기 때문.
라운드 로빈 스케줄링은 일반적으로 SJF 방식보다 평균 대기시간은 길지만 응답시간은 더 짧다.
할당시간이 만료되어 CPU를 회수하는 방법으로 타이머 인터럽트를 사용. CPU 버스트 시간이 할당시간보다 짧으면 CPU를 자신의 버스트 시간만큼 사용후 반납.
SJF 스케줄링이 CPU버스트 시간이 짧은 프로세스에게만 유리한 데에 비해 라운드 로빈 스케줄링은 공정한 스케줄링 방식. CPU를 쓰고자하는 양이 적으면 소요시간이 짧아지고 양이 많으면 소요시간도 비례해 길어진다.
FCFS 스케줄링은 평균 대기시간이나 평균 소요시간 측면에서 좋은 결과를 얻을 수 있는 반면 프로세스간 대기시간과 소요시간에 큰 편차를 가짐. 라운드 로빈 스케줄링은 할당시간을 극단적으로 짧게 할 경우 프로세스가 거의 동시에 CPU버스트를 끝마치게 됨. 이 경우 평균 대기시간과 평균 소요시간은 FCFS보다 비효율적이지만 프로세스간 대기시간과 소요시간의 편차가 거의 없음. 평균 응답시간은 훨씬 짧아진다.
- 멀티레벨 큐(Multi-Level Queue)
준비 큐를 여러개로 분할하여 관리. 즉 프로세스들이 여러 줄로 서는 것. 일반적으로 성격이 다른 프로세스들을 별도로 관리. 일반적으로 멀티레벨 큐에서 준비 큐는 대화형 작업을 담기 위한 전위 큐(foreground queue)와 계산 위주의 작업을 담기 위한 후위 큐(background queue)로 분할하여 운영됨. 전위 큐는 응답시간을 짧게하기 위해 라운드 로빈 스케줄링을 사용하는 반면, 계산 위주의 후위 큐는 응답시간이 의미를 가지지 않기때문에 FCFS 스케줄링 기법을 사용해 문맥교환 오버헤드를 줄이도록 함. 멀티레벨 큐에서는 또 다른 스케줄링이 필요한데, 어느 큐에 먼저 CPU를 할당할 것인지를 결정하는 스케줄링. 고정 우선순위 방식(fixed priority scheduling)에서는 큐에 고정적인 우선순위를 부여하여 먼저 서비스. 즉 전위 큐와 후위 큐를 사용하는 방식에서는 전위 큐에 있는 프로세스에게 우선적으로 CPU가 할당되고, 전위 큐가 비어있는 경우에만 후위 큐에 있는 프로세스에게 CPU가 할당됨. 타임 슬라이스(Time slice) 방식은 큐에 대한 기아현상을 해소할 수 있는 방식으로, 각 큐에 CPU 시간을 적절한 비율로 할당. 예를 들어 전체 CPU 시간 중 전위큐에는 80%, 후위 큐에는 20%를 할당해 스케줄링.
- 멀티레벨 피드백 큐(multilevel feedback queue)
프로세스를 여러 큐에 줄 세운다는 측면에서 멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능. 우선순위 스케줄링에서 기아 현상을 해결하기 위해 등장했던 노화 기법을 멀티레벨 피드백 큐 방식으로 구현할 수 있다. 우선순위가 낮은 큐에서 오래 기다렸으면 우선순위가 높은 큐로 승격시키는 방식이 그것이다.
멀티레벨 피드백 큐를 정의하는 요소: 큐의 수, 각 큐의 스케줄링 알고리즘, 프로세스를 상위 큐로 승격시키는 기준, 하위 큐로 강등시키는 기준, 프로세스가 도착했을 때 들어갈 큐를 결정하는 기준.
대표적 방식: 라운드로빈(할당시간 5)-라운드로빈(할당시간 10)-FCFS
프로세스가 준비 큐에 도착하면 우선순위가 가장 높은 큐에 줄을 선다. 그러면 CPU 사용시간이 짧은 대화형 프로그램들은 이 큐에서 빨리 서비스받고 작업을 완료할 수 있다. 그러나 CPU 버스트 시간이 긴 프로세스들은 주어진 할당시간동안 끝마치지 못해 하위 큐로 내려가 줄을 선다. 그 큐에서도 작업이 완료되지 못하면 CPU를 오래사용하는 계산 위주의 프로세스로 간주되어 최하위 큐로 이동하여 FCFS 스케줄링을 적용받게 된다.
큐에 대한 스케줄링 방식으로는 최상위 큐가 우선적으로 CPU를 배당받고, 상위 큐가 비었을 때만 하위 큐로 넘어감. 프로세스의 CPU 작업시간을 다단계로 분류함으로써 작업시간이 짧은 프로세스일수록 빠른 서비스가 가능하게 하고, 긴 프로세스는 문맥교환 없이 CPU 작업에만 열중할 수 있는 FCFS 방식을 채택할 수 있게 한다.
- 다중처리기 스케줄링(multi-processor system)
CPU가 여러 개인 시스템. 다중처리기 환경에서 CPU 스케줄링은 보다 복잡한 문제가 됨. 프로세스를 준비 큐에 한 줄로 세워서 각 CPU가 알아서 다음 프로세스를 꺼내가도록 할 수 있다. 마치 은행창구에서 번호표를 뽑고 기다리면 이전 고객이 끝나면 다음 고객을 부른 방식. 그러나 반드시 특정 CPU에서 수행되어야 하는 프로세스가 있는 경우에는 한 줄이 아니라 각 CPU별로 줄을 세울 수 있다. 여러 줄로 세우는 경우 일부 CPU에 작업이 편중되는 현상이 발생할 수 있기때문에 다중처리기 스케줄링에서는 부하균형(load balancing) 메커니즘으로 각 CPU별 부하가 적절히 분산되도록 한다.
대칭형 다중처리(symmetric multi-processing): 각 CPU가 각자 스케줄링을 결정하는 방식
비대칭형 다중처리(asymmetric multiprogramming): 하나의 CPU가 나머지 CPU의 스케줄링 및 데이터 접근을 책임.
- 실시간 스케줄링
시분할 시스템에서는 작업처리가 빠를수록 좋지만 데드라인이 있는 것은 아니다. 이와 달리 실시간 시스템(real-time system)에서는 각 작업마다 주어진 데드라인이 있어 반드시 그 시간안에 작업을 처리해야 한다.
실시간 시스템: 경성 실시간 시스템/ 연성 실시간 시스템
경성 실시간 시스템(hard real-time system): 미사일 발사, 원자로 제어 등 시간을 정확히 지켜야 하는 시스템
연성 실시간 시스템(soft real-time system): 데드라인이 존재하지만 지키지 못해서 위험한 상황이 발생하지 않는다. 예를 들어 멀티미디어 스트리밍 시스템. 화면이 끊길 뿐 시스템이 붕괴되거나 치명적인 결과를 초래하진 않음.
빠른 서비스도 좋지만 데드라인을 지키는 서비스가 더욱 중요. 실시간 환경에서는 따라서 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 EDF(ealist deadline first) 스케줄링을 사용.
5. 스케줄링 알고리즘 평가
큐잉모델(queueing model): 이론가들이 수행. 확률분포를 통해 프로세스들의 도착률과 CPU의 처리율을 입력값으로 주면 복잡한 수학 계산을 통해 각종 성능지표인 CPU처리량, 프로세스의 평균 대기시간 등을 구함.
구현 및 실측(implementation & measurement): 구현가들이 수행. 운영체제 커널의 소스코드 중 CPU 스케줄링을 수행하는 코드를 수정해서 커널을 컴파일한 후 시스템에 설치하는 과정을 필요로 함. 그런 다음 동일한 프로그램을 원래 커널과 CPU 스케줄러를 수정한 커널에서 수행시켜보고 실행시간을 측정하여 알고리즘의 성능을 평가.
시뮬레이션(simulation): 가상으로 CPU 스케줄링 프로그램을 작성한 후 프로그램의 CPU 요청을 입력값으로 넣어 어떠한 결과가 나오는 지 확인. 입력값은 가상으로 생성할 수도, 실제 시스템에서 CPU 요청 내역을 추출해 사용할 수도 있다. 이때 실제 시스템에서 추출한 입력값을 트레이스(trace)라고 부른다. 트레이스는 몇 초에 어떤 프로세스가 도착하고, 각각 CPU 버스트 시간을 얼마로 하는지에 대한 정보를 시간순으로 적어놓은 파일.
댓글