[운영체제] CPU 스케줄링(CPU Scheduling)

Multiprogramming: CPU를 최대한 이용해서 여러 프로그램을 concurrently하게 실행

운영체제에 의해 Kernel level 스레드가 scheduled 됨

 

보통 CPU 처리(CPU burst)와 IO를 기다리는 것(I/O burst)이 번갈아 가면서 수행됨

CPU bound program: IO burst가 얼마 없어서 CPU Burst가 길고 끊김이 별로 없는 프로그램

IO bound program: IO burst가 많아서 CPU Burst가 짧고 여러 개인 프로그램

 

CPU scheduler: ready queue에 있는 프로세스를 골라 CPU에 돌림

 

 

 

Preemptive & Nonpreemptive

• Nonpreemptive scheduling: 동작하는 프로세스가 실행이 끝날 때까지 CPU를 점유하는 스케줄링
• Preemptive scheduling: 프로세스 실행 중에 다른 프로세스가 실행될 수 있는 스케줄링

 

 

 

Dispatcher

• CPU scheduler가 실행시킬 프로세스를 고르면 context switch를 통해 프로세스를 바꿔주고 다시 유저모드로 들어가서 프로세스가 실행될 수 있게 함
• PCB에 기록되어 있는 프로세스 기록에 접근해 프로세스가 다시 실행될 때 그 때부터 실행될 수 있게 함
• Dispatcher Latency: dispatcher가 프로세스를 정지시키고 다른 프로세스를 실행시키는 것

 

 

 

Scheduling Criteria

• Cpu utilization – CPU가 얼마나 바쁜지
• Throughput – 일정 시간동안 끝난 프로세스의 개수
• Turnaround time – 프로세스가 create 되고 처리가 끝날 때까지의 시간
• Waiting time – ready state에서 실행될 때까지 기다리는 시간
• Response time – 처음으로 응답을 하는 시간

위에 두 개는 클수록 좋음, 나머지 세 개는 짧을수록 좋음

 

 

 

Scheduling algorithms

1. First-Come First-Served(FCFS) Scheculing

• 먼저 온 것부터 처리 (nonpreemptive)
• Average waiting time이 길다
• Convoy effect: 긴 프로세스가 먼저 실행되면 효율이 많이 떨어짐

 

 

2. Shortest Job First(SJF) Scheduling

• 짧은 것부터 먼저 처리(nonpreemptive)
• Average waiting time을 최적화 가능
• CPU burst의 길이를 예측해야 함

burst 길이 예측

 

3. Shortest Remaining Time First(SRTF) scheduling

• SJF의 preemptive 버전
• 프로세스를 실행하고 남아있는 시간을 고려

 

4. Round Robin (RR) Scheduling

• 프로세스를 조금씩 번갈아 가면서 실행
• Response가 빠름, but 전체 실행 시간은 김
• 프로세스를 너무 잘게 쪼개면 context switch가 많아서 효율이 떨어짐
• 너무 크게 쪼개도 프로세스가 바뀌기 전에 다 끝나버릴 수도 있음

 

5. Priority Scheduling

• 우선순위가 높은 프로세스부터 실행
• Preemptive와 nonpreemptive 중 preemptive가 주로 쓰임
• 낮은 우선순위 프로세스는 실행되지 못하는 starvation 문제가 생김 -> 기다리는 시간이 길어질수록 우선순위가 높아지게 함(aging)
• 우선 순위가 같은 프로세스끼리는 RR을 사용하기도 함

 

 

 

 

Multilevel queue

• 각 각의 queue에 대해 스케줄 알고리즘을 다르게 할 수 있다.

• 우선순위가 같거나 프로세스 타입이 같은 것끼리 다르게 처리할 수 있음
• Aging을 사용하면 우선순위가 바뀌므로 프로세스가 다른 queue로 이동할 수 있다.

 

 

 

Thread scheduling

• 커널 스레드는 운영체제에 의해 스케줄링되고 유저 스레드는 thread library에 의해 스케줄링된다.
• Process-contention scope(PCS): 동일한 프로세스 내부의 스레드끼리 경쟁
• System-contention scope(SCS): 시스템 전체의 스레드 간의 경쟁
• Many to one과 many to many를 지원하는 운영체제에서는 lightweight process(LWP)를 사용, LWP에 매핑된 프로세스끼리만 경쟁하므로 PCS
• SCS는 one to one에서 일어 남, 커널과 유저 스레드가 각각 매핑 되어있기 때문에 경쟁이 시스템 전체에서 일어남

     

 

 

Pthread scheduling

• Pthread_Scope_process: 같은 프로세스 내의 pthread끼리 resource를 두고 경쟁
• Pthread_scope_system: 시스템 내의 모든 프로세스의 pthread끼리 경쟁
• Linux, mac OS에서는 Pthread_scope_system만 허용

 

 

 

Multi-processor scheduling

• 멀티 프로세서는 cpu 칩이 여러 개 달려있는 컴퓨터 시스템, 멀티 코어는 싱글 프로세서 안에 스레드를 처리할 수 있는 코어가 여러 개 있는 컴퓨터 시스템

 

• Numa systems: CPU 각자 memory를 가지고 있어서 자신의 메모리에 접근할 때는 빠르지만 다른 CPU의 메모리에 접근할 때는 느려, 메모리 접근 시간이 일정하지 않은 시스템

 

• Heterogeneous multiprocessing: 하나의 칩 안에 코어들이 성능이 다른 것

 

• Symmetric multiprocessing(SMP)

      - 하나의 ready queue의 스레드들을 여러 개의 코어들이 실행

      - 코어마다 queue가 있음

 

• 하나의 스레드가 compute 하고 있다가 memory stall이 걸리면 다른 스레드가 바로 실행될 수 있도록 레지스터에 스레드를 저장해놓음

 

• Chip-multithreading: 예를 들어 하나의 코어가 2개의 hardware thread를 지원할 때 네 개의 코어를 가진 시스템이 있으면 8개의 논리적 cpu를 가진 것으로 간주

 

첫번째로 software thread 중에서 logical processor 개수만큼 thread를 고르고 프로세서 코어는 그 thread를 번갈아 가면서 실행시킴

 

• Load balancing: 각 CPU가 처리해야 할 일들을 골고루 분배하는 것

     - Push migration: 각 프로세서를 일 분배를 체크하다가 한 쪽에 일이 많이 쏠리면 다른 프로세서로 넘겨줌

     - Pull migration: 게으른 프로세서가 있으면 바쁜 프로세서로부터 일을 가져옴

 

• Processor affinity: 스레드가 여러 프로세서로 옮겨 다니면서 실행되면 캐시를 지속해서 변경해줘야 하므로 스레드가 하나의 프로세서에서 실행되는 것이 권장되도록 설정하는 것

     - Soft affinity: 이 프로세서에서 실행되면 좋지만 안 되도 괜찮음

     - Hard affinity: 무조건 이 프로세서에서 실행되게 함

 

 

 

 

 

Real time CPU scheduling

1. Soft real time scheduling: 데드라인을 지키는 것이 권장
2. Hard real time scheduling: 무조건 데드라인을 지켜야 함

시간에 따른 결과 값의 값어치 그래프

 

• Event latency

     1. Interrupt latency: interrupt handler가 interrupt를 처리하는 시간

     2. Dispatch latency: 현재 실행되는 프로세스를 다른 프로세스로 바꾸는 시간

 

 

 

Periodic task scheduling

하나의 task가 한번 실행되고 끝나는 것이 아니라 주기적으로 실행될 때

• Relative deadline: 작업의 도착과 작업 마감 시간 사이 간격 (d-t)
• Absolute deadline: 시간 0과 작업 마감 시간 사이 간격 (d)

 

 

 

 

Rate monotonic(RM) scheduling

Task가 release되는 속도에 따라 스케줄링 -> 주기가 짧을수록 높은 우선순위

 

 

 

 

Earliest deadline first(EDF) scheduling

Deadline이 제일 빠른 순서로 스케줄링

 

 

 

 

Little laws

queue 길이 = 평균 도착 개수 X 평균 대기 시간

 

 

 

 

Completely fair scheduler(CFS)

• Linux scheduling에서 사용
• 각각 우선순위를 가짐
• 가장 높은 우선순위의 task를 선택, nice value를 이용해 time quantum을 정함
• Nice value는 CPU를 얼마나 사용했는지를 나타내며, nice value가 낮을수록 우선순위가 높음 -> CPU를 적게 사용한 task에 CPU를 할당
• Vruntime(virtual runtime)은 프로세스가 그 동안 실행한 시간을 정규화한 시간 정보
• Realtime class가 default class보다 우선순위가 높음