-
[Chapter-4] cpu 스케줄링개발공부/OS 2024. 7. 21. 17:49
cpu burst : cpu만 연속적으로 사용
i/o burst : io만 연속적으로 사용
- 두가지를 반복하며 사용, 프로그램마다 다름
- io bound job : io가 많이 끼어든 작업
- cpu bound job : io가 별로 안끼어든 작업
스케줄링에서 io bound job 이 문제
이 중 cpu 보단 io 에 더 비중을 줘서 interactive job 에게 적절한 response를 기대함
io bound ps : cpu를 잡고 계산하는 시간보다 io에 많은 시간이 필요
cpu bound ps : cpu 위주
cpu 스케줄러 : ready 상태 프로세스 중 이번에 cpu를 줄 프로세스를 고른다.
dispatcher : cpu의 제어권을 스케줄러에 의해 선택된 프로세스에게 넘겨주는 역할을 하는 친구 ==> 이 과정을 context switch라 한다.
스케줄링이 필요한 경우
1. running => blocked(io요청)
2. running => ready (할당 시간 만료)
3. blocked ready (io 완료후 인터럽트)
4. terminate
cpu 스케줄링크게 아래 두분류
1. nonpreemptive(= 비 선정형 ): 자진반납
2. preemptive (= 선정형): 강제로 뺏기(뺏기가 가능하다)- scheduling criteria(cpu 성능척도)
1. 시스템 입장에서의 성능 척도
- uitilization(이용률) : 놀지않고 일한 시간
- throughput(처리량) :
2. 프로세스 입장에서의 성능 척도
- 소요시간 : 식당에서 보내는 풀 시간
- 대기시간 : 기다리는 시간
- 응답시간 : 첫번째로 음식이 나오는 시간
cpu스케줄링 알고리즘
1. fcfs = fast come first-served
- 고전적인 알고리즘
- 그렇게 좋은 방법은 아니다. (처음 온 프로세스가 계속 잡고있으면 곤란 = convoy effect 유발)
- waiting time : 기다린 총 시간
- average time : 기다린 총 시간의 합 / 3
==> 처음 온 프로세스에 따라 time이 많이 달라짐
2. sjf = shortest-job-first
- 짧게 쓰는 프로그램에 (cpu 버스트가 제일 짧은) 스케줄을 줌
==> 가장 짧은 average waiting time을 보장
- non-preemptive : 새치기가 불가능, 두번째 순서부터 줄세우기
- preemptive : 새치기가 가능
- 문제점 : starvation(긴 프로세스의 정체), 실제 본인의 프로세스가 얼마나 시간을 사용할지 모름
but 과거의 cpu burst time을 통해 추정가능
3. priority scheduling
- pid가 제일 높은 순서로 스케줄링
- 마찬가지로 preemptive, nonpreemptive 가 있다.
- 우선순위가 가장 높은 프로세스 = 가장 낮은 정수
- 문제점 : starvation(pid가 높은 애들이 무시당함)
- 해결책 : aging = 오래 기달리면 우선순위를 높여주자
4. Round Robin (RR)
- 현대 스케줄링은 보통 RR 에 기반
- 각 프로세스는 동일한 크기의 할당시간(time quantum)
- 시간이 끝나면 readyque
- 응답시간이 빨라진다.
- 할당시간이 커지면 fcfs처럼 되고, 작아지면 오버헤드가 커진다.
5. Multilevel Queue
- 여러줄서기 (foreground - RR이 적합, backgound - FCFS가 적합)
- 줄 마다 우선순위가 있다.
- 우선순위가 높은 큐가 비어있어야 다음 우선순위로 간다. (큐에 대한 스케줄링이 필요)
6. Multilevel Feedback Queue
- 프로세스가 다른 큐로 이동가능
- 에이징 구현 가능
7. Multiple-Processor scheduling
- cpu가 여러 개인 경우 스케줄링은 더욱 복잡해짐
- homogeneous processor :
- Queue에 한줄로 세워서 알아서 꺼내가도록
- but 특정 프로세서에서 수행되어야 하는 프로세스시 문제가 복잡
- Load sharing :
- 부하를 적절히 공유
- 별개의 큐, 공동 큐
- SMP : 각 cpu가 알아서 스케줄링
- asymmetric multiprocessing : 하나의 프로세스가 시스템 데이터의 접근, 공유를 책임
8. Real-Time Scheduling
- Hard real-time systems : 정해진 시간 안에 반드시
- Soft real-time copmuting : soft real-time task는 높은 priority를 갖도록 해야함
9. Thread Scheduling
- Local Scheduling : 사용자 수준의 쓰레드 라이브러리에 의해 어떤 쓰레드를 스케줄 할지 결정
- Global Scheduling : 커널의 단기 스케줄러가 어떤 쓰레드를 스케줄 할지 결정
알고리즘 evaluation
1. queueing models
- 확률 분포로 주어지는 arrival rate, service rate, performance index 값을 계산
- 요즘 별로 안씀
2. 구현 & 성능측정
- 실제 시스템에 알고리즘을 구현, 실제 작업에 성능을 측정, 비교
3. simulation
- 알고리즘을 모의 프로그램으로 작성후 trace를 입력
'개발공부 > OS' 카테고리의 다른 글
[Chapter-6] Deadlock (0) 2024.08.10 [Chapter-5] Process Synchronization (0) 2024.08.04 [Chapter-3] 프로세스 관리 (0) 2024.07.21 [Chapter-2] 프로세스 (0) 2024.07.21 [Chapter-1] 시스템 구조 (0) 2024.07.20