: 여러 프로세스가 있고 이 프로세스들이 자원을 동시에 요구할 때, 자원이 제한되어 있다면 이 제한된 자원들 어떻게 분배할 것인지
: CPU 하나는 동시에 여러개의 프로세스를 처리할 수 없기 때문에 한 순간에 어떤 프로세스가 CPU를 점유할 수 있는지 결정하는 정책
목차
Workload (부하)
•
행해져야할 일의 양
•
프로세스의 세트들이 얼마나 많은 자원들을 요구하는 지
workload에서 고려되는 프로세스에 대한 가정
•
모든 프로세스는 같은 시간에 시작되고 같은 시간동안 수행
•
한번 시작되면 각각의 프로세스는 중지되지 않음
•
모든 프로세스는 CPU만 사용한다고 가정
•
각 프로세스의 수행시간을 미리 알고 있다고 가정
Metric
: workload를 측정하는 기준
•
Turnaround Time : 종료시간에서 도착시간을 뺀 값이 작을수록
•
Response Time : 처음에 실행된 시간에서 도착 시간을 뺀 값이 작을수록
•
Waiting Time : ready queue에서 스케쥴링을 기다린시간이 작을수록
•
Fairness : 단위시간 동안 모든 process가 얼마나 공평하게 스케쥴링되었는지
•
Throughput : 단위시간 동안 처리한 process가 많을수록
•
Overhead : 컨텍스트 스위치 횟수가 적을수록 (작업이 종료되고 전환되는 과정)
•
Utilization : hierarchy가 높은 자원을 최대한 바쁘게 했는가
Preemptive Scheduling
•
STCF
•
RR
•
MFQ
•
Lottery
Non-preemptive Scheduling
•
FIFO
•
SJF
Ready Queue
:ready queue에는 프로세스 상태 중에서 ready 상태에 있는 프로세스들, 즉 메모리에 load 되어있는 프로세스들이 쌓여 있습니다.
Multiprocessor에서의 Scheduling
•
Multiprocessor: 말그대로 프로세서가 여러개가 있는 것. 물리적인 프로세서 수
•
Multi Core: 프로세서 내부에 코어가 여러개가 있을 수 있음.
•
Hyper Thread: 코어 내부에 하드웨어적으로 스레드를 두개 이상 지원할 수 있는데 이를 하이퍼 스레드, CPU가 두개로 뻥튀기 되어 보이게 됨.
•
CPU cache(L1,L2,LLC)
◦
Temporal locality(시간 지역성): 어떤 데이터에 접근했을 때, 이는 곧 나중에 다시 접근될 것이다.(stack, for 반복문 같이..)
◦
Spatial locality(공간 지역성): array나 sequential execution 같이 데이터가 한번 접근되면 줍ㄴ에 있는 데이터도 접근될 것이다.
◦
장점: main memory보다 접근이 빨라서 금방 다시 접근할 수 있는 cache hit의 효과가 있다.
◦
Multiprocessor 구조에선 더 복잡한데, cache 사이에서의 일관성을 유지하기가 어렵다. 그래서 Bus snooping을 사용해 주소 버스를 모니터링하고 캐시 상의 메모리 접근을 체크해 일관성을 유지한다.
Cache affinity Scheduling
: 프로세스를 실행 할 때, 이전에 실행했던 프로세스를 동일한 CPU에서 실행하는 것이 더 나으므로(cache hit때문에) 이를 활용한 스케줄링 방식
SQMS(Single Queue Multiprocessor Scheduling)
: A~E가 single queue에 있다고 할 때, cache affinity를 고려하지 않으면
A E D C B . . .
B A E D C . . .
C B A E D . . .
D C B A E . . .
C
복사
cache affinity를 고려해 다음과 같은 스케줄링을 해주면
A E A A A . . .
B B E B B . . .
C C C E C . . .
D D D D E . . .
C
복사
: 간단한 스케줄링이지만, 위와 같이 E 프로세스를 affinity에 잘 활용할 복잡한 메커니즘이 필요함
MQMS(Multi Queue Multiprocessor Scheduling)
: Queue를 여러개 만들어서, 각각의 큐를 각각의 CPU에 사용하는 스케줄링
: 예를 들어, queue 2개가 Q0 -> A -> C, Q1 -> B -> D처럼 있다고 했을 때, 각각의 CPU는 다음과 같이 스케줄 될 수 있음
CPU0 | A A C C A A C C A A C C . . .
CPU1 | B B D D B B D D B B D D . . .
C
복사
: cache affinity에 효율적이고 lock contention은 적지만 위의 예에서 A와 C 프로세스가 먼저 끝이 났을 경우에 CPU0이 놀고 있을 경우가 발생
: 이를 방지하기 위해 다시 재분배해 주는 load balancing이라는 기법이 사용됨
