[OS] CPU 스케줄링

Suyeon·2022년 2월 17일
1

Operating System

목록 보기
6/10

💡 CPU 스케줄러는 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 한다.

1. 스케줄링의 단계

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

1.1 고수준 스케일링

  • 전체 시스템의 부하를 고려하여 프로세스를 활성화할지 말지를 결정하여 전체 프로세스의 수를 조절한다.
  • 시스템의 전체 프로세스수가 결정되는데 이를 멀티프로그래밍 정도(Degree of multiprogramming)이라고 한다.
  • 작업 요청이 오면 승인할지 거부할지를 결정하므로 승인 스케줄링(Admission scheduling)이라고도 한다.

1.2 저수준 스케일링

  • 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 결정한다.
  • 프로세스 상태에 관한 내용은 대부분 저수준 스케일링에 해당한다.
  • 아주 짧은 시간에 일어나기 때문에 단기 스케줄링(short-term scheduling)이라고도 한다.

1.3 중간수준 스케일링

  • 시스템에 과부화가 걸려서 전체 프로세스수를 조절해야한다면 이미 활성화된 프로세스중 일부를 보류 상태로 보낸다. 보류된 프로세스는 처리 능력에 여유가 생기면 다시 활성화된다.

2. 선점형 스케줄링/비선점형 스케줄링

2.1 선점형 스케줄링

  • 어떤 프로세스가 CPU를 할당받아 실행중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있다.
  • 실행 상태에 있는 작업을 중단시키고 새로운 작업을 실행할 수 있다.
  • 빠른 응답시간을 요구하는 대화형 시스템, 시분할 시스템에 적합하다.
    • 하나의 프로세스가 CPU를 독점할 수 없기때문이다.
    • 대부분의 저수준 스케줄러는 선점형 스케줄링 방식을 사용한다.
  • 단점: 문맥교환의 오버헤드가 많다.
  • e.g. 인터럽트 처리

2.2 비선점형 스케줄링

  • 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을수 없다.
  • 실행 상태에 있는 작업이 완료될 때까지 다른작업이 불가하다.
  • CPU 스케줄러의 작업량이 적고 문맥 교환의 오버헤드가 적다.
  • 단점: 기다리는 프로세스가 많아 시스템의 효율이 떨어진다.
  • 일괄 작업 시스템에서 사용하던 방식이다.

💡 비선점형과 선점형 프로세스가 혼재하는 경우, 비선점형 프로세스의 중요도를 매우 낮게 설정하여 선점형 프로세스에 영향을 덜 미치도록한다.

3. 프로세스 우선순위

💡 우선순위가 높다는 것은 더 빨리 자주 실행된다는 의미이다.

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

3.1 용어

  • CPU 집중 프로세스: 수학 연산과 같이 CPU를 많이 사용하는 프로세스
  • 입출력 집중 프로세스: 저장장치에서 데이터를 복사하는 일과 같이 입출력을 많이 사용하는 프로세스
  • 전면 프로세스: GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스
    • 현재 입력과 출력을 사용하는 프로세스
    • 상호작용 프로세스라고도 한다.
  • 후면 프로세스: 사용자와 상호작용이 없는 프로세스
    • 일괄 작업 프로세스라고도 한다.
    • e.g. 압축프로그램
  • CPU 버스트(CPU burst): CPU를 할당받아 실행하는 작업
  • 입출력 버스트(I/O burst): CPU를 할당받아 실행하는 입출력 작업

3.2 특징

  1. 일반 프로세스의 우선순위는 사용자가 조절할 수 있다.
    1. 관리자(Administrator)만 우선순위를 높일 수 있고 일반 계정은 우선순위를 낮추는 것만 가능하다.
  2. 입출력 집중 프로세스의 우선순위를 CPU 집중 프로세스보다 높이면 시스템의 효율이 높향상된다.
    1. 입출력 집중 프로세스가 실행 상태로 가면 입출력 요구에 의해 대기상태로 옮겨지기 때문에 다른 프로세스가 CPU를 사용할 수 있다.
    2. CPU 집중 프로세스가 먼저 실행 상태로 들어가면 자신의 타임 슬라이스를 다 사용할 때까지 다른 프로세스가 실행되지 못한다.
    3. 사이클 훔치기(Cycle stealing): 입출력 집중 프로세스가 CPU 집중 프로세스보다 실행 상태에 먼저 들어가는 경우

3.3 예시

워드프로세서와 비디오 플레이어중에서는 비디오 플레이어의 우선순위가 높다.

  1. 워드프로세서의 경우, 사람이 타이핑하는 속도가 CPU의 연산보다 느려서 천천히 실행되어도 문자 입력 처리가 가능하다.
  2. 비디오 플레이어는 실시간으로 데이터를 읽어와 영상과 소리를 출력해야하기 때문에 자주 실행되지 않으면 화면이 끊긴다.

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

  1. 워드 프로세서는 사용자로부터 키보드로 입력을 받아야하기 때문에 전면 프로세스로 실행된다.
  2. 압축 프로그램은 압축이 끝날 때까지 사용자의 입력이 필요없기 때문에 후면 프로세스로 실행 된다.

4. 다중큐

4.1 준비 상태의 다중큐

💡 프로세스의 중요도는 프로제스 제어 블록에 표시된다. CPU 스케줄러는 모든 프로세스 제어블록을 뒤져서 가장 높은 우선순위의 프로세스에 CPU를 할당한다. 그러나 매번 프로세스의 제어 블록을 검색하는 것은 번거로운 일이다.

  • 준비상태의 프로세스를 우선순위에 따라서 여러개의 큐로 관리한다.
  • 준비상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입된다.
  • 한번에 하나의 프로세스를 꺼내어 CPU를 할당한다.

4.1.1 프로세스의 우선순위를 배정하는 방식

  1. 고정 우선순위 방식: 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날때까지 바뀌지 않는 방식
    1. 구현하기 쉽지만 작업 효율이 떨어진다.
  2. 변동 우선순위 방식: 프로세스 생성시 부여받은 우선순위가 작업 중간에 변하는 방식
    1. 구현하기 어렵지만 작업 효율이 올라간다.
    2. 반전 우선순위: 프로세스의 낮은 우선순위를 높은 우선순위로 바꾸는 것으로, 시스템의 효율성을 향상시킬 수 있다.
    3. 우선순위가 낮은 P1이 중요한 자원을 사용하고 있어 이 자원을 사용하는 다른 프로세스는 작업을 기다려야한다. 이 때 프로세스 P1의 우선순위를 높이면 다른 프로세스보다 CPU를 더 자주 할당받게 되어 작업을 빨리 끝낼수 있으며, 이 자원을 기다리던 다른 프로세스의 작업도 원만하게 끝낼 수 있다.

4.2 대기 상태의 다중큐

💡 시스템 내에는 다양한 종류의 입출력장치가 있기 때문에 대기 상태의 프로세스를 한곳에 모아놓으면 관리하기가 불편하다. 예를 들어 하드디스크에서 작업이 끝났다고 인터럽트가 발생한 경우, 해당 프로세스를 찾기 위해 대기 상태의 모든 프로세스를 검색하는 것은 번거로운 일이다.

  • 대기 상태는 입출력이 완료되기를 기다리는 프로세스가 모여있는 곳이다.
  • 같은 장치의 입출력을 기다리는 프로세스의 프로세스 제어 블록은 동일한 입출력 큐에서 관리한다.
    • 하드디스크의 입출력을 기다리는 프로세스 제어 블록은 모두 HDD 큐에 삽입된다.
  • 여러개의 프로세스 제어 블록을 동시에 꺼내어 준비 상태로 옮긴다. (인터럽트 벡터)

5. 스케줄링 알고리즘

💡 스케줄링 알고리즘은 선점형 알고리즘과 비선점형 알고리즘으로 나뉜다. 오늘날에는 대부분 선점형 알고리즘을 사용한다. 준비큐를 몇개로 나눌지, 어떤 프로세스에 CPU를 할당할지등은 스케줄링 알고리즘에 따라서 달라진다.

5.1 용어

  • 처리량: 단위 시간당 작업을 마친 프로세스의 수
  • 반환 시간: 대기 시간 + 실행 시간
  • 평균 대기시간: 프로세스 수/모든 프로세스의 대기 시간의 합

5.2 선점형 알고리즘

  1. 시분할 시스템을 고려하여 만들어진 알고리즘
  2. 특정 프로세스가 CPU를 할당받아 실행중이더라도 운영체제가 강제로 CPU를 빼앗을 수 있다.
  3. 프로세스가 CPU를 일정 시간동안 사용한 후 다른 프로세스에게 주어야하기 때문에 콘베이 효과가 줄어든다.

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

  • 한 프로세스가 할당받은 타임 슬라이스동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식
  • 선점형 알고리즘 중 가장 대표적이고 단순한 방식으로, 프로세스들이 작업을 완료할 때 까지 계속 순환하면서 실행된다.
  • 라운드 로빈 알고리즘이 효과적으로 작동하려면, 문맥 교환에 따른 추가시간을 고려하여 타임 슬라이스를 적절하게 설정해야한다. 타임 슬라이스의 크기는 프로세스의 반응 시간 및 시스템 전체의 성능에 영향을 미친다.
    • 타임 슬라이스가 큰 경우
      • 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것 처럼 보인다.
      • 실행하는 프로그램이 끊겨보이고 반응 속도가 매우 느리다.
    • 타임 슬라이스가 작은 경우
      • 문맥교환이 너무 자주 일어나 문맥교환에 걸리는 시간이 실제 작업 시간보다 커지며, 문맥 교환에 ㅈ시간을 낭비하여 실제 작업을 못하는 문제가 발생한다.
      • 시스템의 성능이 떨어진다.
    • 유닉스 운영체제에서는 타임 슬라이스가 10~200 밀리초 사이로 조정한다.

5.2.2 SRT 스케줄링(Shortest Remaining Time)

  • SJF스케줄링과 라운드로빈 스케줄링을 혼합한 방식 (SJF 스케줄링의 선점형 버전)
  • 최소 잔류 시간 우선 스케줄링
  • 기본적으로 라운드로빈 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아있는 작업시간이 가장 적은 프로세스를 선택한다.

단점

  • 현재 실행중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥교환을 해야하므로 오버헤드가 발생한다.
  • 운영체제가 프로세스의 종료시간을 예측하기 어렵다.
  • 아사 현상

5.2.3 우선순위 스케줄링

  • 우선순위를 반영한 스케줄링 알고리즘
    • 프로세스는 중요도에 따라서 우선순위를 갖는다.
  • 우선순위는 비선점형 방식과 선점형 방식에 모두 적용할 수 있다.
    • SJF 스케줄링(비선점형): 작업시간이 짧은 프로세스에 높은 우선순위 부여
    • HRN 스케줄링(비선점형): 작업시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순위 부여
    • SRT 스케줄링(선점형): 남은시간이 짧은 프로세스에 높은 우선순위 부여

단점

  • 공평성 위배, 아사 현상 유발
    • 우선순위가 높은 프로세스에 먼저 CPU를 할당
  • 프로세스의 우선순위를 매번 바꿔야하기때문에 오버헤드가 발생하여 시스템의 효율성이 떨어진다.

5.2.4 다단계 큐 스케줄링

  • 우선순위에 따라 준비큐를 여러개 사용하는 방식
  • 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입된다.
    • 라운드로빈 방식으로 운영되는 큐는 우선순위에 따라 다단계로 나뉘어 있어 프로세스가 큐에 삽입되는 것만으로도 우선순위가 결정된다.
    • 우선순위는 고정형 우선순위를 사용한다.
  • 우선순위에 따라 다양한 스케줄링이 가능하다.
    • 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스보다 먼저 작동할 수 있다.
    • 우선순위에 따라 타임슬라이스를 조절하여 작업 효율을 올릴 수 있다.
      • e.g. 전면 프로세스는 반응속도를 높이기 위해 타임슬라이스를 작게 설정하고, 후면 프로세스는 사용자와 상호작용이 없으므로 FCFS방식으로 처리한다.
  • 우선순위가 높은 상위 큐 프로세스의 작업이 끝날때까지 하위큐 프로세스의 작업을 할 수 없다.
    • 이점을 개선한 알고리즘이 다단계 피드백 큐 스케줄링이다.

5.2.5 다단계 피드백 큐 스케줄링 💫

  • 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식
  • CPU를 사용하고 난 프로세스의 우선순위가 낮아진다.
    • CPU를 사용하고난 프로세스는 원래의 큐로 돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.
    • 다단계 큐 스케줄링에서는, 우선순위에는 변화가 없다.
    • 다단계 큐 스케줄링에서 발생하는 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화한다.
  • 우선순위에 따라 타임슬라이스의 크기가 다르다.
    • 우선순위가 낮은 프로세스의 경우, 어렵게 얻은 CPU를 오랫동안 사용할 수 있도록 타임슬라이스를 크게 설정한다.
  • 오늘날의 운영체제가 CPU스케줄링을 위해 일반적으로 사용하는 방식으로, 변동 우선순위 알고리즘의 전형적인 예이다.
  • 유닉스 운영체제에서 타임슬라이스를 10~200밀리초 사이에서 조정할 수 있도록 한 이유는 다단계 피드백 큐 스케줄링을 사용하기 때문이다.

5.3 비선점형 알고리즘

  1. 프로세스가 CPU를 할당받으면 작업이 끝날때까지 CPU를 놓지않는다.
  2. 효율이 떨어져서 오늘날에는 거의 사용하지 않는다.

5.3.1 FCFS 스케줄링 (First Come First Served)

  • 준비큐에 도착한 순서대로 CPU를 할당받는 비선점형 알고리즘
  • 선입선출(FIFO) 스케줄링으로, 프로세스에 큐가 도착한 순서대로 실행되며 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있다.
  • 큐가 하나라서 모든 프로세스는 우선순위가 동일하다.

단점

  • 단순하고 공평하지만, 처리기간이 긴 프로세스가 CPU를 차지하면 다른 프로세스는 기다려야해서 세스템의 효율성이 떨어진다. (콘보이 효과, Convoy effect)
  • 현재 작업중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어진다.

5.3.2 SJF 스케줄링 (Shortest Job First)

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

  • 최단 작업 우선 스케줄링
  • FCFS 스케줄링의 콘보이 효과를 완화하여 평균 대기 시간이 줄기때문에 시스템의 효율성을 높인다.

단점

  • 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.
    • 현대의 프로세스는 사용자와의 상호작용이 빈번하게 발생하기 때문
  • 공평성 위배
    • 작업시간이 긴 특정 프로세스의 작업이 계속 연기된다.
      • 아사 현상(Starvation)
      • 무한 봉쇄(Infinite Blocking)

5.3.3 HRN 스케줄링 (Highest Response Ratio Next)

  • SJF 스케줄링에서 발생할 수 있는 아사현상을 해결하기위해 만들어진 비선점형 알고리즘
  • 최고 응답률 우선 스케줄링
  • 우선순위 = (대기 시간 + CPU 사용 시간) / CPU 사용시간
  • 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도(=SJF 스케줄링) 대기 시간을 고려하여 아사 현상을 완화한다.

단점

  • 공평성 위배
profile
Hello World.

0개의 댓글