[OS] CPU 스케줄링 알고리즘 / 프로그램 vs 프로세스 vs 스레드

 

스터디에서 운영체제를 공부하며 정처기 공부 시 무작정 외웠던 내용들이 아,,, 이런 내용들이었구나 라고 이제서야 조금씩 알게 되는 시간이었다. 아는만큼 보인다고 정처기를 제일 처음 아무 것도 모르던 시절(올해 초) 봤을 때는 정말 검은 건 글씨요, 하얀 건 종이로다...하는 마음으로 봤다. 

 

이번에 실기 준비를 하며 봤을 때 프로젝트 준비때문에 비록 정말 짧고 급하게 보긴 했지만 어느정도 학습이 된 후 봐서 그런지 (컴퓨터와 친해졌나보다) 익숙한 용어들도 많았고 재미있지는 않았지만 그래도 그렇구나 하고 넘어갈 수 있었다.

 

그리고 이제 이렇게 보니 아~! 이게 이런 거였고 이럴 때 일어나는 거구나 를 알게 되었다. 

 

컴퓨터 사이언스 나름.. 재밌을지도? 를 몇 번이나 외쳤던 네트워크와 운영체제였다.ㅋㅋㅋ (베프 되기까지는 아직 오래 더 봐야 할 듯 하다 😋) 아무튼 스터디 덕분에 깊이 알 수 있어서 그리고 서로 모르는 부분에 대해 채워줄 수 있어서 좋다.

 

---

 

CPU 스케줄링 알고리즘

🔵 CPU 스케줄링 알고리즘의 개념

운영체제에서 CPU 사용을 최적화하기 위해 프로세스나 스레드를 어떤 순서로 실행할지 결정하는 메커니즘이다. 여러 CPU 스케줄링 알고리즘이 있으며, 각각의 알고리즘은 특정 시스템의 요구 사항이나 환경에 따라 다르게 적용된다.

 

• 메모리에 올라온 프로세스들 중 어떤 프로세스를 먼저 처리할지 순서를 정하는 것
• Readey Queue에 있는 프로세스들 중 누구에게 CPU를 할당해 줄 것인지 정하는 것

 

프로그램 vs 프로세스 vs 스레드

프로그램이란?

✅ 컴퓨터에서 작업을 위해 실행가능한 코드의 집합으로 “정적”파일을 말한다.

✅ 보조기억장치에 저장되어 있다.

 

프로세스란?

✅ 컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램이다. 즉, 프로그램이 보조기억장치(RAM)에 로드되어 실행될 때 생성되는 동적인 인스턴스이다.

✅ 실행 중인 프로그램

✅ 운영체제가 관리하는 실행단위이다.

✅ 독립적인 메모리 영역과 시스템 리소스를 할당 받아서 사용한다.

 

스레드란?

✅ 프로세스 내에서 실행되는 독립적인 실행 흐름을 의미한다.

✅ 하나의 프로세스는 하나 이상의 스레드를 가진다. (멀티 스레드)

✅ 프로세스의 메모리를 공유하며 실행되지만 각 스레드는 자신만의 레지스터와 스텍을 가진다. (Stack 영역만 별도로 할당받고 부모 프로세스의 Code, Data, Heap 영역은 공유)

 

🔻 더 자세히 알아보기

🔗 [Inpa Dev] 완전히 정복하는 프로세스 vs 스레드 개념

🔗 https://velog.io/@gparkkii/ProgramProcessThread

 

🔵 CPU 스케줄링 의 목적

시스템 자원

• CPU, RAM, 보조기억장치, I/O장치, 버스, 시스템 콜(운영 체제의 서비스를 요청할 수 있도록 인터페이스를 제공하는 서브루틴 또는 프로그램)

프로세스의 요구

1. CPU 시간: 프로세스는 자신의 명령어를 실행하기 위해 CPU의 실행 시간을 필요로 한다.
2. 메모리: 프로세스는 자신의 코드, 데이터, 스택 등을 저장하기 위한 메모리 공간을 필요로 한다.
3. I/O 요청: 프로세스는 파일 읽기/쓰기, 네트워크 통신, 사용자와의 상호작용 등 다양한 I/O 작업을 수행할 수 있다.
4. 파일 접근: 프로세스는 특정 파일이나 데이터베이스에 대한 읽기/쓰기 접근을 요구할 수 있다.
5. 동기화: 멀티스레드 또는 병렬 처리 환경에서, 프로세스나 스레드 간의 동기화를 위해 세마포어, 뮤텍스 등의 동기화 메커니즘을 요구할 수 있다.
6. 시스템 서비스: 프로세스는 네트워크 설정, 시간 조회, 사용자 인터페이스 조작 등 다양한 시스템 서비스에 대한 요청을 할 수 있다.

 

 

🔵 스케줄링 성능 척도

1. 프로세서 차원

• CPU 사용률
• Throuhgput(처리량)

2. 프로세스 차원

• 응답시간 : 프로세스가 대기 상태에 들어와 CPU를 최초로 얻기까지 걸리는 시간
• 반환시간 : 프로세스가 생성되어 종료된 후 자원을 모두 반환하는데 걸리는 시간
• 대기 시간 : 프로세스가 CPU를 할당받기 전 대기상태일 때의 시간

 

 

🔵 스케줄링 기법

선점형 스케줄링(Preemptive)

• 다른 프로세스가 실행 중이더라도 운영체제가 CPU를 강제로 뺏을 수 있는 방식
• CPU 처리 시간이 매우 긴 프로세스가 CPU 사용 독점을 막을 수 있어 효율적인 운영이 가능
• 대기 시간을 최소화할 수 있다.
• 잦은 문맥 교환으로 오버헤드가 많이 발생한다.
• Round Robin, SRT, 다단계큐(MLQ, Multi-Level Queue), 다단계 피드백 큐(MLFQ, Multi-Level Feedback Queue)

 

비선점형 스케줄링(Non-Preemptive)

• 프로세스가 CPU를 점유하고 있다면 빼앗을 수 없는 방식
• 순서대로 처리되는 공정성 보장
• 구현이 단순하다.
• 프로세스의 실행 순서와 응답시간 예측이 가능하다. → 예상대로의 움직임은 신뢰성을 높인다. → 자원 할당, 확장, 백업 등의 계획에 있어서 유용하다.
• → 사용자 요청에 대한 응답 시간을 보다 정확히 예측 가능하며 문제 발생 시 원인 파악 및 해결이 쉽다.
• 낮은 문맥 교환으로 오버헤드가 작다.
• CPU 사용시간이 짧은 여러 프로세스가 오래 기다릴 수 있어 처리율이 떨어질 수 있다.
• FCFS, SJF, HRN, 우선순위, 기한부 등

 

기아현상과 에이징 기법

기아현상과 에이징 기법은 문제 상황과 문제를 해결하기 위한 기법으로 기아현상이 문제 상황, 에이징 기법이 문제 해결방법으로 나누어질 수 있다.

 

 

스케줄링 알고리즘

🔵 선점형 기법

스케줄링 기법은 현재 CPU를 점유하고 있는 프로세스를 중단하고 다른 프로세스에게 CPU를 할당할 수 있는 기법

Round Robin

• 시간 단위(Time Quantum - 시간 할당량 / Slice - 타임슬라이스)를 정해서 프로세스를 순서대로 CPU를 할당하는 방식이다. → 각 프로세스는 동일한 크기의 할당 시간을 가지며, 이 시간 동안만 CPU를 사용한다. 할당 시간이 경과하면 현재 프로세스는 중단되고 준비 큐의 다음 프로세스가 CPU를 사용하게 된다.
• 컴퓨터 자원을 사용할 수 있는 기회를 프로세스들에게 공정하게 부여하기 위한 방법이다.

특징

✅ 빠른 응답 시간을 제공하므로 대화형 작업에 적합하다.

✅ 할당시간마다 문맥 교환이 이루어지므로 오버헤드가 높을 수 있다.

✅ 시분할 시스템에 적합하며 시간 또한 할당량의 크기에 좌우된다.

 

RR 알고리즘의 성능

✅ 퀀텀의 크기 선택은 RR의 성능에 큰 영향을 미친다.

• 짧으면 문맥 교환이 자주 발생해서 오버해드가 높아진다. → 시간 할당량은 문맥교환시간보다 커야 한다. 그렇지 않으면 오버헤드로 성능저하가 발생한다.
• 길면 선점형 스케줄링의 장점(우선 순위를 빼앗을 수 있다.)을 살리지 못한다. 이 경우 FCFS와 비슷하게 처리된다.

 

SRT(Shortest Remainig Time)

• 비선점 스케줄링인 SJF(Shortest Job First) 기법을 선점 형태로 변경한 기법
• CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식이다.
• 만약 새로운 프로세스가 현재 실행 중인 프로세스보다 더 짧은 실행 시간을 가지면 현재의 프로세스는 중단되고 새로운 프로세스가 실행된다.

특징

✅ 최소의 평균 대기 시간을 제공한다.

✅ 높은 우선순위의 프로세스를 빠르게 처리할 수 있다.

✅ 문맥 교환이 빈번하게 발생하여 오버헤드가 높을 수 있다.

✅ 낮은 우선순위의 프로세스가 계속 대기하는 기아현상(Starvation) 이 발생할 수 있다.

 

 

다단계 큐(Multi-Level Queue, MLQ)

프로세스를 우선순위나 유형에 따라 여러 큐로 분류한다. 각 큐는 자신만의 스케줄링 알고리즘을 가질 수 있다. (예: 전면 작업용 큐, 배경 작업용 큐 등)

 

특징

✅ 여러 큐를 동시에 운영하여 효율적인 스케줄링이 가능하다.

✅ 프로세스 유형에 따라 적절한 스케줄링 알고리즘을 적용할 수 있다.

✅ 우선순위에 따라 프로세스를 구분하기 때문에 응답 시간이 개선될 수 있다.

✅ 복잡한 구조로 인해 관리와 유지가 어려울 수 있다.

✅ 특정 그룹의 준비상태 큐에 들어갈 경우 다른 준비상태 큐로 이동할 수 없다.

✅ 하위 준비 상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 준비 상태 큐에 프로세스가 들어오면 상위 프로세스에게 CPU를 할당한다.

 

다단계 피드백 큐(Multi-Level FeedBack Queue, MLFQ)

다단계 큐와 유사하나, 프로세스의 행동과 특성에 따라 동적으로 프로세스의 우선순위를 변경한다. 프로세스가 CPU를 너무 오래 사용하면 우선순위를 낮추고, 입출력 작업이 많으면 우선순위를 높인다.

 

특징

✅ 프로세스의 동작을 기반으로 동적으로 우선순위를 조정하여 효율적인 스케줄링이 가능하다.

✅ 짧은 프로세스나 입출력 중심의 프로세스에 빠른 응답 시간을 제공한다.

✅ 오버헤드가 상대적으로 높을 수 있으나, 성능 향상을 위한 복잡한 정책을 구현할 수 있다.

✅ 올바른 우선순위 조정 메커니즘을 구현하는 것이 중요하다. 잘못된 조정은 성능 저하로 이어질 수 있다.

✅ 프로세스 생성 시 가장 높은 우선순위 준비 큐에 등록되며 등로된 프로세스는 FCFS 순서로 CPU를 할당받아 실행되고 할당된 시간이 끝나면 다음 단계로 이동한다. 단계가 내려갈수록 할당량이 증가하고 하위큐는 RR(라운드로빈) 방식으로 진행한다.

 

🔵 비선점형 기법

비선점형 스케줄링에서는 한번 CPU를 할당받으면 해당 프로세스의 작업이 완료될 때까지 CPU를 반환하지 않는다. 문백 오버헤드가 없지만 , 일부 프로세스가 CPU를 너무 오래 점유할 경우 다른 프로세스의 대기 시간이 길어질 수 있다.

 

FCFS(First Come First Served)

먼저 도착한 프로세스를 먼저 처리하는 스케줄링 알고리즘이다.

 

특징

✅ 공평성이 유지되지만, 중요한 작업이 중요치 않은 작업에 밀려서 늦게 처리되는 문제점이 발생될 수 있다.

✅ 실행시간이 긴 프로세스가 먼저 도착하게 되면 효율성이 떨어진다.

 

 

SJF(Shortest Job First)

실행시간이 가장 짧은 프로세스에게 CPU를 할당하는 방식이다. (평균 대기 시간이 짧아 효율적이지만 정확한 시간을 알아내기 어려워 실제 시스템에서는 잘 사용되지 않음)

 

특징

✅ 짧은 작업을 우선적으로 처리하다보니 평균 대기시간이 가장 적은 최적의 스케줄링

✅ 실행 시간이 긴 프로세스는 CPU를 얻기 어려울 수 있어 기아현상이 발생할 수 있다.

 

 

참고자료

🔗 흥달쌤 정처기 실기

🔗 https://choiyeonho903.tistory.com/49

🔗 https://code-lab1.tistory.com/45