CPU 스케줄링

I. CPU의 효율적 사용, CPU 스케줄링

가. CPU 스케줄링의 개념

  • 프로세스 작업 수행을 위해 언제, 어느 프로세스에 CPU를 할당할 것인지 결정하는 작업

나. CPU 스케줄링 기법 종류

구분기법설명
선점RR– 초기 FCFS, 환형 순환구조 뒤로 보냄
SRT– 가장 짧게 남은 시간
MLQ– 여러 개 큐 이용
MLFQ– 서로 다른 타임 슬라이스의 큐 이용
비선점Priority– 우선순위 높은 순서대로 처리
FCFS– 대기 큐에 도착한 순서에 따라 할당
SJF– 수행시간(버스트시간) 짧게 판정 먼저
HRN– 우선순위=(대기 + 버스트) / 버스트 시간
  • 스케줄러 동작 시점, Time Slice, 프로세스 생성/소멸 시, 프로세스 Block 상태 변경 시
  • 스케줄러가 운영체제에 많이 관여-선점, 적게 관여-비선점

 

II. SJF(Shortest Job First), SRT(Shortest Remaining Time)

가. SJF(Shortest Job First)

개념
설명– 비선점 방식 (non-preemptive)
– 대기 작업 중 수행시간이 짧게 판정된 작업 수행
– 짧은 작업 먼저 수행이 오버헤드 측면에서 유리
문제점– 작업 수행시간을 사전에 정확히 판정 어려움

나. SRT(Shortest Remaining Time)

개념
설명– 선점 방식 (preemptive)
– SJF 기법에 선점방식을 도입/변형 방식
– 실행 중 작업이라도 처리시간이 더 짧은 작업이 생기면 선점
문제점– 각 작업에 대한 실행 시간 추적 보유(오버헤드)
– 긴 작업은 SJF 보다 대기 시간 오래 소요

 

III. SJF와 SRT의 평균 대기시간 및 평균 반환시간

프로세스도착 시간실행 시간
P106
P213
P321
P434

가. SJF 기법 계산

프로세스
자원점유
그래프
프로세스
시간
테이블
항목P1P2P3P4
도착 시간0123
실행 시간6314
종료 시간610714
반환 시간69511
대기 시간0647
평균 대기평균 대기시간 = (0 + 6 + 4 + 7) / 4 = 4.25
평균 반환평균 반환시간 = (6 + 9 + 5 + 11) / 4 = 7.75

나. SRT 기법 계산

프로세스
자원점유
그래프
프로세스
시간
테이블
항목P1P2P3P4
도착 시간0123
실행 시간6314
종료 시간14539
반환 시간14416
대기 시간8102
평균 대기평균 대기시간 = (8 + 1 + 0 + 2) / 4 = 2.75
평균 반환평균 반환시간 = (14 + 4 + 1 + 6) / 4 = 6.25
  • 대기시간: 작업이 대기 큐에서 대기한 시간, 반환시간: 작업이 제출된(도착) 시간부터 완료까지 시간
  • 프로세스 자원 점유 변경 시 문맥 교환이 일어나므로 빈번한 자원 점유 변경 시 오버헤드 증가에 따른 성능 감소
3 Comments

콘텐츠 사용 시 출처 표기 부탁 드리고, 댓글은 큰 힘이 됩니다^^