🌑 CPU Scheduling

• 단계별 처리 스케줄링
  • 장기 스케줄링 Long-Term Scheduling
    • 어느 프로그램을 먼저 적재할 것인가 하는 수준의 스케줄링
    • 잡 스케줄링이라고도 함
  • 중기 스케줄링 Medium-Term Scheduling
    • 메모리에 적재된 프로그램들 중, 상당기간 동안 처리를 보류하여 자원을 확보하는 차원의 스케줄링
    • 대상이 된 프로세스들은 잠시 디스크로 이동하여 기다림 (스와핑)
  • 단기 스케줄링 Short-Term Scheduling
    • 실행 준비가 된 프로세스들 중, 어느 프로세스에게 CPU를 보낼 것인가 하는 수준의 스케줄링
    • 보통 CPU 스케줄링이라 함은 이 수준을 말함 (이후 통일)

---

@0411

• CPU 스케줄링 전략의 목표 및 기준

• 사용자 관점에서의 기준 (평가 기준)
  • 응답 시간 Response Time
    • 사용자 입력에 대하여 출력이 이루어질 때까지 소요되는 시간
    • 동일한 조건에서 CPU 스케줄링 방법에 따라 달라질 것임
  • 반환시간 Turnaround Time
    • 프로그램이 제출(혹은 적재)된 후 최종 결과물을 얻을 때까지의 소요시간
    • 총 처리시간이라고도 함
  • 대기 시간 Waiting Time
    • CPU가 주어질 때까지 기다리는 시간들의 합
    • CPU는 자주 조금씩 주어짐
  • 지표 분석
    • 사용자들은 세 가지 지표가 모두 짧아지기를 희망
• 시스템 관점에서의 기준
  • CPU 이용률 CPU Utilization
    • CPU가 순수하게 사용자 프로그램을 실행하는데 소요한 시간의 비율
    • 쉬는 시간이나 시스템 자체의 내부 처리를 위해 보낸 시간이 많으면 좋지 않음
    • @ 문맥 교체 등
  • 처리량 Throughput
    • 전체적으로 단위 시간당 처리하는 프로그램의 수
  • 지표 분석
    • 시스템 (컴퓨터 운영자) 입장에서는 두 지표 모두 높이기를 희망
• @ ~ 사용자 관점과 시스템 과점의 두 입장이 상충됨

• 둘 다 잡을 수 없음 = 하나는 조금 희생해야 한다

• 기타
  • 가용성 Availability
    • 전체 시간 (서비스, 고장, 유지보수, 점검 등) 대비 서비스 시간의 비율 (신뢰성, 가동율)
    • 특정 자원에 대하여 즉시 접근할 수 있는 정도 (즉시 접근 가능 빈도 비율)

• CPU 스케줄링이 이루어지는 시기

• 프로세스가 입출력을 요구할 때
  • 진행 중이던프로세스가 입출력을 요구하면, OS는 입출력 진행중인 동안 마냥 기다릴 수 없으므로 다른 프로세스를 선택해서 CPU를 보내야한다.← 비선점 CPU 스케줄링
• 프로세스가 종료를 요구할 때
  • 프로그램의 진행 절차상 모든 처리가 끝나 종료를 선언하면, OS는 다른 프로세스를 선택하여 CPU를 보내야 한다 ← 비선점 CPU 스케줄링
• 높은 우선 순위의 프로세스가 나타났을 때
  • 높은 우선순위의 프로세스가 입출력을 마치고 준비상태로 전환되면, OS는 현재 실행중인 프로세스를 보류하고, 더 높은 우선 순위의 프로세스에게 CPU를 보낼 수 있다. ← 선점 CPU 스케줄링
• 실행시간이 초과되었을 때
  • 현재 실행 중인 프로세스에게 허용된 최대 실행 시간이 초과하면, CPU는 다른 프로세스 ~여 CPU를 보낼 수 있다. ← 선점 CPU 스케줄링
• 선입 선처리 FCFS First-Come First-Served 스케줄링
  • 개념
    • 준비 대기열 Ready Queue 에 도착한 순서대로 처리
    • 입출력이나 종료 시까지 계속 실행 ← 비선점형
    • 분석
• 최단 작업 우선 SJF Shortest Job First 스케줄링
  • 개념
    • 현재 준비 대기열 Ready Queue에 도착한 프로세스들 중, CPU 버스트 CPU Burst가 짧은 것을 선택하여 실행
    • SPN Shortest Process Next 라고도 함
    • 즉, 입출력이나 종료 시까지 계속 실행 ← 비선점형
  • 분석
    • 기아 상태 현상
    • CPU 버스트는 어떻게 계산?
      • 예측 하는 방법론이 있다 (수업에서 다루지는 않음)

@0413

• 최단 잔여 시간 우선 SRTF Shortest Remaining Time First 스케줄링
  • 개념
    • 실행 중 새로운 프로세스가 도착하면, 현 프로세스의 남은 시간과 새 프로세스의 CPU 버스트 시간을 비교하여 새 프로세스가 더 짧으면 교체 ← 선점형
  • 분석
    • 평균 대기 시간과 평균 응답 시간을 더욱 개선 → CPU 이용률 저하 현상 발생 억제
    • 반면 기아 상태 발생 가능성 더 높음
• 최고 응답률 우선 HRRF Highest Response Ratio First 스케줄링
  • HRN Highest Response Ratio Next
  • 응답률
    • CPU 버스트 대비 대기열에서 기다린 정도의 검증 (CPU 버스트가 크면 그만큼 많이 기다려도 무바앟다는 취지)
    • 응답률 = (준비큐 대기시간 +CPU버스트 시간) / (CPU 버스트시간) = 1 + 준비큐시간 / CPU 버스트 시간)
    • 선점 혹은 비선점 운영 가능
  • 개념
    • SJF나 SRTF의 기아 Starvation 현상을 해결
• 라운드 로빈 RR Round Robin 스케줄링
  • 개념
    • 모든 프로세스에게 동일한 최대 실행 허용 시간 (타임 퀀텀 혹은 타임 슬라이스)를 부여하고, 그 시간만큼씩 공평하게 조금씩 CPU를 보냄 ← 선점형
  • 분석
    • 타임 퀀텀에 따른 문맥 교환 Context Switching)
    • 부담 및 평균대기 시간
• 다단계 큐 MQ Multi-Level Queue
  • 개념
    • 모든 프로세스에게 획일적인 스케줄링 전략을 적용하지 않고, 프로세스들을 특성별로 그룹화하여 각각 독립된 정책을 사용
  • 예 -프로세스를 중요도 등에 따라 크게 그룹화하여 별도의 큐 관리
    • 계산 위주의 프로세스들은 타임 퀀텀을 길게 주고, 우선 순위는 낮게 부여
    • 입출력 위추 프로세서들은 반대로
  • 분석
    • 더욱 정교한 전략을 적용하기 위해 동일 준비 큐 프로세스들 간에는 다른 스케줄링 전략이 적용
• 다단계 피드백 큐 MFQ Multi-level Feedback Queue