[Chapter 2] 개념 이해를 위한 운영체제 [프로세스]

프로세스

프로세스는 컴퓨터 시스템 내부의 생명체와 같은 것으로 흔히 "컴퓨터 시스템이 살아있다."함은 컴퓨터 시스템 내부에 최소한 하나의 프로세스가 존재함을 의미한다. 이러한 프로세스 개념은 운영체제를 이해하는데 매우 중요하다.

프로세스는 1960년대 멀티태스킹(Multi-tasking) 시스템의 효시인 멀틱스 시스템(Multics System)을 개발하면서 처음 사용된 용어로써 오늘날에는 테스크(task) 혹은 스레드(thread) 개념과 함께 사용되고 있다. 

사전적으로 프로세스는 "어떤 일이 시작되어 끝날 때 까지 단계별로 진행되는 일련의 과정"을 의미한다. 유의할 점은 프로세스를 '처리' 혹은 '과정'이라고 번역하여 사용하지 않고 그냥 프로세스라고 부르며 CPU와 같은 처리기를 일걷는 한 사전적 의미를 가지고 있는 프로세스를 운영 체제에서는 다음과 같이 다양한 개념으로 정의하고 있다.

• 실행중인 프로그램(Program in execution) 
•  CPU를 할당하는 대상(Dispatchable objects of CPU)
• 시스템 내부에서의 작업 (unit of works in a system)
• PCB에 존재하는 개체(entity of PCB)
• 하나의 스레드(thread)로 구성된 테스크(task)

프로세스 상태

프로세스는 상태를 가지고 있다. 하나의 생명체가 태어나서 죽을때까지 생명 주기(life cycle)를 거치는 것처럼 프로세스도 운영체제에 의해 생성되어 실행되다가 종료할 때까지 여러가지 상태를 거치게 된다.

프로세스의 상태는 운영체제에 따라 다양한 상태로 구별되지만 기본적으로 다음과 같은 세 가지 상태가 존재한다.

• 준비(Ready) : CPU가 할당되기를 기다리고 있는 상태
• 실행(Running): CPU가 할당된 상태
• 대기(Waiting):요청한 사건(ex: 입출력)이 발생되기를 기다리고 있는 상태

• 프로세스가 생성되면 준비 상태에서 CPU의 할당을 기다린다. 운영체제는 준비상태에 있는 여러 프로세스들 중에서 우선순위가 높은 프로세스를 선정한 후 그 프로세스에게 CPU를 할당한다.
• CPU가 할당된 프로세스는 준비상태에서 실행 단계로 변환된다. 시분할(time-sharing)시스템을 위한 운영 체제에서는 하나의 프로세스가 CPU를 너무 오랫동안 사용하는 것을 방지하기 위하여 일정시간 동안만 CPU를 사용하도록 제한한다. 이 시간을 프로세스의 "CPU 할당시간(time quantum)"이라고 한다.
• 실행 상태의 프로세스가 정상적으로 실행을 완료할 경우 그 프로세스는 종료된다. 그러나 프로세스가 실행되는 과정에서 어떤 사건(ex: 입출력)을 요청할 경우 대기 상태로 변환되거나 주어진 CPU 사용 시간동안 완료하지 못했을 경우 다시 준비상태로 변환된다.
• 대기 상태의 프로세스는 자신이 요청한 사건이 발생하게 되면 준비상태로 변환된다. 다중 프로그래밍 환경에서는 여러 개의 프로세스가 존재할 수 있지만 하나의 CPU를 경쟁적으로 사용하기 때문에 실질적으로 실행중인 프로세스는 오직 하나 뿐일 것이다. 이러한 관점에서 오직 "실행 중인 프로그램"만이 프로세스라는 일반적인 정의에 한계가 있음을 유의해야 한다.

프로세스 영역

디스크에 존재하는 프로그램이 실행되기 위해서는 우선적으로 그 프로그램이 반드시 메모리에 적재되어 프로세스 형태로 존재하여야 한다. 이때 메모리에 존재하는 프로세스의 구조는 파일 형태로 디스크에 저장되었던 프로그램의 구조와 동일하지 않다.

파일 형태의 프로그램은 코드(혹은 명령어) 영역과 데이터 영역으로 구성되지만 프로세스는 기본적으로 다음과 같은 세 가지 영역으로 구성된다.

1. 코드(Code) 영역 : 프로그램의 코드(명령어)가 저장된 영역
2. 데이터(Data)영역 : 프로그램의 데이터가 저장된 영역
3. 스택(Stack) 영역 : 프로그램이 실행되는 과정에서 일시적인 데이터(ex: 함수 호출에 대한 반환 주소)를 저장하기 위해 LIFO(Last-In-First-Out) 방식으로 관리되는 영역

서로 다른 프로세스들에 의해 동일한 프로그램이 실행될 경우 운영 체제는 동일한 크기의 메모리 주소 공간을 각각의 프로세스에게 할당한다. 다수의 프로세스를 지원하는 다중 프로그래밍 환경에서 운영체제는 어느 프로세스에게 CPU를 할당한 것인가를 결정하여야 한다. 이러한 관점에서 프로세스를 "CPU를 할당하는 대상"이라고 정의할 수 있을 것이다. 결국 운영체제는 컴퓨터 시스템의 자원을 관리하는 주체이고 자원을 사용하는 주체가 바로 프로세스임을 알 수 있다. 따라서 프로세스는 자원을 사용하기 위하여 운영체제에게 요청하고 운영체제는 요청한 프로세스에게 자원을 할당하게 된다. 그러나 모든 자원은 한정되어 있기 때문에 프로세스가 요청한 자원을 항상 할당해줄 수 없을 것이다.

이러한 프로세스들은 요청한 자원이 할당될 때까지 기다려야 한다.

프로세스 제어 블록

일반적으로 프로세스는 생성되어 종료될 때까지 계속적으로 진행되지 못하고 잠시 동안 정지되었다가 다시 진행되기를 반복하게 된다. 따라서 운영체제는 정지된 프로세스를 정상적으로 다시 진행시키는데 필요한 정보를 저장하고 관리하기 위한 자료 구조가 요구된다.

프로세스 관리에 필요한 정보를 저장하기 위한 운영체제의 자료 구조를 "프로세스 제어 블록(PCB: Process Control Block)"이라고 부른다.

운영체제는 시스템 내부에 존재하는 모든 프로세스들에 대한 각각의 정보를 PCB에 저장해 둠으로써 프로세스 관리에 필요한 정보를 참조한다. 프로세스의 생성은 그 프로세스의 정보가 PCB에 등록됨을 의미하고 프로세스 종료는 그 프로세스의 정보가 PCB에서 삭제됨을 의미한다. 

이러한 관점에서 프로세스를 "PCB에 존재하는 개체"라고 정의할 수 있을 것이다.

운영 체제는 프로세스를 관리하기 위해서 PCB에 어떤 정보를 유지하여야 하는가? -> 기본적으로 프로그램이 위치한 메모리 주소 공간을 포함하여 이미 할당된 자원과 프로세스의 속성들에 대해 보다 자세히 정보를 유지할수록 유리할 것이다. 그러나 필요 이상의 정보를 유지 관리하는 것은 비효율적이기 때문에 최소의 정보를 유지 관리 하는 것이 중요하다. 프로세스 관리를 위해 유지되는 정보는 운영체제에 따라 다르지만 기본적으로 아래와 같은 내용을 가지고 있다.

• 프로세스의 식별자(PID: Process Identification)
• 프로세스의 상태
• 프로세스 스케줄링을 위한 우선 순위
• 프로세스가 적재된 메모리 주소 공간

CPU의 레지스터 값

• 부모 프로세스 식별자(PPID: Parent Process Identification)
• 자식 프로세스 식별자(CPID: Child Process Identification)

CPU 사용 기간

• 사용 가능한 파일
• 할당된 자원에 대한 포인터

프로세스 문맥 교환

프로세스의 문맥 교환은 "현재 실행중인 프로세스의 정보를 PCB에 저장하고 다른 프로세스의 정보를 PCB로부터 복구시키는 작업"을 말한다.

실행중인 프로세스(i)가 PCU 할당시간이 초과되어 준비상태로 변화되고 스케쥴러에 의해 준비상태의 프로세스(j)가 선택된 CPU 할당 시간이 초과되어 준비상태로 변화되고 스케줄러에 의해 준비상태의 프로세스(i)가 선택되어 다시 실행될 경우 발생하는 문맥 교환 과정을 나타내고 있다.

운영체제는 타이머 인터럽트에 의해 프로세스의 CPU 할당 시간 초과를 인지하고 현재 실행 중인 프로세스의 정보를 그 프로세스의 PCB에 저장하고 스케줄러에 의해 다음 실행할 프로세스를 선택한 후 다음에 실행할 프로세스의 정보를 그 프로세스의 PCB로부터 복구함으로써 문맥 교환이 이루어진다. 문맥 교환이 완료되면 CPU의 실행 모드가 아닌 커널 모드에서 사용자 모드로 전환되고 선택된 프로세스의 PCB로부터 PC 레지스터 값을 복구함으로써 새로운 프로세스가 실행된다. 문맥 교환에 소요되는 시간은 PCB에 저장하고, 복구해야할 프로세스의 정보량, 메모리 속도, 레지스터의 수 등 하드웨어에 따라 상당한 차이가 있지만, 문맥 교환에 의해 소요되는 시간은 프로세스 고유의 일과는 상관없는 오버헤드이다. 문맥 교환이 빈번히 발생할 경우 시스템 성능에 많은 영향을 미치게 됨으로 이 시간을 최소화하는 것은 운영체제에서 매우 중요하다.

프로세스 생성 및 종료

새로운 프로세스의 생성은 운영체제에서 제공하는 서비스 함수를 호출함으로써 이루어진다. 이때 새로운 프로세스 생성을 위한 시스템 함수를 호출한 프로세스를 "부모(Parent)프로세스" 라고 부르고 새롭게 생성된 프로세스를 시스템 함수를 호출한 프로세스의 "자식(Child)프로세스"라고 한다. 따라서 시스템 내부에 존재하는 모든 프로세스들은 부모-자식 관계를 유지하게 된다. 따라서 새로운 프로세스가 생성되기 위해서는 부모 프로세스가 필요하다.

• 대부분의 운영체제는 컴퓨터 시스템이 부팅될 때 운영체제 초기화 과정에서 최초의 프로세스를 생성한 후 사용자의 명령어 입력을 무한정 기다린다.
• 사용자가 입력한 명령어가 임의의 응용 프로그램을 실행시키기 위한 것이면 운영체제는 그 응용 프로그램을 실행시키기 위한 것이면 운영체제는 그 응용 프로그램을 실행하기 위해서는 새로운 프로세스를 생성한다. 또한 응용 프로그램이 실행되는 과정에서 또 다른 프로세스를 생성할 수 도 있다.
• 결국 최초의 프로세스를 제외하고 시스템 내의 모든 프로세스는 시스템 호출을 통하여 생성된다.

운영체제 내부에서 새로운 프로세스가 생성되는 개략적인 과정은 아래와 같다.

1. PCB 엔트리를 할당하고 PID 번호를 부여한다.
2. 프로세스를 위한 메모리 공간을 확보한다.
3. PCB 자료구조의 모든 정보를 초기화 한다.

대부분의 프로세스는 정상적으로 종료되지만 경우에 따라서는 비정상적으로 종료되어질 수 있다. 프로세스의 정상적인 종료는 시스템 호출에 의해서 이루어지지만 비정상적인 종료는 오류에 의해서 발생된다.

프로세스가 종료되면 그 프로세스에게 할당된 모든 자원을 회수한다.

프로세스 관리와 유사한 방법은 학교에서 학생관리를 할 때 신상 기록 카드에 필요한 모든 정보를 학생 신상 기록 카드에 작성하여 재학생 목록에 추가한다. 이 경우 신상기록카드는 PCB, 학번은 PID, 학년은 프로세스의 우선 순위, 현 주소는 프로세스가 적재된 메모리 주소에 해당될 것이다. 또한 정상적으로 졸업을 하거나 비정상적으로 퇴학이 될 경우에는 해당 신상기록카드를 재학생 목록에서 삭제한다.

스레드

스레드(thread)의 사전적 의미는 '실' 혹은 '실타래'로서 한 가닥으로 감겨진 실타래(단일 스래드: Single thread)와 여러 가닥으로 감겨진 실타래(다중 스래드: multiple threads)를 생각해볼 수 있을 것이다.

스래드의 정의

스래드는 프로세스와 매우 유사한 속성을 가지고 있으며 일반적으로 다음과 같이 다양하게 정의되고 있다.

 

CPU 제어의 흐름(flow of CPU Control)

실행단위(unit of execution)

한 프로세스 내부에서 스케줄링이 가능한 개체

 

프로세스 내부에서 스케줄링이 가능한 개체

프로세스 내부의 명령어에는 조건문 혹은 반복문들이 있을 수 있기 때문에 항상 일정한 경로로 진행되는 것은 아니다. 하지만 프로세스가 실행되는 동안 CPU 제어의 흐름을 따라 지나온 경로를 따라가면서 그려보면 마치 실타래의 실처럼 보일 것이다. 따라서 스래드를 "CPU 제어의 흐름"이라고 정의할 수 있을 것이다. 이와 같이 스래드는 프로세스 내부에 존재하며 프로세스 내부에는 기본적으로 하나의 스래드가 존재하고 있는 것이다. 이러한 관점에서 프로세스를 "하나의 스래드로 구성된 태스크"라고 정의할 수 있을 것이다.

스래드는 프로세스처럼 생명 주기를 가지고 있으며 CPU를 할당하는 대상으로써 스래드 단위로 스케줄링이 이루어진다. 따라서 스래드를 지원하는 운영체제에서는 스래드를 '실행단위'라고 정의할 수 있을 것이다.

 

스래드는 프로세스처럼 생명 주기를 가지고 있으며 CPU를 할당하는 대상으로써 스래드 단위로 스케줄링이 이루어진다. 따라서 스래드를 지원하는 운영체제에서는 스래드를 실행단위라고 정의할 수 있을 것이다.

프로세스 내부에 오직 하나의 스래드만을 허용하는 단일 스래딩(single-threading)일 경우에는 프로세스 내부에 존재하는 스래드 개념을 별도로 언급할 필요가 없다. 그러나 프로세스 내부에 다수의 스래드를 허용하는 다중 스래딩(multi-threading)에서는 스래드 단위로 스케줄링하여 CPU를 할당하기 때문에 프로세스 내부의 스래드들을 반드시 구별할 필요가 있다. 이러한 관점에서 스래드를 "한 프로세스 내부에서 스케줄링이 가능한 개체"라고 정의할 수 있을 것 같다.

다중 스래딩

• 다중 스래딩(Multi-threading)을 지원하는 운영체제에서는 프로세스 내부에 다수의 스래드를 허용하며 스래드 단위로 스케줄링을 한다.
• 프로세스가 생성될 때 기본적으로 하나의 스래드가 존재하지만 프로세스가 실행되는 과정에서 새로운 스래드를 생성할 수 있기 때문에 하나의 프로세스 내부에 다수의 스래드가 존재하게 된다.
• 이때 동일한 프로세스에서 생성된 스래드들은 그 프로세스에게 할당된 모든 자원을 공유한다.

다중 스래드를 지원하는 운영체제에서 스래드 관리는 프로세스 관리와 매우 유사하다. 각각의 스래드는 프로세스처럼 생명 주기를 가지고 있으며 생성되어 종료될 때 까지 여러가지 상황을 거치게 된다. 프로세스 내부의 스래드 단위로 스케줄링하여 CPU를 할당한다.

스래드가 실행될 때 프로세스 내부의 코드 ,데이터, 그리고 그 프로세스에게 할당된 모든 자원들을 공유한다. 따라서 스래드 관리에 필요한 정보량은 프로세스 관리에 필요한 정보량보다 상대적으로 적기 때문에 스래드 간 문맥 교환에 의한 오버헤드는 프로세스 간 문맥 교환보다 훨씬 적어진다.

이러한 관점에서 기존의 프로세스를 '중량프로세스(heavyweight process)'라고 부르는 반면 스래드를 '경량 프로세스(light process)'라고 부른다.

 

다중 스래드 개념의 이해를 돕기 위하여 제과점에서 빵을 만드는 작업이 처리되는 과정에 비유하면 빵을 만들기 위해 밀가루 ,물과 같은 여러가지 재료(데이터)와 오븐과 같은 도구(입출력 장치) 그리고 만드는 순서를 설명하는 조리법(코드)이 갖춰진 작업장(메모리 공간)이 필요하다. 이러한 제반의 환경이 준비된 상태(준비 상태의 프로세스)에서 제빵사(CPU)가 조리법의 순서에 따라 절차(코드)를 처리하면 최종적으로 맛있는 빵이 만들어질 것이다. 이 과정에서 제빵사가 움직이는 동선을 그려보면 실타래 동선이 보일 것이다. 이것이 바로 스래드 개념에 해당될 것이다. 이 경우 모든 빵 만들기에 필요한 재료와 도구들은 공유한다.

 

한편 동일한 상황을 다중 프로그래밍 개념으로 처리한다면 두 개의 작업 공간을 마련하여 첫 번째 작업장(프로세스-1)에서 빵 만들기 작업을 진행하다 오븐에서 구워지고 있는 동안 제빵사로 하여금 또 다른 작업장(프로세스-2)으로 이동하여 새로운 빵 만들기를 시작함으로써 동시에 여러 개의 빵 만들기를 진행할 수 있다. 이 경우 동일한 빵 만들기임에도 빵 만들기에 필요한 재료와 도구들을 갖춘 별도의 작업 공간이 있어야 한다.

파일 서버를 단일 스래딩으로 지원할 경우 하나의 서비스 요청에 대한 처리가 완료될 때 까지 다른 서비스 요청을 처리하지 못한다. 그러나 다중 스래딩으로 지원할 경우 또 다른 서비스 요청을 병행하여 처리할 수 있기 때문에 파일 서버의 성능과 CPU 이용률이 향상될 것이다.

스케줄링

프로세스 스케줄링은 준비 상태에 있는 여러개의 프로세스들 중에서 하나의 프로세스를 선정하여 CPU를 할당하는 것으로써 스케줄링 정책에는 여러가지가 있다.

한편 준비 상태에 있는 여러 개의 스래드들 중에서 하나의 스래드를 선정하여 CPU를 할당하는 스래드 스케줄링은 프로세스 스케줄링과 동일한 개념이다.

스케줄링 정의

• CPU의 이용률를 극대화 하기 위하여 대부분의 운영체제들은 다중 프로그래밍 환경을 제공한다.
• 다중 프로그래밍 환경에서는 다수의 프로세스들이 제한된 자원들을 경쟁적으로 사용하기 때문에 이 경쟁을 조정하는 기능이 요구된다.
• 프로세스 스케줄링은 CPU 사용에 대한 프로세스들의 경쟁을 조장하는 기능으로서 준비 상태에 있는 여러개의 프로세스들 중 하나의 프로세스를 선정하여 CPU를 할당하는 것이다. 이러한 기능을 담당하는 프로세스 스케줄러는 하나의 프로세스를 선정하는 스케줄링 정책(policy) 부분과 선정된 프로세스에게 CPU를 할당하는 디스패처(dispatcher) 부분으로 구성된다. 또한 여러 개의 준비 상태 프로세스를 관리하기 위한 준비 큐(ready queue)를 유지한다.
• 결국 프로세스 스케줄링이란 "준비 큐에 등록된 여러 개의 프로세스들 중에서 스케줄링 정책에 따라 하나의 프로세스를 선정하고 선정된 프로세스에게 CPU 할당하는 것"이라고 정의할 수 있다.

선점/비선점

모든 프로세스 스케줄링 정책은 크게 선점(preemptive) 혹은 비선점 (non-preemptive) 스케줄링으로 구분되며 프로세스 스케줄링이 발행하는 경우에 따라 구별할 수 있다. 기본적으로 스케줄링이 발생할 수 있는 경우는 다음과 같다.

이와 같이 비선점 스케줄링 정책에서는 어떤 프로세스가 CPU를 할당받으면 자발적으로 CPU 사용권을 내놓을 때까지 CPU 사용권이 보장된다. 그러나 선점 스케줄링 정책에서는 실행중인 프로세스의 CPU 사용권이 강제적으로 빼앗길 수 있음을 유의하여야 한다.

스케줄링 정책

프로세스 스케줄링 정책은 준비 큐에 등록된 여러 개의 프로세스들 중에 하나의 프로세스를 선정하기 위한 알고리즘이다. 여러 가지 종류의 스케줄링 정책들을 비교하기 위해서 아래의 요소들을 고려한다.

• CPU 이용률(CPU utilization) : 주어진 시간에 대한 CPU 사용 시간
• 처리율(throughput) : 단위 시간 당 처리된 프로세스의 개수
• 반환 시간(turnaround time) : 프로세스가 생성된 후 종료될 때 까지 소요된 시간
• 대기 시간(response time) : 어떤 사건(event)이 발생한 후 첫 번째 응답이 나오는 데 소요된 시간

이들 요소들 중에서 CPU 이용률과 처리율은 최대화하고 변환 시간, 대기 시간, 응답 시간은 최소화하는 것이 바람직하다. 그러나 모든 요소를 최적화할 수 있는 스케줄링 정책은 없다. 결국 프로세스 스케줄링 정책은 시스템의 사용 목적에 가장 적합한 요소를 우선적으로 고려하여 결정할 수 밖에 없다. 

ex)대화식 시스템에서는 주어진 시간 내의 응답 시간을 보장할 수 있도록 하는 것이 중요하다.

 

선입 선처리(FCFS:First-Come-First-Served)스케줄링

• 선입 선처리는 가장 먼저 준비 큐에 등록된 프로세스를 선정하는 전형적인 비선점 스케줄링 정책이다. 이때 유의할 점은 프로세스가 생성된 순서가 아니라 준비 큐에 등록된 순서이다.
•  

  프로세스	CPU 사용시간(초)
  P1	13
  P2	4
  P3	2

• 준비 큐에 등록된 순서가 p1, p2, p3라고 가정하면 프로세스가 처리되는 순서는 p1, p2, p3이고 각 프로세스의 대기시간과 평균 대기시간은 다음과 같이 계산된다.
• P1의 대기시간 = 0초P3의 대기시간 = 17초한편 준비 큐에 준비된 프로세스 순서가 P2, P1, P3라 가정하면 프로세스가 처리되는 순서는P2, P1, P3이고 각 프로세스의 대기시간과 평균 대기시간은 아래와 같이 계산된다.P1의 대기시간 = 4초평균 대기시간 = (0+4+17)/3 = 7(초)
• P3의 대기시간 = 17초
• P2의 대기시간 = 0초
• 평균 대기시간 = (0+13+17) / 3 = 10(초)
• P2의 대기시간 = 13초
• FCFS 스케줄링은 매우 간단하지만 CPU 사용 기간이 긴 프로세스가 CPU 사용 시간이 짧은 프로세스들을 오랫동안 기다리게 하는 '호송 효과(convoy effect)'가 발생할 수 있다.
• 호송 효과의 정도는 준비 큐에 도착한 프로세스의 순서에 따라 다르지만 일반적으로 FCFS 스케줄링 정책에서는 호송 효과에 의한 평균 대기시간이 길어지는 단점이 있다.

최단 작업 선처리(SJF: Shortest Job First) 스케줄링

• 최단 작업 선처리(SJF)는 준비 큐에 등록된 프로세스들 중에서 CPU 사용시간이 가장 짧은 프로세스를 선정하는 비선점 스케줄링 정책이다. SJF 스케줄링은 CPU 사용 시간이 가장 짧은 프로세스를 선정하기 떄문에 호송 효과를 방지할 뿐 아니라 최소의 평균 대기시간을 보장할 수 있다. ex) 다음과 같은 세 개의 프로세스(p1, p2, p3)가 준비 큐에 등록되어 있을 경우를 가정

• 프로세스	CPU 사용시간(초)
  P1	13
  P2	4
  P3	2

• 이 경우 준비 큐에 등록된 프로세스 순서에 상관 없이 이들이 처리되는 순서는 p3, p2, p1이고, 각각의 대기시간과 평균 대기 시간은 다음과 같이 계산된다.
• P3의 대기시간 = 0
• P2의 대기시간 = 2초
• P1의 대기시간 = 6초
• 평균 대기시간 = (0+2+6)/3 = 8/3(초)
• FCFS 스케줄링에 비하여 평균 대기시간이 훨씬 단축됨을 알 수 있다. 이와 같이 SJF 스케줄링은 최소의 평균 대기 시간을 보장할 수 있다. 그러나 정확한 CPU 사용시간의 예상이 불가능하기 때문에 SJF 스케줄링은 주로 다른 스케줄링 정책들의 평균 대기시간을 이론적으로 평가하기 위한 기준으로 이용되고 있다. 프로세스의 CPU 사용시간을 이론적으로 평가하기 위한 기준으로 이용되고 있다. 프로세스의 CPU 사용 시간을 정확하게 예상할 수는 없지만 다음과 같은 지수평균(exponential average)공식을 이용하여 프로세스의 CPU 사용시간을 예측할 수 있다.

지수 평균 공식에서 tn, Tn은 실제 측정된 CPU 사용시간과 예층한 CPU 사용시간을 의미하며 매개 변수는 a는 Tn+1을 결정하는데 두 정보(tn, Tn)에 대한 가중치를 의미한다.

기본적으로 SJF 스케줄링은 CPU 시간이 가장 짧은 프로세스가 준비 큐에 등록될 경우 새로운 프로세스의 CPU 사용시간과 실행중인 프로세스의 CPU 잔여시간(remaining time)을 비교하여 보다 짧은 프로세스에게 CPU를 할당할 수도 있다. 이러한 스케줄링을 '최단 잔여시간 선처리(SRTF : Shortest Remaining-Time First)' 혹은 '선점 SJF'라고 부른다.

ex) 세 개의 프로세스 (P1, P2, P3)가 다음과 같은 순서로 준비 큐에 등록되어 있을 경우를 가정 (P2는 P1 실행 4초 후 P3는 6초 후에 준비 큐에 등록됨)

프로세스 등록시간 CPU 사용 시간(초)

P1	0	13
P2	4	5
P3	6	2

SJF 스케줄링에 의해 프로세스가 처리되는 순서는 P1, P3, P2이고 각각의 CPU 대기시간, 평균 대기시간 그리고 문맥 교환의 횟수는 다음과 같이 계산된다.

P1의 대기시간 = 0초

P3의 대기시간 = (13-6) = 7초

P2의 대기시간 = (13-4+2) = 11초

평균 대기시간 = (0+7+11)/3 = 6초

문맥 교환 횟수 = 2회

한편 SRTF스케줄링에 의해 프로세스가 처리되는 순서는 P1, P2, P3, P2, P1이고 각각의 CPU 대기시간, 평균 대기시간 그리고 문맥 교환의 횟수는 다음과 같이 계산된다.

P1의 대기시간 = (2+2+3) = 7초

P2의 대기시간 = 2초

P3의 대기시간 = 0초

평균 대기시간 = (7+2+0)/3 = 3(초)

문맥 교환 횟수 4회

위의 예에서 SRTF 스케줄링은 SJF 스케줄링에 비하여 평균 대기시간이 훨씬 단축됨을 알 수 있다. 그러나 SRTF 스케줄링은 SJF 스케줄링에 비하여 문맥 교환의 오버헤드가 더 발생함을 유의해야 한다. 한편 SJF 스케줄링에서 CPU 사용 시간이 짧은 프로세스들이 계속하여 준비 큐에 등록될 경우 CPU 사용 시간이 긴 프로세스는 무한정 기다리게 되는 기아현상(starvation)이 발생할 수 있다. 이러한 기아 현상을 방지하기 위하여 Brinch Hansen이 제안한 HRN(Highest-response Ratio Next)스케줄링 정책이 있다.

 

HRN 스케줄링에서는 프로세스의 우선 순위를 다음과 같이 계산한다.

우선순위 = (CPU 대기시간 + CPU 사용시간) / CPU 사용시간

 

프로세스의 우선순위는 CPU 사용시간과 CPU 대기시간을 고려하여 결정된다. 다시 말해서 CPU 사용시간이 짧고 CPU 대기 시간이 길수록 프로세스의 우선 순위는 높아질 것이다. 따라서 SJF 스케줄링에서 CPU 사용시간이 긴 프로세스가 무한정 기다리게 되는 기아현상을 방지할 수 있게 된다. 이와 같이 프로세스 스케줄링에서 기아 현상을 방지하기 위하여 CPU 대기시간을 고려하여 프로세스의 우선 순위를 결정하는 기법을 '에이징(aging)'이라 한다.

우선 순위 스케줄

• 우선순위(prioity) 스케줄링은 준비 큐에 등록된 프로세스들 중에서 프로세스의 우선 순위가 가장 높은 프로세스를 선정하는 비선점, 스케줄링 정책이다.
• 우선 순위 스케줄링에서는 프로세스의 크기, CPU 사용시간, 입출력 대기시간 등의 내적 요소와 프로세스에게 우선 순위를 부여한다.
• FCFS와 SJF는 프로세스에게 우선순위를 부여하지는 않지만 우선 순위 스케줄링의 특별한 경우에 해당된다. 
• FCFS에서는 준비 큐에 도달하는 순서, SJF에서는 CPU 사용시간이 프로세스의 우선 순위에 해당되기 때문이다.
• 우선순위 스케줄링은 기본적으로 비선점 방식이다. 그러나 프로세스가 실행되는 동안에 새로운 프로세스가 준비 큐에 도착할 경우 새로운 프로세스의 우선 순위가 실행 중인 프로세스의 우선 순위보다 높으면 새로운 프로세스에게 CPU를 할당할 수도 있다.
• 이러한 스케줄링을  "선점 방식의 우선순위 스케줄링"이라고 부른다. 또한 프로세스의 우선순위는 정적 혹은 동적으로 부여할 수 있다.
• 우선순위를 정적으로 부여할 경우 우선 순위가 높은 프로세스가 계속 들어오게 되면 우선 순위가 낮은 프로세스는 무한정 기다리게 되는 기아현상이 발생할 수 있다. 이러한 기아 현상은 에이징 기법을 이용하여 우선순위를 동적으로 부여함으로서 해결할 수 있다.

순환 처리 스케줄링

• 순환 처리(RR:Round-Robin)스케줄링은 시분할 시스템을 지원하기 위하여 개발된 전형적인 선점 스케줄링 정책이다.
• 시분할 시스템에서는 모든 프로세스에게 CPU 할당 시간을 부여하여 CPU 사용 시간을 제한한다.
• RR 스케줄링은 기본적으로 FCFS 스케줄링처럼 준비 큐에 먼저 도착된 프로세스를 선정한다. 선정된 프로세스는 주어진 CPU 할당 시간동안 CPU를 독점적으로 사용한다.
• 만약 CPU 사용시간이 CPU 할당 시간을 초과할 경우 그 프로세스는 선점되어 준비큐의 맨 뒤쪽에 등록되어 또 다시 CPU 할당을 기다리게 된다.

RR 스케줄링에서 적절한 CPU 할당시간 결정은 매우 중요하다. 만약 CPU 할당시간이 너무 크면 FCFS스케줄링과 유사하게 되어 호송 효과가 예상되고 너무 적으면 빈번한 문맥 교환에 의한 오버헤드가 발생하게 될 것이다.

다단계 큐

 

• 스케줄링 정책들은 하나의 준비큐를 사용하였다 그러나 다단계 큐(multi-level queue) 스케줄링에서 다수의 준비 큐를 사용한다. 각각의 준비 큐에게 단계별 우선순위를 부여한다. 준비큐들 사이에 우선 순위가 존재한다. 또한 모든 프로세스들은 준비 큐의 우선 순위를 부여한다.
• 준비큐들 사이에 우선 순위가 존재한다. 또한 모든 프로세스들은 준비큐의 우선순위 별로 분류하여 프로세스가 생성될 때 해당 준비 큐에 등록된다. 
• 우선순위가 동일한 프로세스들은 동일한 준비 큐에서 CPU 할당을 기다린다.
• 각각의 준비 큐마다 서로 다른 스케줄링 정책을 적용할 수 있지만 준비큐들 사이의 스케줄링이 우선적이다. 우선순위가 높은 준비 큐에 등록된 프로세스들을 우선적으로 스케줄링한다.

---

Reference

개념 이해를 위한 운영체제 

https://blog.skby.net/%EB%AC%B8%EB%A7%A5%EA%B5%90%ED%99%98-context-switching/

문맥교환 (Context Switching) < 도리의 디지털라이프

https://velog.io/@xeropise1/%EC%8A%A4%EB%A0%88%EB%93%9C%EB%9E%80

스레드란?

 

​https://wikidocs.net/231651

03-2 프로세스의 상태천이

​https://velog.io/@yu-jin-song/OS-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81CPU-Scheduling