[OS] CPU 스케줄링

스케줄링은 다중 프로그래밍을 가능하게 하는 운영 체제의 동작 기법입니다.

cpu 스케줄링 결정은 다음의 네가지 상황 하에서 발생할 수 있습니다.

1. running → waiting
2. running → ready
3. waiting → ready
4. terminated

1번과 4번에서 스케줄링이 발생하는 경우 비선점(nin-preemptive) 또는 협조적(cooperative)라고 합니다. 나머지 경우 선점(preemptive)라고 합니다.

cpu 스케줄링 기능에 디스패처(dispatcher)도 포함되어 있습니다. 디스패처는 cpu의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈이며 아래와 같은 작업을 포함합니다.

• context switch
• 사용자 모드 전환
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동(jump)하는 일

cpu 스케줄링 알고리즘은 많지만 최선의 알고리즘을 결정하는데 여러가지 기준이 있습니다.

• CPU 이용률(utilization)
• 처리량(throughput)
• 총처리 시간(turnaround time)
• 대기 시간(waiting time)
• 응답 시간(response time)

스케줄링 알고리즘

중국집 음식점에 갔을 때로 비유

 

선입선처리 스케줄링 알고리즘(First-Come, First-Served Scheduling, FCFS)

• 먼저 들어온 프로세스먼저 처리하는 알고리즘
• FIFO 큐로 관리됨
• 음식이 먼저 나온 순으로 다 먹음.

 

최단 작업 우선 스케줄링(Shortest-Job-First scheduling, SJF)

• 가장 작은 CPU 버스트를 가진 프로세스 먼저 처리하는 알고리즘
• 장기 스케줄링에서 자주 사용됨
• 단점 : CPU 요청의 길이를 파악하는 것이 어려움
• 먼저 나온 단무지를 다 먹고나서 뒤에 나온 짜장면, 탕수육, 짬뽕 중 가장 빨리 다 먹을 수 있는 것을 선택하여 먹음

 

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

• 높은 우선순위를 가진 프로세스먼저 처리하는 알고리즘
• 단점 : 무한 봉쇄(indefinite blockin) 또는 기아(starvation)상태에 빠질 수 있음
• 단점의 해결 방안 : 노화(aging)를 사용하여 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킴
• 먼저 나온 단무지를 먹고 짜장면, 탕수육, 짬뽕 중 우선순위를 세워 우선순위가 높은 것 먼저 먹음

 

라운드 로빈 스케줄링(Round-Robin Scheduling, RR)

• 시간 할당량(time quantum)또는 시간 조각(time slice)를 각 프로세스에게 할당하여 CPU 스케줄러는 준비 완료(ready) 큐를 돌면서 한 번에 한 프로세스에게 한 번의 시간 할당량 동안 CPU를 할당하는 알고리즘
• 시간 할당량의 크기에 매우 많은 영향을 받음
• 나온 단무지, 짜장면, 탕수육, 짬뽕들을 한 입씩 번갈아 가면서 먹음

 

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

• 준비 완료 큐를 다수의 별도의 큐로 분류함. 각 큐는 자신의 스케줄링 알고리즘을 갖고 있음. 큐에 우선순위를 부여하여 높은 우선순위를 가진 큐를 처리. 프로세스는 큐 사이를 이동할 수 없음
• 단점 : 낮은 우선순위의 프로세스에게 기아(starvation) 현상이 발생할 수 있음

 

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

• 다단계 큐와 같이 준비 단계 큐를 여러개로 분류. 다단계 피드백 큐 스케줄링에서는 프로세스들이 큐들 사이를 이동하는 것을 허용. 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동됨. 이런 노화(aging) 현태로 기아 상태를 예방
• 큐 0, 1, 2가 있다고 가정했을 때 큐 0에 있는 프로세스가 할당된 시간을 초과하는 경우 큐 1의 꼬리에 붙음. 큐 1의 프로세스가 실행되고 완료되지 않으면 큐 2의 꼬리에 붙는 방식의 알고리즘

 

다중 처리기 스케줄링

여러 개의 CPU가 사용 가능하다면, 부하 공유(load sharing)이 가능해짐

 

다중 처리기 시스템의 CPU 스케줄링에 관한 두가지 방법

• 주 서버라는 하나의 처리기가 모든 스케줄링 결정과 입출력 처리 그리고 다른 시스템의 활동을 취급하게 하고 다른 처리기들은 사용자 코드만을 수행 ⇒ 비대칭 다중처리(asymmetric multiprocessing)
• 대칭 다중 처리(symmetric multiprocessing, SMP)를 사용. 모든 프로세스는 공동의 준비 완료 큐에 있거나 각 처리기 마다 가지고 있는 사유의 준비 완료 큐에 있게 됨. 스케줄링은 각 처리기의 스케줄러가 준비 완료 큐를 검사하여 실행할 프로세스를 선택하면서 진행. 서로 다른 2개의 처리기가 같은 프로세스를 선택하지 않아야 하며 프로세스들이 큐에서 사라지지 않는나는 것을 보장해야 함.

부하 균등화(Load Balancin)

부화 균등화는 SMP 시스템의 모든 처리기 사이에 부하가 고르게 배분되도록 시도. 부하 균등화를 위해서 두가지 접근법이 있음

• push 이주(migration) : 특정 태스크가 주기적으로 각 처리기의 부하를 검사하고 만일 불균형 상태로 밝혀지면 과부하인 처리기에서 쉬고 있거나 덜 바쁜 처리기로 프로세스를 이동(push) 시킴으로써 부하를 분배
• pull 이주(migration) : 쉬고 있는 처리기가 바쁜 처리기를 기다리고 있는 프로세스를 가져오는 방식

 

다중 코어 프로세서(Multicore Processors)

SMP 시스템은 다수의 물리 처리기를 제공함으로서 다수의 스레드가 동시에 실행되게 하지만 컴퓨터 하드웨어에서는 하나의 물리적인 칩 안에 여러 개의 처리기 코어를 장착하는 것을 다중 코어 프로세서라고 합니다.

 

프로세서가 메모리 접근할 때 데이터가 가용해지기를 기다리면서 많은 시간을 허비하는 것을 메모리 멈춤(memory stall)이라고 하는데 캐시 미스 등 여러 원인 때문에 발생합니다.

 

memory stall로 인해 50%의 시간을 허비하게 되는데 이걸 타개하기 위해 다중스레드 프로세서 코어를 구현하게 됩니다.

 

스레드0과 스레드1을 번갈아 가면서 수행하면 하나의 스레드가 memory stall 상태에서도 다른 스레드가 수행할 수 있습니다.

 

실시간 CPU 스케줄링

우선순위 기반의 스케줄링(Priority-Based Scheduling)

우선순위가 높은 프로세스 먼저 수행

 

Raate-Monotic 스케줄링

주기가 짧은 태스크가 높은 우선순위로 배정되도록 하는 스케줄링

 

Earliest-Deadline-First 스케줄링(EDF)

마감시간이 빠를수록 우선순위가 높은 스케줄링

 

일정 비율의 몫 스케줄링(Proportionate Share Scheduling)

모든 응용프로그램이 몫 T를 공유하여 한 개의 응용 프로그램당 N개의 시간 몫을 할당하면 N/T 시간을 할당받게 되는 스케줄링