학습목표
- 운영체제에서 프로세스를 실행하고 종료될 때 까지의 작업을 시뮬레이션해보자.
🔥 학습내용
- 프로세스를 관리하는 자료구조에 대해 학습한다.
- 프로세스와 스레드의 관계에 대해 학습한다.
- 운영체제에서 사용하는 작업 스케줄링 알고리즘에 대해 학습한다.
🌱 개념학습
✅ 운영체제란?
- 실행할 프로그램에 필요한 자원을 할당하고
- 프로그램이 올바르게 실행되도록 돕는
- 특별한 프로그램
운영체제는 어디에?
- 운영체제는 메모리에 적재되서 실행된다.
- 다만, 미리 할당된 메모리(커널영역)에 적재되는 프로그램이다.
- 운영체제가 아닌 일반적인 응용 프로그램은 사용자 영역에 적재된다.
운영체제의 역할
1. 메모리 관리
2. CPU 관리
3. 입출력장치 관리
요약하면 운영체제란 운영 프로그램과 하드웨어 사이에서 관리를 해주는 역할을 한다.
(하드웨어 시스템 리소스를 효율적으로 관리하기 위한 소프트웨어다.)
운영체제가 필요한 이유
- 메모리에 적재해주고 관리해주는 역할
- 1 + 2 를 명령하면 더해주는 CPU 역할을 한다.
- 하드웨어에 접근하게 해준다. (ex. 파일을 만들어줘)
- 모니터에 보이게 해줘
운영체제를 알아야 하는 이유
- 운영체제는 프로그램을 위한 프로그램이다.
- 개발하는 프로그램을 잘 만들기 위해서는 운영체제의 도움을 잘 받아야 한다.
- 운영체제를 잘 알아야 운영체제의 도움을 많이 받을 수 있다.
<참고자료>
✅ 프로세스란?
- 프로세스란 실행중인 프로그램을 의미한다.
- 스케줄링의 대상이 되는 작업(task)와 같은 의미로 쓰인다.
- 프로세스(실행 프로그램) 내부에는 최소 하나의 스레드(thread)를 가지고 있다.
- 이 스레드의 단위로 스케줄링을 한다.
- 하드에 있는 A라는 프로그램을 실행하면, OS는 실행을 위해 A에게 메모리를 할당하고,
할당된 메모리 공간으로 A프로그램의 바이너리 코드가 저장되면서 프로세스를 실행한다.
이 프로세스를 운영체제가 관리하는 상태를 프로세스 관리라 한다.
운영체제는 프로세스 관리를 통해 여러 프로세스가 효율적으로 돌아가도록(멀티프로그래밍) 관리한다.
프로세스 제어(관리) 블록 PCB
운영체제는 어떻게 프로세스 관리를 할까?
PCB(Process Control Block)는 프로세스에 대한 모든 정보가 있는 곳으로, TCB(Task Control Block)라고도 한다.
PCB 안에는 프로세스의 상태, 번호, PC 등 이 포함되어 있으며, 운영체제는 이를 통해 프로세스들을 관리한다.
(PCB는 프로세스의 커널영역에 저장된 자료구조라고도 한다.)
- PCB 자료구조에 포함된 정보
- 프로세스 스케줄링 상태
- 프로세스 주소 정보
- 프로세스 권한
- 프로세스 상태
- 프로세스 ID
- 프로그램 카운터 (PC)
- CPU 레지스터 값
- CPU 스케줄링 정보
- 메모리 관리 정보
- 계정 정보
- I/O 상태정보
CPU는 한 프로세스가 종료될 때까지 수행하지 않는다. (프로세스가 언제 종료될지 모른다.)
때문에 여러 프로세스를 바꿔가면서 수행하고 현재 수행중인 프로세스에서 다른 프로세스로 이동할 때
작업 정보를 저장해야 나중에 이어서 작업이 가능하다. 이런 정보, 상태 등을 저장하는 곳이 PCB가 된다.
문맥 교환(context switch)
- 한 프로세스에서 다른 프로세스로 실행 순서가 넘어가면?
- 기존에 실행되던 프로세스는 지금까지의 중간 정보를 백업한다.
- 뒤이어 실행할 프로세스의 문맥을 복구한다.
이처럼 기존의 실행 중인 프로세스 문맥을 백업하고 새로운 프로세스 실행을 위해 문맥을 복구하는 과정을 문맥교환 이라 한다.
✅ 프로세스 스케줄링
운영체제와 프로세스가 무엇인지 그리고 운영체제가 프로세스를 관리한다고 이해했다.
그리고 운영체제는 PCB의 정보를 통해 프로세스를 관리한다고도 이해했다.
그런데 아래와 같은 의문이 생긴다.
- CPU는 하나인데 동시에 여러개의 프로세스가 실행되고 있다?
- 프로세스 종료 시점을 모르는데 현재 프로세스를 종료하고 다른 프로레스를 실행한다?
- 종료시점은? 어떤 다른 프로세스를 실행하는거지?
CPU는 운영체제의 프로세스 관리로 여러 프로세스를 알고리즘을 통해 효율적인 순서로 선정하고,
생성, 준비, 실행, 대기, 종료를 고속으로(누구보다 빠르게) 반복하는 것이다.
이걸 프로세스 스케줄링이라 한다.
그리고 스케줄링이 너무 빨라서 동시에 실행되는 것처럼 보이는 것을 멀티프로그래밍이라고 부른다.
프로세스 상태
프로세스 스케줄링을 이해하기 위해 프로세스의 상태를 먼저 알아야한다.
프로세스 상태는 생성, 준비, 실행, 대리, 종료까지 5가지 상태가 있다.
프로세스를 생성하고 계속해서 실행하지 않고, 다른 프로세스를 실행하는 동안 대기했다가 다시 실행하는 순서를 반복한다.
- 생성(new): 프로세스가 생성되는 중이다.
- 준비(ready): 프로세스가 프로세서를 사용하고 있지는 않지만 언제든지 사용할 수 있는 상태로, CPU가 할당되기를 기다리고 있다.
- 실행(running): 프로세스가 프로세서를 차지하여 명령어들이 실행되고 있다.
- 대기(waiting): 프로세스가 입출력 완료, 시그널 수신 등 어떤 사건을 기다리고 있는 상태를 말한다.
- 종료(terminated): 프로세스의 실행이 종료되었다.
<프로세스 상태 전이도>
-
new -> ready
: new 상태에서 프로세스가 생성되게 되면 OS 커널에 존재하는 Ready Queue에 들어간다. -
ready -> running
: Ready Queue에 있는 프로세스들을 OS가 프로세스 스케줄링 알고리즘에 의해서 Running 상태로 가야할 프로세스를 CPU로 할당한다.
그러면 프로세스가 Running 상태가 된다. -
running -> ready
: 현재 running 상태에 있는 프로세스A 보다 Ready Queue에서 대기하고 있는 프로세스 B가 우선순위가 높으면,
preemptive schedule(선점형)인 경우 프로세스A는 Ready 상태로 오게되고 프로세스B가 running 상태로 가서 CPU를 할당 받는다. -
running -> waiting
: 현재 running 상태에 있는 프로세스A에서 입출력(I/O) 이벤트가 발생했을때 프로세스A가 waiting 상태로 가게된다. -
waiting -> ready
: 입출력(I/O)이벤트가 종료된 프로세스는 다시 Ready상태로 오게된다. -
running -> terminate
: 프로세스가 종료된다.
프로세스 계층 구조
- 프로세스 실행 도중 (시스템 호출을 통헤) 다른 프로세스 생성이 가능하다.
- 이때, 새 프로세스를 생성한 프로세스를 부모 프로세스라 한다.
- 부모 프로세스에 의해 생성된 프로세스를 자식 프로세스라 한다.
부모 프로세스와 자식 프로세스는 별개의 프로세스이므로 각자 다른 PID를 가진다.
일부 운영체제에서는 자식 프로세스 PCB에 부모 프로세스 PID(PPID)를 명시하기도 한다.
자식 프로세스가 자식을 낳고 또 그 자식이 자식을 자식이 또 자식을 낳고 하면 프로세스 계층 구조가 만들어 진다.
프로세스 생성 기법
부모 프로세스는 자식 프로세스를 어떻게 만들어 내고,
자식 프로세스는 어떻게 자신만의 코드를 실행할까?
- 복제와 옷 갈아입기
: 부모 프로세스는 fork 시스템 호출을 통해 자신의 복사본을 자식 프로세스로 생성한다.
: 자식 프로세스는 exec 시스템 호출을 통해 자신의 메모리 공간을 다른 프로그램으로 교체한다.
위와 같은 방식으로 프로세스가 생성되고 계층 구조를 이룬다.
스케줄링 방식
프로세스 상태 전이도를 통해 여러 프로세스들은 운영체제를 통해 순서를 할당 받고
순서에 맞게 상태가 변경되면서 실행됨을 이해 할 수 있다.
그렇다면 이 순서를 만드는 기준이 어떻게 될까?
운영체제는 프로세스들의 알고리즘으로 순서를 정하고 순차적인 실행을 위해 큐에 저장한다.
이를 위한 알고리즘을 스케줄링이라 하고, 여러가지 알고리즘(방식)을 가진다.
스케줄링(알고리즘) 평가기준 (Scheduling Criteria)
| 평가기준 | 설명 |
|---|---|
| CPU Utilization(이용률, %) | CPU가 수행되는 비율 |
| Throughput(처리율, jobs/sec) | 단위시간당 처리하는 작업의 수(처리량) |
| Turnaround time(반환시간) | 프로세스의 처음 시작 시간부터 모든 작업을 끝내고 종료하는데 걸린 시간이다. |
| Waiting time(대기시간) | CPU를 점유하기 위해서 ready queue에서 기다린 시간을 말한다.(다른 큐에서 대기한 시간은 제외한다.) |
| Response time(응답시간) | 일반적으로 대화형 시스템에서 입력에 대한 반응 시간을 말한다. |
스케줄링(알고리즘) 기법(종류)
스케줄링 방식은 크게 선점과 비선점의 형태로 구분된다.
Preemptive (선점)
Preemptive(선점)은 프로세스가 CPU를 점유하고 있는 동안 I/O나 인터럽트가 발생한 것도 아니고 모든 작업을 끝내지도 않았는데,
다른 프로세스가 해당 CPU를 강제로 점유 할 수 있다.
즉, 프로세스가 정상적으로 수행중인 가운데 다른 프로세스가 CPU를 강제로 점유하여 실행할 수 있는 것이다.
Non-preemptive (비선점)
Non-preemptive(비선점)은 말 그대로 preemptive의 반대이다.
한 프로세스가 한 번 CPU를 점유했다면, I/O(프로세스 상태가 실행 -> 대기로 변경되는 경우)
또는 프로세스가 종료될 때까지 다른 프로세스가 CPU를 점유하지 못하는 것이다.
- 선점 스케줄링
-
SRT(Shortest Remaining Time) 스케줄링
: 짧은 시간 순서대로 프로세스를 수행한다. 남은 처리 시간이 더 짧은 프로세스가 Ready 큐에 들어오면 그 프로세스가 바로 선점됨. 아래에 소개할 SJF의 선점 버전이라고 할 수 있다. -
라운드로빈(Round-Robin)스케줄링
: 각 프로세스는 같은 크기의 CPU 시간을 할당 받고 선입선출에 의해 행된다. 할당시간이 너무 크면 선입선출과 다를 바가 없어지고, 너무 작으면 오버헤드가 너무 커진다. -
다단계 큐(Multi-level Queue) 스케줄링
: Ready큐를 여러 개 사용하는 기법. 각각의 큐는 자신의 스케줄링 알고리즘을 수행하며, 큐와 큐 사이에도 우선순위를 부여한다. -
다단계 피드백 큐 스케줄링
: 다단계 큐와 비슷하나 프로세스들이 큐를 이동할 수 있다.
- 비선점 스케줄링
-
HRN(Highest response ratio next) 스케줄링
: 긴 작업과 짧은 작업간의 지나친 불평등을 어느 정도 보완한 기법. 수행시간의 길이와 대기 시간을 모두 고려해 우선순위를 정한다. -
SJF(Shortest Job First) 스케줄링
: 큐 안에 있는 프로세스 중 수행시간이 짧은 것을 먼저 수행. 평균 대기 시간을 감소시킨다. -
우선순위(priority) 스케줄링
: 프로세스에게 우선순위를 정적, 혹은 동적으로 부여하여 우선순위가 높은 순서대로 처리한다. 동적으로 부여할 경우, 구현이 복잡하고 오버헤드가 많다는 단점이 있으나, 시스템의 응답속도를 증가시킨다. -
기한부(Deadline) 스케줄링
: 작업을 명시된 시간이나 기한 내에 완료하도록 계획. -
FIFO 스케줄링
: 프로세스들은 Ready큐에 도착한 순서대로 CPU를 할당 받는다. 작업 완료 시간을 예측하기 매우 용이하다. 하지만 덜 중요한 작업이 중요한 작업을 기다리게 할 수도 있다.
프로그램이 실행되면 운영체제가 메모리를 할당하고 실행하는 것을 프로세스라고 이해했다.
그리고 이렇게 실행된 여러 프로세스를 스케줄링(알고리즘) 방식을 통해 순차적으로 반복 실행하는 것을
운영체제의 프로세스 스테줄링이라고 이해 할 수 있다.
<프로세스 참고자료>
프로세스란?
프로세스 스케줄링방식
프로세스 스케줄링 그리고 기법
스케줄링 기법
✅ 스레드(Thread)
프로세스라는 덩어리에서 실행 제어만 분리해서 처리하는 단위를 스레드라 한다.
즉, 프로세스 내부의 실행흐름의 단위를 가져와서 관리하는 경량 프로세스 (Light Weight Process)라 할 수 있다.
- 스레드는 프로세스 내부의 실행흐름(단위)를 뜻한다.
- 프로세스는 하나 이상의 스레드를 가지고 있다.
- 여러 스레드를 가지는 것은 다중스레드라 하고 각 스레드는 해당 프로세스의 코드, 메모리 주소 공간, 운영체제 리소스를 공유한다.
스레드의 구성요소
스레드는 스레드 ID, 프로그램 카운터를 비롯한 레지스터 값, 스택 등 실행에 필요한 최소한의 정보로 구성된다.
프로세스에 여러개의 스레드가 존재한다면 각각의 스레드는 각자들의 실행단위를 가지고 있으며 프로세스의 자원을 공유한다.
앞에서는 운영체제가 여러 프로세스를 스케줄링 방식으로 순서를 정하고 CPU에 명령을 전달한다고 했는데,
사실은 프로세스들의 각각의 스레드가 전달된다고 생각 할 수 있다.
멀티 프로세스 vs 멑티 스레드
동일한 작업을 수행하는 단일 스레드 프로세스 여러개와 하나의 프로세스를 여러 스레드로 실행시 어떤 차이가 있을까?
결과값은 둘다 동일한 결과를 반환한다.
다만,
프로세스들 끼리는 기본적으로 서로 남남처럼 자원을 공유하지 않는다.
메모리에는 같은 프로세스가 반복해서 실행되고 각각의 프로세스 값들을 메모리에 저장한다.
-> 프로세스 수만큼의 PCB가 생성된다. (메모리 차지가 늘어나고 속도도 더 걸린다.)
하지만 스레드들은 프로세스의 자원을 서로 공유한다. 즉, 협력과 통신에 유리하다.
(정보를 공유하는 만큼 프로세스가 종료되면 모든 스레드도 정보가 날라가는 등 단점도 존재한다.)
스레드 참고자료
✅ 구현학습
기능요구사항
- 마치 운영체제가 프로세스를 스케줄링하는 것처럼 프로세스를 일정한 시간동안 실행하는 프로그램을 구현한다.
- 프로세스 A, B, C 3개가 있다고 가정한다. (프로세스A : 3초, 프로세스B : 5초, 프로세스C : 7초)
- 우리가 목표로 하는 운영체제는 한 번에 프로세스 하나씩만 1초동안만 실행할 수 있다. 해당 프로세스 외 다른 프로세스는 실행하지 않는다.
- 1초 이후에는 같은 프로세스가 아니라 다른 프로세스를 실행해야 한다. 만약 프로세스가 1개만 남은 경우 반복해서 같은 프로세스를 실행할 수 있다.
- 관리할 프로세스 상태는 준비ready, 실행running, 대기waiting, 종료terminated 4 가지 상태 중에 하나다.
프로그래밍 요구사항
- 프로세스는 준비 또는 대기 상태에서만 실행 상태로 바뀔 수 있다.
- 누적 동작 시간이 최대 동작 시간만큼 실행한 프로세스는 종료 상태로 바뀐다.
- 누적 동작 시간이 최대 동작 시간보다 작으면, 대기 상태로 바꿨다가 준비 상태로 변경한다
- 대기 상태는 입출력 대기나 다른 응답을 위해서 사용하지만, 입출력을 다루지 않기 때문에 준비 상태로 바로 바꾸지 않고 대기 ⟹ 준비로 변경한다.
- 프로세스마다 작업 정보를 포함하는 데이터 구조 또는 타입을 선언한다.
- 단지 출력을 하기 위한 프로그램을 작성하는 게 아니라, 프로세스 타입을 선언하고 프로세스마다 1초씩 동작하는 구조를 구현해야 한다.
- 프로그램은 1초마다 전체 프로세스 상태와 대기 시간과 누적 실행 시간을 표시한다.
- 프로그램은 모든 프로세스가 종료 상태가 되면 종료한다.
- 프로그램에서 구현해야 하는 스케줄링 방식은 다음과 같다. 3개 중에 1개를 골라서 구현하고 여유가 되면 다른 방식도 구현해본다.
- 기한부 스케줄링 (deadline scheduling)
- 고정 우선순위 스케줄링 (static priority scheduling)
- 라운드 로빈 스케줄링 (Round Robin scheduling)
프로세스 스케줄링 구현 - 1
-
전체적인 흐름은 아래 그림을 참고로 구성하고자 한다.
-
1초마다 프로세스가 동작하기 위해 setInterval 함수를 이용하여
-
매초마다 disPatch함수를 실행한다.
-
disPatch 실행시 ready큐와 running큐를 이용하여 프로세스를 관리한다.
-
본 과정에서 waiting큐는 생략한다. (문제를 간략화하여 필요성이 없다고 판단된다.)
// 생성되어 준비큐에 들어가 있는 프로세스 A,B,C
const readyQueue = [
{ name: "A", endTime: 3, runTime: 0, waitingTime: 0 },
{ name: "B", endTime: 5, runTime: 0, waitingTime: 0 },
{ name: "C", endTime: 7, runTime: 0, waitingTime: 0 },
];
// 러닝큐
const runningQueue = [];
// 종료 프로세스 스택
const terminated = [];
// 매초마다 disPatch 함수 실행
const disPatch = function () {
// 준비큐 함수 선언
const setReadyQueue = function () {
// 큐의 가장 앞을 가져와서 러닝큐에 넣는다.
// 준비큐에서 대기중인 프로세스들은 대기시간이 증가한다.
const selectFirstProcess = readyQueue.shift();
for (let i = 0; i < readyQueue.length; i++) {
readyQueue[i].waitingTime++;
}
runningQueue.push(selectFirstProcess);
};
// 러닝큐 함수 선언
const setRunningQueue = function () {
// 러닝큐에 들어온 프로세스는 러닝타임이 1 증가한다.
runningQueue[0].runTime++;
// 프로세스의 러닝타임과 엔드타임이 같다면 종료상태가 된다.
// 아니라면 준비큐로 다시 넘어간다.
if (runningQueue[0].runTime === runningQueue[0].endTime) {
const exitProcess = runningQueue.splice(0, 1);
terminated.push(exitProcess);
} else {
const runDoneProcess = runningQueue.shift();
readyQueue.push(runDoneProcess);
}
};
console.log(readyQueue);
// 준비큐의 프로세스가 모두 종료되서 비어있다면 프로그램이 종료된다.
if (readyQueue.length === 0)
return clearInterval(
start,
console.log(`\n종료 되었습니다.\n`),
console.log(terminated)
);
setReadyQueue();
setRunningQueue();
};
const start = setInterval(disPatch, 1000);프로세스 스케줄링 구현 - 2
- 프로세스의 런타임과 상태 그리고 프로그램 평가를 위한 정보를 가져오기 쉽게 하기 위해 프로세스들을 클래스로 생성한다.
// 프로세스 속성과 메서드를 부여한다.
class Process {
constructor(name, endTime) {
this.name = name;
this.endTime = endTime;
this.runTime = 0;
this.waitTime = 0;
this.status = "ready";
}
totalRunTime() {
return this.runTime + this.waitTime;
}
addRunTime() {
this.runTime++;
}
addWaitTime() {
this.waitTime++;
}
setStatusToReady() {
this.status = "Ready";
}
setStatusToWaiting() {
this.status = "Waiting";
}
setStatusToRunning() {
this.status = "Running";
}
setStatusToEnd() {
this.status = "Terminated";
}
getRunTime() {
return this.runTime;
}
getEndTime() {
return this.endTime;
}
}
export default Process;- 스케줄링 클래스를 만들어서 생성된 프로세스들로 스케줄링을 구현한다.
import Process from "./process.js";
// 스케줄링 클래스에는 프로세스들과 준비큐, 러닝큐, 종료스택이 주어진다.
class Scheduling {
constructor(process) {
this.process = process;
this.readyQueue = [];
this.runningQueue = [];
this.terminated = [];
}
// 매초 disPatch가 실행되며 앞서 구현한 라운드로빈 방식 로직을 따른다.
disPatch() {
let i = 1;
const timer = setInterval(() => {
this.setReadyQueue();
this.setRunningQueue();
this.runtime(i);
this.running();
i++;
if (this.readyQueue.length === 0) {
console.log(`\n 라운드로빈 방식 스케줄링이 종료되었습니다.\n`);
this.end();
clearInterval(timer);
}
}, 1000);
}
setReadyQueue() {
const selectFirstProcess = this.readyQueue.shift();
for (let i = 0; i < this.readyQueue.length; i++) {
this.readyQueue[i].addWaitTime();
this.readyQueue[i].setStatusToWaiting();
}
this.runningQueue.push(selectFirstProcess);
}
setRunningQueue() {
this.runningQueue[0].addRunTime();
this.runningQueue[0].setStatusToRunning();
if (
this.runningQueue[0].getRunTime() === this.runningQueue[0].getEndTime()
) {
this.runningQueue[0].setStatusToEnd();
const exitProcess = this.runningQueue.splice(0, 1);
this.terminated.push(exitProcess);
} else {
const runDoneProcess = this.runningQueue.shift();
this.readyQueue.push(runDoneProcess);
}
}
start() {
this.process.forEach((psc) => {
this.readyQueue.push(psc);
const processInfo = `${psc.name}(${psc.status}), ${psc.runTime} / ${psc.endTime} sec`;
this.print(processInfo);
});
}
running() {
this.process.forEach((psc) => {
const processInfo = `${psc.name}(${psc.status}), \x1b[36m${psc.runTime}\x1b[0m / ${psc.endTime} sec, waiting ${psc.waitTime}`;
this.print(processInfo);
});
}
runtime(i) {
console.log(`\x1b[30m\n-----------------${i}초-------------------\x1b[0m`);
}
// 프로그램이 종료되면 프로그램의 평균 대기시간과 반환시간이 반환된다.
end() {
const averWaitTime =
this.process.reduce((acc, psc) => acc + psc.waitTime, 0) /
this.process.length;
const averEndTime =
this.process.reduce((acc, psc) => acc + psc.totalRunTime(), 0) /
this.process.length;
console.log(`평균 대기시간 = ${averWaitTime.toFixed(2)}`);
console.log(`평균 반환시간 = ${averEndTime.toFixed(2)}`);
}
init() {
this.start();
this.disPatch();
}
print(result) {
console.log(result);
}
}
// 프로세스 생성자로 A, B, C 프로세스 생성
const processArray = [];
const processA = new Process("A", 3);
const processB = new Process("B", 5);
const processC = new Process("C", 7);
processArray.push(processA);
processArray.push(processB);
processArray.push(processC);
const processSchedule = new Scheduling(processArray);
processSchedule.init();구현 결과
