5.1 기본 개념
CPU버스트 시간에 따른 빈도
짧은 CPU 버스트 기간을 가지는 프로세스가 굉장히 많다.
선점 및 비선점 스케줄링
CPU스케줄링 결정은 다음과 같은 상황에서 발생할 수 있다.
1.
실행 상태에서 대기 상태로 전환될 때
2.
실행 상태에서 준비 완료 상태로 전환될 때
3.
대기 상태에서 준비 완료 상태로 전환될 때
4.
프로세스가 종료할 때
1,4번의 상황의 경우 실행을 위해 새로운 프로세스가 반드시 선택되어야한다. 2,3번 상황에서는 선택의 여지가 있다.
1,4번의 상황에서만 스케줄링 발생한다면 이것은 비선점이라고 한다.
그렇지 않으면 선점이라고 한다.
선점 스케줄링은 데이터가 다수의 프로세스에게 공유될 때 경쟁 조건을 초래할 수 있다.
한 프로세스가 자료를 갱신하는 동안 선점되어 두번째 프로세스가 실행 가능한 상태가 될 수 있다.
이러면 데이터의 일관성이 깨진다.
비선점형 커널은 컨텍스트 스위칭을 하기 전에 시스템 콜이 완료되거나 입출력 완료를 기다리며 프로세스가 봉쇄되기를 기다림. 실시간 컴퓨팅을 지원하기에 좋은 모델은 아니다.
선점형 커널은 대신 데이터 구조에 엑세스할 때 경쟁 조건을 방지하기 위해 mutex락과 같은 기법이 필요하다.
인터럽트는 어느 시점에서건 일어날 수 있고, 영향을 받는 코드 부분은 반드시 동시 사용으로부터 보호되어야 한다. 운영체제는 거의 항상 인터럽트를 받아들일 필요가 있는데, 그렇지 않으면 입력을 잃어버리거나 출력이 겹쳐서 쓰일 수 있다. 따라서 이런 코드 부분은 다수 프로세스가 병행으로 접근할 수 없도록 전입점에서 인터럽트를 불능화하고 출구에서 인터럽트를 가능하게 한다.
디스패처
디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데까지 소요되는 시간을 디스패치 지연이라고 한다.
스케줄링 기준
•
CPU이용률
◦
가능한 CPU를 바쁘게 유지하기
•
처리량
◦
CPU가 바쁘면, 작업이 진행되고 있는 것이다. 단위 시간당 완료된 프로세스의 개수로 이것을 처리량이라고 한다.
•
총처리 시간
◦
특정 프로세스 입장에서 보면 중요한 기준은 프로세스 실행의 총 소요 시간이다.
◦
제출 시간과 완료 시간의 간격을 총처리 시간. 준비 큐에서 대기한 시간, CPU에서 실행하는 시간, 그리고 I/O를 합한 시간.
•
대기 시간
◦
스케줄링 알고리즘은 프로세스가 실행하거나 I/O를 하는 시간 양에는 영향을 미치지 않는다.
◦
단지 준비 큐에서 대기하는 시간의 양에만 영향을 준다.
◦
대기 시간은 준비 큐에서 대기 하면서 보낸 시간의 합
•
응답시간
◦
하나의 요구를 제출한 후 첫번째 응답이 나올 때까지의 시간.
스케줄링 알고리즘
선입 선출 스케줄링(FCFS)
평균 대기 시간은 일반적으로 최소가 아니며, CPU버스트 시간이 크게 변할 경우에는 대기 시간도 상당히 변할 수 있다.
모든 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 convoy effect라고 한다. 이용률이 낮앚이는 결과를 낳는다. 비선점형 알고리즘이다.
최단 작업 우선 스케줄링
가장 작은 다음 CPU를 버스트를 가진 프로세스에게 할당한다.
하지만 다음 CPU 버스트의 길이를 알 방법이 없기 때문에 CPU스케줄링 수준에서는 구현할 수 없다. 그러나 값을 예측할 수는 있는데, 이를 통해 그낫값을 계산해 프로세스를 선택한다.
일반적으로 측정된 이전의 CPU버스트들의 길이를 지수 평균한 것으로 예측한다.
라운드 로빈 스케줄링
시간 할당량, 타임 슬라이스라고 하는 작은 단위의 시간을 정의
준비큐를 돌면서 한 번에 한 프로세스엑 시간 할당량동안 CPU를 제공
CPU스케줄러는 준비 큐에서 첫번째 프로세스를 선택해 한 번의 시간 할당량 이후에 인터럽트를 걸도록 타이머를 설정한 후, 프로세스를 디스패치 한다.
라운드 로빈 스케줄링 알고리즘에서 유일하게 실행 가능한 프로세스가 아니라면 연속적으로 두 번 이상의 시간 할당량을 받는 프로세스는 없다.
종종 RR하에서 평균 대기 시간은 길다.
시간 할당량을 4초로 하면 위 그림처럼 된다.
P1은 6밀리초를 기다리고, P2는 4밀리초 P3는 7밀리초, 평균 대기 시간은 17/3으로 5.66 밀리 초이다.
RR은 선점형이다.
준비큐에 n개의 프로세스가 있고, 시간 할다량이 q이면, 각 프로세스는 다음 시간 할당량이 할당될 때까지 (n-1)*q 이상의 시간을 기다리지 않는다.
RR의 성능은 시간 할당량의 크기에 많은 영향을 받는다. 극단적으로 시간 할당량이 매우 크면 선입 선처리랑 같다. 반대로 시간 할당량이 매우 작으면 매우 많은 컨텍스트 스위칭이 일어난다.
우선순위 스케줄링
CPU는 가장 높은 우선순위를 가진 프로세스에 할당된다. 우선순위가 같은 프로세스들은 선입 선처리 순서로 스케줄
선점형 우선순위 스케줄리 알고리즘은 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높다면 CPU를 선점한다. 비선점형 우선순위 스케줄리 알고리즘은 단순히 준비오나료 큐의 머리 부분에 새로운 프로세스를 넣을 뿐.
무한 봉쇄 또는 기아 상태가 생길 수 있다. 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 발생한다.
이것에 대한 해결 방법은 aging이다. 주기적으로 대기중인 프로세스의 우선순위를 1씩 증가시킬 수 있다.
다단계 큐 스케줄링
우선순위 스케줄링이 라운드 로빈과 결합한 경우에도 효과적이다.
프로세스 유형에 따라 프로세스를 여러 개 개별 큐로 분할하기 위해 사용할 수 있다.
포그라운드와 백그라운드 프로세스를 구분한다. 포그라운드가 백그라운드보다 우선순위가 높다. 포그라운드 및 백그라운드 프로세스에 별도의 큐가 사용될 수 있으며, 각 큐에는 자체 스케줄링 알고리즘이 있을 수 있다. 추가로 큐와 큐 사이에 스케줄링도 반드시 있어야한다.
각 큐는 낮은 우선순위의 큐보다 절대적인 우선순위를 가진다. 또 다르게는 큐들 사이에 시간을 나누어 사용하자. 각 큐는 CPU시간의 일정량을 받아서 자기 큐에 있는 다양한 프로세스들을 스케줄 할 수 있다.
포그라운드 큐는 CPU시간의 80프로가, 백그라운드는 CPU시간의 20프로를 받아 돌아갈 수 있다.
다단계 피드백 큐 스케줄링
다단계 피드백 큐 스케줄링 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용함.
프로세스들을 CPU버스트 성격에 따라서 구분한다.
어떤 프로세스가 CPU시간을 너무 많이 사용하면 낮은 우선순위 큐로 이동. I/O중심의 프로세스와 대화형 프로세스들을 높은 우선순위의 큐로 옮긴다. 비슷하게 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동할 수 있다.
다음과 같은 조건에 따라 정의된다
•
큐의 개수
•
각 큐를 위한 스케줄리 알고리즘
•
한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
•
한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
•
프로세스에 서비스가 필요할 때 프로세스가 들어갈 큐를 결정하는 방법
스레드 스케줄링
프로세스 내에서 스레드가 선정되는 것을 프로세스 경쟁 범위(process-contention scope)
CPU상에서 어떤 커널 스레드를 스케줄할 것인지를 정하는 것은 시스템 경쟁 범위(system-contention scope, SCS)
다중 처리기 스케줄링
두 가지 전략이 있다.
1.
모든 스레드가 공통 준비 큐에 있을 수 있다.
a.
공유 준비 큐에 경쟁 조건이 생길 수 있으므로, 다른 프로세서가 동일한 스레드를 스케줄 하지 않도록, 큐에서 스레드가 없어지지 않도록 보장해야함.
b.
공통 준비 큐를 보호하기 위해 락킹 기법의 하나를 사용할 수 있다.
c.
큐에 대한 모든 엑세스에는 락 소유권이 필요하므로, 락에 대한 경쟁이 심화될 것이고, 공유 큐 엑세스의 성능 병목이 될 수 있음.
2.
각 프로세서는 자신만의 스레드 큐를 가질 수 있다
a.
위와 같은 문제가 없다.
b.
SMP를 지원하는 가장 일반적인 방법
c.
큐마다 부하의 양이 다를 수 있다.
d.
균형 알고리즘을 사용하여 부하를 균등하게 만들 수 있다.,
다중 코어 프로세서
각 코어는 구조적인 상태를 유지하고 있어서 운영체제 입장에서는 개별적인 논리적 CPU처럼 보인다.
프로세서가 메모리보다 훨씬 빠르기 때문에 메모리 스톨이 발생한다. 이 시나리오에서 프로세서는 메모리의 데이터를 사용할 수 있을 때까지 기다린다.
이를 위해 하나의 코어에 2개 이사의 하드웨어 스레드가 할당된다. 메모리를 기다리는 동안 하나의 하드웨어 스레드가 중단되면 코어가 다른 스레드로 전환할 수 있음. 운영체제 관점에서 하드웨어 스레드는 논리적 CPU로 보인다. 이런 기술을 CMT(chip multi, threading)으로 부름
일반적으로 처리기를 다중 스레드화 하는데는 2가지 방법이 있다.
•
coarse-grained 스레딩
◦
스레드가 긴 지연시간을 가진 이벤트가 발생할 때까지 한 코어에서 수행된다. 긴 지연시간을 가진 이벤트에 의한 지연이 생기면 그 대 다른 스레드르 실행한다. 프로세서 코어에서 다른 스레드가 수행되기 전에 명령어 파이프라인이 오나전히 정리되야해서 스레드 간 교환 비용이 많이 든다.
•
fine-grained 스레딩
◦
명령어 주기의 경계에서 좀 더 세밀한 정밀도를 가진 시점에서 스레드 교환이 일어남.
◦
스레드 교환을 위한 회로를 포함하므로, 스레드 간 교환의 비용이 줄어든다.
부하 균등화
SMP시스템의 모든 프로세서 사이에 부하가 고르게 배분되도록 시도한다.
두 가지가 있다.
•
push이주
◦
특정 태스크가 주기적으로 각 처리기의 부하를 검사하고, 만일 불균형 상태로 밝혀지면 과부하인 처리기에서 덜 바쁜 처리기로 이동시킨다.
•
pull 이주
◦
쉬고 있는 처리기가 바쁜 처리기를 기다리고 있는 프로세스를 pull할 때 일어난다.
처리기 선호도
스레드에 의해 가장 최근에 접근된 데이터가 처리기의 캐시를 채운다.
이럴 때 스레드가 이주한다면, 첫 프로세서의 캐시 메모리의 내용은 무효화되고 두 번째 프로세서의 캐시는 다시 채워져야한다. 캐시 무효화 및 다시 채우는 비용이 많이 들기 때문에 SMP를 지원하는 대부분의 운영체제는 이주시키지 않고 대신 같은 프로세서에서 계속 실행시키면서 warm-cache를 이용하려고 한다.
공통 준비 큐 접근 방식으로 하면 스레드가 어느 프로세서에서든 스케줄될 수가 있고, 해당 프로세서의 캐시를 다시 채워야한다.
프로세서마다 자신만의 큐를 사용하면 스레드는 항상 동일한 프로세서에 스케줄 되므로 warm cache의 내용을 활용할 수 있다.
오에스 사례
리눅스
CFS - Completely Fair Scheduler
nice, virtual run time, priority 이 세가지를 기반으로 할당된다.
일단 CFS에서는 각 프로세스별 time slice가 고정되어있지 않고, 가변적으로 변한다.
얼마나 가변적으로 변하는지를 정하는게 nice 값
time slice를 정하는 것은 vruntime이다. 한 프로세스가 CPU를 점유한 시간을 합한 것으로, 시간에 대한 감쇠율을 적용함. 이 감쇠율이 우선순위가 높은 프로세스가 더 높기에, vruntime이 적게 올라간다.
자세한 것은 4.4 BSD Scheduler를 참고
