스케줄링

• 다음에 실행할 프로세스와 대기할 프로세스를 결정함.
• 프로세스에게 cpu를 공평하게 할당하는 것이 중요함

스케줄링은 언제 발생할까?

1. Time Quantum
2. I/O
3. exit()

프로세스 교환 문단 참고

스케줄링 평가 기준

• 반환 시간 (Turn around time) = 작업 완료시간 - 작업 도착시간
• 공평성(Fairness)
• 응답 시간 (Response time) : 첫번째 응답이 온 시간 - 작업 도착시간
  응답성이 높을 수록 속도도 빨라짐
  

선입 선출(FIFO, FCFS)

• Non preemption(뺏길 수 없음)
• 먼저 들어온 프로세스 순서대로 수행
  

Shortest Job First(SJF,SPN)

• Non preemption
• 짧은 작업 우선으로 수행함, 기아 발생 가능
  

Shortest Time-to-Completion First(STCF,SRT)

• preemption(뺏길 수 있음)
• 최소 잔여시간 우선, 남은 service time이 짧을 수록 유리함
  예를 들어 A가 수행 중에 B가 도착하면 스케줄링이 일어남. 스케줄러가 A와 B 중 잔여 시간이 더 짧은 A를 선택함.
• 기아 발생 가능
  

Highest Response Ratio Next (HRRN)

• Non preemption
• 응답성을 높이기 위해 대기시간을 고려함
• (대기 시간 + 작업 시간) / 작업 시간이 더 큰 프로세스를 선택함
  여기서 대기 시간은 작업 도착 시간 ~ 스케줄링이 일어나는 시점
  예를 들어 B작업이 끝난 후 스케줄링이 일어날 때
  C = (5+4)/4 > D=(3+5)/5 이므로 C 선택
  

Round Robin(RR, Time Slicing)

• preemption
• Time slicing = 스케줄링 퀀텀
• 큐를 이용하여 스케줄링한다.
  Time Quantum은 즉 제한 시간으로써 프로세스가 할당받은 cpu 시간이다. 만약 타임 퀀텀이 1초라면 1초만에 다른 프로세스에게 선점된다. 하나의 큐에 프로세스들이 도착 순서대로 들어가있고, 수행 중이던 프로세스는 타임 퀀텀이 끝나면 큐의 제일 뒤로 다시 들어간다. 만약 작업 수행이 끝나면 큐에 더 이상 들어가지 않는다.
  

Incorporating I/O

• 입출력 시간을 고려함
  I/O는 10ms 필요함
• I/O 요청이 있으면 해당 프로세스는 I/O를 마칠 때까지 블럭 상태가 되고 다른 프로세스에게 넘겨줌
• I/O를 마치면 다시 준비 상태가 됨
  

Multi-Level Feedback Queue (MLFQ)

• Rount Robin은 응답시간을 단축시키는 대신 반환시간이 최악
• MLFQ는 반환 시간을 최적화함
• 대화식 사용자에게 응답 시간을 최소화시킴
  
  MLFQ는 위 그림과 같이 여러 개의 큐로 이루어져 있다.
• 각 큐는 다른 우선순위가 부여되며 상위 큐일 수록 우선순위가 높다. 같은 큐이면 우선순위는 같다
• 큐마다 여러 개의 프로세스가 있을 수 있으며 각 큐는 Round Robin 형태이다.
• 따라서 프로세스에게 고정된 우선순위가 아닌 동적으로 우선순위를 부여한다.
• 먼저 A라는 프로세스가 들어오면 무조건 최상위 우선순위 큐에 올린다. Time Quantum 이내에 작업을 완료 못할시 하위 큐로 내려간다. 마찬가지로 B프로세스가 들어오면 최상위 큐에 있다가, Time Quantum이 끝나고 하위 큐로 내려가는데 A 프로세스 뒤로 들어간다.
• 하위 큐로 내려갈수록 TQ(Time Quantum)은 길어지고 cpu를 차지할 확률은 줄어든다
• 주어진 TQ가 끝나기 전에 I/O를 함으로써 cpu를 양도하면 큐를 유지한 채로 우선순위가 유지된다. 하위큐로 내려가지 않는다.
• 만약 I/O를 하는 프로세스가 많다면 기아 발생이 가능함
  해결책 -> 일정 시간이 지나면 모든 프로세스의 우선순위를 최상위 큐로 이동
  

복권 스케줄링(Lottery Scheduling)

• Proportional Share
  공정 배분을 함으로써 반환 시간이나 응답 시간을 최적화하면서 각 작업에게 CPU를 일정 비율로 할당한다. 프로세스별이 아닌 작업별로 공정하게 준다.

예를 들어 작업 A, 작업 B가 있을 때 작업 A에서는 2개의 프로세스가 돌아가고 작업 B에서는 1개의 프로세스가 돌아간다. 프로세스별로 cpu를 1/3씩 할당한다면 결과적으로 작업 A는 2/3, 작업 B는 1/3만큼을 얻어 작업 B가 불리해지고 공정하지 못하게 된다. 이를 해결하기 위해 작업 별로 cpu를 할당한다.

• 티켓
  프로세스가 받아야 할 자원의 몫이다.
  A : 75장의 티켓 -> 75% 할당
  B : 25장의 티켓 -> 25% 할당

• 복권 스케줄링
  타임 퀀텀이 끝날 때마다 확률적으로 티켓을 선택한다. 스케줄러는 몇 장의 티켓이 있는지 알고 있고 티켓 0~99 중에서 확률적으로 선택한다. A의 경우는 0~74, B는 75~99를 선택한다.

• 티켓 Currency 기법(추첨권 기법)
  200개의 티켓이 존재할 때, 지역 화폐와 글로벌 화폐를 활용함
  user A : 100장의 티켓이 있고 A1, A2 두개의 프로세스 실행 중
  user B : 100장의 티켓이 있고 B1 한 개의 프로세스를 실행 중
  user A : A1 에게 500(지역 화폐), A2 에게 500(지역 화폐)
  ->각각 50씩 변환(글로벌 화폐)
  user B : B1 에게 10(지역 화폐)
  ->100으로 변환(글로벌 화폐)

• 티켓 Transfer 기법(양도 기법)
  한 프로세스가 다른 프로세스에게 일시적으로 티켓을 빌려준다. 클라이언트-서버 환경에서 유용하다.

• 티켓 Inflation 기법
  프로세스는 일시적으로 자신의 티켓 수를 줄이거나 줄일 수 있다. 프로세스간의 신뢰하는 상황에서 유용하며 서로 경쟁 상황에서는 사용할 수 없다.

• 복권 스케줄링은 보통 연결리스트를 이용하여 구현한다. 복권 스케줄링은 리눅스의 CFS 스케줄링의 기초가 되었다.