(운영체제) 4 - CPU 스케줄링

## 목차 ##

• 1. 스케줄링의 개요
• 2. 스케줄링 시 고려사항
• 3. 다중 큐
• 4. 스케줄링 알고리즘
• 5. 인터럽트 처리

## 1. 스케줄링의 개요 ##

CPU 스케줄러는 여러 프로세스의 상황을 고려하여 CPU와 시스템 자원을 어떻게 분배할지 결정하는 일을 한다.

(1) 스케줄링의 단계

CPU 스케줄링은 규모에 따라 고수준, 중간수준, 저수준으로 구분된다.

• 고수준 스케줄링

  • 시스템 내의 전체 작업(일반적으로 프로세스) 수를 조절하는 것
  • 어떤 작업을 시스템이 받아들일지 거부할지를 결정한다. 이러한 이유로 고수준 스케줄링을 승인 스케줄링이라고도 한다.
  • 고수준 스케줄링에 따라 시스템에서 동시에 실행 가능한 프로세스 수(멀티프로그래밍 수준)가 결정된다.

• 저수준 스케줄링

  • 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 것
  • 준비 상태의 프로세스 중 하나를 골라 실행시키고, 실행 상태의 프로세스를 대기 상태로 보내며, 대기 상태의 프로세스를 준비 상태로 보내는 것 등
  • 프로세스의 상태를 제어하는 것이 저수준 스케줄링이다.

• 중간수준 스케줄링

  • 프로세스의 중지(보류상태), 활성화를 통해 프로세스 수를 조절하여 과부하를 막는 것
  • 과부하가 걸리면 일부 활성화 프로세스를 보류상태로 보내고 여유가 생기면 다시 활성화 시킨다.
  • 저수준 스케줄링이 원만하게 이루어지도록 하는 완충 역할을 한다.

(2) 스케줄링의 목적

• 공평성

  • 모든 프로세스가 공평하게 자원을 배정받아야 한다.
  • 특정 프로세스의 독점이 일어나면 안된다.

• 효율성

  • 시스템 자원이 유휴 시간 없이 최대한 사용되도록 해야한다.

• 안정성

  • 우선순위에 따라 중요한 프로세스가 먼저 실행되도록 해야한다.

• 확장성

  • 프로세스 수가 증가해도 시스템이 안정적으로 작동해야한다.
  • 시스템 자원이 늘어나는 경우 시스템에 반영되어야한다.

• 반응 시간 보장

  • 적절한 시간 안에 프로세스의 요구에 반응해야 한다.

• 무한 연기 방지

  • 특정 프로세스의 작업이 너무 오래 연기되어서는 안된다.

## 2. 스케줄링 시 고려사항 ##

(1) 선점형 스케줄링과 비선점형 스케줄링

• 선점형 스케줄링

  • 프로세스가 실행중이더라도 OS가 강제로 CPU를 빼앗을 수 있는 스케줄링 방식
  • 대표적으로 인터럽트 처리가 있다.
  • 문맥교환에 따른 부가적인 오버헤드가 생기는 것이 단점이다.
  • 하나의 프로세스가 CPU를 독점할 수 없기때문에 빠른 응답시간을 요구하는 시분할 시스템, 대화형 시스템에 적합하다.
  • 대부분의 저수준 스케줄러는 선점형 스케줄링 방식을 사용한다.

• 비선점형 스케줄링

  • 프로세스가 CPU를 점유중이면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식
  • 문맥교환에 따른 부가적인 오버헤드가 없다.
  • CPU 사용시간이 긴 프로세스 때문에 다른 프로세스들이 오랫동안 기다릴 수 있어 전체 시스템 처리율이 떨어질 수 있다.
  • 과거 배치 시스템에서 사용하던 방식

(2) 프로세스 우선순위

• 커널 프로세스는 사용자 프로세스보다 높다.

• 우선순위가 높으면 더 빨리 더 자주 실행된다.

• 커널 프로세스 사이에서도, 사용자 프로세스 사이에서도 우선순위가 존재한다.

  • ex) 실시간으로 영상 데이터를 처리하는 비디오 플레이어는 사람이 타이핑하는 것을 처리하는 워드 프로세서보다 우선순위가 높다.
  • UNIX 운영체제에서는 사용자 프로세스의 우선위가 조절이 가능하다.

(3) CPU 집중 프로세스와 입출력 집중 프로세스

• 프로세스 상태 중에 실제 작업이 일어나는 것은 실행 상태와 대기 상태이다.

  • 실행 상태에서는 CPU를 사용하여 작업을 한다. -> CPU 버스트
  • 대기 상태에서는 입출력을 요청하여 완료되기까지 기다린다. -> 입출력 버스트

• CPU 집중 프로세스

  • 수학 연산과 같이 CPU를 많이 사용하는 프로세스
  • CPU 버스트가 많은 프로세스

• 입출력 집중 프로세스

  • 저장장치에서 데이터를 복사하는 일과 같이 입출력을 많이 일으키는 프로세스
  • 입출력 버스트가 많은 프로세스

• 입출력 집중 프로세스가 CPU 집중 프로세스보다 우선순위가 높은것이 유리하다.

  • 입출력 버스트는 입출력 요구 후 대기상태로 접어들기 때문에 다른 프로세스가 CPU를 사용할 수 있기 때문이다.

(4) 전면 프로세스와 후면 프로세스

• 전면 프로세스

  • 화면의 맨 앞에 놓인 프로세스
  • 현재 입력과 출력을 사용하는 프로세스이며 사용자와 상호작용이 가능하다.

• 후면 프로세스

  • 사용자와 상호작용이 없는 프로세스이다.

• 전면 프로세스의 우선순위가 후면 프로세스의 우선순위보다 높다.

  • 전면 프로세스는 사용자의 요구에 즉각 반응해야 하기 때문이다.

## 3. 다중 큐 ##

(1) 준비상태 다중 큐

• 프로세스 우선순위는 각 프로세스의 제어 블록에 표시된다.

• 프로세스는 준비상태에 들어올 때 자신의 우선순위에 해당하는 큐의 마지막에 삽입된다.

• 준비 큐를 몇 개로 나눌지, 어떤 프로세스에 CPU를 할당할지는 스케줄링 알고리즘에 따라 다르다.

• 프로세스에 우선순위를 배정하는 방식

  • 고정 우선순위 방식
    • 운영체제가 프로세스에 우선순위를 부여하면 프로세스 종료 시 까지 바뀌지 않는다.
    • 시스템 변화에 대응하기 어려워 작업 효율이 떨어질 수 있다.
  • 변동 우선순위 방식
    • 구현하기 어렵지만 시스템 변화에 대응하여 작업 효율성을 높일 수 있다.

(2) 대기상태 다중 큐

• 대기 상태에 있는 프로세스들 중 같은 입출력을 요구한 프로세스끼리 같은 큐에 모아놓는다.

  • 입출력 완료 인터럽트가 발생했을 때 대기상태의 모든 큐를 검색하지 않아도 된다.

• 입출력 완료 인터럽트를 받은 프로세스는 준비 큐로 이동한다.

  • 준비 큐와는 다르게 대기상태 큐에서는 여러 프로세스가 한 번에 준비상태로 옮겨질 수 있다.
  • 동시에 끝나는 인터럽트를 처리하기 위해 인터럽트 벡터를 사용한다.

• 대기상태 큐에 있는 프로세스들은 보통 순서대로 처리되지만 나중에 들어온 프로세스가 먼저 처리되는 경우가 있다.

  • 작업 속도를 높이기 위해 입출력장치가 작업 순서를 바꾸는 일이 있기 때문이다.

아래 그림은 프로세스 제어 블록이 준비 큐와 대기 큐 사이를 이동하는 모습이다.

## 4. 스케줄링 알고리즘 ##

(1) 스케줄링 알고리즘 선택 기준

• CPU 사용률

• 처리량

  • 단위 시간당 작업을 마친 프로세스의 수

• 대기 시간

  • 프로세스 시작(준비 큐 도착) 후 실행까지의 시간

• 응답 시간

  • 프로세스 시작(준비 큐 도착)부터 첫 번째 출력을 얻기까지의 시간

• 반환 시간

  • 프로세스 시작(준비 큐 도착)부터 종료되어 자원을 모두 반환하는데 걸리는 시간 = (대기 시간 + 실행 시간)

• 스케줄링 알고리즘의 성능을 비교할 때 주로 '평균 대기 시간'을 본다.

• 작업 패턴과 유형에 따라 알고리즘의 성능이 달라지므로 평균 대기 시간은 절대적인 성능 지표가 아닌 참고해야할 수치일 뿐이다.

(2) FCFS 스케줄링

• FCFS(First Come First Served) 알고리즘은 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 스케줄링 방식이다.

  • 초기의 배치 시스템에서 사용되던 스케줄링 알고리즘이다.
  • 비선점형이므로 프로세스가 끝나야만 다음 프로세스가 실행된다.
  • 큐가 하나라 모든 프로세스의 우선순위가 동일하다.

• FCFS 스케줄링 성능
  

  • 평균 대기시간 = (0 + 27 + 42) / 3 = 23ms

• 평가

  • 단순하며 공평하다.
  • 앞에있는 프로세스의 대기시간이 길면 뒤에있는 프로세스가 기다리는 시간이 길어진다.(콘보이 효과)
  • 프로세스가 입출력을 요청하는 경우 CPU가 쉬는 시간이 길어져 작업 효율이 떨어진다.

(3) SJF 스케줄링

• SJF(Shortest Job First) 알고리즘은 준비 큐의 프로세스 중 작업 시간이 가장 짧은 작업부터 처리하는 비선점형 알고리즘이다.

  • FCFS 스케줄링의 콘보이 효과 완화

• SJF 스케줄링 성능
  

  • P1이 도착했을 때 준비 큐에는 P1 뿐이므로 바로 시작한다.
  • 평균 대기시간 = (0 + 24 + 36) / 3 = 20ms

• SJF 스케줄링 평가

  • FCFS의 콘보이 효과 완화로 평균 대기시간은 짧아지지만 여전히 문제점들이 존재한다.
  • 실제로 사용하기 어렵다.

• SJF 스케줄링 문제점

  • 프로세스의 실행시간이 얼마나 될지 정확히 예측하기 어렵다.
    • 사용자 입력 횟수 및 사용자의 응답 시간 등의 변수가 존재한다.
  • 공평하지 못하다.
    • 특정 프로세스보다 작은 작업들이 계속 준비 큐에 들어오면 특정 프로세스가 계속해서 연기될 수 있다.(아사, 기아)

(4) HRN 스케줄링

• HRN(Highest Response Ratio Next) 알고리즘은 SJF의 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘이다.

  • 스케줄링의 실행시간과 지금까지 대기한 시간을 우선순위 파라미터로 집어넣는다.
  • 우선순위 = (대기시간 + CPU 사용 시간) / CPU 사용 시간
  • 대기시간이 길수록 우선순위가 높아지기때문에 아사 현상을 완화한다.

• HRN 스케줄링 성능
  

  • P1이 도착했을 때 준비 큐에는 P1 뿐이므로 바로 시작한다.
  • P1 종료 시점에서 P2, P3의 우선순위는 P2 = (27 + 18) / 18 = 2.5, P3 = (24 + 9) / 9 = 3.67
  • 평균 대기시간 = (0 + 24 + 36) / 3 = 20ms

• HRN 스케줄링 평가

  • SJF처럼 실행시간이 짧은 프로세스부터 실행시킴으로써 콘보이 효과를 완화한다.
  • SJF에서 나타나는 기아 현상을 완화한다.
  • 여전히 공평성에 위배되어 많이 사용되지는 않는다.

(5) 라운드 로빈 스케줄링

• 라운드 로빈(Round Robin) 스케줄링은 프로세스가 할당받은 시간(타임 슬라이스)동안 작업하고 타임아웃되면 준비 큐의 가장 뒤에 다시 삽입되는 방식이다.

  • 선점형 알고리즘 중 가장 단순하고 대표적인 알고리즘
  • FCFS와 비슷하지만 차이점은 타임 슬라이스만큼만 CPU를 사용하고 물러난다는 점이다.
  • 우선순위가 적용되지 않은 알고리즘이다.

• 라운드 로빈 스케줄링 성능
  

  • 타임 슬라이스가 10ms인 경우의 라운드 로빈 스케줄링이다.
  • FCFS보다 미세하게 앞서지만 실제로는 문맥교환에 따르는 비용이 추가되어 더 비효율적이 된다.
  • 프로세스 도착 순서가 바뀌면 평균 대기시간이 달라진다.

• 타임 슬라이스가 큰 경우

  • FCFS 스케줄링에 가까워진다.

• 타임 슬라이스가 작은 경우

  • 너무 작으면 문맥교환에 따른 오버헤드가 커진다.

• 라운드 로빈 스케줄링 평가

  • 라운드 로빈 스케줄링이 효과적으로 동작하려면 타임 슬라이스를 되도록 작게 설정하되 문맥 교환 시간을 고려하여 적절히 설정해야한다.

(6) SRT 우선 스케줄링

• SRT(Shortest Remaining Time) 스케줄링은 SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식이다.

  • SJF 스케줄링의 선점형 버전
  • 라운드 로빈과 같이 타임 슬라이스의 시간만 배분받지만 실행할 잡을 선택할 때 남은 시간이 가장 짧은 프로세스를 선택한다.

• SRT 스케줄링 성능
  

  • 타임 슬라이스가 10ms인 경우의 SRT 스케줄링이다.
  • P1이 10ms 실행 된 후 P1, P2, P3 중 P3가 선택되어 9ms만에 종료되고 P2가 연달아 실행된다. 이후 P1이 두 번의 실행으로 끝난다.
  • 평균 대기 시간 = (0 + 4 + 16 + 27) / 3 = 15.66ms

• SRT 스케줄링 평가

  • 남은 시간을 주기적으로 계산하는 추가적인 오버헤드가 존재한다.
  • OS가 프로세스의 실행 시간을 예측하기 어렵고 실행시간이 긴 프로세스의 아사 현상이라는 문제점이 존재하여 잘 사용하지 않는다.

(7) 우선순위 스케줄링

• 선점형, 비선점형 방식 모두 구현 가능하다.

• 비선점형 알고리즘의 우선순위 구현

  • 작업 시간이 짧은 프로세스의 우선순위가 높게 -> SJF 스케줄링
  • 작업 시간이 짧고 대기한 시간이 긴 프로세스의 우선순위가 높게 -> HRN 스케줄링

• 선점형 알고리즘의 우선순위 구현

  • 남은 작업시간이 짧은 프로세스의 우선순위가 높게 -> SRT 스케줄링
  • 모든 프로세스의 우선순위가 동일하게 -> 라운드 로빈 스케줄링

• 고정 우선순위 알고리즘

  • 한 번 부여받은 우선순위는 프로세스 종료까지 변하지 않는다.
  • 구현이 단순하지만 시스템 상황을 반영하지 못해 효율성이 떨어진다.

• 변동 우선순위 알고리즘

  • 일정 시간마다 우선순위가 변한다.
  • 구현이 복잡하지만 시스템 상황을 반영하여 효율적인 운영이 가능하다.

• 우선순위 스케줄링 평가

  • 준비 큐에서의 프로세스 순서를 무시하고 우선순위 순으로 실행하므로 공평성을 위배하고 아사현상이 발생할 가능성이 있다.
  • 변동 우선순위의 경우 우선순위를 바꾸기 위한 오버헤드가 발생한다.

(8) 다단계 큐 스케줄링

• 우선순위 별로 준비큐를 사용하는 스케줄링 방식
  • 프로세스는 준비상태로 들어올 때 OS가 부여한 우선순위에 해당하는 큐에 삽입된다.

• 우선순위에 따라 타임슬라이스를 조정하여 작업 효율을 높일 수 있다.

  • 전면 프로세스는 반응속도를 높이기 위해 타임 슬라이스를 작게 한다.
  • 후면 프로세스는 사용자와 상호작용이 없으므로 FCFS로 처리할 수 있다.

• 높은 우선순위 큐의 모든 프로세스가 끝나야 다음 우선순위 큐의 프로세스가 실행된다.

  • 우선순위가 낮은 프로세스가 무기한 연기되는 문제를 해결하기 위해 제안된 것이 다단계 피드백 큐 스케줄링이다.

(9) 다단계 피드백 큐 스케줄링

• 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식
  • CPU 사용을 끝내고 타임아웃 된 프로세스의 우선순위가 한 단계 낮아진다.
  • 타임아웃 된 프로세스는 우선순위가 한 단계 낮은 큐의 끝으로 들어간다.
  • 우선순위가 낮은 프로세스가 연기되는 문제를 완화한다.

• 우선순위가 낮을수록 큐의 타임 슬라이스가 커진다.

  • 우선순위가 낮은 프로세스가 어렵게 얻은 CPU를 좀 더 오랫동안 사용하도록 하기 위해서다.

• 오늘날의 운영체제가 일반적으로 사용하는 스케줄링 방식이다.

## 5. 인터럽트 처리 ##

(1) 인터럽트의 개념

• 이벤트가 발생하면 프로세스에 알려주어 처리하도록 하는 방식
  • 프로세스가 주기적으로 확인하는 폴링(polling) 방식과 대비되는 개념

(2) 동기 인터럽트/비동기 인터럽트

• 동기 인터럽트 : 명령어를 실행한 결과로 발생하는 인터럽트

  • 트랩(trap)이라고도 한다.
  • ex) 0으로 나누기, UNIX의 Ctrl+C, 다른 사용자의 메모리 침범, 오버플로, 언더플로 등

• 비동기 인터럽트 : 명령어와 관련없는 인터럽트

  • 키보드 타이핑, 마우스 클릭, 하드디스크 읽기 오류, 메모리 불량 등

(3) 인터럽트 처리 과정

• 인터럽트가 발생하면 실행시킬 함수가 정의되어 있다.(인터럽트 서비스 루틴 - ISR)

  a. 인터럽트가 발생하면 프로세스가 일시정지되고 현재 정보를 임시저장한다.

  b. 인터럽트 컨트롤러가 실행되고 인터럽트 벡터에 정의된 인터럽트의 우선순위에 따라 처리 순서를 결정한다.
  (인터럽트 벡터는 인터럽트 번호와 ISR을 1:1로 연결한 자료구조이다.)

  c. 처리할 인터럽트 번호에 등록된 인터럽트 서비스 루틴이 실행된다.

  d. 인터럽트 처리가 끝나면 일시정지되었던 프로세스가 다시 실행되거나 오류 인터럽트의 경우에는 종료된다.

(4) 인터럽트와 이중 모드

• 커널 모드와 사용자 모드

  • 커널 모드 : 커널 프로세스가 실행되는 상태
  • 사용자 모드 : 사용자 프로세스가 실행되는 상태

• 사용자가 커널 함수를 사용하기 위해 시스템 콜을 하면?

  • 사용자 모드에서 커널 모드로 전환
  • 커널 모드에서 시스템 콜을 처리
  • 사용자 모드로 전환

• OS가 사용자 모드와 커널 모드를 전환하며 일처리 하는것을 이중 모드라고 한다.

  • 이중 모드는 시스템 자원을 보호하기 위해 사용하는 기법이다.

• 시스템 호출에 의한 자발적 커널모드 진입과 인터럽트에 의한 비자발적 커널모드 진입이 존재한다.
  • 프로세스에 의한 인터럽트 발생은 잘못된 명령어에 의한 동기적 인터럽트이므로 프로세스가 강제 종료된다.
  • 자발적으로 커널모드에 진입하는 수단은 시스템 호출이다.