CPU Scheduling
- 프로세스는 CPU 버스트 후 I/O 버스트가 발생하고 서로 번갈아 가며 나타난다.
- 마지막엔 실행을 종료하기 위한 시스템 요청으로 끝난다.
- 일반적으로 짧은 CPU 버스트가 많이 있다.
- CPU가 유휴 상태가 될 때 마다, OS는 준비 큐에 있는 프로세스를 선택해 실행해야 한다. 선택 절차는 CPU 스케줄러가 한다. 큐에 있는 레코드는 일반적으로 PCB이다
preemptive: 선점
Non preemptive, cooperative
Dispatcher
CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈
스케줄링 기준(scheduling criteria)
- cpu 이용률(utilization): 40%~90%
- 처리량(throughput): 단위 시간 당 완료된 프로세스의 개수
- 총처리시간(turnaround time): 프로세스의 제출시간과 완료시간의 간격, - 준비 큐 대기 + CPU 실행 + I/P
- waiting time: CPU 스케줄링 알고리즘이 영향을 주는 것
- response time: 하나의 요구를 제출한 후 첫 응답까지의 시간
FCFS
- First Come First Served
- convoy effect: 긴 프로세스를 다른 모든 프로세스들이 기다림.
SJF
- shortest job first
- 가장 짧은 CPU 버스트 시간을 가진 프로세스 선택. 구현 불가능
- 근삿값 이용. 선점 비선점 가능. 최소 잔여시간 우선 알고리즘 이라고도 불린다.
RR(Round-Robin)
- time quantum 또는 time slice 라는 단위 시간 설정.
- 준비 큐는 원형 큐, 돌면서 통일 시간 할당.
- 선점형
Priority Scheduling
- 프로세스에 우선순위를 준다. 우선 순위가 같으면 FCFS
- 선점형, 비선점형 가능
- indefinite blocking(무한 봉쇄), starvation(기아 상태)를 방지하기 위해 aging(노화) 사용
Multilevel Queue Scheduling
- 우선 순위 마다 별도의 큐를 갖는다.
- 우선 순위 스케줄링과 RR이 결합한 경우에 효과적. 우선 순위가 가장 높은 큐에서 라운드 로빈.
- 큐 사이의 스케줄링도 필요하다. 절대적인 우선 순위나 CPU시간 할당
Multilevel Feedback Queue Scheduling
- 프로세스가 우선 순위 큐 사이를 이동한다.
- 어떤 프로세스가 CPU를 많이 사용하면 낮은 우선 순위 큐로 이동한다. 낮은 우선순위 큐에서 오래 대기하면 높은 우선 순위 큐로 이동한다.
최신 OS에서 스케줄 되는 대상은 커널 수준 스레드이다. 사용자 수준 스레드는 스레드 라이브러리에 의해 관리된다. CPU 상에서 실행 되기 위해서는 LWP를 통한 간접적인 방식일지라도 커널 수준 스레드에 사상되어야 한다.
경쟁 범위 contention scope
PCS
process-contention scope: 같은 프로세스 내에 존재하는 스레드 간의 경쟁.
다대일, 다대다 에서 스레드 라이브러리는 사용자 수준 스레드를 가용한 LWP에서 스케줄한다. 이는 실제로 CPU 상에서 실행 중이라는 것을 의미하지 않는다. 원 순위에 따라
SCS
system-contention scope: SCS 스케줄링에서 CPU에 대한 경쟁은 모든 스레드 사이에서 일어난다. 일대일 모델은 SCS만 사용.
OS가 LWP의 커널 스레드를 물리적인 CPU 코어로 스케줄 하는 것을 필요로 한다.
Multiple-Processor Scheduling
부하 공유가 가능. 다중 코어 CPU 다중 스레드 코어. NUMA 시스템, 이기종 다중처리
asymmetric multiprocessing
하나의 코어만 시스템 자료구조에 접근하여 자료공유의 필요성을 배제하기 때문에 간단하다. 마스터 서버가 전체 시스템 성능을 저하할 수 있는 병목이 된다는 단점이 있다.
SMP(symmetric multiprocessing)
각 프로세서는 스스로 스케줄링 할 수 있다. 각 프로세서의 스케줄러가 준비 큐를 검사하고 실행할 스레드를 선택하여 스케줄링이 진행된다.
- 모든 스레드가 공통 준비 큐에 있을 수 있다. 경쟁 조건이 생길 수 있다. 큐에 스레드가 남아 있어야 한다. 락킹 기법
- 각 프로세서가 자신만의 스레드 큐를 가질 수 있다. SMP를 지원하는 시스템에서 일반적인 방식
- 캐시 메모리를 효율적으로 사용할 수 있다. 프로세서마다 부하의 양이 다를 수 있다.
Multicore Processor
동일한 물리적인 칩 안에 여러 개의 처리 코어를 장착, OS 입장에서는 개별적인 논리적 CPU처럼 보인다.
메모리 stall
프로세서가 메모리에 접근할 때 데이터가 가용해지기를 기다리는 상황
하드웨어 스레드
하나의 코어 당 2개 이상을 할당하여 메모리가 기다리는 동안 하나의 하드웨어 스레드가 중단되면 코어가 다른 스레드로 전환할 수 있다.
Chip Multi-Threading, CMT
위에 적은 기술. OS 입장에서 각 하드웨어 스레드는 명령어 포인터 및 레지스터 집합과 같은 구조적 상태를 유지하므로 소프트웨어 스레드를 실행할 수 있는, 논리적 CPU로 보인다.
coarse-grained threading
거친 다중 스레딩. 스레드가 메모리 스톨과 같은 긴 지연시간을 가진 이벤트가 발생할 때까지 한 코어에서 수행된다. 지연이 발생하면 코어는 다른 스레드를 실행하게 된다. 그러나 다른 스레드 수행 전 명령어 파이프 라인이 완전히 정리되어야 하므로 교환 비용이 많이 든다. 새로운 스레드가 실행하면 자신의 명령어들로 파이프라인을 채우기 시작한다.
fine-grained multi-threading
명령어 주기의 경계 같이 좀 더 세밀한 정밀도를 가진 시점에서 교환이 일어난다.
다중 스레드 다중 코어 프로세서는 두 단계의 스케줄링이 필요하다.
1. OS가 각 하드웨어 스레드에서 실행할 소프트웨어 스레드를 선택
2. 각 코어가 실행할 하드웨어 스레드 결정
Load Balancing
부하 균등화. SMP 시스템의 모든 처리기 사이 부하가 고르게 배분되도록 한다.
자기 자신만의 준비 큐를 가지고 있는 시스템에서만 필요한 기능이다.
push migration
특정 태스크가 주기적으로 각 처리기의 부하를 검사하고 만일 불균형 상태로 밝혀지면 과부하인 처리기에서 덜 바쁜 처리기로 스레드를 이동시킨다.
pull migration
쉬고 있는 처리기가 바쁜 처리기를 기다리고 있는 프로세스를 가져온다.
두 이주 방식은 상호 배타적일 필요는 없다.
processor affinity
처리기 선호도. 캐시를 비우고 다시 채우는데 비용이 든다. 그래서 SMP를 지원하는 OS는 스레드를 한 프로세서에서 계속 실행시키면서 warm cache를 이용.
soft affinity: OS가 동일한 처리기에 프로세스를 실행시키려고 노력하는 정책은 있지만 보장X
프로세스가 처리기 사이에서 이주가 가능하다.
hard affinity: 시스템 콜을 통해 프로세스는 자신이 실행될 처리기를 명시할 수 있다.
heterogeneous multiprocessing: 이기종 다중 처리. 모바일 시스템에서는 전력 소비를 조정하는 기능을 포함하며 설계됐다. 비대칭 다중 처리 형태는 아니다.
big.little: 고성능 big. 에너지 효율적인 little. 둘을 결합하여 사용
Real-Time CPU scheduling
soft real time system:중요한 실시간 프로세스가 스케줄되는 시점에 관해 보장을 하지 않는다. 중요 프로세스가 그렇지 않은 프로세스에 비해 우선권을 가진다는 것만 보장한다.
hard real time system: 태스크는 마감시간 까지 서비스를 받아야 하며 마감 시간이 지난 후 서비스를 받는 것은 받지 않은 것과 동일하다.
Minimizing Latency: 지연시간 최소화
이벤트 지연시간: 이벤트가 발생해서 그에 맞는 서비스가 수행될 때 까지의 시간
인터럽트 지연시간: CPU에 인터럽트가 발생한 시점부터 해당 인터럽트 처리 루틴이 시작하기 까지의 시간
디스패치 지연시간: 스케줄링 디스패처가 하나의 프로세스를 블록 시키고 다른 프로세스를 시작하기 까지 걸리는 시간
Priority Based Scheduling: hard real time system에서는 프로세스를 정의할 필요가 있다.
- 주기적: 일정한 간격으로 CPU가 필요하다.
0≤수행시간t ≤마감시간d ≤주기p
실행빈도 1/p
시간사이의 관계를 이용해 우선 순위를 부여한다.
- admission-control 알고리즘을 이용해 스케줄러는 마감시간 이내에 완료 가능한 프로세스의 요청을 허락한다.
Rate-Monotonic Scheduling: 주기가 짧으면 높은 우선순위. 길면 낮은 우선순위. 시스템에 진입하면 우선순위 결정
Earliest-dead line-first EDF: 마감시간에 따라서 우선순위를 동적으로 부여한다.
proportionate share scheduling: 일정 비율의 몫. 스케줄러는 모든 application들에게 T개의 시간 몫을 할당하여 동작한다. 한 응용 프로그램이 N개의 시간 몫을 할당 받으면 모든 프로세스 시간중 N/T 시간을 할당 받는다.
algorithm evaluation
deterministic modeling: 사전에 정의된 특정한 작업부하를 받아들여 그 작업부하에 대한 알고리즘들의 성능을 정의한다.
Queueing Models: CPU와 I/O 버스트의 분포는 측정할 수 잇다.
도착률과 서비스율을 알기 때문에 이용률, 평균 큐 길이, 평균 대기시간 등을 계산할 수 있다.
n=평균 큐 길이, w=큐에서의 대기시간, (람다)=평균 도착률(예: 1초에 3개의 프로세스)
n= (람다)*w
simulation: 실제시스템을 관찰해 이벤트들의 순서를 기록하여 추적파일을 생성하고 이를 이용
implementation: 구현하는 것. 비용이 크다
