5. CPU 스케줄링

CPU 스케줄링(CPU Scheduling)

CPU 스케줄러

• 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 한다.
  
  
• CPU 스케줄링
  
  • 어떤 프로세스에 CPU를 배정할지 결정하고, 이 작업은 컴퓨터 시스템의 효율에 직결되는 중요한 일
    
    
  • 목적 : 모든 프로세스가 공평하게 작업을 할 수 있도록 하는 것
    
    • 공평성 : 모든 프로세스가 자원을 공평하게 배정받아야 되며, 특정 프로세스가 배제되면 안 된다.
      
      
    • 효율성 : 시스템 자원을 놀리는 시간없이 스케줄링해야 된다.
      
      
    • 안정성 : 우선순위를 사용해 중요한 프로세스가 먼저 처리되도록 해야 된다.
      
      
    • 반응 시간 보장 : 응답이 없는 경우엔 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 된다.
      
      
    • 무한 연기 방지 : 특정 프로세스의 작업이 무한히 연기되어선 안 된다.
      
      

스케줄링 단계

• 고수준 스케줄링(high level scheduling, long-term scheduling, job scheduling, admission scheduling)
  • 시스템 부하를 고려하여 어떤 작업을 승인할지 결정하므로 시스템 내에서 동작 시에 실행 가능한 프로세스의 총 개수가 정해진다. -> 멀티 프로그래밍 정도(degree of multiprogramming) 
    
    
  • 시스템 내의 전체 작업(운영체제에서 다루는 일의 가장 큰 단위, 1개 또는 여러 개의 프로세스로 이루어짐) 수를 조절하는 것
    
    
  • 작업 요청 시 스케줄러가 시스템 상황을 고려해서 작업을 승인할지, 거부할지 결정하므로 승인 스케줄링이라고도 한다.
    
    
  • 메인프레임과 같은 큰 시스템에서 규모가 큰 일괄 작업을 처리할 때 사용
    
    
• 중간 수준 스케줄링(middle level scheduling) 
  • 고수준 스케줄링과 저수준 스케줄링 사이에 일어나는 스케줄링
    
    
  • 중지(suspend)와 활성화(active)로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막는다.
    일부 프로세스를 중지 상태로 옮김으로써, 나머지 프로세스가 원만하게 작동되도록 지원(보류 상태) -> 저수준 스케줄링이 원만하게 이루어지도록 완충하는 역할
    
    
• 저수준 스케줄링(low level scheduling, short-term scheduling)
  • 가장 작은 단위의 스케줄링
    
    
  • 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정
    
    
  • 아주 짧은 시간에 일어나기 때문에 단기 스케줄링이라고도 한다.
    
    
  • 3의 프로세스 상태에 관한 내용은 대부분 저수준 스케줄링
    
    

이미지 첨부 예정(스케줄링 단계)

스케줄링 시 고려사항

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

• 선점형 스케줄링
  • 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 방식
    
    
  • 운영체제가 필요하다고 판단하면 실행 상태에 있는 프로세스의 작업을 중단시키고 새로운 작업을 시작할 수 있다.
    ex) CPU가 인터럽트를 받으면 현재 실행 중인 작업을 중단하고 커널을 깨워서 인터럽트를 처리시키며, 인터럽트 처리가 완료되면 원래의 작업으로 돌아간다.
    
    
  • 대부분 저수준 스케줄러가 해당 스케줄링 방식을 사용
    
    
  • 장점
    • 하나의 프로세스가 CPU를 독점할 수 없기 때문에 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합
      
      
  • 단점
    • 잦은 컨텍스트 스위칭으로 오버헤드가 발생
      
      
• 비선점 스케줄링 
  • 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 방식
    
    
  • 어떤 프로세스가 실행 상태에 들어가 CPU를 사용하면 해당 프로세스가 종료되거나 자발적으로 대기 상태에 들어가기 전까지 계속 실행
    
    
  • 장점
    • 스케줄러의 작업량이 적고 컨텍스트 스위칭에 의한 낭비가 적다.
      
      
  • 단점
    • 프로세스 배치에 따라 효율성 차이가 많이 난다.
      
      
• 비교

구분	선점형 스케줄링	비선점형 스케줄링
작업 방식	실행 상테에 있는 작업을 중단시키고 새로운 작업을 실행할 수 있다.	실행 상태에 있는 작업이 완료될 때까지 다른 작업이 불가능하다.
장점	프로세스가 CPU를 독점할 수 없어, 대화형이나 시분할 시스템에 적합	CPU 스케줄러의 작업량이 적고, 컨텍스트 스위칭의 오버헤드가 적다.
단점	컨텍스트 스위칭의 오버헤드가 많다.	기다리는 프로세스가 많아, 처리율이 떨어진다.
사용	시분할 방식	일괄 작업 방식의 스케줄러
중요도	높다.	낮다.ㅎ

CPU 집중 프로세스와 입출력 집중 프로세스

• 프로세스가 대기 상태에 있다가 CPU를 할당받아 실행하는 작업 CPU 버스트, 입출력 작업은 입출력 버스트
  
  
• CPU 집중 프로세스
  • 수학 연산과 같이 CPU를 많이 사용하는 프로세스
    
    
  • CPU 버스트가 많은 프로세스
    
    
• 입출력 집중 프로세스
  • 저장장치에서 데이터를 복사하는 일과 같이 입출력을 많이 사용하는 프로세스
    
    
  • 입출력 버스트가 많은 프로세스
    
    

전면 프로세스와 후면 프로세스

• 전면 프로세스
  • GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스를 말한다.
    
    
  • 현재 입력과 출력을 사용하는 프로세스
    
    
  • 사용자와 상호작용이 가능하여 상호작용 프로세스라고도 한다.
    
    
• 후면 프로세스 
  • 사용자와 상호작용이 없는 프로세스
    
    
  • 압축 프로그램처럼 사용자의 입력 없이 작동하기 때문에 일괄 작업 프로세스라고도 한다.
    
    

우선순위

우선순위 ⬆️	우선순위 ⬇️
커널 프로세스	일반 프로세스
전면 프로세스	후면 프로세스
대화형 프로세스	일괄 처리 프로세스
입출력 집중 프로세스	CPU 집중 프로세스

 

다중 큐

• 프로세스를 효율적으로 관리하기 위해 큐를 여러 개 두어 관리하는 것
  
  
• 준비 상태의 다중 큐
  • 우선순위에 따라 다중 큐를 운영
    
    
  • CPU 스케줄러는 우선순위가 가장 높은 큐(0번 큐)의 맨 앞에 있는 프로세스에 CPU를 가장 먼저 할당한다.
    
    
  • 스케줄링 알고리즘
    • 준비큐를 몇 개로, 여러 개의 준비 큐에 있는 프로세스 중 어떤 프로세스에 CPU를 할당할지 결정하는 일
      
      
    • 고정 우선순위 방식
      • 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 않는 방식
        
        
      • 구현 쉬움
        
        
      • 시스템의 변화에 대응하기 어려워, 작업 효율⬇️
        
        
    • 변동 우선순위 방식
      • 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식
        
        
      • 구현 어려움
        
        
      • 시스템 효율성 높임
        
        
• 대기 상태의 다중 큐 
  • 같은 입출력을 요구한 프로세스를 모아 다중 큐를 운영
    
    
  • 준비 큐는 한 번에 하나의 프로세스를 꺼내어 CPU를 할당하는 반면, 대기 큐는 여러 개의 프로세스 제어 블록을 동시에 꺼내어 준비상태로 옮긴다.
    
    
  • 시스템에는 많은 입출력장치가 있기 때문에 입출력이 동시에 끝날 경우 여러 개의 인터럽트가 한꺼번에 처리된다.
    
    

스케줄링 알고리즘

구분	종류
비선점형 알고리즘	FCFS 스케줄링, SJF 스케줄링, HRN 스케줄링
선점형 알고리즘	라운드 로빈 스케줄링, SRT 스케줄링, 다단계 큐 스케줄링, 다단계 피드백 큐 스케줄링
둘 다 가능	우선순위 스케줄링

선택 기준

• CPU 사용률
  • 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
    
    
  • 이상적 수치는 100%지만 실제로는 여러가지 이유로 90%에도 못 미침
    
    
• 처리량 : 단위 시간당 작업을 마친 프로세스의 수로, 이 수치가 클수록 좋은 알고리즘
  
  
• 대기 시간 : 대기 시간은 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간으로, 이 시간이 짧을수록 좋은 알고리즘
  
  
• 응답 시간 : 프로세스 시작 후 첫 번째 출력 또는 반응이 나올 때까지 걸리는 시간으로, 이 시간이 짧을수록 좋은 알고리즘
  
  
• 반환 시간 : 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는데까지 걸리는 시간으로, 대기 시간 + 실행 시간
  
  

FCFS  스케줄링(First Come First Served)

• 동작 방식
  • 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식, 선입선출 스케줄링
    
    
  • 큐가 하나라 모든 프로세스는 우선순위가 동일하다.
    
    
• 평가
  • 단순하고 공평
    
    
  • 콘보이 효과(convoy effect, 처리시간이 긴 프로세스가 CPU를 차지하여 다른 프로세스가 하염없이 기다려서 효율이 떨어지는 문제)가 있을 수 있다.
    
    

SJF 스케줄링(Shortest Job First)

• 동작 방식
  • 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식, 최단 작업 우선 스케줄링
    
    
• 평가 
  • 작은 작업을 먼저 실행하기 때문에 시스템 효율⬆️
    
    
  • 단점
    • 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.
      
      
    • 공평하지 못하다.
      
      
  • 대처 방안 
    • 프로세스가 자신의 작업 시간을 알려준다 -> 프로세스가 자신의 작업 시간을 알기 어렵 & 악의적인 프로세스일 수도 있다.
      
      
    • 에어징(프로세스가 양보할 수 있는 상한선을 정하는 방식) -> 에어징 값 기준을 정하기 어렵
      
      

HRN 스케줄링(Highest Response Ratio Next)

• 동작 방식
  • SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘, 최고 응답률 우선 스케줄링
    
    
  • 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링 하는 방식
    
    
• 우선순위 결정 방법
  우선순위 = (대기 시간 + CPU 사용 시간) / CPU 사용시간
  
  
• 평가
  • 대기 시간이 긴 프로세스의 우선순위를 높임으로써 CPU를 할당받을 확률을 높인다. -> 여전히 공평성 위배
    
    

라운드 로빈 스케줄링(Round Robin)

• 동작 방식
  • 한 프로세스가 할당받은 시간(타임슬라이스)동안 작업 하다가 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식
    
    
  • 선점형 알고리즘 중 가장 단순하고 대표적인 방식
    
    
  • 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행
    
    
  • 우선순위 X
    
    
• 평가 
  • 비선점형 방식에 비해 컨텍스트 스위칭이 일어나므로 시스템 전체의 성능에도 영향을 미친다.
    
    
  • 타임 슬라이스가 큰 경우
    • 하나의 작업이 끝난 후 다음 작업이 실행되는 거처럼 보인다.
      
      
  • 타임 슬라이스가 작은 경우
    • 시스템 전반적인 성능 ⬇️
      
      
    • 잦은 컨텍스트 스위칭
      
      

SRT 우선 스케줄링(Shortest Remaining Time)

• 동작 방식
  • SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식으로, 최소 잔류 시간 우선 스케줄링
    
    
  • 선점형 방식
    
    
•  평가
  • 좋은 알고리즘 X
    
    
  • 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산 & 탐은 시간이 더 적은 프로세스와 컨텍스트 스위칭을 해야 하므로 SJF 스케줄링에는 없는 작업이 추가된 것이다.
    
    
  • 운영체제가 프로세스의 종료 시간 예측 어렵 & 아사 현상이 일어난다.
    
    

우선순위 스케줄링(Priority)

• 동작 방식
  • 프로세스 중요도에 따른 우선순위를 반영한 스케줄링 알고리즘
    
    
• 적용
  • FCFS : 작업 시간이 짧은 프로세스에 높은 우선순위 부여 
    
    
  • SJF : 작업 시간이 짧은 프로세스에 높은 우선순위 부여
    
    
  • HRN : 작업 시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순위 부여
    
    
  • SRT : 남은 시간이 짧은 프로세스에 높은 우선순위 부여
    
    
• 우선순위 알고리즘
  • 고정 우선순위 알고리즘 : 한 번 우선순위를 부여받으면 종료될 때까지 우선순위 고정 -> 단순 구현 가능, But 계속 변하는 시스템 상황을 반영하지 못해 효율 ⬇️
    
    
  • 변동 우선순위 알고리즘 : 일정 시간마다 우선순위 변경 -> 시스템 복잡(구현 복잡), 효율⬆️
    
    
• 평가
  • 준비 큐에 있는 프로세스 순서를 무시하고 프로세스 우선순위를 매번 바꿔야 하기 때문에 오버헤드 발생 -> 시스템 효율 ⬇️
    
    

다단계 큐 스케줄링(multilevel queue)

• 동작 방식
  • 우선순위에 따라 준비 큐를 여러 개 사용하는 방식
    
    
  • 고정 우선순위
    
    
  • 우선순위에 따라 다양한 스케줄링이 가능한 선점형 방식
    
    
• 평가 
  • 우선순위가 낮은 프로세스는 무한이 연기되는 문제
    
    

다단계 피드백 큐 스케줄링(multilevel feedback queue)

• 동작 방식
  • 우선순위를 가진 여러 개의 큐 사용 & CPU를 사용하고 난 프로세스의 우선순위는 낮아진다. -> CPU를 사용하고 난 프로세스는 원래 큐로 돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.
    
    
  • 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링을 보완한 방식
    
    
• 평가
  • 현재 제일 일반적으로 사용하는 방식
    
    
  • 변동 우선순위 알고리즘의 전형적 예
    
    

인터럽트 처리

인터럽트

• 동기적 인터럽트 : 프로세스가 실행중인 명령어로 인해 발생
  • 프로그램상 문제 때문에 발생하는 인터럽트(ex) 다른 사용자의 메모리 영역에 접근하는 경우, 오버플로나 언더플로에 의해 발생하는 경우)
    
    
• 비동기적 인터럽트 : 실행 중인 명령어와 무관하게 발생
  • 하드디스크 읽기 오류, 메모리 불량과 같은 하드웨어적 오류
    
    
• 사용자 프로세스가 자발적으로 커널모드에 진입할 수 있는 유일한 수단은 시스템 호출(인터럽트에 의한 커널모드 진입은 비자발적(오류로 인한 것이니))