CPU Scheduling

게시 2023/11/10 업데이트 2024/08/29

By Mascari4615

9 분읽는 시간

단계별 처리 스케줄링
- 장기 스케줄링 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

💫Computer, 🌑Computer-OS

Computer OS CPU CPU-Scheduling

인기 태그