*스케쥴링 알고리즘
=>스케쥴링은 준비 완료 큐에 있는 어느 프로세스에게 CPU를 할당할 것인지 결정하는 문제를 다룬다.
1. 선입 선처리 스케쥴링(First-come ,First-Served Scheduling)
1) 가장 간단한 CPU 스케쥴링 알고리즘이다.
2) CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다. , FIFO(큐)로 쉽게 관리
3) 프로세스가 준비완료 큐에 진입하면, 이 프로세스의 프로세스 제어 블록(PCB)을 큐의 끝에 연결한다.
4) CPU가 자유상태가 되면 준비 완료 큐의 앞부분에 있는 프로세스에 할당
5) 이 실행상태의 프로세스는 이어 준비 완료큐에서 제거된다.
선입 선처리 정책하에서 평균 대기시간은 일반적으로 최소가 아니며, 프로세스 CPU 버스트 시간이 크게 변할 경우에는 평균 대기 시간도 상당히 변할 수 있다.
=>요약 정리를 하자면,
가정) 하나의 CPU 중심 프로세스와 많은 수의 입출력 중심 프로세스를 갖는다고 가정
1. CPU중심 프로세스가 CPU를 할당받아서 점유
2. 그 동안 다른 모든 프로세스들은 입출력을 끝내고 준비 완료 큐로 이동하여 CPU를 기다린다.
3. 프로세스들이 준비 완료 큐에서 기다리는 동안, 입출력 장치들은 쉬고있다.
4. CPU 중심 프로세스가 자신의 CPU 버스트를 끝내고 입출력 장치로 이동
5. 모든 입출력 중심의 프로세스들은 매우 짧은 CPU 버스트를 가지기 때문에 CPU 작업을 신속히 끝내고 다시 입출력 큐로 이동 후 이 시점에 할당받는다.
6. CPU 중심 프로세스가 끝날 때까지 모든 입출력 프로세스들은 다시 준비 완료 큐에서 기다림
※ 6번처럼 모든 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기 기다리는 ‘호위 효과’
결과 : 이러한 효과는 잛은 프로세스들이 먼저 처리되도록 허용 될 때보다 CPU 장치 이용률이 저하됨
*최단 작업 우선 스케쥴링(Shortest-job-First Scheduling)
=> 이 알고리즘은 각 프로세스에 다음 CPU 버스트 길이를 연관시킨다.
1. CPU가 이용 가능해지면 가장 작은 다음 CPU 버스트를 가진 프로세스에게 할당한다.
2. 두 프로세스가 동일한 길이의 다음 CPU 버스트를 가지면, 순위를 정하기위해 선입 선처리스케쥴링 적용
+ 이 스케쥴링은 프로세스의 전체 길이가 아니라 다음 CPU 버스트의 길이에 의해 스케쥴링이 되 기 때문 (대부분 사람들이 이런 타입의 스케쥴링을 SJF로 언급한다.)
**SJF 스케쥴링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균 대기 시간을 가진다는 점에서 최적임이 증명 가능
짧은 프로세스를 긴 프로세스의 앞으로 이동함으로써, 짧은 프로세스의 대기 시간을 긴 프로세스의 대기 시간이 증가되는 것 보다 더 많이 줄일 수 있다. 결과적으로, 평균 대기 시간이 줄어든다.
※SJF 알고리즘의 어려움. : 다음 CPU 요청의 길이를 파악하는 것
일괄처리 시스템에서 장기 스케쥴링을 위해서는 사용자가 작업을 제출할 때 지정한 처리 시간 제한을 이용할 수 있다. 이러한 경우 사용자들이 처리 시간 제한을 정확하게 예상하도록 하는 동기가 된다. 왜냐하면 시간이 짧을수록 신속한 응답을 기대할 수 있지만 너무 짧으면 시간-초과 오류가 발생하게 되어 사용자는 작업을 다시 제출해야 하기 때문이다. 그러므로 SJF스케쥴링은 장기 스케쥴링에 자주 사용된다.
*SJF 알고리즘의 한계
=> SJF 알고리즘이 최적이긴 하지만, 단기 CPU 스케쥴링 수준에서는 구현할 수 없다.
=> 단기 스케쥴링에서는 다음 CPU 버스트의 길이를 알 수 있는 방법이 없다. 한가지 접근 방식은 SJF 스케쥴링과 근사한 방법을 사용하는 것 이다.
+ 다음 CPU 버스트의 길이를 알 수는 없으나, 그 값을 예측 할 수 있다. 우리는 다음 CPU 버스트가 이 전 의 버스트와 기링가 비슷한다고 기대하기 때문에, CPU버스트 길이의 근사 값을 계산해 가장 짧은 예상 CP U버스트를 가진 프로세스를 선택한다.
※ 다음 CPU 버스트는 일반적으로 측정된 이전의 CPU 버스트들의 길이를 지수 평균 한 것으로 예측
공식 : τ(n+1) = ∂tn + (1 - ∂)τn
과거에 처음 스케줄링이란걸 배웠을 때 많이 어렵고 어색했는데, 다시 공부 해 보니, 조금씩 그 당시에 배웠던 내용들이 이해가 갑니다. 한글파일로 따로 정리하고 Velog에도 정리하니 이중으로 정리하고있어서 내용을 다시한번 보게 되어서 좋은 것 같습니다.
앞으로도 더 열심히 OS 공부를 해야겠습니다!
