멀티 프로세서의 발전 - 처리기가 늘어남에 따라 어떤 프로세스에 어떤 처리기를 할당할지 복잡해짐
주요 이슈
cache affinity (친화력)
- 특정 프로세서에서 실행된 프로세스는 가능하다면 계속 동일한 프로세서에 할당함
Concurrency (병행성)
여러 프로세서에 프로세스를 할당하기 위해 레디큐(싱글 큐라고 가정)에 동시 접근하여 프로세스를 불러올 때 생기는 문제를 해결
Shared data를 이용할 때 생기는 문제 -> race condition
공유자원에 대해서 한번에 한번씩 접근하게 하는 기법 -> mutual exclusion (ex: 동기화, 데드락)
SQMS(single-queue multiprocessor scheduling)
각 cpu가 단순히 전역적인 싱글큐에서 프로세스를 선택하고 실행
장점 : 구현이 단순함
단점 : concurrency 때문에 동기화 기법을 적용해야 하고 그로 인해 확장성이 떨어짐, 캐시 친화력을 복잡한 방식으로 구현
MQMS(multi-queue multiprocessor scheduling)
프로세서마다 별도의 큐가 존재하고 프로세스들은 계속 같은 큐에서 스케쥴링됨
캐시 친화력을 유지
큐가 분리되었기 때문에 shared data에 대한 race condition을 해결
큐마다 별도의 rule을 만들 수 있음
단점 : 특정 CPU에서 큐에 존재하는 모든 프로세스가 끝나면 대기시간이 생김 -> load imbalance
한가한 프로세서에 다른 프로세서의 프로세스를 할당하는 것 -> migration
하지만 cache 친화력의 이점을 해칠 수 있다.
migration
큐의 길이의 정도에 따라서 프로세스를 다른 cpu에 할당함
너무 빈번하게 하면 overhead 발생
초기 리눅스의 멀티 프로세서 스케쥴러
o(1) scheduler - 리눅스 2.5
멀티 큐에서 큐들은 각각 우선순위와 task를 가지고 있다
task가 우선순위를 받으면 해당하는 순위의 queue에 들어감
특정 큐에 더 빠르게 접근하기 위해 bitmap이 존재
active queue와 expired queue가 동시에 존재하는데,
time slice를 모두 소진한 task들은 expired queue에 저장되고 active queue가 비었을 때 active queue가 expired queue가 되고 expired queue가 active queue가 되서 다시 실행 (서로 포인터를 바꿈)
-> 우선순위를 지킬 수 있다
할당할 프로세스를 탐색할 때 우선순위 큐의 크기만큼만 탐색하면 되므로 O(1) scheculer
-> 프로세스의 수와 상관없음
proportional Share schedling - 리눅스 2.6
멀티 미디어에 대한 요구사항이 올라감 -> 하나의 프로세스에서 충분한 CPU 할당 시간을 요구
프로세스마다 다른 weight에 적절한 CPU 수행 시간을 각각 다르게 할당
WFQ 알고리즘
위의 스케쥴링에서 weight를 계산하는 알고리즘
누적 수행시간을 정규화 -> virtual time
A:B:C:D = 4:3:2:1 의 weight를 가지고 있을 때 정규화된 virtual time은 다음과 같다.
같은 1초라도 가중치가 다르기 때문에 자신의 weight로 실행한 시간을 정규화 하여 낮은 실행 시간을 가지는 프로세스의 우선순위를 높게 하자
completely fair scheduler - 현재
레드 블랙 트리로 프로세스 순위를 저장하여 계속 균형을 맞춰줌
'CS > OS' 카테고리의 다른 글
Semaphore with 수도 코드 (0) | 2022.05.25 |
---|---|
Race condition과 간단한 동기화 (0) | 2022.05.23 |
process scheduling(프로세스 스케쥴링) - FIFO, SPN, Round Robin, SRT (0) | 2022.04.09 |
Process 생성 (in unix) (0) | 2022.04.06 |
Process model - 프로세스 전환(process switch) (0) | 2022.04.05 |