[운영체제] CPU 스케줄링, 프로세스 상태, CPU 스케줄링 기법

728x90

CPU 스케줄링

<여기서 설명하는 CPU 스케줄링은 단일 처리 시스템에서의 스케줄링이다. - 싱글코어라는 뜻임>

준비 상태의 프로세스들이 순서에 따라 CPU를 할당 받으면 실행 상태가 되는데

이때 CPU를 누구한테 먼저 줄 것인지 순서를 정하는 것을 CPU 스케줄링이라고 한다.

다양한 기준과 방식들이 있겠지?

여기서 조금 하나 먼저 짚고 들어갈 것은 다중 프로그래밍은 하나의 메모리에 올라가 있는 여러 프로세스에게 CPU가 할당되는 거니까,

어떤 하나의 프로세스가 완전히 끝나버리고 -> 그 다음 프로세스가 처리되는 게 아니라는 점이다. (FIFO기법상 그럴수도..?)

그렇다면, 여기서 CPU를 스케줄링의 단위는 바로 스레드인 것을 알 수 있다.

프로세스는 CPU 할당 단위이고, 프로세스보다 더 작은 단위인 스레드가 CPU 스케줄링 단위인 것이다.

결과적으로, 스레드가 CPU를 할당 받는데 중요한 단위가 된다고 볼 수 있지 않을까? 아닌가? 아닌가요..?

헷갈령..

그렇다면 왜 스케줄링을 하는 건데?

전체적으로 시스템의 성능을 높이기 위해서!!!!!!

결론, 성능이 좋다는 건 CPU 이용률이 높고, 처리량이 많다.

성능이 안좋다는 건 소요시간/대기시간/응답시간이 길다는 것

프로세스의 상태

여튼, CPU 스케줄링을 알아보기 전에 프로세스에는 다양한 상태가 존재한다는 것부터 알아야 한다.

프로세스에는 [ 생성, 준비, 실행, 대기, 보류준비, 보류대기, 종료 ] 요론 상태들이 있는데,

이 상태가 어디에 저장이 되냐면, 문맥교환을 할 때 각각의 프로세스가 메모리에 올려둔 PCB에 저장되어서 알 수 있다.

참고로, PCB(운체의 커널영역에 저장 - 커널은 메모리에 올라간 운체의 중추!)에는 아래와 같은 내용을 저장한다.
프로세스 번호
프로세스 상태
프로세스 우선순위 : 스케줄링에 사용됨
프로세스 카운터 값 : 스레드에게 부여되는 Program Counter 값 (어느 명령어부터 실행하면 됨?~?)
메모리 포인터 : 프로그램/데이터가 저장되어 있는 메모리 블록 위치
문맥데이터
할당받은 자원들에 대한 목록
계정정보
입출력 정보

여하튼, PCB에 프로세스 상태가 저장된다는 것을 알고, 그것에 따라서 이제 CPU는

아 1번 프로세스가 문맥교환을 통해서 다시 CPU를 할당 받았을 때 어떤 상태인지 파악을 하겠쥐..?

여튼! 여기서 프로세스의 상태에 대해서 알아볼 건데,,,

1) 생성

PCB가 만들어져서 프로세스가 만들어진 다음 준비/보류준비로 넘어가기 전 단계

if 메모리 공간 충분 -> 준비
else -> 보류준비

2) 준비 [활성상태 - 메모리 부여받음]

CPU만 받아봐.. 어? 나 진짜 바로 실행 때려? 같은 상태

다중 프로그래밍이니까, 메모리 하나에 여러개의 프로세스들이 있어서 CPU를 할당받으려면 Ready Queue에서 기다려야 됨

CPU 스케줄링에 의해서, 순서에 따라 CPU를 할당받을 예정임

3) 실행 [활성상태 - 메모리 부여받음]

CPU 할당받아서 실행 중인 상태 / 할당하는 걸 Dispatch

CPU가 여러개면 동시에 여러개의 프로세스가 실행 가능함 = 다중처리 (싱글코어 아닌 멀티코어 like 쿼드코어..)

하나의 메모리에 여러개의 프로세스 = 다중프로그래밍

✔️뺏기는 이유는

1. timeout [ 뺏기면 -> 준비상태 ]

2. 입출력이 필요해서 [ 뺏기면 -> 대기상태 ]

Q. 왜 입출력은 대기상태일까? 바로 준비/실행은 안되나?

약간 이 맥락이라고 보면 된다.
버스 타려고 기다리고 있는데 (준비상태) 갑자기 딴 일하다가 늦게 온 사람이 (입출력하다가 온 프로세스) 지금 타려는 사람을 (실행) 밀치고 타는 바이브

A. 중요도의 차등 + 동급인 경우, 공평하게 대우하기 위한 운영체제의 노력

4) 대기 [활성상태 - 메모리 부여받음]

실행되다가 입출력 처리를 요청하거나 / 바로 확보될 수 없는 자원을 요청하면 CPU 양도하고 요청한 일이 완료되기까지 대기

이때도, Queue에서 관리되다가 - 요청한 일이 완료되면 Ready Queue에서 기다리며 실행되기를 기다림

[활성상태 - 메모리 부여받음]
활성상태에 있는 프로세스들을 메모리 부족 등의 이유로 메모리를 회수할 경우, 보류시킨다고 부른다.

(보류)

한정된 메모리 공간에서 잠시 메모리 회수해도 괜찮을 프로세스는 보류시킨다.

회수되면 디스크로 프로세스가 쫓겨나겠지

이걸 우리는 Swapped Out && 다시 메모리에 올라오는 건 Swapped In === 통틀어서 Swapping

Q. 보류가 필요한 이유?

A1. 메모리 여유가 없는데 엄청나게 무지막지하게 중요한 프로세스가 갑자기 막 나타났어
EX1. 내가 팔이 빠져서 응급실에 가서 마지막 배드를 차지했음, 근데 갑자기 동맥출혈 환자가 온 경우

A2. 메모리 내의 모든 프로세스가 다 입출력 중이라 CPU가 쉬고 있어, 그렇다면 효율을 위해 현재 대기 중인 CPU가 필요없는 프로세스는 보류시키고, 새로운 프로세스에게 CPU 주기
EX2. 미용실 손님들이 죄다 펌 손님이라 당장은 미용사가 뭘 해주지 않아도 돼, 근데 군입대하려고 머리 밀러온 남자애가 온 경우

즉, 메모리 공간 확보가 1차적인 이유
+ 시스템에 오류 / 위해가 있을 수상한 행동 등..

5) 보류준비 [메모리X]

- 생성된 프로세스가 바로 메모리 받지 못한 경우

- 준비/실행 상태에서 메모리를 잃게 될 경우

- 실행 상태의 프로세스가 CPU 반납하면서 준비 상태로 바뀔 때 메모리 공간까지 잃어야 하는 경우

6) 보류대기 [메모리X]

- 대기 상태일 때 메모리 공간을 잃은 상태

- 근데 특별한 경우가 아니라면, 보류대기 상태의 프로세스는 입출력/요청 끝나면 보류준비 상태가 된다.

대기 (실행되다가 입출력 처리를 요청하거나 / 바로 확보될 수 없는 자원을 요청하면 CPU 양도하고 요청한 일이 완료되기까지 대기)

7) 종료

할당된 모든 자원이 회수되고 PCB만 커널에 남아있음

운영체제가 PCB를 삭제하면 프로세스가 완전히 사라지게 된다.

프로세스를 스케줄링하기 위한 큐

프로세스들은 큐들을 오가며 수행된다.

1. Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합 (Ready, Device queue도 포함)

2. Ready Queue : 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합

3. Device Queue : 입출력 장치의 처리를 기다리는 프로세스의 집합

처리과정이 어떻게 되냐면,,,

1. 프로그램이 시작되면 Ready Queue에 와서 줄을 서게 된다.

2. 자기 차례가 되면 CPU를 얻고, 얻은 상황에서 작업을 처리하다가

3. Timer가 다 되면 다시 Ready Queue에 와서 줄을 서고,

4. CPU를 가지고 있다가 오래 걸리는 작업을 수행하면 해당하는 작업의 큐에 가서 줄을 서서 기다린다.

5. 다 끝나면 Queue를 빠져나간다.

스케줄링의 단계

수행단계에 따라서 장기/중기/단기로 나뉜다.

스케줄러 : 시스템 안에서 각각의 자원 별로 이번에 무엇을 하고, 다음에는 무엇을 하는지 알려주는 역할을 한다.

1). 단기 스케줄러 aka CPU Scheduler or Dispatcher

어떤 프로세스에게 CPU를 주는지에 대한

즉, 준비단계에서 실행단계로 갈 프로세스를 결정하는 것

단기 스케줄러가 가동되는 이유로는 입출력/timeout interrupt/system call 등이 있고,

횟수도 매우 잦아서 한 번 실행 시 드는 시간을 최대한 줄이는 것이 중요하다.

이게 결국 문맥교환임!!!!

문맥교환은 CPU를 한 프로세스에서 다른 프로세스로 넘겨주는 과정인데

CPU를 내어주는 프로세스 상태의 문맥을 해당 프로세스의 PCB에 저장하고,

CPU를 새롭게 얻는 프로세스의 상태의 문맥을 해당 프로세스의 PCB에서 읽어온다.

근데, 시스템 콜이나 인터럽트 발생 시에 반드시 문맥 교환이 일어나는 것은 아니고, CPU 제어권이 다른 프로세스로 넘어간 경우에만 해당된다. CPU 제어권이 한 프로세스 내의 사용자 모드에서 운영체제에게 넘어가 커널 모드로 변경된 경우에는 해당되지 않는다는 말이다.

문맥교환이 발생 시에는 캐시 메모리를 다 지워야 해서 오버 헤드가 상당하다.

2). 장기 스케줄러 aka Job Scheduler

준비상태의 프로세스 중 어떤 프로세스에게 메모리를 주는지에 대한

메모리를 준다? = 프로세스로 만든다.

- 다중 프로그래밍의 정도를 조절하겠지?

- 횟수가 적으면 FIFO / 프로세스 성격 반영해서 우선순위 방식 사용 가능

- 속도가 느려서 실행 빈도수가 적다.

3). 중기 스케줄러 aka Swapper

보류상태의 프로세스 중 어떤 프로세스에게 메모리를 주는지에 대한

swapped out -> swapped in

But, 지금의 시스템은 장기 스케줄러는 없다.
왜냐하면 요새는 시분할 시스템이니까.
대신 중기 스케줄러가 다중 프로그래밍의 정도를 제어한다.

Q. 왜 중기 스케줄러가 더 이득이냐?
A. 메모리 공간이 부족한데,
지금 생성된 프로세스가 더 중요해서 반드시 메모리를 줘야 하는 경우에 메모리 공간에 있는 프로세스를 쫓아내는 게 좋다.

다시 CPU 스케줄링으로 돌아와서!목적에 맞게 스케줄링 정책을 만들 때 고려해야 하는 몇 가지 기준 중

< 프로세스의 성격 >

CPU를 사용하는 연산 > 입출력 = 연산위주 CPU-bound 프로세스

CPU를 사용하는 연산 < 입출력 = 입출력위주 I/O-bound 프로세스

여튼! CPU의 Path는 CPU를 실행하는 경우(CPU bound) + 입출력을 실행하는 경우(I/O bound)가 반복해서 연결지어서 나타남

- 사람들이 사용하는 프로그램의 경우, CPU bound + I/O bound가 자주 반복되어 나타남

- I/O bound의 경우(사람들과의 인터렉션이 많은 경우), CPU를 우선적으로 주는 것이 필요하다. (공평보다 효율성이 좋음)

interactive job이 너무 오래 기다리지 않게 하는 것 => 기억해 사용자들은 빨리빨리의 민족임

- I/O bound 프로세스는 CPU를 짧게 자주 쓴다.

- CPU bound 프로세스는 CPU를 많이 오래 쓴다.

이렇게 대부분의 시스템에는 두 종류의 프로세스가 섞여있음

목적에 따라서 어떤 종류의 프로세스를 우대할 건지 생각해야함

1. 응답시간?

2. 처리량?

3. 프로세스 크고작음? *여기서 크기는 CPU 실행시간

등등.. 고민해봐야 함

스케줄링 기법

🔆 언제 스케줄링이 가동되어야 하나?

1️⃣ 실행 -> 대기 (입출력요청)

2️⃣ 실행 -> 준비 (timeout interrupt)

3️⃣ 대기 -> 준비 (입출력종료 like 버스 새치기 금지)

4️⃣ 수행 후 종료

비선점 스케줄링 1️⃣4️⃣ = 자발적

스스로 CPU를 반납할 때까지 계속 사용하도록 허용

선점 스케줄링 2️⃣3️⃣ = 비자발적

프로세스로부터 CPU를 빼앗는 방식

ex). 우선순위가 더 높은 프로세스가 생성된 경우

⭐️ CPU 요구량 == 프로세스의 완료를 위해 요구되는 CPU 시간의 양 == 프로세스의 크기

FCFS 비선점

First Come First Service = FIFO

먼저 도착한 프로세스에게 먼저 CPU 할당

- 😊 언제 실행되는지 예층 가능, 공평

- 😱 대화식 시스템에 적합X : Cuz, 긴 프로세스가 먼저 도착할 경우, 뒤에 도착한 프로세스는 오랜 시간 대기해야 함

도착순서 : P1 P2 P3 P4 | 완료순서 : P1 P2 P3 P4

평균 응답 시간 = (100+110+120+130)/4 = 115

평균 응답 시간 = (10+20+30+130)/4 = 47.5

평균 응답 시간이 짧다고 해서 모든 프로세스의 응답 시간이 짧아지는 것은 아니지만
보편적으로 그럴 확률을 높일 수 있으니

평균 응답 시간을 줄이기 위한 노력은 필요하다!

SPN = SJF 비선점

Shortest Process Next / Shortest Job First

Ready Queue에서 기다리고 있는 프로세스 중에서 CPU 요구량이 가장 적은 것을 먼저 실행

- 😊 평균 응답 시간 최소화

- 😱 Starvation : 실행시간이 긴 프로세스는 무한 대기 현상 발생

[해결법] Aging - 기다린 시간만큼 우선순위를 높여주는 것 ex. HRRN 기법

- 😱 프로세스의 크기를 실행 전에는 정확히 알 수 없는데 그 크기로 스케줄

[해결법] 지수평균 - 예전에 실행됐을 때의 추정치로 이번에도 짐작해서 스케줄

프로세스 실행 순서 : P1 P3 P2

평균 응답 시간 = (10 + 16.5 + 11)/3 = 12.5

SRT 선점

Shortest Remaining Time

Ready Queue에서 완료까지 남은 CPU 요구량이 가장 짧은 것을 먼저 실행

만약, 실행 도중 남은 실행 시간이 더 적은 프로세스가 들어올 경우, CPU 뺏어서 할당해줌

- 😊 반환시간 단축 가능

- 😱 Starvation 발생

- 😱 짧은 프로세스가 자주 도착 시에 문맥교환으로 오버헤드 발생

[해결법] 임계값 사용 : 현재 실행 중인 프로세스와 선점할 프로세스의 시간 차이가 임계값을 넘지 않으면 pass~

[해결법] Future-Knowledge 스케줄링 : 가까운 미래에 도착하게 될 프로세스의 정보를 알 수 있다면 CPU 쉬게 하자.

프로세스 실행 순서 : P1 P2 P3 P2 P1

평균 응답 시간 = (17 + 7 + 2)/3 = 8.67

HRRN 비선점

Hightest Response Ration Next

수행 시간이 긴 프로세스의 무한대기 현상을 방지하기 위한 기법

- SPN, SRT의 무한대기 현상 방지

- Ready Queue에 있는 프로세스들 중에 응답률이 가장 높은 프로세스에 높은 우선순위 부여

즉, 오래 기다린 사람 우대해준다 이거다. = 대기시간 Aging

따라서, 큰 프로세스일수록 응답률이 작아서 평균 응답 시간이 단축된다.

응답시간 : Ready Queue에 들어와서 처음 CPU를 할당받기까지의 걸리는 시간

큰 프로세스가 먼저 올 경우, 다 끝날 때까지 요구량이 작은 프로세스가 한참을 기다리니까
평균 응답 시간이 길어진다.라고 이해하겠다.

Round-Robin 선점 요즘 사용하는 기법

FCFS 기반으로 시간 할당량이 지나면 시간 종료 인터럽트에 의해 CPU를 뺏기는 방식

시간 할당량이 너무 크면, FCFS / 너무 작으면 문맥교환이 잦은 오버헤드 발생

- 😊 한 프로세스가 CPU 독점하는 것 방지

- 😱 문맥교환의 오버헤드 감수

- 😱 대화식 시스템, 시분할 시스템에 적합한 방식 (빠르게 모든 프로세스에게 조금조금씩 분할)

프로세스 실행 순서 : P1 -> P2 -> P3 -> P4

온 순서대로 실행된다.

평균 응답 시간 : (63 + 18 + 53 + 38)/4 = 43

부가적으로, 입출력보다 연산 프로세스가 더 우대받는다.
연산 위주 : 모든 시간 할당량을 소진 후 준비 큐의 맨 뒤로 돌아감
입출력 위주 : 대부분 시간 할당량을 남긴 채 준비 큐의 맨 뒤로 돌아감

if 입출력 위주 프로세스가 시간 할당량 다 채우면 -> 기존 준비 큐로 들어감
else if 다 못 채우고 남기면 -> 2번의 준비 큐로 들어감
- 준비 큐(그림에서 2번)를 따로 두고, 남은 시간 할당량만큼만 주도록 한다.

1번과 2번 큐의 우선순위는 다르다. 2번의 우선순위가 좀 더 높다.
2번의 큐가 있는 경우, 가상 라운드 로빈!

우선순위 스케줄링 대부분 선점

우선순위가 높은 프로세스에게 CPU를 준다.

- 선점 : 뺏어서 준다.

- 비선점 : 온다고 바로 뺏지 않는다.

근데 우선순위 스케줄링 속성상 높은 우선순위가 오면 대부분 해당 프로세스에게 CPU를 주기 때문에

대부분 선점 방식이 많다.

- 정적 : 프로세스가 생성될 때 부여된 우선순위가 완료 때까지 변하지 않는 값일 경우

- 동적 : 시스템에 있는 동안 조정되도록 할 경우

Multi-level Queue (다단계 큐) 선점

정적 우선순위(큐들 간에 프로세스 이동 불가능)를 사용하는 스케줄링 구현 시 적합

같은 우선순위 값을 가지는 프로세스들을 위해 큐가 필요하고

동시에 서로 다른 우선순위의 프로세스들을 구별하고 관리하기 위해 우선순위의 개수만큼 큐가 필요하다.

- 자신들의 우선순위 값에 해당하는 큐에 들어감

- 계급으로 우선순위를 나누는 것

1. 시스템 프로세스

2. 사람과 인터렉트하는 프로세스

- 우선순위가 낮은 하위 단계 큐가 실행 중이더라도 상위 단계 큐에 프로세스가 도착하면 CPU 뺏김

각각의 큐는 독립적인 알고리즘을 선택함

- 사람과 상호작용이 있는 프로세스에 해당 시 : foreground + RR (빠른 응답이 필요해서)

- 계산 위주의 프로세스에 해당 시 : background + FCFS

여러개의 큐가 있기 때문에 어느 큐에게 CPU를 주고, 그 큐 내에서도 어떤 프로세스에게 CPU를 줄 건지?
1. 고정 우선순위 방식 - foreground 우선시하고 비어있는 경우에만 background 큐에 할당, starvation 가능
2. time slice 방식 - 각 큐에 CPU를 적절히 할당, 80%는 우선순위가 높은 곳, 20%는 낮은 곳에 할당

Multi-level Feedback Queue, MFQ (다단계 큐) 선점

- 동적 우선순위 기반

- 여러 단계의 큐가 있고, 각 단계마다 서로 다른 CPU 시간 할당량을 가진다.

- 우선순위가 높은 단계일수록 시간 할당량은 작다.

- 중간 단계의 큐는 앞 상위 큐가 비어있을 경우에만 CPU를 받을 수 있다.

- 시간 할당량 도중에는 CPU를 선점 당하지 않는다.

동작방식은
1. 새로운 프로세스가 들어오면 최상위 큐에 들어가 FCFS 기법으로 실행
2. 시간 할당량이 끝나면 한 단계 아래 준비 큐로 들어가서 우선순위가 한 단계 낮아짐
3. 그 다음 단계 큐에서도 시간 할당량이 끝나면 그 아래 큐로 들어감
4. 마지막 단계에서는 더 내려갈 단계가 없어서 RR 방식으로 실행

만약, 시간 할당량이 다 끝나기 전에 입출력으로 인해 CPU를 뺏기면 다시 준비 상태가 됐을 때,
한단계 위의 큐에 들어가게 해서 우선순위를 높인다.

즉, 입출력은 우선순위를 높여주기 때문에 입출력 프로세스가 선호됨을 알 수 있다.
즉, 프로세스 성격에 맞게 우선순위를 조정해줘서 적응성이 있는 스케줄링이 가능하다.

덕분에 CPU 요구량을 몰라도 짧은 프로세스들에게 유리하면서 입출력 프로세스를 우대할 수 있다.

Fair-share

위 기법들은 다 모든 프로세스들을 하나의 그룹으로 취급했다.

Fair-share는 중요도 및 특성에 따라 그룹으로 나누고, 각각의 그룹에 일정량의 CPU를 할애하는 방식이다.

스케줄링 기법을 뭘 사용하든 그룹별로 일정량의 CPU 시간을 할애했을 때,

특정 그룹에 속한 프로세스의 과도한 CPU 사용은 그 그룹내의 다른 프로세스에게만 영향을 주고, 다른 그룹으로는 파급되지 않는다.

실시간 스케줄링 Realtime 선점

실시간 시스템은 실행될 모든 프로세스들이 정해진 시간 내에 완료되어야 하는 걸 말한다.

만약, 작업이 마감시한 내에 종료되지 X

- 경성 실시간 시스템 : 시스템이 중지되는 결과 초래

- 연성 실시간 시스템 : 데이터 손실의 피해는 있지만, 계속해서 운영 가능한 시스템

일반적으로 실시간은 경성을 의미한다.

정적인 방법 : 프로세스들의 특징/개수 알 수 있는 경우에 사용 ex).RM Rate Monotonic 선점, 정적 실시간 스케줄링

동적인 방법 : 알 수 없는 경우에 사용 ex). EDF Earliest Deadline First 선점, 동적 실시간 스케줄링

실시간으로 운영되는 환경은 대부분 특수해서 성격/개수를 사전에 알 수 있는 게 많다.

결론, Round-Robin 제일 깔쌈하고 + SRT 젤 양아취~