CPU Scheduling_운영체제(4)

CPU scheduling

• ready process 중 CPU를 누구한테 전달할 것인가를 정하는 것

Scheduling algorithm goals

• All systems
  • No starvation : CPU를 분배
  • Fairness : CPU 자원을 공평하게 분배 받아야 한다.
  • Balance : system 전체적으로 골고루 자원을 사용하도록 한다.
• Batch systems
  • Throughput : 단위시간 당 처리 성능
  • Turnaround time : 전체 작업 시간, 실행 시간(process가 system에 들어왔을 때부터 나갈 때까지의 시간)+대기시간
  • CPU utilization : CPU를 최대한 쉬지않고 사용
• Interactive systems (Online systems) - multitasking이 지원되는 system
  • Response time : 응답 시간, 명령 전달 후 얼마 만에 답이 오는지
  • Proportionality : 비례 지분, 1/n정도의 자원을 확보해야 한다.
• Real time systems – time critical systems
  • Meeting deadlines : deadline을 만족하지 못하면 data가 사라질 수도 있기 때문에 기한을 잘 맞춰야한다.
  • Predictability : 예측성, ex) buffering을 이용한 networking

    hard real time : deadline을 맞추지 못하면 안 되는 것, mission fail이라고 판단
    soft real time : deadline을 맞추지 못하면 mission fail은 아니지만 quality가 낮다고 판단

Starvation

• 다른 process가 계속 요청해서 자신이 못쓰는 상황
• sheduling policy, algorithm이 안 좋으면 이러한 상황이 발생할 수 있다.
• synchronization 또한 starvation을 야기할 수 있다.
  • ex) reader가 계속해서 들어와서 write를 하지 못하는 상황

Non-preemptive scheduling

• 반납할 때까지 CPU를 가져올 수 없는 scheduling
• job끼리 협력적이면 사용이 가능하지만 거의 불가능하다.

Preemptive scheduling

• CPU를 빼앗을 수 있는(선점이 가능한) scheduling – 강제적으로 context switching
• 일반적으로 OS에서 채택하는 방식
• preempt를 해야 하는데 매우 중요한 작업을 하고 있거나 I/O와 같은 시간이 많이 걸리는 system call을 하는 경우에는 context switching을 하면 안된다.
  • system call에 따라 달라진다 – 간단한 system call은 가능 하지만 오래 걸리는 것은 불가능하다.

Execution Characteristics

CPU burst vs. I/O burst

• CPU burst : CPU를 이용하는 구간
• CPU-bound process : 주로 CPU를 사용하는 process
• I/O burst : I/O를 사용하는 구간
• I/O-bount process : CPU와 I/O를 함께 사용하는 process
  

↑ CPU-burst time histogram

Scheduling Criteria(평가 기준) - optimization(최적이 되기 위한 것)

• 모든 case에 대해 만족할 수 없고 trade-off 때문에 적절한 상황으로 맞춰야한다.
• CPU utilization - Max
• Throughput - Max
• Turnarount time - Min
• Waiting time - Min
  • ready queue에서 대기하는 시간
• Response time - Min
  • 명령을 하고 사용자에게 처음으로 응답하게 되는 시간
  • 작업이 완료된 시간이 아니라 반응한 시간이다.

FCFS / FIFO

• First Come First Served : 먼저 들어온 것을 먼저 해결하는 방식
• non preemptive 방식으로 초반에 사용된 방식
• job이 동등하기 대우를 받기 때문에 starvation이 없다.
• 문제점 : average waiting time이 길어질 수 있다. ex) 짧은 작업이 큰 작업 뒤에 있는 경우
• concurrency가 낮아진다.
• convoy effect : long process가 먼저 와서 전체 시간이 길어지는 경우, 부정적인 효과

SJF

Non-Preemptive

Preemptive

• Shortest Job First : 짧은 것을 먼저 해결하는 방식
• tie braking(처리 시간이 같은 경우) : 먼저 온 process
• TAT(TurnAround time) = ET(Execution Time = CPU burst) + WT(Waiting Time) 으로 WT를 구할 수도 있다.
• starvation이 발생할 가능성도 많다.

SRTF

• Shortest Remaining Time First : SJF의 preemptive 방식

CPU Burst Determining

• 이전의 CPU Burst를 참고하여 예측한다.
• : n번째에 일어난 CPU burst의 실제 길이
• : n번째를 본 뒤 다음 CPU burst의 예측치
• 예측치, 실제 값에 가중치를 둔다.
• 시간이 오래될수록 가중치는 작아지고 최근 것일수록 가중치가 높아지는 공식이 된다.
• : 이전 예측 값들 중 직전의 예측 값만 생각해서 예측한다. (일반적으로 사용 X)
• : 직전의 예측을 버리고 그 이전의 값만 이용하여 예측한다. (일반적으로 사용 X)

• 파란 선 : 예측 값
• a = 0.5 : 전반적으로 추세를 따라가며 예측이 가능한 것을 확인할 수 있다.

RR(Round Robin)

• Ready queue에 있는 process를 1바퀴 단위로 실행시키는 방식
• time slice(time quantum) : 1개의 process를 처리하는 평균적인 시간 / 일반적으로 10~100ms 정도로 설정
• time sharing에 좋다.
  • starvation이 없다.
  • SJF 보다는 평균 TA가 길지만 반응 시간이 더 좋다.
  • 반응 시간(응답 시간) : 처음으로 process가 CPU를 받은 시간
• preemptive 방식이다.
• 일반적으로 전체 CPU burst(work load) 중 80%는 개별 time quantum을 다 쓰지 못하는 경우기 때문에 해결되는 process가 전체 time quantum의 80%만큼 설정하면 된다.
• 모든 job을 동등하게 처리한다

• quantum이 짧을수록 응답 시간은 빨라지지만, context switches overhead가 많아져서 교환비용이 늘어난다.
• 1) time quantum이 늘어나면서 짧은 처리 시간을 가진 process들이 나가기 때문에 평균 TA가 줄어든다.
• 2) 빠져나가는 process의 수가 차이가 없고 time quantum이 늘어나서 기다리는 process의 대기시간(waiting time)이 늘어남에 따라 평균 TA가 증가한다.

Priority Scheduling

• 중요한 process는 우선순위(priority)를 높게 부여하여 먼저 처리하도록 한다.
• priority queue에 동등한 priority를 가진 process를 묶어서 순서대로 처리하는 방식도 있다.
• 1개의 queue에서 제일 높은 우선순위를 가진 process를 처리하는 방식도 있다.
• Linux에서는 숫자가 낮을수록 priority를 높게 부여할 수도 있다. - 사용자 정의
• preemptive일 수도 있고 non-preemptive일 수도 있다. - 일반적으로 완전히 preemptive로 설정하기는 어렵다.
• priority는 dynamic하게 조정될 수 있는 값이다.

MLFQ(Multi-Level Feedback Queue)

• multi level로 queue를 두고 상황에 따라 priority 조정을 하는 모델링 방식

Starvation problem & Solution

• 기다리던 process보다 더 높은 priority를 가진 process가 들어오면 계속해서 대기해야하는 문제가 생긴다.
• Aging : starvation 문제를 해결하는 법
  • wait time이 있던 process의 priority를 조금씩 올려주는 상황
  • 사용한 CPU 양이 많다면 priority를 낮추는 방향도 있다.

Priority inversion problem

• 낮은 priority를 가진 process가 높은 priority를 가진 process보다 먼저 실행되는 현상
• 낮은 priority가 lock을 가진 상태가 되었을 때 발생할 수 있다.
• lock은 OS도 함부로 빼앗지 못하는 상태이기 때문에 일어나는 현상이다.

Priority inheritance protocol(PIP)

• 높은 priority task가 낮은 priority task에게 priority를 상속시키는 방법(주는 방법)
• low priority의 task가 high priority와 접촉(접근)이 있어야 한다. 둘 사이 접촉이 없다면 상속이 되지 않는다.

Priority ceiling protocol(PCP)

• lock을 잡을 때 high priority가 되는 방법
• 다른 process와 접촉이 없어도 lock만 잡으면 priority가 높아진다.
• 일반적으로 더 좋은 방식이다.

Multi-Level Queue

• feedback을 받지 않고 priority를 수정하지 않는 방식의 queue
• starvation이 발생한다.
• foreground(interactive) : RR 방식을 사용
• background(batch) : FCFS 방식을 사용
• priority를 고정하는 scheduling 방식이다. background 작업은 foreground 작업이 끝난 뒤 실행된다.
• time slice : 전체 CPU time에 일정 부분만큼 시간 동안 burst가 끝나도록 하는 것
• proportional scheduling : 일정 지분만큼 나눠서 진행하는 방식
  • time slice를 foreground는 80% / background는 20% 만큼 분배

Multi-Level Feedback Queue

• job이 여러 priority를 수정할 수 있는 방식
• process가 CPU time이 높으면 low priority를 가지게 된다.
• 최상위 priority process는 보통 I/O bound나 interactive process가 된다.
• lower priority에 오래 있는 process는 aging을 이용하여 priority를 높인다.
• 정의할 때 정하는 parameter
  • 몇 개의 queue를 둘 것인다.
  • 각 queue에 어떤 algorithm을 적용할 것인가 – 일반적으로 RR
  • 언제 process의 priority를 높이거나 낮출 것인가에 대한 algorithm

Real-Time Scheduling

Hard real-time systems

• time critical한 scheduling으로 어떤 시간 내에 작업을 완료해야 하는 scheduling이다.
• ex) military, medical, nuclear power plant 등
• deadline을 만족하지 못하면 mission failed 처리를 하는 방식이다.
• EDF, RMS protocol algorithm이 있다.

Soft real-time systems

• 일상적으로 사용할 수 있는 방식이다.
• medial player, VoIP 등
• deadline을 만족하지 못하면 mission fail이 아닌 서비스의 품질이 낮아진다.
• 범용적인 OS에서도 구현이 가능하다.