이번 주제는, CPU 스케줄러를 구현하면서 프로세스와 스레드의 개념을 이해해보는 것입니다. 프로세스와 스레드의 개념에 대해서는 제 블로그의 반효경 운영체제 시리즈에 정리해두었으므로, 이번 포스팅에서는 간단히 개념을 짚어보면서 관련된 구현의 내용을 설명해드리겠습니다. 이번 포스팅에서 구현할 것은 프로세스와 스레드를 관리하는 스케줄러의 프로토 타입입니다. 프로세스, 스레드의 개념을 먼저 학습하고, CPU는 한 개인데 어떻게 수많은 프로세스와 스레드들을 CPU가 처리하는지 궁금하실겁니다. 이러한 프로세스와 스케줄러를 관리하는 스케줄러에 대해서도 알아보겠습니다. 스케줄링 알고리즘에도 여러 종류가 있는데, 그 중에서 한 가지 방법을 골라서 구현에 적용해보았습니다. 다시 본론으로, 프로세스와 스레드에 대해 알아보겠습니다.
프로세스, 스레드의 개념
프로세스란?
프로세스란, 간단하게 실행 중인 프로그램을 의미합니다. 프로그램을 실행하면, 하드디스크에 있던 프로그램이 실행되어 메모리에 올라가게되고, 이러한 상태부터 프로세스라고 불리게 됩니다. 프로세스는 CPU 수행 상태를 나타내는 하드웨어적인 문맥, 프로세스의 주소 공간과 커널 자료구조를 합쳐서 의미합니다. 하드웨어 문맥은 Program Counter(프로그램에서 몇 번째 Instruction까지 수행했는지 저장하는 계수)나 각종 지역 변수 값을 저장하는 Register의 정보를 포함합니다. 이는 CPU가 여러가지 프로그램을 동시에 시행하기 때문에 문맥을 저장할 필요가 생기기 때문입니다. 사실 CPU는 여러가지 일을 동시에 처리하는 것이 아닌, 매우 빠르게 한 번에 한 가지 일을 처리합니다. 프로세스 간 전환 속도가 빠르기 때문에 여러 일을 동시에 처리하는 것처럼 보이죠. 이를 '동시성'이라고 합니다.
쓰레드란?
그렇다면 여기에서 쓰레드란 무엇인지 알아보겠습니다. 쓰레드는 프로세스와 비슷하게 실행 중인 프로그램의 상태를 저장하지만, 조금 더 경량화된 수행 단위라고 할 수 있습니다. 즉, 프로세스마다 프로세스 내부에 있는 CPU 수행 단위라고 할 수 있습니다. CPU는 한 번에 한 프로세스를 처리함에도 프로그램마다 동시에 여러가지 일을 처리할 수 있는 것이 이러한 쓰레드의 존재 때문입니다. 단일 쓰레드라면 웹 브라우저에 이미지를 요청하고, 요청한 이미지가 반환될 때까지 기다리겠죠? 실제로는 브라우저라는 하나의 프로세스 내에서도 이미지 로딩 중에 텍스트가 렌더링되는 등 다른 작업도 같이 수행됩니다. 이것이 한 쓰레드가 대기하는 동안 다른 쓰레드로 전환해서 일을 처리할 수 있기 때문입니다. 이러한 이유로 멀티 스레드를 사용하면 응답성이 향상된다고 볼 수 있는 것이죠.
그렇다면 무엇이 경량화된 것일까요? 프로세스는 독립적인 메모리 공간을 할당받는다고 했는데요, 한 프로세스 내에서는 쓰레드끼리 할당받은 메모리 공간을 공유합니다. 단, Stack 영역은 제외됩니다. 쓰레드마다 함수의 콜스택은 개별적으로 관리해야하기 때문입니다.
여기서 정리하면, 프로세스는 메모리에 로드되어 실행 중인 프로그램의 단위를 의미하며, 쓰레드는 CPU가 실제로 처리하는 프로세스의 경량화된 수행 단위라고 정리할 수 있을 것 같습니다.
주의점
그렇지만 쓰레드를 사용할 때 주의해야할 사항이 있습니다. 아주 중요한 내용이니 살펴보겠습니다. 바로 쓰레드의 동기성과 관련된 내용입니다. 여러 개의 수행 단위가 같은 데이터에 접근할 때 동기화 문제가 발생할 수 있습니다. 이러한 문제가 발생했을 때, 스레드는 데이터 공간을 공유하기 때문에 프로세스 전체에 문제를 야기할 수 있습니다. 그렇기에 스레드 안정성을 가진 설계를 구상하는것이 프로그래머의 역량이라고도 합니다.
문맥 교환
CPU가 처리하는 프로세스를 바꾸는 일을 문맥 교환(Context Switch)라고 합니다. CPU에 올라와있는 일을 처리하다가 다른 더 급한 프로세스를 처리해야할 때, 하던 프로세스의 문맥(사용하고 있던 레지스터에 저장되어있는 정보, 프로그램 카운터)을 그대로 다시 저장하고 다른 프로세스의 문맥을 꺼내오는 것이죠. 이러한 문맥을 저장하는 자료구조를 Process Control Block(PCB)라고 합니다. 우리의 운영체제 커널 메모리 상에는 프로세스마다 PCB라는 자료구조가 생성되어 저장됩니다. 이는 사용자 프로그램이 메모리에 로드될 때 차지하는 사용자 메모리 영역(보통 heap, data, stack, code 영역이라고 합니다.)과는 별도로 커널의 메모리 영역에 생성됩니다.
프로세스 상태
스케줄러에 대해 알아보기 전에 프로세스의 상태를 알아보겠습니다. 프로세스는 스케줄러에 의해서 상태가 변경되면서 수행됩니다. 상태는 아래와 같이 정의합니다.
- Running : CPU를 잡고 instruction을 수행 중인 상태
- Ready : CPU를 기다리는 상태(메모리 등 다른 조건을 모두 만족)
- Blocked (wait, sleep)
- CPU를 주어도 당장 instruction을 수행할 수 없는 상태
- Process 자신이 요청한 event(예: I/O)가 즉시 만족되지 않아 기다리는 상태
- (예) 디스크에서 file을 읽어와야 하는 경우
- Suspended (stopped)
- 외부적인 이유로 프로세스의 수행이 정지된 상태
- 프로세스는 통째로 디스크에 swap out 된다.
- (예) 사용자가 프로그램을 일시 정지시킨 경우, 시스템이 메모리 등 이유로 프로세스를 잠시 중단시킴
- Terminated : 수행이 끝난 상태, 정리할 것이 남아 있는 상태
- Blocked : 자신이 요청한 event가 만족되면 ready
- Suspended : 외부에서 resume해주어야 active
스케줄러
다음으로, 스케줄러에 대해 알아보겠습니다. 어떤 프로세스를 먼저 처리할지를 결정하는 것이 스케줄러입니다. 크게 단기, 중기, 장기 스케줄러로 구분되는데, 장기 스케줄러는 어떤 프로세스를 메모리에 로딩할지를 결정합니다. 단기 스케줄러는 어떤 프로세스를 CPU가 처리할지를 결정하며, 중기 스케줄러는 메모리에 로딩된 수많은 프로세스 중 어떤 것을 swap-out할지 결정합니다. 여기에서 제가 구현할 것은 단기 스케줄러입니다. 다음에 어떤 프로세스를 결정할지를 여러가지 알고리즘을 기반으로 결정하는 것입니다.
스케줄링 알고리즘
FCFS(First-Come First-Served)
비선점형 스케쥴링으로, 먼저 도착한 프로세스가 먼저 스케쥴되는 알고리즘입니다. 비선점형의 의미는, 한 번 스케쥴되면 프로세스가 강제로 빼앗기지 않는다는 의미입니다. CPU를 짧게쓰는 프로세스가 도착해도 오래 기다려야한다는 단점이 있습니다. 이를 Convoy Effect라고 하는데, 긴 프로세스가 선점하였을 때, 뒤의 짧은 프로세스가 오래 기다려야하는 상황을 뜻합니다.
SJF(Shortest Job First)
SJF 각 프로세스의 다음번 CPU burst time을 가지고 스케쥴링에 활용하는 방식으로, CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케쥴합니다. 전체적인 Queue의 길이가 짧아지는 효과가 있고 또한 주어진 프로세스에 대해 minimum average waiting time을 보장된다는 특징이 있습니다. 프로세스가 도착할 때마다 스케쥴링이 이루어지면 Shortest-Remaining-Time-First(SRTF)라고 하는데, 동적으로 스케쥴링하는 방식입니다.
SJF의 문제점도 존재합니다. 바로 Starvation(기아 현상)인데, CPU 사용 시간이 긴 프로세스는 영원히 점유를 못할 수도 있어 형평성에 어긋납니다.
Priority Scheduling
우선순위가 가장 높은 프로세스에게 CPU 할당하는 방식으로, 우선순위는 어느 것이든 정할 수 있습니다. 위에서 살펴본 SJF는 일종의 priority scheduling입니다. (Priority = predicted next CPU burst time) 따라서 문제점도 동일하게 Starvation이 발생 가능하다는 점입니다. 해결책으로는 Aging 기법이 있는데, 시간이 지나면서 프로세스의 우선순위가 높아지도록 설정하는 방법이 있습니다.
Round Robin(RR)
각 프로세스는 동일한 크기와 할당 시간(time quantum)을 가지도록 설정합니다. 할당 시간이 지나면 프로세스는 선점(preempted) 당하고 ready queue의 제일 뒤에 가서 대기하는 것을 반복합니다. 전체적인 응답 시간이 빨라진다는 특징이 있습니다.(할당 시간이 너무 긴 경우는 해당되지 않습니다.) 또한 SJF나 우선순위와 달리 예측이 필요없습니다.
구현
위에서 배웠던 내용을 정리해서 예제처럼 구현해봅니다. 목표는 아래와 같이 프로세스의 스레드를 생성하고, 시한부 스케쥴링을 통해 수행한 결과를 출력하는 것입니다.
이 프로그램은
프로세스A(3초) - 스레드 1개
프로세스F(21초) - 스레드 10개
프로세스B(5초) - 스레드 2개
총 스레드는 13개입니다.
A(READY), 0 / 3sec , waiting 0 , remaining Time 10 sec
F(READY), 0 / 21sec , waiting 0 , remaining Time 80 sec
B(READY), 0 / 5sec , waiting 0 , remaining Time 15 sec
.
A(RUNNING), 2 / 3sec , waiting 0 , remaining Time 9 sec
F(WAITING), 0 / 21sec , waiting 1 , remaining Time 79 sec
B(WAITING), 0 / 5sec , waiting 1 , remaining Time 14 sec
.
A(WAITING), 2 / 3sec , waiting 1 , remaining Time 8 sec
F(WAITING), 0 / 21sec , waiting 2 , remaining Time 78 sec
B(RUNNING), 4 / 5sec , waiting 1 , remaining Time 13 sec
.
A(RUNNING), 3 / 3sec , waiting 1 , remaining Time 7 sec
F(WAITING), 0 / 21sec , waiting 3 , remaining Time 77 sec
B(WAITING), 4 / 5sec , waiting 2 , remaining Time 12 sec
.
A(TERMINATED), 3 / 3sec , waiting 1
F(WAITING), 0 / 21sec , waiting 4 , remaining Time 76 sec
B(RUNNING), 5 / 5sec , waiting 2 , remaining Time 11 sec
.
A(TERMINATED), 3 / 3sec , waiting 1
F(RUNNING), 20 / 21sec , waiting 4 , remaining Time 75 sec
B(TERMINATED), 5 / 5sec , waiting 2
.
A(TERMINATED), 3 / 3sec , waiting 1
F(RUNNING), 21 / 21sec , waiting 4 , remaining Time 74 sec
B(TERMINATED), 5 / 5sec , waiting 2
.
A(TERMINATED), 3 / 3sec , waiting 1
F(TERMINATED), 21 / 21sec , waiting 4
B(TERMINATED), 5 / 5sec , waiting 2
.
기한부 스케줄링 (deadline scheduling)이 종료되었습니다.
평균 대기시간 = (1 + 4 + 2) / 3 = 2.33sec
평균 반환시간 = (4 + 25 + 7) / 3 = 12.00sec
우선 아래와 같이 전체적인 구조를 작성했습니다. 전체 흐름을 관리하는 ProcessApplication 클래스를 선언하고, 프로세스 스케쥴을 담당할 CPU Scheduler 클래스, 그리고 프로세스와 프로세스의 자료를 저장하는 ProcessControlBlock 타입 클래스를 선언했습니다.
가장 하위 구조인 PCB부터 살펴보겠습니다. PCB는 Process ID(A,B,C 등)와 동작 시간, 실행 시간, 대기 시간과 Deadline Scheduling이므로 마감 시간과 상태를 저장하는 자료 구조입니다.
public class PCB {
private static int currentTime = 0;
private String processId;
private int runningTime;
private int executionTime;
private int waitingTime;
private int deadline;
private Status status;
//getter, setter ...
}
그리고 PCB를 참조하는 Process 타입은 멀티 스레드 환경을 고려해서 Threads를 참조하며, execute 메서드를 통해서 프로세스를 실행할 수 있습니다. 자바에서는 스레드를 java.lang.Threads를 상속받아 실행할 부분을 run으로 오버라이딩하여서 사용 가능합니다. 오버라이딩한 스레드를 원하는 개수만큼 Thread의 List에 추가하였으며, execute와 executeThread를 분리해서 싱글 스레드 환경, 멀티 스레드 환경에서 실행을 분기했습니다.
다음으로, 가장 중요한 알고리즘의 구현에 앞서서 Process 간 비교를 위해서 Comparable Interface를 구현했습니다. CompareTo를 우선순위에 따라 비교하도록 overriding하였으며, 이를 통해서 아래의 Cpu Scheduler 클래스에서 우선순위 큐로 가장 대기시간이 적게 남은 프로세스를 먼저 꺼내오는 로직으로 구현했습니다.
public class Process extends Thread implements Comparable<Process> {
private PCB pcb;
private List<Thread> threads = new ArrayList<>();
Process(String processId, int runningTime, int deadline) {
pcb = new PCB(processId, runningTime, deadline);
}
//Java.lang.Threads로 멀티 스레드로 실행할 메서드 Overriding
public void initThread() {
int threadNumbers = pcb.getRunningTime() / 2;
for (int i = 0; i<threadNumbers;i++) {
threads.add(new Thread(new Runnable() {
@Override
public void run() {
executeThread();
}
}));
}
}
//싱글 스레드 실행환경
public void execute() {
setStatus(Status.RUNNING);
pcb.incrementExecutionTime();
pcb.incrementCurrentTime();
}
//멀티 스레드 실행환경
public void executeThread() {
setStatus(Status.RUNNING);
if (pcb.getRunningTime() > pcb.getExecutionTime()) {
pcb.incrementExecutionTime();
}
if (pcb.getRunningTime() > pcb.getExecutionTime()) {
pcb.incrementExecutionTime();
}
}
//Priority Queue에서 우선순위 비교를 위한 Comparable Interface Overriding
@Override
public int compareTo(Process target) {
return (pcb.getPriority() >= target.pcb.getPriority()) ? 1 : -1;
}
}
마지막으로 Cpu Scheduler 클래스 구현입니다. Waiting Queue와 Ready Queue는 우선순위 큐로 만들어서 대기시간이 가장 짧은 프로세스가 항상 먼저 큐에서 빠져나옵니다. 프로세스는 Waiting Queue -> Ready Queue -> Running -> Waiting Queue로 순서대로 순환하는 로직이며, 실행을 완료하면 Terminated 상태로 변경되어 더 이상 실행되지 않습니다. 핵심 로직이 아닌 자잘한 메서드는 가독성을 위해 생략했습니다.
public class CpuScheduler {
private PriorityQueue<Process> readyQueue = new PriorityQueue<>(); //준비 Queue
private PriorityQueue<Process> waitingQueue = new PriorityQueue<>(); //입출력 대기 Queue
private List<Process> executionProcessList = new ArrayList<>(); //출력을 위한 프로세스 list
public void run(List<Process> processList) {
executionProcessList = initRandomProcess(processList);
queueReady();
initThreads();
display();
while (true) {
// waiting Queue에 모든 프로세스를 줄세운다.
queueWaiting();
// 모든 프로세스가 실행 완료되었는지 검사한다.
if (waitingQueue.isEmpty()) {
break;
}
//우선 순위 대기의 첫 번째 원소를 뽑는다.
Process waitingProcess = waitingQueue.poll();
//최근에 실행한 프로세스인데, 대기 큐에 다른 프로세스가 있을 때, 다른 프로세스를 먼저 실행
if (!waitingQueue.isEmpty() && waitingProcess.equals(recentExecution)) {
waitingProcess = waitingQueue.poll();
//다시 집어넣기
waitingQueue.add(recentExecution);
}
//준비 큐에 집어넣기
readyQueue.add(waitingProcess);
Process currentProcess = readyQueue.poll();
//프로세스를 실행한다.
if (threadOption.equals(ThreadOption.SINGLE_THREAD)) {
currentProcess.execute();
}
if (threadOption.equals(ThreadOption.MULTI_THREAD)) {
currentProcess.startThreads();
}
//나머지 프로세스의 대기시간 증가
doWait();
//프로세스 상태를 출력한다.
display();
currentProcess.terminateOrWait();
//실행된 프로세스가 종료되지 않았으면 다시 대기 큐에 추가한다.
if (!currentProcess.isTerminated()) {
waitingQueue.add(currentProcess);
}
// 최근 실행 프로세스를 기억한다.
recentExecution = currentProcess;
}
display();
showStatistics();
}
}
이상으로, 프로세스와 스레드의 개념, 스케줄러 알고리즘을 살펴보았고 CPU 스케줄러를 구현해보는 예제였습니다.
'Computer Science > 운영체제' 카테고리의 다른 글
| 반효경 운영체제 - 6. DeadLock (1) | 2023.05.08 |
|---|---|
| 반효경 운영체제 - 5. Process Synchronization (0) | 2023.05.07 |
| 반효경 운영체제 - 4. CPU Scheduling (0) | 2023.01.15 |
| 반효경 운영체제 - 3. 프로세스 관리 (0) | 2023.01.08 |
| 반효경 운영체제 - 2.2 쓰레드 (0) | 2023.01.04 |
