반응형
CPU bound job
- CPU를 길게 쓰는 프로그램들
I / O bound job
- 입출력이 많은 작업들, 키보드 입력같은거
여러 종류의 JOB( = process)이 섞여 있기 때문에 CPU 스케줄링이 필요하다
CPU Scheduler
- Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.
Dispactcher
- CPU의 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘긴다
- 이 과정을 context switch(문맥교환)라고 한다
CPU스케줄링이 필요할 때
- Running - > Blocked ( 예 : I / O 요청을 위한 시스템 콜) - > 자진 반납
- Running - > Ready ( 예 : 할당시간만료로 timer interrupt) - > 강제
- Blocked - > Ready ( 예 : I / O 완료 후 인터럽트) - > 강제
- Terminate - > 자진 반납
Scheduling Criteria( 성능 척도 )
- Cpu utilization ( 이용률)
- Throughput( 처리량 )
- Turnaround time( 소요시간, 반환시간)
- Waiting time( 대기 시간)
- Response time( 응답 시간)
다양한 스케줄링 알고리즘
1. FCFS ( First - Come First - served)
단순하게 먼저오는 것부터 처리하는 알고리즘, 비선점 스케줄링 방법 중 하나이다
Convey effect ( 호위 효과 ) : 긴 시간을 잡아먹는 프로세스가 먼저오게 되면 뒤에 있는 프로세스들이 오랜시간 기다려야 하는 현상
2. SJF ( Shortest - Job - First)
- CPU burst time이 가장 짧은 프로세스를 제일 먼저 실행
- SJF is optimal, 주어진 프로세스들에 대해 minimum average waiting time을 보장
- 두가지 방식이 존재한다
- Nonpreemptive : 수행중인 CPU는 계속 실행...
- Preemptive : 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김. Shortest - Remaining - Time - First ( SRTF )
- 단점 : 다음번 CPU burst time을 어떻게 알 수 있는가? 추정(estimate)만이 가능하다. 과거의 CPU burst time을 이용해서 추정
3. Priority Scheduling
- highest priority를 가진 프로세스에게 CPU 할당
- SJF는 일종의 Priority Scheduling이다. 왜냐하면 CPU burst time이 짧은 일에 우선순위를 주기 때문이다
- Starvation 현상이 발생가능하다, ( Starvation : 우선순위가 낮은 프로세스가 계속 실행되지 않는 현상)
- 해결책으로는 Aging이 있다 ( Aging : 오래기다리면 우선순위를 높여준다 )
4. Round Robin ( RR )
- Preemtive 방식
- 각 프로세스는 동일한 크기의 할당시간( time quantum )을 가짐
- 할당시간이 너무 크면 FCFS, 너무 작으면 Context Switch 오버헤드가 너무 커진다
- 제일 많이 사용하는 CPU 스케줄링의 근간이 됨
- response time은 더 짧다
- 일반적으로 SJF보다 average turnaround time이 길다
5. Multilevel Queue
- ReadyQueue를 여러 개로 분할
- foreground ( interactive )
- background ( batch - no human interaction)
- 각 큐는 독립적인 스케줄링 알고리즘을 가짐
- 큐에 대한 스케줄링이 필요
- Fixed Priority Scheduling
- 무조건 foreground 먼저, background는 나중에...
- Starvation 발생 가능....
- Time Slice, 각 큐에 CPU time을 적절한 비율로 할당
- Fixed Priority Scheduling
6. Multilevel Feedback Queue
- 여러개의 줄이 있는데( 큐가 존재 ), 프로세스가 다른 큐로 이동 가능
- 에이징을 이 방식으로 구현 가능
- Multilevel - Feedback - queue scheduler를 정의하는 파라미터들
- Queue의 수
- 각 큐의 Scheduling algorithm
- Process를 상위 큐로 보내는 기준
- Process를 하위 큐로 내쫓는 기준
- 프로세스가 CPU 서비스를 받으러 할 때 들어간 큐를 결정하는 기준
7. Multiple - Processor Scheduling
- CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
- Homogeneous processor인 경우
- 큐에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다
- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐...
- Load Sharing( Load balancing)
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
- 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
- Symmetric Multiprocessing ( SMP )
- 각 프로세서가 각자 알아서 스케줄링 결정
- Asymmetric Multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
8. Real - Time Scheduling
- Hard real - time systems
- Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링 해야함
- Soft real - time systems
- Soft real-time task는 일반 프로세스에 비해 높은 Priority를 갖도록 해야함 ex) 동영상
9. Thread Scheduling
- Local scheduling
- User level thread의 경우 사용자 수준의 Thread library에 의해 어떤 Thread를 스케줄할지 결정 ( = 프로세스 내부에서 결정)
- Global scheduling
- Kernal level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 Thread를 스케줄할지 결정
Algorithm Evaluation
- Queueing models
- 확률분포로 주어지는 arrival rate와 service rate등을통해 각종 Performance index 값을 계산
- Implementation ( 구현 ) & measurement ( 성능 측정 )
- 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 비교
- Simulation ( 모의 실험 )
- 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
이 포스팅은 이화여대에서 무료로제공하는 반효경님의 운영체제강의를 수강하며 정리한 내용입니다.
필자가 잘 이해하지 못해서 잘못된 내용이 있을 수 있으므로 주의바라며, 발견되면 알려주시면 감사하겠습니다.
http://www.kocw.net/home/search/kemView.do?kemId=1046323
반응형
'CS > 운영체제' 카테고리의 다른 글
운영체제(8) -Semaphores ,Monitor (1) | 2023.10.05 |
---|---|
운영체제(7) - Race condition과 임계구역(Critical-Section problem) (1) | 2023.10.03 |
운영체제(5) - 프로세스의 생성과 관련 시스템콜 (1) | 2023.09.22 |
운영체제(4) - 스케줄러와 Thread (0) | 2023.09.22 |
운영체제(3) - 프로세스 (0) | 2023.09.13 |