•
참고 강의
contents
Multilevel Queue
Ready queue를 여러 개로 분할
줄마다 Process를 집어넣는 방식
줄마다 Process를 집어넣는 방식•
foreground Queue(interactive job)
•
background Queue(batch-no human interaction job : 사람과 크게 interaction없는 job)
각 줄마다 스케줄링 방식•
foreground Queue - RR(사람과 interaction하기 때문에 응답시간을 짧게 하기 위해서)
•
background Queue - FCFS(CPU를 오랫동안 사용하기 때문에)
어떤 Queue한테 CPU를 줄것인가
어느 줄에게 CPU를 줄지 결정하기 → 줄 안에서 누구에게 CPU를 줄 지 결정•
Fixed priority scheduling(우선순위를 강하게 적용)
◦
우선순위 높은 큐가 비어있는 경우에만 낮은 우선순위로 내려가기 때문에 starvation 발생
•
Time slice(각 줄 별로 어느정도 CPU 시간을 나누어서 줌)
◦
각 큐에 CPU Time을 적절한 비율로 할당
•
줄마다 우선순위 존재(위가 가장 우선순위 높음)
•
System Processes가 우선순위가 가장 높다.
•
프로세스가 자신에 맞는 프로세스 줄에 가서 선다. → 우선순위가 낮은 프로세스는 CPU를 받기 힘들다.
•
CPU는 하나인데, 줄이 여러개이기 때문에 고려해야할 사항이 여러가지가 존재
1.
프로세스를 어느줄에 넣을 것인가
2.
우선순위가 낮은 프로세스는 starvation를 겪는데 그 부분은 어떻게 해결해야하나
•
공정하지 않고 차별적인 방식
◦
신분을 영원히 극복하지 못하는 방식
추가
Multilevel Feedback Queue
•
여러 줄로 줄서기를 하면서 프로세스가 줄 간의 이동 가능
•
고려해야할 기준
◦
큐를 몇 개 둘건가
◦
각 큐는 어떤 스케줄링을 사용할 것인가?
◦
높은 큐로 보내는 기준
◦
낮은 큐로 내보내는 기준
◦
처음 프로세스는 어느 큐로 들어갈 것인가?
처음 들어오는 프로세스 → 가장 우선순위가 높은 큐로 들어감 → 높은 우선순위의 큐는 RR에서 Time Quantam를 짧게 준다 → 밑으로 갈 수록 RR의 할당 시간을 길게 주고, 마지막 큐는 FCFS 방식을 따른다.
•
할당 시간이 맨 위 큐에서 끝나게 되면 아래 큐로 강등이 되고, 아래 큐도 처리가 안되면 더 아래 큐로 내려가게 된다.
•
CPU Burst가 짧은 프로세스는 도착하자마자 CPU를 얻어서 짧은 시간 쓰고 빠져나갈 수 있다. 긴 프로세스는 아래 큐로 점점 이동을 해서 할당 시간을 더 받게 되지만 위에 큐가 빌 때까지 기다려야 하는 상황을 겪을 수 있다.
•
CPU 사용 시간이 짧은 프로세스에게 우선순위를 많이 주는 스케줄링 방식
•
CPU 사용 시간이 긴 지, 짧은 지 예측을 할 필요가 없다.
◦
처음 들어올 때, 모든 프로세스에게 짧은 시간이 주어지기 때문에(우선 순위 가장 높은 큐) 예측도 필요없고 짧은 프로세스가 더 우대를 받는 방식
지금까지의 스케줄링은 하나의 CPU만 존재할 때 사용할 수 있는 CPU 스케줄링추가
Fair-share
프로세스들의 특성이나 중요도에 따라 몇 개의 그룹으로 나누고, 각각의 그룹에 할애된 일정량의 CPU 시간은 그 그룹에만 영향을 미치도록 하는 것
•
특정 그룹에 속한 프로세스의 과도한 CPU 사용은 그 그룹 내의 다른 프로세스들에게만 불이익을 줄 뿐, 다른 그룹으로싸기 파급되지 않도록 한다.
[ CPU, Thread가 여러개 있거나 데드라인 제약 조건이 있는 경우 ]
Multiple-processor Scheduling
CPU가 여러 개 존재할 때의 Scheduling
Homogeneous processor
•
Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
•
반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
ex. 나를 전담하는 헤어 디자이너한테 머리를 잘라야 하는 경우
Load sharing
•
일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
•
별개의 큐를 두는 방법(CPU마다 줄 서기) vs. 공동 큐를 사용하는 방법(한 줄 서기)
•
모든 CPU가 골고루 일을 해야지 시스템의 전체 성능이 좋아지기 때문에 몰리지 않도록 해주는 메커니즘이 필요
Symmetric Multiprocessing(SMP)
•
각 프로세서가 각자 알아서 스케줄링 결정
•
모든 CPU가 대등한 것
Asymmetric multiprocessing
•
하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
•
CPU 여러개 중에서 하나가 전체적인 컨트롤 책임지는 것
Real-Time Scheduling
Deadline이 있는 job
정해진 시간안에 반드시 실행되어야 하는 프로세스 → 데드라인 안에 끝내는 것을 보장해야 함
•
미리 스케줄링을 해서 데드라인이 보장되도록 적재적소에 배치를 하는 방식을 사용
Hard real-time systems
•
정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
정적인 방법
•
프로세스들의 특징과 개수를 알 수 있는 경우 유용
ex. RM(Rate Monotonic) 알고리즘
동적인 방법
•
프로세스의 생성 시간이나 특성을 알 수 없는 경우에 사용
ex. EDF(Earliest Deadline First) 알고리즘
Soft real-time computing
•
일반 프로세스에 비해 높은 priority를 갖도록 해야 함
•
데드라인이 있어야 하긴 하지만 반드시 지킬 필요가 없는 프로세스 → 조금은 어겨도 상관없는 것
추가
Thread Scheduling
User level Thread, Kernel level thread로 나뉘기 때문에 스케줄링하는 방식이 다르게 나타남
Local Scheduling
•
User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
•
운영체제는 Thread를 몰라서, 프로세스에게 CPU를 줄 지 안 줄 지 결정하는 정도
•
프로세스에게 CPU가 갔을 때, 어떤 thread에게 CPU를 줄 지는 프로세스 내부에서 결정
◦
사용자 프로세스가 직접 CPU를 주는 것을 결정
Global Scheduling
•
운영체제가 Thread의 존재를 알고 있음
•
일반 프로세스와 마찬 가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
Algorithm Evaluation
어떤 알고리즘이 좋은 지 평가하는 방법
1. 큐에 job들이 도착해서 쌓인다.(도착율 : arrival rate) |
2. CPU(server) 용량에 따라서 job를 처리한다.(처리률 : service rate) |
| CPU의 throughput과 job들이 평균적으로 얼마나 기다렸는지 계산에 의해서 확인 가능 |
1.
Queueing models : 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산
•
굉장히 이론적인 방식
•
예전에 많이 사용했던 방식
2.
Implementation(구현) & Measurement(성능 측정) : 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
•
실제 시스템에다가 구현을 해서 정말로 돌려보고 성능을 측정(실측)
3.
Simulation(모의 실험) : 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
•
Implementation & Measurement 보다 쉬운 방식
•
실제로 돌려보는 것이 아니고 모의 실험을 진행
•
프로세스 시작부터 종료까지 계산을 하려면 어렵기 때문에 이걸 할 수 있는 프로그램을 생성 → 단지 하나의 예제를 두고 주장을 하게 되면 적절하지 않음(여러 개 추출)
•
trace : 실제 프로그램을 통해서 추출한 Input 데이터