FCFS, SJF, HRN, RR, SRT 스케줄링

 

• 프로세스 스케줄링
  • 수많은 어떤 프로세스를 Dispatch 하는지, 어떤 Process가 CPU 자원을 사용하게 할 것인지, 어떤 프로세스에게 메모리 자원을 할당하게 할 것인지
  • Multi Programming 환경에서는 필수
  • 목적 : 성능을 극대화해서 효율적으로 사용

 

• 성능 지표
  • 응답성(Response Time)
  • 작업처리량(ThroughPut)
  • 자원 활용도(Utilization)

 

• 추정 가능한 수치
  • 대기시간(Wait) : 요청 후 실행 상태로 진입할 때 까지 기다리는 시간
  • 실행시간(Burst) : 실행에 필요한 순수한 시간
  • 응답시간(Response) : 실행 후 첫번째 반응이 나오기까지 걸리는 시간
  • 반환시간(Turn Arround) : 대기시간 + 실행시간 + Sleep시간

 

• 스케줄링 레벨
  • 장기(롱텀, JOB, 스케줄링) : 요청한 작업을 프로세스로 등록시킬지, 말지를(커널에 등록할지 말지, PCB를 만들지 말지..)
    • 멀티 프로그래밍의 정도가 결정됨
    • 식당 대기줄, 홀 안에서의 고객 수를 결정
    • 시분할 시스템에서는 무용지물
    • IO Bound 프로세스 vs Comput Bound 프로세스
  • 중기(미드텀, ...)
    • 메모리를 할당할지 말지를 결정하는
  • 단기(숏텀, 프로세스 스케줄링)
    • 준비상태에 있는 여러 프로세스들 중에 어떤 프로세스를 Dispatch 할것인지

 

• 스케줄링 정책
  • 비선점 : 스스로 반납할때까지 기다리는 정책
    • 문맥교환 자주 발생하지 않음, Overhead가 적게 발생함
    • 응답시간이 길어질 수 있음, 콘보이 효과
  • 선점 : OS가 강제로 CPU를 뺏는 정책
  • 우선순위
    • 결정된 우선순위에 따라....
    • 정적, 동적

 

 

---

• FCFS(First Come First Serve)
  • 선착순(먼저 들어온 것을 먼저 처리함)
  • 비선점
  • 장점 : 문맥교환이 상대적으로 덜함, Overhead가 없음, 공평한 정책
  • 단점 : 콘보이 효과 발생(앞에 무거운 프로세스가 있다면 뒤에 가벼운 프로세스가 있어도 그만큼 기다려야함), 반응시간이 느릴 수 있음
  • 일괄처리하는 시스템에 적합. Interactive한 시스템은 부적합

 

• SJF(Shortest Job First) : SPN(Shortest Process Next)
  • 비선점
  • Burst Time이 짧은게 먼저 처리됨
  • 장점 : FCFS의 비선점 특성을 그대로 따름
    • 대기시간 최소화 > 빠른 응답 시간, 메모리 절약
  • 단점 : 기아현상(Starvation) 발생 가능 == 무한 대기현상 > Aging 기법 적용하여 해결

 

• HRN(Highest Response ratio Next)
  • 비선점
  • (대기시간 + Burst Time) / Burst Time 값이 큰 것 부터
  • 장단점 : SJF와 유사하나 SJF 단점을 개선

 

• Round Robin
  • 선점
  • 주어진 시간만큼만 돌아가면서 실행되는 기법
  • 준비큐에 우선순위대로
  • 장점 : 독점을 방지, 첫 반응시간을 빨리
  • 단점 : 문맥교환 다소 많이 발생, 오버헤드 발생
  • 시분할 시스템

 

• SRT(Shortest Remaining Time)
  • 선점이나 SJF의 변형
  • 주어진 시간만큼만 돌아가면서 실행되는 기법
  • 짧은거 먼저
  • SJF기법의 극대화
  • 오버헤드 발생, 잔여시간을 매 Slice마다 계산해야 함

 

• SJF, SRT, HRN vs RR, FCFS
  • 앞의 3개는 BurstTime을 알고 있어야만 선택이 가능함
  • 뒤의 2개는 간트차트를 그리는게 아니라면 BurstTime을 몰라도 선택이 가능함

---