스케줄링 알고리즘

• 스케줄링 알고리즘 기준
  CPU 이용률과 처리율을 최대화하고 반환 시간, 대기 시간, 응답 시간을 최소화 함

기준	내용
CPU 이용률	프로세스들이 CPU를 이용하는 비율
처리율(Throughput)	단위 시간당 완료 되는 작업의 수
반환 시간(Turnaround Time)	진입한 시간과 완료한 시간의 차이
대기 시간(waiting Time)	대기 큐에서 대기하면서 보낸 시간
응답 시간(Response Time)	대화식 시스템에서 하나의 작업을 제출한 후, 첫 번째 응답이 나오는 데 걸리는 시간

▶ 스케줄링 알고리즘 기준

   

• 스케줄링 알고리즘의 종류
  • 우선순위 스케줄링
    • 각 프로세스에게 우선 순위를 부여하여 높은 순서대로 처리하는 방법
    • 정적 우선순위 방법 : 우선순위가 불변
    • 동적 우선순위 방법 : 상황에 따라 우선 순위가 가변
  • 마감 시간 스케줄링
    • 작업들이 명시된 시간이나 기한 내에 완료되도록 계획
    • 사용자는 사전에 작업이 요구하는 정확한 자원을 제시
  • FCFS(First Come First Served) 스케줄링
    프로세스가 대기 큐(준비 큐)에 도착한 순서에 따라 CPU 할당
  • 라운드 로빈(Round Robin) 스케줄링
    • FCFS에 의해 보내진 프로세스가 할당된 CPU 시간 내에 처리를 완료하지 못하면 리스트의 가장 뒤로 보내지고, CPU는 대기 중인 다음 프로세스로 넘어감
    • 시분할 방식에서 효과적이며 할당 시간의 크기가 동작에 영향을 미침
    • 할당 시간이 크면 FCFS와 동일하고, 작으면 문맥교환의 오버헤드가 증가
      • 문맥교환[Context Switch]
        • 하나의 프로세스가 CPU를 사용 중인 상태에서 다른 프로세스가 CPU를 사용하도록 하기 위해 이전의 프로세스의 상태(문맥)를 보관하고 새로운 프로세스의 상태를 적재하는 작업
        • 한 프로세스의 문맥은 그 프로세스의 PCB(프로세스 제어 블록)에 기록
  • SJF(Shortest Job First) 스케줄링
    • 일반적인 우선순위 알고리즘의 특별한 경우로, 대기 큐에서 수행 시간이 가장 짧은 작업을 먼저 수행
    • 평균 대기 시간이 감소하고, 짧은 작업에 유리
    • 프로세스 수행 예측이 어려움
  • SRT(Shortest Remaining Time) 스케줄링
    • 대기 큐에서 가장 짧은 시간이 소요되는 프로세스를 먼저 수행
    • 처리 시간이 짧은 프로세스에게 실행 중인 프로세스가 선점 가능성
    • SJF 기법 + 선점 방식 시분할에 유리
    • 실행 시간의 추적 보유(선점 오버헤드 증가)
    • 긴 작업은 SJF보다 대기 시간이 길어짐
  • HRN(Highest Response ration Next) 스케줄링
    • SJF의 약점을 보완한 기법으로, 긴 작업과 짧은 작업 간의 불평등을 완화시킴
  • 다단계 큐(MLQ; Multi Level Queue) 스케줄링
    • 작업들을 여러 종류의 그룹으로 나누고, 여러 개의 큐를 사용하는 방법
    • 준비 상태 큐를 여러 종류로 분할(작업 분류별 묶음)하고, 다른 큐로의 작업 이동은 불가)
    • 각 큐는 자신만의 독자적인 스케줄링을 가짐
    • 상위 단계 작업에 대해 하위 단계 작업이 선점 당함
  • 다단계 피드백 큐(MFQ; Multilevel Feedback Queue) 스케줄링
    • 입.출력 위주나 CPU 위주인 프로세스 특성에 따라 서로 다른 CPU 타임 슬라이스를 부여
    • 새로운 프로세스는 높은 우선 순위를 할당(단계 1)하고, 수행 후 점차 낮은 우선 순위를 부여(단계 n까지)
    • 단계 n에서 완료까지는 라운드 로빈으로 순환
    • 짧은 작업에 유리(입.출력 위주 작업에 우선권)하고, 작업 특성에 따라 신속한 스케줄링 가능
    • 하위 단계일수록 할당 시간 증가(공평성 부여)
    • CPU 요구량에 따른 프로세스 분류에 유리하고, 시스템 제어 동작 변화에 민감한 적응 기법
    • 다른 큐로의 작업 이동은 불가능함
    • UNIX에서 사용
         
• 스케줄링 알고리즘의 비교

종류	방법	특징	구분
우선 순위	우선 순위를 할당하여 우선 순위가 높은 순서대로 처리	고정적 우선 순위 가변적 우선 순위 구입된 우선 순위	비선점
마감 시간	프로세스가 주어진 시간 내에 작업이 끝나도록 계획	마감 시간을 계산해야 하므로 막대한 오버헤드와 복잡성이 발생	비선점
FCFS	작업이 시스템에 들어온 순서대로 수행	대화형에는 부적합 간단하고 공평함 반응 속도를 예측할 수 있음	비선점
라운드 로빈	FSFS 방식의 변경으로, 각 프로세스에 일정한 시간을 부여하는 방법	시분할 방식에 효과적 할당 시간이 크면 FIFO와 동일 할당 시간이 작으면 문맥 교환이 자주 발생	선점
SJF	수행 시간이 짧은 작업을 우선적으로 처리	수행시간이 짧은 작업에 유리하고,큰 작업은 상당 시간 소요	비선점
SRT	수행도중 나머지 수행 시간이 작은 작업을 우선적으로 처리	작업처리는 SJF와 같으나, 이론적으로 가장 작은 대기 시간이 소요	선점
HRN	SJF에서 큰 작업이 시간이 많이 걸리는 점을 보완	우선순위 = (대기 시간 + 수행 시간) / 수행 시간	비선점
MLQ	서로 다른 작업을 각각의 큐에서 타임 슬라이스(time slice)에 의해 처리	각각의 큐는 독자적인 스케줄링 알고리즘을 사용	선점
MFQ	하나의 준비 상태 큐를 통해 여러 개의 피드백 큐에 걸쳐 처리	CPU와 I/O 장치의 효율을 높일 수 있음	선점