[OS] CPU Scheduler

단기, 중기, 장기 스케쥴러

장기 스케쥴러

디스크에서 새로운 프로세스를 가져와 준비 상태로 만들어 놓는 역할만 수행

시작 프로세스중 어떤것을 ready queue로 보낼지 결정
프로세스에 memory(및 각종자원)을 주는 문제
메모리에 올라가는 프로그램 수를 제어

 

중기 스케쥴러

실행 가능한 프로세스를 선택하여 메모리에 로드

메모리 관리와 같은 중요한 운영 체제 리소스의 할당을 관리

ex. 페이지 교체 알고리즘이 있습니다.

 

단기 스케쥴러: 어떤 프로세스를 대기상태로 보낼지, cpu를 할당할지 정함
어떤 process를 다음번에 running 시킬지를 결정
프로세스에 cpu를 주는 문제.
충분히 빨라야한다.
즉, 단기 스케줄러의 실행 빈도가 높습니다. 단기 스케줄러는 이벤트가 발생할 때마다 호출됩니다.

 

실행 가능한 프로세스 중에서 CPU를 할당합니다.

프로세스의 실행 순서를 결정하고, CPU의 자원을 효율적으로 사용할 수 있도록 돕는다.

ex.Round Robin, FCFS(First-Come, First-Served), SJF(Shortest Job First) 등의 알고리즘

 

 

*현대 OS에는 단기, 중기, 장기 스케쥴러를 모두 사용하고 있나요?

현대 운영 체제에서는 time sharing system을 사용하여 장기 스케줄러를 대부분 사용하지 않습니다. 

time sharing system에는 보통 장기스케쥴러를 안쓴다 -> 지금은 program 시작시 바로 memory에 올려서 ready로 들어간다.
: 메모리에 너무 많은 program이 동시에 올라가면 문제가 되어 중기 스케쥴러를 사용한다.

 

* time sharing system

현대 운영 체제에서는 여러 사용자가 동시에 컴퓨터를 사용하고, 각 사용자가 실행하는 프로그램도 많아졌기 때문에,

CPU 시간을 한 프로세스에만 할당하는 것은 비효율적 -> 여러 개의 프로세스를 생성하여 CPU를 공유 -> 다른 프로그램도 실행할 수 있도록 함

이를 가능하게 하는 것이 time sharing system입니다. 운영 체제는 각 프로세스에 일정 시간 동안 CPU를 할당하고, 해당 시간이 지나면 다른 프로세스에게 CPU를 넘겨주어 다른 작업도 처리할 수 있도록 합니다. 이렇게 여러 프로세스가 동시에 실행되면서 시스템 자원을 효율적으로 활용할 수 있습니다.

 

장점

- 여러 프로세스가 동시에 실행되면서 시스템 자원을 효율적으로 활용

- 프로세스 간의 우선순위를 조정하여 우선순위가 높은 프로세스가 먼저 실행

 

 

프로세스의 스케쥴링 상태

New : 프로세스가 생성된 상태이며, 운영체제가 아직 할당되지 않은 자원을 가지고 있습니다.

Ready : 프로세스가 실행을 기다리는 상태이며, 운영체제가 필요한 자원을 할당하여 실행 가능한 상태가 됩니다.

Running : 프로세스가 CPU를 사용하여 실행되는 상태이며, CPU 시간을 할당 받아 작업을 수행합니다.

Blocked : 프로세스가 실행을 중지하고, 특정 이벤트가 발생하기를 기다리는 상태입니다. 이벤트는 주로 입출력(IO) 작업과 같은 외부 요청입니다.

Terminated : 프로세스가 완전히 종료되어 더 이상 실행되지 않는 상태입니다.

 

 

 

*Memory가 부족할 경우, Process는 어떠한 상태로 변화할까요?

 

만약 시스템에 충분한 메모리가 없으면, 프로세스는 다음과 같은 상태로 변화할 수 있습니다.

Swapping : 운영체제는 현재 메모리에 올라와 있는 프로세스를 디스크의 스왑 공간으로 이동시킵니다. 이러한 과정을 스왑아웃(Swap Out)이라고 합니다.

Blocked : 메모리가 부족해 프로세스가 필요한 데이터를 가져올 수 없는 경우, 프로세스는 블록(Block) 상태가 됩니다. 이 경우, 프로세스는 다른 프로세스가 실행되는 동안 대기합니다.

Terminated : 메모리가 부족한 상황에서도 계속해서 프로세스를 실행할 수 없는 경우, 운영체제는 해당 프로세스를 강제로 종료시킵니다.

메모리가 부족한 상황에서는 운영체제의 스왑 메커니즘이나 메모리 관리 정책에 따라 프로세스의 상태가 변할 수 있습니다. 이러한 상황을 방지하기 위해서는 운영체제가 메모리를 효율적으로 관리하고, 필요 없는 프로세스나 데이터를 적절히 정리하여 공간을 확보하는 것이 중요합니다.

 

 

스케쥴러란?

CPU burst

CPU Burst는 프로세스가 CPU를 사용하여 연산을 수행하는 시간을 의미합니다. 예를 들어, 계산, 비교, 논리 연산 등의 작업이 CPU를 사용하는 작업으로, CPU Burst는 이러한 작업을 수행하는 시간을 나타냅니다. CPU Burst의 길이는 프로세스의 특성에 따라 다르며, 짧은 CPU Burst와 긴 CPU Burst가 번갈아 나타나는 형태로 나타납니다.

 

I/O burst

I/O Burst는 프로세스가 입출력(I/O) 장치를 사용하여 데이터를 읽거나 쓰는 등의 작업을 수행하는 시간을 의미합니다. 예를 들어, 디스크에서 파일을 읽는 작업이나, 프린터로 출력하는 작업 등이 I/O Burst의 예시입니다. I/O Burst는 CPU Burst와 반대로 프로세스의 특성에 따라 상대적으로 길게 나타납니다.

ex.I/O Burst는 CPU Burst와 반대로, 프로세스가 CPU에서 실행되지 않고 대기 상태에서 I/O 작업을 수행하며 상대적으로 길게 나타나는 특성을 가지고 있습니다. 이는 프로세스의 입출력 작업이 빈번하게 발생하는 경우에 특히 두드러지게 나타납니다.

예를 들어, 파일을 읽어들이는 작업을 수행하는 프로세스의 경우, 디스크에서 데이터를 읽어들이는 동안 CPU를 사용하지 않기 때문에 CPU Burst가 짧고, 그에 비해 I/O Burst가 길어지는 경향이 있습니다. 따라서, 운영체제는 이러한 특성을 고려하여 프로세스의 스케줄링을 수행하며, I/O 작업이 빈번하게 발생하는 프로세스에 대해서는 I/O 관련된 스케줄링 알고리즘을 적용할 수도 있습니다.

 

프로세스 실행주기

프로세스는 CPU Burst와 I/O Burst를 번갈아 수행하면서 실행됩니다. 예를 들어, CPU Burst를 수행한 후 I/O 작업을 수행하는 동안 CPU는 유휴 상태가 되며, I/O 작업이 완료되면 다시 CPU Burst를 수행하게 됩니다. 이러한 과정을 프로세스의 실행 주기(cycle)라고 합니다

 

 

왜 프로세스 실행주기를 지켜야 할까?

일반적으로 프로세스가 CPU에서 실행되는 동안 I/O 작업을 수행하게 되면 CPU는 해당 작업이 완료될 때까지 대기해야 함

일반적으로 I/O 작업은 CPU가 처리할 수 없는 외부 장치와의 상호작용을 의미합니다. 예를 들어, 파일을 디스크에 저장하는 경우, 디스크는 CPU가 직접 제어할 수 없는 외부 장치입니다. 마찬가지로, 네트워크 통신은 외부 장치와의 상호작용을 필요로 합니다.

ex.네트워크 통신이 있습니다. 예를 들어, 웹 브라우저에서 웹 페이지를 요청하는 경우, 프로세스는 네트워크를 통해 데이터를 요청하고 해당 데이터가 수신될 때까지 대기합니다. 이 경우 CPU는 다른 작업을 수행할 수 있지만, 데이터 수신이 완료되기 전에 결과를 처리할 수 없습니다.

 

 

왜 결과처리를 I/O가 할까?

일반적으로 I/O 작업은 CPU가 처리할 수 없는 외부 장치와의 상호작용을 의미합니다. 예를 들어, 파일을 디스크에 저장하는 경우, 디스크는 CPU가 직접 제어할 수 없는 외부 장치입니다. 마찬가지로, 네트워크 통신은 외부 장치와의 상호작용을 필요로 합니다.

따라서 I/O 작업을 처리하는 것은 CPU가 아닌 I/O 장치의 역할입니다. I/O 작업이 완료되면, I/O 장치는 그 결과를 CPU에게 알리고, CPU는 이를 처리하여 결과를 화면에 출력하거나 다른 작업을 수행합니다.

즉, CPU는 I/O 작업이 완료될 때까지 대기하고, I/O 장치는 I/O 작업을 수행하여 결과를 생성하고, 완료되면 CPU에게 알리는 역할을 합니다. 이를 통해 시스템이 외부 장치와 상호작용하여 데이터를 처리할 수 있습니다.

 

 

CPU 스케줄러

CPU 스케줄러는 준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할 지 결정하는운영체제의 코드이다.

 

CPU 스케줄러가 필요한 경우

Running → Blocked (ex. I/O 요청하는 시스템 콜)

Running → Running (ex. 할당 시간 만료로 인한 타이머 인터럽트)

Blocked → Ready (ex. I/O 완료 후 인터럽트)

Terminated

 

 

Waiting Time / Response Time이란?

Waiting Time : CPU를 얻었다가 뺐겼다가 줄서서 기다리는 모든 시간을 모두 합친것

Response Time : ReadyQueue에 들어와서 처음으로 CPU로 얻기까지의 기다린 최초의 시간

 

 

burst time이란?

버스트 시간은 프로세스가 CPU에서 실행하는 데 걸리는 총 시간이다.

 

 

 

 

preemptive/non-preemptive

- preemptive

현재 실행중인 프로세스를 중단시키고 다른 프로세스가 CPU를 점유할 수 있도록 하는 방식

 

단점

우선 순위가 높은 프로세스를 빠르게 처리할 수 있지만 상황에 따라 잦은 컨텍스트 스위칭으로 오버헤드가 발생할 수 있습니다.

ex.SRTF,RR,스케줄링 우선순위(Scheduling Priority(priority = 다음 cpu burst time을 예))

-non-preemptive

현재 프로세스가 작업을 종료하고 CPU를 반환할때까지 다른 프로세스가 CPU를 점유할 수 없는 방식

 

단점

Burst time이 긴 프로세스가 종료될때까지 다른 프로세스들이 대기해야 되기 때문에 처리율이 떨어질 수 있고 우선 순위가 높은 프로세스가 대기해야 되는 문제점이 있다.
ex.SJF,MLFQ와 FCFS,최대 우선순위 처리(Highest Priority First)

 

*preemptive/non-preemptive 에서 존재할 수 없는 상태가 있을까요?

-네, 존재합니다. 예를 들어 블록 상태가 있습니다. 블록 상태는 작업 실행이 불가능한 상태로, 작업이 사전 정의된 다른 작업이 완료될 때까지 수행이 중지되는 상태입니다. 따라서 블록 상태는 preemptive 및 non-preemptive 스케줄링 모두에 존재할 수 없습니다.

 

 

 

 

 

 프로세스 스케줄링 알고리즘

 - FCFS(FirstComeFirstServoce 

 -> SJF(ShortestJobFirst) : CPU를 짧게 쓰는 Process에게 먼저 CPU를 할당한다 (기아현상 발생)

 -> SRTF(Preemptive 방식: shortest Remaining time first)으로 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착시 CPU를 빼앗김 (기아현상 발생)

-> RR

: RR은 한 프로세스에게 일정 시간만큼 CPU를 할당하고, 할당 시간이 지나면 강제로 다른 프로세스에게 일정 시간 만큼 CPU를 할당하는 방식이다. 강제로 CPU를 뺏긴 프로세스는 큐의 가장 뒷부분으로 밀려난다.

 

*Round Robin에서 '오버헤드가 너무 크다'라는 말이 뜻하는 바는?

RR 알고리즘 성능은 타임 슬라이스 값에 따라 크게 달라지는데, 여기서 타임 슬라이스는 프로세스가 할당 받은 시간을 의미한다. 이때 타임 슬라이스를 너무 적게 설정하면 컨텍스트 스위칭이 자주 일어나게 되고, 타임 슬라이스에서 실행되는 프로세스의 처리량보다 컨텍스트 스위칭을 처리하는 양이 훨씬 커져서 비효율적이다. 이런 상황을 '오버헤드가 너무 크다'고 말한다.

 

 

*기아현상이란?

상대적으로 높은 우선순위를 갖지 못하는 프로세스가 계속해서 높은 우선순위를 갖지못해서 거의 영원히 실행되지 못하는 현상

 

*Aging이란?(기아현상 해결법)

기다리는 시간이 길어지면 우선순위를 조금씩 높여, 언젠가는 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 해주는 방법

 

 

 

 

 

 

싱글 스레드 CPU 에서 상시로 돌아가야 하는 프로세스가 있다면, 어떤 스케쥴링 알고리즘을 사용하는 것이 좋을까요? 또 왜 그럴까요?

동시성과 병렬성의 차이에 대해 설명해 주세요.

타 스케쥴러와 비교하여, Multi-level Feedback Queue는 어떤 문제점들을 해결한다고 볼 수 있을까요?

https://steady-coding.tistory.com/530