[CS스터디] CPU 스케줄링

지영·2023년 5월 30일
0

CS

목록 보기
15/77

CPU를 최대한 효율적으로 사용하기 위해서 어떻게 프로세스를 배정할까?

1. 스케줄링이란?

: CPU를 잘 사용하기 위해 프로세스를 잘 배정, 실행 중인 모든 프로세스들에게 골고루 CPU를 할당

  • 조건 : 오버헤드는 줄이고, CPU사용률은 늘리며, 기아 현상은 줄이기
  • 목표
    * Batch System : 가능하면 많은 일을 수행. 중요도) 시간 < 처리량
    • Interactive System : 빠른 응답 시간, 적은 대기 시간
    • Real-time System : 데드라인 맞추기

1) 선점형 운영체제(Preemptive OS)

: 현재 실행 중인 프로세스보다 높은 우선순위를 가진 프로세스가 등장함녀 스케줄러가 실행 순서를 바꿀 수 있음. OS가 자원을 강제로 회수할 수 있음

  • ✨ 장점 : 응답이 빠름.
  • 🧐 단점 : 처리 시간을 예측하기 어려움. 우선순위가 높은 프로세스들이 많아지면 오버헤드가 초래

    오버헤드란? 어떤 처리를 하기 위해 들어가는 간접적인(부가적인) 처리 시간/자원 등을 말함
    ex) A라는 프로세스를 단순하게 처리하는 데에 10초가 걸리고 안전성을 고려하여 추가적으로 5초가 더 걸렸다면, 오버헤드는 5초가 됨.

2) 비선점형 운영체제(Non-Preemptive OS)

: 현재 실행 중인 프로세스가 끝나야 다음 프로세스가 CPU를 할당받을 수 있음. OS가 자원을 강제로 회수 불가능

  • ✨ 장점 : 긴 작업을 오래 기다려야 함.
  • 🧐 단점 : 처리 시간을 예측하기 쉬움

2. CPU 스케줄링 종류

선점 스케줄링비선점 스케줄링
Priority Scheduling, Round Robin,
Multilevel-Queue, Multilevel-Feedback-Queue
FCFS, SJF, HRN

1_1) 비선점 스케줄링_FCFS

: First-come, First-served / First in First out 방식

  • 선입선출 방식으로 실행
  • Convoy Effect(호위효과) : 짧은 작업들이 긴 작업 뒤에 오랫동안 나란히 대기할 수 있음

1_2) 비선점 스케줄링_SJF

: Shortest Job First, 실행시간이 가장 짧은 작업 먼저 실행하는 방식

  • FCFS에 비해 평균대기시간(Average Waiting Time)이 짧음
  • 단, 각 프로세스가 시작 전에 얼마나 걸리지 현실적으로 정확히 알기 어렵기 때문에 현실적으로 적용이 어려움

1_3) 비선점 스케줄링_HRN

: 우선순위를 계산하여 점유 불평등을 보완한 방법

  • SJF의 단점을 보완한 방법
  • 우선 순위 = (대기시간 + 실행 시간) / (실행 시간), 즉 대기시간이 많을 수록 우선순위가 점점 높아짐

2_1) 선점 스케줄링_Priority Scheduling

: 정적, 동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리

  • 우선순위의 값이 작을 수록 우선순위가 높음
  • 우선순위가 낮은 프로세스는 무한정 기다리는 기아현상(Starvation)이 생길 수 있음
  • 오래 기다린 프로세스의 우선 순위를 높이는(Aging기법)기법으로 기아현상 해결 가능

2_2) 선점 스케줄링_Round Robin

: 시분할 시스템을 위해 설계된 선점형 스케줄링 방식

  • 프로세스에 우선순위를 두지 않고 순서대로 시간단위(Time-Quantum)로 CPU를 할당

  • 시간 단위 안에 완료되지 않으면 큐의 맨 뒤에 배치되어 CPU를 독점하지 않음. 공평하게 사용 가능

    Time Quantum(Time Slice)이란? 실행 단위 시간, 프로세스에 타임 퀀텀만큼 CPU를 할당하고 그 시간이 지나면 바로 다음 프로세스에 타임 퀀텀만큼 CPU를 할당

  • 시간 단위가 너무 작으면 Context Switching이 잦아져서 오히려 성능이 떨어짐.

  • 시간 단위가 너무 크면 FCFS와 비슷해짐.

2_3) 선점 스케줄링_Multilevel-Queue(다단계 큐)

: 작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 방식

  • 각 큐마다 독자적인 스케줄링 알고리즘을 가질 수 있음.
  • 우선순위가 낮은 큐들이 실행 못하는 것을 방지하고자 큐들마다 다른 타임퀀텀을 설정
    • 우선순위가 낮은 큐 : 타임퀀텀
    • 우선순위가 높은 큐 : 작은 타임퀀텀
  • ✨ 장점 : 응답이 빠름
  • 🧐 단점 : 한 번 해당 큐에 들어가면 다른 큐로 이동이 불가능(유연적이지 못함)

2_3) 선점 스케줄링_Multilevel-Feedback-Queue(다단계 피드백 큐)

: 프로세스들이 큐 사이를 갈아탈 수 있는 다단계 큐 스케줄링

  • 목표 : 짧은 작업을 먼저 실행시켜서 반환시간을 최적화, 응답 시간 최적화

  • 규칙
    1. 작업은 무조건 가장 높은 우선순위에서 시작(Q2)
    2. 우선순위(A) > 우선순위(B)이면 A 실행. B는 실행되지 않음
    3. 우선순위(A)=우선순위(B)이면 A,B를 라운드 로빈으로 실행
    4. 작업이 지정된 단계에서 배정받은 시간을 소진하면 우선순위 감소(한단계 아래 큐로 이동)(Q2→Q1, Q1→Q0)
    5. 일정 주기마다 모든 작업을 가장 높은 우선순위 큐로 이동

3.스케줄링이 언제 발생할까

  • 매 타임퀀텀마다
  • 새로운 프로세스가 등장할 때마다
  • 현재 실행 중인 프로세스가 종료될 때마다
  • 현재 실행 중인 프로세스가 입출력 요청으로 Blocked상태에 놓일 때 마다
profile
꾸준함의 힘을 아는 개발자📍

0개의 댓글