운영체제 - 반효경 5강

Posted Aug 20, 2024

By sunjong0214 10 min read

프로그램 실행 시 흐름

위 그림으로 알 수 있는 사실은 I/O bound job = CPU를 짧게 자주 I/O로 바뀜, CPU bound job = 실제로 CPU를 길게 씀
CPU 스케줄링이 필요한 이유
- 만약 CPU bound job과 I/O bound job에게 공평하게 CPU를 할당하면 사람과 직접 연관있는 interactive job인 I/O job이 오래 기다려야 함 -> 사람이 답답함
- 이런 이유 때문에 CPU bound job과 I/O bound job의 우선순위를 적절히 정해줘야 함 -> 스케줄링이 필요함

I/O-bound process : CPU를 잡고 계산한느 시간보다 I/O에 많은 시간이 필요한 job, many short CPU bursts
CPU-bound process : 계산 위주의 job, few very long CPU bursts

CPU Scheduler : Ready 상태의 프로세스 중 어떤 프로세스에게 CPU를 줄지 선택해주는 코드
Dispatcher : CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 CPU를 넘겨주는 코드, context switch라고 함
Scheduling 알고리즘 두 분류
- nonpreemptive(자진 반납) : Runing -> Blocked, Terminate의 경우, 비선점형
- preemptive(강제로 뺐음) : Runing -> Ready, Blocked -> Ready, 선점형

시스템 입장에서의 성능 척도 : CPU를 얼마나 효율적으로 사용하는가
- CPU utilization(이용률) : CPU가 놀지 않고 일한 시간
- Throughput(처리량) : 주어진 시간 동아 몇개의 작업을 완료 했는가
프로그램 입장에서의 성능 척도 : 내(프로그램) 일을 얼마나 빨리 처리해주는지
- Turnaround time(소요 시간) : CPU burst가 시작되고 끝나고 나갈 때까지의 시간
- Waiting time(대기 시간) : 기다린 총 시간
- Response time(응답 시간) : queue에 들어와서 처음으로 CPU를 얻기까지 걸린 시간
여기서 성능 척도는 프로세스가 시작하고 끝날 때를 의미하는 것이 아니라 CPU burst 단위로 시작과 끝날 때를 의미한다.

Shortest-Job-First
CPU burst가 짧은 프로세스에게 우선순위를 주는 스케줄링
Nonpreemptive 방식
- 프로세스가 CPU를 잡으면 그 프로세스의 CPU burst가 끝날 때까지 CPU를 뺏기지 않음
preemptive 방식
- 현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 들어오면 CPU를 뺏김
- 이 방법을 Shortest-Remaining-Time-First(SRTF)라고 부름
평균 대기시간이 가장 짧은 스케줄링(preemptive 방식일 때)
예제 1(nonpreemptive 방식) - SJF
예제 2(preemptive 방식) - SRTF
문제점
- Starvation(기아 현상) : SJF는 항상 짧은 시간을 가진 프로세스에게 CPU를 할당하기 때문에 긴 시간을 가진 프로세스는 영원히 CPU를 할당 받지 못할 수 있다. 이런 형상을 Starvation이라고 한다.
- 다음 CPU Burst time 예측 불가능 : CPU burst time을 미리 알 수 없다는 문제. 하지만 추정은 가능. 과거의 CPU burst time을 이용해서 추정
  Priority Scheduling
높은 우선순위를 가진 프로세스에게 CPU 할당
preemptive와 nonpreemptive 둘 다 구현 가능
SJF는 일종의 priority scheduling
Starvation 문제가 발생할 수 있음
starvation 문제를 해결하기 우해 aging(노화)를 도입 : 오래 기다린 프로세스에게 점차 더 높은 우선순위를 부여

현대의 대부분의 운영체제는 RR을 기반으로 스케줄링
각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐 (10 - 100ms)
할당 시간이 지나면 프로세스는 선점 당하고 ready queue의 제일 뒤로 보냄
RR의 가장 큰 장점은 Response time(응답 시간)이 빨라짐
- 할당 시간을 기반으로 스케줄링하기 때문에 n(프로세스 수) * q(할당 시간) 안에 한번은 CPU를 할당 받을 수 있음
- 또 waiting time(대기 시간)도 프로세스의 CPU 사용 시간에 비례해서 증가함
성능
- q large -> FCFS와 같아짐
- q small -> context switch 오버헤드가 커짐
예제
발생할 수 있는 문제
- 만약 같은 CPU burst를 가진 프로세스 4개가 있다고 가정하자
- 그때 RR로 스케줄링을 하면 average turnaround time이 매우 길어질 수 있다
- RR의 경우 CPU burst가 짧은 프로세스의 경우에 금방 CPU를 사용하고 빠져나갈 수 있다
- 하지만 모든 프로세스의 CPU burst가 같다면 4개의 프로세스가 먼저 CPU burst를 끝내고 빠져나가지 못하기 때문에 평균적인 turnaround time이 상당히 길어질 수 있다
- 하지만 보통 이 문제는 잘 발생하지 않는다

Ready queue를 여러 개로 분할
- foreground : interactive job
- background : batch - no human interation job
각 queue는 독립적인 스케줄링 알고리즘을 가짐
- foreground : RR
- background : FCFS
queue에 대한 스케줄링도 필요
- Fixed priority scheduling :높은 우선 순위의 queue에게 스케줄링, starvation 현상 발생할 수 있음
- Time slice : 각 queue에 CPU time을 적절한 비율로 할당, foreground = 80 / background = 20

Multilevelm Queue의 문제를 해결하기 위해 나옴
프로세스가 다른 큐로 이동 가능 ex) aging
Multilevel Feedback Queue scheduler 정의하는 파라미터들
- Queue의 수
- 각 큐의 scheduling algorithm
- Process를 상위 큐로 보내는 기준
- Process를 하위 큐로 내쫓는 기준
- 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
보통은 처음 들어오는 프로세스는 우선 순위가 가장 높은 queue에 넣음 -> quantum을 지나면 하위 큐로 강등 -> 상위 queue가 비었을 때 하위 queue를 처리 -> 반복(상위 queue에서 하위 queue로 갈수록 할당 시간이 줄어들게 설계)

Local Scheduling : User level thread(운영체제가 스레드에 대해 모르는 경우)의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
Global Scheduling : Kernel level thread(운영체제가 스레드에 대해 앎)의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄링할지 결정

출처)

[운영체제 - 이화여자대학교

KOCW 공개 강의](http://www.kocw.net/home/cview.do?cid=3646706b4347ef09)

This post is licensed under CC BY 4.0 by the author.