CPU스케줄링

-CPU스케줄링은 다중 프로그램 운영체제의 기본이다. 

-이 포스팅에서 일반적인 스케줄링 개념을 논의하는 경우에는 프로세스 스케줄링이라하고 스레드에 국한될 경우 스레드 스케줄링이라는 용어를 사용한다. 

1.개요(Overview)

-다중 프로그래밍에 대한 기본 개념은 어떤 프로세스가 대기해야 할 경우, 운영체제는 CPU를 그 프로세스로부터 회수해 다른 프로세스에 할당한다. 

 

1-1.CPU-입출력 버스트 사이클(CPU-I/O Burst Cycle)

-프로세스 실행은 CPU실행과 입출력 대기의 사이클로 구성된다. 프로세스 실행은 CPU 버스트로 시작된다. 뒤이어 입출력 버스트가 발생하고, 왔다 갔다 한다. 결국 마지막 CPU버스트는 실행을 종료하기 위한 시스템 요청과 함께 끝난다. 

1-2.CPU스케줄러(CPU Scheduler)

-CPU가 유휴 상태가 될 때마다 운영체제는 준비완료 큐에 있는 프로세스들 중에서 실행될 프로세스를 선택한다. 

-이 선택은 단기 스케줄러가 한다. 큐에 있는 레코드들은 일반적으로 프로세스 제어 블록이다. 

1-3.선점 스케줄링(Preemptive Scheduling)

-CPU스케줄링은 다음의 네가지 상황하에서 발생할 수 있다. 

a.한 프로세스가 실행 상태에서 대기 상태로 전환될 때 

b.프로세스가 실행 상태에서 준비완료 상태로 전환될 때 

c.프로세스가 대기 상태에서 준비완료 상태로 전환될 때 

d.프로세스가 종료할 때 

-상황 a와 d의 경우 스케줄링 측면에서 선택의 여지가 없다. 새로운 프로세스가 반드시 선택되어야 한다. 

그러나 b, c의 경우 선택의 여지가 있다. 

-상황 a와 d에서만 스케줄링이 발생할 경우, 이러한 스케줄링 방법을 비선점(non-Preemptive)이라하고 그렇지 않으면 선점(Preemptive)라고 한다. 

-즉 비선점에서는 CPU에 한 프로세스가 할당되면 프로세스가 종료 또는 대기상태로될 때 까지 CPU를 점유한다. 

-선점 스케줄링을 사용할 경우 공유 자료를 접근하는 경우 비용이 발생한다. 

-공유 자원을 조정할 새로운 메커니즘이 필요하다. 

-선점은 또한 운영체제 커널 설계에도 영향을 준다. 

1-4.디스패처(dispatcher)

-CPU스케줄링 기능에 포함된 또 하나의 요소는 디스패처이다. 

-디스패처는 CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈이며 다음과 같은 작업을 포함한다. 

a.문맥을 교환하는일

b.사용자 모드로 전환 하는 일

c.프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동(Jump)하는 일

-디스패처가 하나의 프로세스를 중단시키고 다른 프로세스를 실행하는데 소요되는 시간을 디스패치 지연이라 한다. 

2.CPU스케줄링 기준(Scheduling Criteria)

2-1.CPU 알고리즘 선택시 사용되는 기준

-CPU 이용률(Utilization)

-처리량(throughput)

-총처리 시간(turnaround time)

-대기 시간(waiting time)

-응답시간(response time)

3.스케줄링 알고리즘(Scheduling Algorithm)

3-1.선입 선처리 스케줄링(First-Come, First-Served Scheduling)

-CPU를 머저 요청하는 프로세스가 CPU를 먼저 할당받는다.

-ex)

프로세스    버스트시간    대기시간

   p1             24               0                평균대기시간 (0+24+27) / 3 = 17

   p2              3               24        

p3              3                3    

Abraham Silberschatz , Peter B. Galvin, Greg Gagne Operating System Concepts 지음 | 조유근, 고건, 김영찬, 박민규 옮김 | 홍릉과학출판사 | 2013년 02월 15일 출간, p.209

3-2.최단 작업 우선 스케줄링(Shortest-Job-First Scheduling/ SJF)

-이 알고리즘은 각 프로세스에 다음 CPU 버스트 길이를 연관 시킨다. CPU가 이용가능해지면 다음 CPU 버스트가 가장 작은 프로세스에게 할당된다. 

-두 프로세스의 다음 CPU 버스트가 같다면 순위를 정하기 위해 선입선처리 스케줄링을 적용한다. 

-ex)

프로세스    버스트시간    대기시간

   p1               6                3                평균대기시간 (3+16+9+0) / 4 = 7

   p2               8               16        

p3               7                9    

p4               3                0       

Abraham Silberschatz , Peter B. Galvin, Greg Gagne Operating System Concepts 지음 | 조유근, 고건, 김영찬, 박민규 옮김 | 홍릉과학출판사 | 2013년 02월 15일 출간, p.209

-SJF알고리즘은 최소의 평균 대기 시간을 가진다. 

-그러나 실제 어려움은 다음 CPU 요청 길이를 파악하는 것이다. 

-SJF알고리즘은 장기 스케줄링에서 자주 사용된다. 

-SJF는 선점형이거나 비선점일 수 있다. 이전 프로세스가 실행되는 동안 새로운 프로세스가 준비완료 큐에 도착하면 선택 상황이 발생한다. 새로운 프로세스가 현재 실행되고 있는 프로세스의 남은 시간보다 더 짧은  CPU버스트를 가실 수도 있다. 

-비선점형 SJF는 형재 실행하고 있는 프로세스가 자신의 CPU끝내도록 허용한다. 

-선점형 SJF는 현재 실행하는 프로세스를 선점 할 것이다. 

-선점형 SJF EX)

프로세스    도착시간   버스트시간    대기시간

   p1              0              6            (10-1)               평균대기시간 (9+0+15+2) / 4 = 6.5

   p2              1              8            (1-1)       

   p3              2              7            (17-2)    

   p4              3              3            (5-3)

Abraham Silberschatz , Peter B. Galvin, Greg Gagne Operating System Concepts 지음 | 조유근, 고건, 김영찬, 박민규 옮김 | 홍릉과학출판사 | 2013년 02월 15일 출간, p.213

    

3-3.우선순위 스케줄링(Priority Scheduling)

-우선순위가 각 프로세스들에게 연관되어 있으며 CPU는 가장 높은 우선순위를 가진 프로세스에게 할당된다. 

-SJF는 우선순위가 다음 CPU버스트의 반대인 단순한 우선순위 알고리즘이다. 

-여기서 우선순위가 낮은 숫자가 높은 우선순위를 나타낸다 가정한다. 

-EX) 프로세스들은 시간 0에 p1,p2...p5순서로 도착

프로세스    버스트시간   우선시간    대기시간

   p1              10              3              6               평균대기시간 (6+0+16+18+1) / 5 = 8.2

   p2               1              1               0       

p3               2              4              16    

p4               1              5              18        

    p5               5              2               1   

Abraham Silberschatz , Peter B. Galvin, Greg Gagne Operating System Concepts 지음 | 조유근, 고건, 김영찬, 박민규 옮김 | 홍릉과학출판사 | 2013년 02월 15일 출간, p.214

    

-우선순위는 내부적 or 외부적으로 정해질 수 있다. 

-내부적으로는 시간제한, 메모리 요구, 열린 파일의 수, 평균 CPU에 대한 비율등이 사용

-외부적으로는 프로세스의 중요성, 지불되는 비용의 타입과 양, 작업을 원하는 부서등에서 기준으로 사용

-우선순위 알고리즘 또한 선점형 비선점형으로 나뉜다. 

-비선점형 우선순위 스케줄링 알고리즘은 단순히 준비완료 큐의 머리 부분에 새로운 프로세스를 넣는다. 

-우선순위 스케줄링의 주요문제는 무기한 봉쇄(indefinite Blocking)또는 기아상태(Starvation)이다. 

-이는 낮은 프로세스들이 CPU를 무기한 대기하는 경우가 발생한다. 

-이를 해결하는 방법은 노화(aging)이다. 노화는 오래 기다린 시스템의 우선순위를 올리는 방법이다. 

3-4.라운드 로빈 스케줄링(Round-Robin Scgeduling)

-라운드 로빈 스케줄링 알로리즘은 특별히 시분할 시스템을 위해 설계

-시간 할당량(time quantom)또는 시간 조각(time slice)이라고 하는 작은 단위의 시간을 정의한다. 

-준비완료 큐는 원형 큐로 동작한다. CPU스케줄러는 준비완료 큐를 돌면서 하번에 하 프로세스에게 한번의 시간 할당량 이후에 인터럽트를 타이머를 설정한 후, 프로세스를 디스패치(dispatch)한다. 

-이러면 두 가지 상황이 발생한다. 

a.프로세스의 CPU 버스트가 한 번의 시간 할당량보다 작을 수 있다. -> 다음 프로세스 진행

b.현재 실행중인 프로세스의 CPU버스트가 한 번의 시간 할당량보다 긴 경우 -> 타이머가 만료되면 O/S가 인터럽트 발생 -> 문맥 교환 발생 -> 다음 프로세스 선택

-EX)

프로세스    버스트시간    대기시간

   p1             24               6                평균대기시간 (6+4+7) / 3 = 5.66

   p2              3                4        

p3              3                7   

시간 할당량 = 4밀리초

Abraham Silberschatz , Peter B. Galvin, Greg Gagne Operating System Concepts 지음 | 조유근, 고건, 김영찬, 박민규 옮김 | 홍릉과학출판사 | 2013년 02월 15일 출간, p.216

-라운드 로빈 알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받는다. 

-시간 할당량이 문맥교환 시간에 비해 커야할지라도 시간 할당량이 너무 커서는 안된다. 

 

3-5.다단계 큐 스케줄링(Multilevel Queue Scheduling)

-프로세스들이 쉽게 상이한 그룹으로 분류될 수 있는 상황을 위해 만들었다. 

-다단계 큐 스케줄링 알고리즘은 준비 완료 큐를 다수의 별도의 큐로 분류한다. 

-각 프로세스를 위해 다른 종류의 큐 사용 가능하다. 

-큐와 큐 사이의 스케줄링도 필요하다. 

Abraham Silberschatz , Peter B. Galvin, Greg Gagne Operating System Concepts 지음 | 조유근, 고건, 김영찬, 박민규 옮김 | 홍릉과학출판사 | 2013년 02월 15일 출간, p.219

3-6.다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)

-다단계 큐의 경우 큐 사이의 이동을 허용하지 않는다 .이러한 방식은 스케줄링 오버헤드는 적지만 융통성이 없다. 

-다단계 피드백 큐의 경우 프로세스가 큐 사이를 이동하는 것을 허용한다. 

-다단계 피드백 큐의 경우 다음의 매개변수에 의해 정의된다. 

a.큐의 개수

b.각 큐를 위한 스케줄링 알고리즘

c.한 프로세스를 높은 우선순위로 올려주는 시기를 결정하는 방법

d.한 프로세스를 낮은 우선 순위 큐로 강등 시키는 시기를 결정하는 방법

e.프로세스가 서비스를 필요로 할 때 프로세스가 들어갈 큐를 결정하는 방법

-이 알고리즘은 특정 시스템에 부합하도록 구성 가능하다. 하지만 가장 복잡한 알고리즘이기도 하다. 

4.스레드 스케줄링(Threads Scheduling)

-스레드를 사용자 수준과 커널 수준으로 구분하였다. 운영체제에서 스케줄되는 대상은 커널 수준 스레드이다. 

-사용자 스레드는 스레드 라이브러리에 의해 관리된다.

-궁극적으로 사용자수준 스레드는 커널스레드에 사상되어야한다. 

4-1.경쟁 범위(Contantion Scope)

-프로세스-경쟁-범위(Process-Contention-Scope,PCS)동일한 프로세스에 속한 스레드 사이에서 CPU경쟁

-시스템-경쟁-범위(System-Contention-Scope,SCS) SCS의 CPU에 대한 경쟁은 시스템 상의 모든 스레드들 사이에서 일어난다. 

5.다중처리기 스케줄링(Multiple-Processor-Scheduling)

-지금까지는 단일처리기를 가진 시스템에서 CPU를 스케줄하는 문제를 다뤘다. 

-만일 여러개의 CPU를 사용 가능하면 부하 공유가 가능해진다.

5-1.다중처리기 스케줄링에 대하 접근방법(Approaches to Multiple Processor Scgeduling)

-다중처리기 시스템의 CPU스케줄링에 관한 한가지 해결 방법은 주 서버(Master Server)라는 하나의 처리기가 모든 스케줄링 결정과 입출력 처리 그리고 다른 시스템의 활동을 처리하게 하는 것이다. 이러한 방법은 비대칭 다중처리(Asymetric multiprocessing)이다. 

-두 번째는 대칭 다중처리(Symmetric multiprocessing,SMP)를 사용하는 것으로 각 처리기가 독립적으로 수행하는 것이다. 여러 처리기가 공동 자료 구조를 접근하려 한다면 신중한 스케줄링이 필요하다.  

5-2.처리기 친화성(Processor Affinity)

-프로세스를 다른 처리기로 이동하면 각 처리기의 캐시 메모리 내용 또한 이주하여야 하기 때문에 비용이 많이 든다.

-그래서 대부분의 SMP 시스템은 한 처리기에서 다른 처리기로 이주를 피하고 한 처리기에서 같은 프로세스를 실행하려한다. 

-이 현상을 처리기 친화성이라 한다.  

5-3.부하 균등화(Load Balancing)

-SMP에서 처리기가 하나 이상인 것을 최대한 활용하려면 부하를 모든 처리기에게 균등하게 처리하는 것이 매우 중요하다. 

-부하 균등화는 SMP시스템의 모든 처리기 사이에 부하가 고르게 배분되도록 시도된다. 

-push 이주(migration)과 pull 이주 방식으로 접근한다. 

5-4.다중 코어 프로세서(Multicore Processors)

-요즘엔 하나의 물리적인 칩안에 여러개의 처리기 코어를 장착하는 것이다. 이러한 구조를 다중 코어 프로세서라 한다. 

-프로세서가 메모리를 접근할 때 많은 시간을 허비한다는 것을 발견하였다. 

-메모리 멈춤(Memory Stall)이라 알려진 이러한 상황은 캐시 미스등의 여러 원인으로 발생한다. 

-밑의 그림은 단일 코어를 사용할 때 메모리 멈춤으로 50%이상 시간을 허비하는 시나리오를 표현하고 있다. 

Abraham Silberschatz , Peter B. Galvin, Greg Gagne Operating System Concepts 지음 | 조유근, 고건, 김영찬, 박민규 옮김 | 홍릉과학출판사 | 2013년 02월 15일 출간, p.227

-이 상황을 타개하기 위해서 다중 코어 시스템을 구현한다. 이 구조에서는 한 스레드가 메모리를 기다리면서 멈추면 코어는 다른 스레드로 전환될 수 있다. 

-다음 그림은 스레드0과 스레드1이 번갈아가며 실행되는 이중 스레드 프로세서 코어를 보여준다. 

-O/S의 관점에선 각 H/W스레드는 S/W스레드를 실행할 수 있는 논리 프로세서로 보인다. 

-따라서 이중 스레드 이중 코어 시스템에서는 4개의 논리 프로세서가 O/S에 제공된다. 

-일반적으로 처리기를 다중 스레드화하는 데에는 크게-나눔(Coarse-Grained)다중 스레딩과 잘게-나눔(Fine-Grained)다중 스레딩의 2가지 방법이 있다. 

5-5.가상화와 스케줄링(Virtualization ans Scheduling)

-하나의 CPU를 가졌더라도 가상화를 지원하는 시스템은 종종 다중 처리기 시스템처럼 동작한다. 

-가상화 기술에는 많은 변형이 존재하여 오히려 악영향을 미칠 수 도 있다. 

-가상화가 스케줄에 미치는 영향을 요약하는 것은 매우 어렵다.