[운영체제] CPU 스케줄링

모의면접으로 학습하는 CS 스터디
- 운영체제 3주차

기아상태

• 정의
  • 특정 프로세스의 우선순위가 낮아 원하는 자원을 계속 할당받지 못하는 상황
    

기아 상태 해결방법

1. 프로세스 우선순위를 수시로 변경
   
   
2. 오래 기다린 프로세스의 우선순위 높이기
   
   
3. 요청 순서대로 처리하는 요청 큐 사용

CPU 스케줄링

• 정의
  • 여러 프로세스 상황을 고려해 CPU와 시스템 자원을 어떻게 배정할지 결정하는 일
    
    
• 특징
  • 시분할 시스템의 경우 각 프로세스의 CPU 수행시간이 다름
  • CPU 스케줄링을 통해 프로세스에게 CPU 적당히 할당
  • 빠른 사용자 응답 시간 제공
  • CPU와 I/O 장치 효율을 높여줌
    

스케쥴러 종류

• 고수준 스케줄링
  • 장기 스케줄링, 작업 스케줄링, 승인 스케줄링
    
    
  • 기능
    • 시스템 내 전체 작업 수 조절
      
      
  • 특징
    • 어떤 작업을 시스템이 받아들일지, 거부할지 결정
    • 작업 요청이 오면 스케쥴러가 상황을 고려해 승인할지, 거부할지 결정
    • 이 결정에 따라 시스템의 전체 프로세스 수 결정

• 저수준 스케줄링

  • 단기 스케줄링
    
    
  • 기능
    • 어떤 프로세스에 CPU를 할당할지, 대기 상태로 보낼지 결정
      
      
  • 특징
    - 아주 짧은 시간에 일어남
    - 오늘날 CPU 스케줄러는 대부분 중간 수준 스케줄링 + 저수준 스케줄링
    - 특별한 명시가 없으면 CPU 스케쥴러는 저수준 스케쥴러를 의미함
    
    
    

• 중간 수준 스케줄링

  • 기능
    • 중지와 활성화로 전체 시스템의 활성화된 프로세스 수를 조절
      
      
  • 특징
    • 고수준 스케줄링과 저수준 스케줄링 사이에서 일어남
    • 시스템 과부하를 막기 위해 일부 프로세스를 중지 상태로 옮김
    • 저수준 스케줄링이 원만하게 이루어지도록 함

선점형 스케줄링 vs 비선점형 스케줄링

• 선점 vs 비선점

  • 선점 : 빼앗을 수 있음
  • 비선점 : 빼앗을 수 없음
    
    

• 선점형 스케줄링

  • 정의

    • 어떤 프로세스가 CPU를 할당받아 실행중이더라도 운영체제가 할당받은 CPU를 빼앗을 수 있는 스케줄링 방식

  • 특징

    • 프로세스가 실행상태여도 작업을 중단시키고 새 작업을 시작할 수 있음
    • 프로세스가 CPU를 독점할 수 없음
    • 문맥 교환으로 인해 낭비가 생김
    • 처리 시간을 예측하기 힘듬
      
      

• 비선점형 스케줄링

  • 정의

    • 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식

  • 특징

    • 순서대로 처리되는 공정성이 있어 응답 시간을 예상할 수 있음
    • 스케쥴러 작업량이 적고 문맥 교환에 의한 낭비도 적음
    • CPU 사용시간이 긴 프로세스가 있을 경우 다른 프로세스가 오랫동안 기다리게 됨
      -> 전체 시스템 효율이 떨어짐
      
      

• 종류

  선점형 스케줄링	비선점형 스케줄링
  대화형 시스템, 시분할 시스템	일괄 작업 시스템
  라운드 로빈 스케줄링	FCFS 스케줄링
  SRT 스케줄링	SJF 스케줄링
  다단계 큐 스케줄링	HRN 스케줄링
  다단계 피드백 큐 스케줄링

FCFS 스케줄링(선입선출 스케줄링)

• 정의

  • 준비 큐에 도착한 CPU를 할당하는 비선점형 방식
    
    

• 특징

  • 일괄작업시스템에 사용
  • 프로세스가 큐에 도착한 순서대로 실행
  • 한번 실행되면 그 프로세스가 끝나야 다음 프로세스 진행 가능
  • 큐가 하나라 모든 프로세스의 우선순위 동일
    
    

• 성능
  

  • 평균 대기 시간을 평가함
    • p1 대기시간 : 0초
    • p2 대기시간 : 30-3 = 27밀리초
    • p3 대기시간 : 48-6 = 42밀리초
    • 총 대기시간 : 23밀리초
      
      

• 평가

  • 단순하고 공평
  • 처리 시간이 긴 프로세스가 CPU를 차지할 경우 전체 시스템 효율성이 떨어짐
    • 콘보이 효과 또는 호위 효과
  • 현재 작업중인 프로세스가 입출력 작업 요청 시 CPU가 쉬게 되어 작업 효율 떨어짐

SJF 스케줄링 (최단 작업 우선 스케줄링)

• 정의

  • 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식
    
    

• 특징

  • 시간이 오래 걸리는 작업이 앞에 있으면 간단한 작업과 순서를 바꾸어 실행
    
    

• 성능
  

  • 평균 대기 시간을 평가함
    • p1 대기시간 : 0초
    • p3가 작업시간 짧아서 p3 먼저 시작
    • p3 대기시간 : 30-6 = 24밀리초
    • p2 대기시간 : 39-3 = 36밀리초
    • 총 대기시간 : 20밀리초
      
      

• 평가

  • 작은 작업을 먼저 실행하기 때문에 시스템 효율성이 좋아짐

  • 다음 같은 이유로 사용하기 힘듬

    1. 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려움
       • 현대 프로세스는 사용자와 빈번하게 상호작용해서 프로그램 종료 시간 예측이 어려움
         
         
       • 프로세스가 자신의 작업시간을 운영체제에게 알려주어 해결할 순 있으나 프로세스도 자신의 작업시간 파악이 힘듬.
         
         
       • 작업시간 속일 경우 시스템 효율성 나빠짐
         
         
    2. SJF 알고리즘은 공평성에 위배됨
       • p2작업이 계속 연기될 가능성이 있음. => 아사현상 또는 무한 봉쇄현상
         
         
       • 에이징으로 완화 가능
         • 에이징 : 프로세스가 양보할 수 있는 상한선 정하기
         • 양보 횟수를 정해 정한 값까지 양보하면 무조건 실행
         • 그러나 이 방법도 에이징 값 설정 기준이 애매함

SRTF 스케줄링 (최소 잔류 시간 우선 스케줄링)

• 정의
  • SJF +라운드 로빈
  • 라운드 로빈 스케줄링을 사용하나 CPU 할당받을 프로세스 선택시 남은 작업 시간이 가장 적은 프로세스 선택
    
    
• 특징
  • 라운드 로빈과 달리 SRT는 남은 작업 시간이 적은 프로세스에 CPU 먼저 할당
    
    
• 성능
  

• 평균 대기 시간을 평가함

  • p1 대기시간 : 0초
  • P1 작업시간 10 밀리초 진행 후 큐 맨뒤 이동
  • P3 작업 시간이 짧아 먼저 실행
  • P3 대기시간 : 10-6 = 4밀리초
  • P3 작업시간 : 9 밀리초 진행 후 작업 마침
  • P2 작업 시간이 짧아 먼저 실행
  • P2 대기시간 : 19-3 = 16밀리초
  • P2 작업시간 : 10 밀리초 진행 후 큐 맨뒤 이동
  • P2 작업 시간이 짧아 먼저 실행
  • P2 작업시간 : 8 밀리초 진행 후 작업 마침
  • P1 대기시간 : 37-10 = 27밀리초
  • P1 작업시간 : 10 밀리초 2번 진행 후 작업 마침
  • 총 대기시간 : 15.66 밀리초
    
    

• 평가

  • SJF 스케줄링에는 없는 작업 추가
    • 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산
    • 남은 시간이 더 적은 프로세스와 문맥교환
  • 운영체제가 프로세스 종료 시간을 예측하기 어려움
  • 아사현상 발생
    

우선순위 스케줄링

• 정의

  • 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당하는 방식
    
    

• 특징

  • 다양한 기준으로 우선순위를 정할 수 있음
    
    
  • 고정 우선순위 알고리즘 vs 변동 우선순위 알고리즘
    • 고정 우선순위 알고리즘 : 한번 우선순위를 부여받으면 종료될 때까지 고정
    • 변동 우선순위 알고리즘 : 일정 시간마다 우선순위를 새로 계산하여 반영
      
      
  • 비선점형 방식, 선점형 방식에 모두 적용할 수 있음
    • (비선점형 방식)SJF 스케줄링 : 작업 시간이 짧은 프로세스에 우선순위
    • (비선점형 방식)HRN 스케줄링 : 작업 시간이 짧거나 대기 시간이 긴 프로세스에 우선순위
    • (비선점형 방식)SRT 스케줄링 : 남은 시간이 짧은 프로세스에 우선순위
    
    

• 평가

  • 공평성 위배, 아사현상을 일으킴

    • 준비 큐에 있는 프로세스의 순서를 무시하기 때문

  • 오버헤드 발생하여 시스템 효율성 떨어짐

  • 그러나 우선순위는 프로세스 중요도 기준으로 결정

라운드 로빈 스케줄링

• 정의
  • 프로세스가 타임 슬라이스 동안 작업 하다가 완료하지 못하면 준비 큐 맨 뒤로 가서 자기 차례를 기다리는 선점형 알고리즘 방식
    
    
• 특징
  • FCFS와 유사하나 타임 슬라이스가 존재한다는 점에서 차이 있음
  • 자신에게 주어진 시간 동안에만 작업 가능하고 다 안끝나면 뒤쪽에 다시 삽입
  • 우선순위가 적용되지 않음
    
    
• 성능
  

• 평균 대기 시간을 평가함

  • p1 대기시간 : 0초
  • P1 작업시간 10 밀리초 진행 후 큐 맨뒤 이동
  • P2 대기시간 : 7밀리초
  • P2 작업시간 : 10 밀리초 진행 후 큐 맨뒤 이동
  • P3 대기시간 : 14밀리초
  • P3 작업시간 : 10 밀리초 진행 후 큐 맨뒤 이동
  • 계속 돌고 돔
  • 총 대기시간 : 22.33 밀리초
    
    

• 평가

  • 콘보이 효과가 줄어듬
  • FCFS보다 대기 시간이 적다고 단정할 수는 없음
  • 만약 FCFS랑 대기시간이 같다면 비효율적
    • 문맥 교환 시간이 추가되기 때문
      

멀티 레벨 큐 스케줄링

• 정의

  • 우선순위에 따라 준비 큐를 여러 개 사용하는 방식
    
    

• 특징

  • 프로세스는 자신의 우선순위에 맞는 큐에 삽입됨
  • 라운드 로빈 방식으로 큐가 운영됨
  • 고정형 우선순위를 사용
  • 상단 큐에 있는 모든 프로세스 작업이 끝나야 다음 우선순위 큐 작업 시작
  
  

• 평가

  • 우선순위에 따라 타임 슬라이스를 조절할 수 있음
  • 우선순위가 낮은 프로세스의 작업이 연기되는 문제 발생

멀티 레벨 피드백 큐 스케줄링

• 정의
  • 멀티 레벨 큐 스케줄링과 기본형태는 같음
  • CPU를 사용한 뒤 원래 큐가 아니라 우선순위가 하나 낮은 큐로 삽입되어 진행되는 방식
    
    
• 특징
  • CPU를 할당받아 실행될 때마다 우선순위를 낮추어 멀티 레벨 큐의 단점 보완
  • 우선순위가 낮아진다해서 커널 프로세스가 일반 프로세스 큐에 삽입되지는 않음
  • 우선순위가 낮아질수록 해당 큐의 타임 슬라이스는 커짐
  • 거의 FCFS 스케줄링 방식으로 진행
  • 변동 우선순위 알고리즘