CPU , 메모리 심화학습

면접 단골 질문 !

스케쥴링

제어장치 (CU)의 핵심 기능인 “스케쥴링”

CS 핵심 용어 간단 정리

• 프로그램을 실행해주는 주체 = 프로세스
  • ex. 카카오톡 💬을 실행하는 프로세스
• 작업을 처리해주는 주체 = 쓰레드
  • ex. 메세지 발송 📤을 처리하는 쓰레드

CPU 를 잘 사용하기 위해 프로세스를 잘 배정해야 합니다.

• CPU는 한정된 자원으로 최대한 성능을 이끌어내기 위해서는 CPU를 적절하고 효율적으로 사용해야 합니다.
• 이해하기 쉽게 표현하다면, OS는 실행 대기중인 프로그램(프로세스)들에게 CPU 자원 배정을 적절히 하여 시스템의 성능을 끌어올릴 수 있습니다. (결국 처리는 CPU 가 하니까)
• 공통 배정조건 : 오버헤드 ↓ / 사용률 ↑ / 기아 현상 ↓
  • 오버헤드 : 프로세스가 필요한 자원보다 더 많이 사치부리며 사용하지 않도록(=투머치🤑)
  • 사용률 : 프로세스가 최대한 자원을 많이받고 빨리 처리하도록 (=알잘딱깔쎈🤓)
  • 기아 현상 : 프로세스가 자원할당을 못받아서 배고픈상태로 대기하지 않도록(=지못미🤕)
• 목표에 따른 배정조건 :
  1. 배치 시스템 : 가능하면 많은 일을 수행. 시간(time) 보단 처리량(throughout)이 중요
  2. 대화형 시스템 : 빠른 응답 시간. 적은 대기 시간이 중요
  3. 실시간 시스템 : 실시간(time) 즉, 최소 응답시간(dead line) 이 중요

정책에 따라서 3가지로 나뉩니다.

• 1.CPU이용률을 최대화,
• 2.오버헤드를 최소화,
• 3.모든 프로세스가 공평하게 분배하는 방식이 있다.

---

스케쥴링 단위

CPU , I/O Burst Cycle

• 프로세스 실행은 “CPU실행 ↔ 입/출력 대기” 의 반복을 의미합니다.
• CPU Burst
  • 프로세스의 사용중에 연속적으로 CPU를 사용하는 구간을 의미합니다.
  • 즉, 실제 CPU 를 사용하는 스케쥴링의 단위이다.
• I/O Burst
  • 프로세스의 실행 중에 I/O작업이 끝날때까지 Block되는 구간을 의미합니다.

스케쥴링 알고리즘 평가기준

• CPU이용률 : 전체 시스템 시간 중, CPU가 작업을 처리하는 시간의 비율
• 처리량 : CPU가 단위 시간당 처리하는 프로세스의 개수
• 총 처리 시간 : 프로세스가 시작해서 끝날때 까지 걸린 시간
• 대기시간 : 프로세스가 준비완료 큐에서 대기하는 시간의 총 합
• 응답시간 : 대화식 시스템에서 요청 후 첫 응답이 오기까지 걸린 시간

---

스케쥴링 종류

✅ 선점 스케쥴링(Preemptive Scheduling)

OS가 CPU의 사용권을 선점할 수 있는 경우, 강제 회수하는 경우 (처리 시간 예측 어려움)

OS가 나서서 CPU사용권을 '선점'하고, 특정 요건에 따라 각 프로세스의 요청이 있을 때 프로세스에게 분배하는 방식입니다.

• 가장 자원이 필요한 프로세스에게 CPU를 분배하며 상황에 따라 강제로 회수할 수도 있습니다.
• 따라서 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세스를 제어할 수 있다.

선점1.Priority Scheduling(우선순위 스케쥴링)

💡 Priority Scheduling 특징

• 정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
• 우선 순위가 낮은 프로세스가 무한정 기다리는 기아 현상 발생 가능
• Aging 방법으로 기아현상 문제 해결 가능

미리 주어진 프로세스의 우선순위에 따라서 스케쥴링하는 방식이다. 2번에서 다룬 SJF도 Priority Scheduling의 일종이다.(최소 버스트 시간 기준)

• 그러나 우선순위가 낮은 프로세스는 할당되지 않기도 하는데, 이를 기아(Starvation)이라고 부릅니다.
• 이를 방지하기 위한 해결법으로는 노화(Aging)이 있는데 기다리는 시간에 따라 우선순위를 증가시켜주는 방식입니다. 마찬가지로 우선순위가 같으면 FCFS를 적용합니다.
• 스케쥴링 예시
  

선점2.Round Robin(라운드로빈)

💡 FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum 만큼 CPU 할당

정해진 시간 할당량 만큼 프로세스를 할당한 뒤, 작업이 끝난 프로세스는 준비완료 큐(순환 큐)의 가장 마지막에 가서 재할당을 기다리는 방법입니다. (회전식)

• 시간 할당량이 중요한데, 너무 작으면 빈번한 문맥 전환(Context Switching)이 발생하고, 너무 길면 FCFS와 다를 바 없어진다.
• 스케쥴링 예시
  

선점3.Multilevel-Queue(다단계 큐)

준비완료 큐를 여러개의 큐로 분류하여 각 큐가 각각 다른 스케쥴링 알고리즘을 가지는 방식. 메모리 크기, 우선순위, 유형 등 프로세스의 특성에 따라 하나의 큐에 영구적으로 할당된다. 따라서 큐와 큐 사이에도 스케쥴링이 필요하다. 우선순위 방식 혹은 시분할 방식으로 한다.

우선순위 방식

고정 우선순위의 선점형 방식으로 구현되며, 따라서 우선순위에 따른 큐의 스케쥴링은 절대적이다. 예를 들어,

우선순위가 높은 Forground Queue

• 대화형 프로세스를 위한 큐
• Round Robin

우선순위가 낮은 Background Queue

• 연산작업을 처리하는 프로세스 큐
• FCFS

여기서 Forground큐가 비어있지 않는 한 Background큐는 먼저 실행될 수 없으며, Background큐가 먼저 실행중이더라도 Forground큐에 프로세스가 들어오면 선점된다.

 비선점.스케쥴링(Non-Preemptive Scheduling)

💡 프로세스 종료 or I/O 등 이벤트가 있을 때까지 실행 보장 (처리시간 예측 용이)

어떤 프로세스가 CPU를 할당받으면 그 프로세스가 종료되거나, 입출력 요구가 발생하여 자발적으로 중지될 때 까지 계속 실행되도록 보장하는 방법입니다.

• 순서대로 처리되는 공정성이 있고, 다음에 처리해야할 프로세스와 상관없이 응답시간을 예상할 수 있습니다.
• 선점방식보다 스케쥴러 호출 빈도가 낮고, 문맥교환에 의한 오버헤드가 적습니다.
• 일괄처리 시스템에 적합하며 자칫 CPU사용시간이 긴 프로세스가 다른 프로세스들을 대기시킬 수 있으므로 처리율이 떨어질 수 있다는 단점이 있습니다.

비선점1. FCFS (First Come , First Serve)

💡 FCFS 특징

• 큐에 도착한 순서대로 CPU 할당
• 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐

먼저 도착한 프로세스를 먼저 처리하는 기본적인 스케쥴링 알고리즘 입니다. 

• 비 선점형이며 FIFO큐(먼저 입력된것 먼저 출력)를 이용하여 간단하게 구현합니다.
• 다만, Convoy Effect(호위효과)가 발생하는데, 긴 처리시간의 프로세스가 선점되어버리면 나머지 프로세스들은 끝날때 까지 대기해야 합니다.
• 따라서 먼저 도착한 프로세스의 버스트 타임에 따라서 평균 대기시간의 편차가 큽니다.
• 스케쥴링 예시
  

비선점2. SJF(Shorted Job First)

💡 SJF 특징

• 수행시간이 가장 짧다고 판단되는 작업 먼저 수행
• FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리

CPU버스트 타임이 가장 짦은, 최단작업을 우선 스케쥴링 하는 알고리즘 입니다.

• 가장 적은 평균 대기 시간을 달성할 수 있다.
• 만약 CPU버스트 시간이 동일하다면 FCFS방식을 따릅니다.
• 다만 선점형인 경우에는 위와같이 진행이 되지만 비 선점형일 경우엔 최소잔여시간우선 법칙을 따릅니다.

현재 CPU에 할당된 프로세스의 남은 잔여시간과, 새로 들어온 프로세스의 CPU버스트 타임을 비교하여 더 적은 프로세스에게 할당하게끔 한다.

최적이긴 하지만 다음 프로세스의 버스트시간을 계산하기 어렵다는 단점이 있어서 '비슷할것이다'라고 추측을 통해 진행하기도 한다.

• 스케쥴링 예시
  

비선점3. HRN (Highest Response-ratio Next)

💡 HRN 특징

• 우선순위를 계산하여 점유 불평등 보완(SJF 단점 보완)
• 우선순위 = (대기시간 + 실행시간) / (실행시간)

스케쥴링 동작시점

프로세스의 상태변화와 스케쥴링

스케쥴링 알고리즘에 따라 프로세스들은 상태변화가 일어나며 준비/수행 상태일때 CPU를 사용하게 됩니다.

아래 그림에서

• 🟠은 프로세스들의 상태를 의미하고
• 🔜 은 스케쥴링에 따라 상태가 변화되는 동작을 의미합니다.

1. 수행 -> 대기 (Running->Waiting) : I/O요청이 발생하거나, 자식 프로세스가 종료 대기를 할 때
2. 수행 -> 종료 (Running -> Terminate) : 프로세스를 종료시켯을때
3. 수행 -> 준비 (Running-> Ready) : 인터럽트가 발생했을때
4. 대기 -> 준비 (Waiting -> Ready) : I/O가 완료되었을때

• 여기서 1,2은 프로세스가 스스로 CPU를 반환하기에 비선점 스케쥴링이 발생되고
  

• 3,4은 프로세스에서 CPU를 강제로 할당(회수)해야 하므로 선점 스케쥴링 이 발생됩니다.
  

📌 예를들어 이해해봅시다.

카카오톡 메세지를 보내기 위해 메세지 창을 켜면 카카오톡 프로세스는 신규 > 준비 상태가 됩니다.

1. 준비 (Ready) 상태:
   1. 카카오톡을 띄워서 메시지를 입력하고 있을 때, 해당 프로세스는 준비 상태가 됩니다.
   2. CPU 스케줄링 알고리즘은 준비 상태의 프로세스 중에서 CPU를 할당할 프로세스를 선택합니다.
   3. 이때, 선택하는 선점 알고리즘에 따라 우선순위, 라운드 로빈 등 다양한 방식이 있을 수 있습니다.
2. 대기 (Waiting) 상태:
   1. 카카오톡이 비활성화 되어있거나, 가만히 상대방의 답장을 기다릴때 대기 상태가 됩니다.
   2. 해당 프로세스는 대기 상태로 변경되면서 수행중 이었다면 CPU를 반납합니다.
   3. CPU 스케줄링 알고리즘은 다른 준비 상태의 프로그램(프로세스)를 선택하여 CPU를 할당할 수 있습니다.
3. 수행 (Running) 상태
   1. 사용자가 메시지를 발송하거나 상대방의 메시지를 수신할때 수행 상태가 됩니다.
   2. CPU 가 준비 상태의 프로세스에 명령을 보내면, 해당 프로세스는 수행 상태로 변경됩니다.
   3. CPU 스케줄링 알고리즘은 실행 시간을 제어하며, 일정 시간이 지나면 해당 프로세스를 중단하고 실행 대기 상태의 다른 프로세스를 선택할 수 있습니다.
4. 종료 (Terminated) 상태:
   1. 카카오톡 프로그램을 종료하면 해당 프로세스는 중지 상태로 변경됩니다.
   2. 이때, CPU 스케줄링 알고리즘은 다른 실행 대기 상태의 프로세스를 선택하여 CPU를 할당할 수 있습니다.

CPU 심화 : 질의 응답 연습하기

질문:
프로세스와 쓰레드의 역할을 간단하게 설명해주세요.
프로세스는 무엇인가요?
쓰레드는 어떤 역할을 하나요?

답변:

프로세스는 실행 중인 프로그램을 의미합니다. 프로세스는 자신의 메모리 영역과 실행 상태를 가지며, 운영체제로부터 CPU 시간을 할당받아 실행됩니다. 예를 들어, 카카오톡을 실행하는 것은 하나의 프로세스입니다.

쓰레드는 프로세스 내에서 실행되는 작은 실행 단위입니다. 하나의 프로세스는 여러 개의 쓰레드를 가질 수 있습니다. 각 쓰레드는 독립적으로 실행되지만 프로세스 내의 자원을 공유합니다. 예를 들어, 메세지 발송과 같은 작업을 처리하는 쓰레드는 하나의 프로세스 내에서 동작합니다.

질문:
CPU 스케줄링이 무엇인지 설명해주세요.
CPU 스케줄링의 주요 목적은 무엇인가요?
어떤 조건을 만족해야 CPU 스케줄링이 효율적으로 이루어질까요?

답변:

CPU 스케줄링은 운영체제가 여러 프로세스의 CPU 사용을 관리하는 기술입니다. 프로세스가 CPU를 사용하는 순서와 시간을 결정하여 시스템 성능을 최적화하고 사용자에게 적절한 응답성을 제공합니다.

주요 목적은 CPU 자원을 효율적으로 활용하여 처리량을 늘리고 대기 시간을 줄이며, 공정한 자원 분배를 실현하는 것입니다.

효율적인 CPU 스케줄링을 위해 다음 조건을 만족해야 합니다:

오버헤드를 최소화하여 자원 낭비를 막아야 합니다.
CPU 사용률을 높여 전체 시스템 성능을 향상시켜야 합니다.
기아 현상을 방지하여 모든 프로세스가 공평하게 자원을 할당받아야 합니다.

질문:
CPU와 메모리의 효율적인 사용을 위해 왜 프로세스를 잘 배정해야 하나요?
CPU의 효율적인 사용을 위한 중요성은 무엇인가요?
어떤 배정 조건을 충족해야 CPU를 효율적으로 사용할 수 있을까요?

답변:

CPU는 시스템의 주요 자원 중 하나이며 한정된 자원입니다. 프로세스를 잘 배정하면 CPU를 효율적으로 활용하여 시스템 성능을 최적화할 수 있습니다.

CPU를 효율적으로 사용하기 위한 중요한 이유는 다음과 같습니다:

시스템의 응답성을 향상시켜 사용자가 더 빠르게 작업을 수행할 수 있습니다.
시스템의 처리량을 높여 더 많은 작업을 동시에 처리할 수 있습니다.
자원의 낭비를 줄여 시스템 성능을 향상시킵니다.
CPU를 효율적으로 사용하기 위한 배정 조건은 다음과 같습니다:

오버헤드를 최소화하여 자원을 낭비하지 않도록 합니다.
CPU 사용률을 높여 처리량을 증가시키도록 합니다.
기아 현상을 방지하여 모든 프로세스가 공평하게 자원을 할당받도록 합니다.

질문:
선점 스케줄링과 비선점 스케줄링에 대해 설명해주세요.
선점 스케줄링과 비선점 스케줄링은 무엇인가요?
어떤 상황에서 각각의 스케줄링 방식이 유용하게 쓰일까요?
답변:

선점 스케줄링은 현재 실행 중인 프로세스를 중단하고 다른 프로세스에게 CPU를 할당하는 스케줄링 방식입니다. 우선순위나 시간 할당량에 따라 프로세스가 CPU를 선점합니다.

비선점 스케줄링은 한 번 CPU를 할당받은 프로세스는 CPU 사용을 종료할 때까지 계속 실행되는 스케줄링 방식입니다.

선점 스케줄링은 다음 상황에서 유용합니다:

대화형 시스템에서 빠른 응답 시간이 필요한 경우
긴급한 작업이 발생했을 때 우선순위를 높여 처리해야 하는 경우
시스템 자원을 효율적으로 할당하여 공정한 자원 분배가 필요한 경우
비선점 스케줄링은 다음 상황에서 유용합니다:

일괄 처리 시스템에서 여러 작업을 순차적으로 처리해야 하는 경우
각 프로세스의 실행 시간을 미리 예측하여 자원을 효율적으로 분배해야 하는 경우

질문:
CPU Burst와 I/O Burst Cycle에 대해 설명해주세요.
CPU Burst와 I/O Burst Cycle은 무엇인가요?
프로세스 실행은 어떻게 CPU Burst와 I/O Burst Cycle의 반복으로 이루어지나요?

답변:

CPU Burst는 프로세스가 연속적으로 CPU를 사용하는 시간을 의미합니다. 이는 프로세스가 실제로 계산 작업을 수행하는 시간입니다.

I/O Burst Cycle은 프로세스가 I/O 작업의 완료를 기다리는 동안 CPU 사용이 중지되는 시간을 의미합니다.

프로세스 실행은 CPU Burst와 I/O Burst Cycle의 반복으로 이루어집니다:

프로세스가 실행을 시작하면 CPU Burst가 시작됩니다. 프로세스가 계산 작업을 수행하며 CPU를 사용합니다.
계산 작업 중에 I/O 작업이 필요하면, 프로세스는 I/O Burst 상태로 전환됩니다. CPU 사용이 중지되고 I/O 작업의 완료를 기다립니다.
I/O 작업이 완료되면 프로세스는 다시 CPU Burst 상태로 전환되어 계산 작업을 계속합니다.
CPU Burst가 끝나면 다시 I/O Burst 상태로 전환되며, 이런 과정이 계속 반복됩니다.

질문:
CPU 스케줄링 알고리즘의 평가 기준은 무엇인가요?
CPU 스케줄링 알고리즘은 어떤 기준으로 평가될까요?
간단히 CPU 스케줄링 알고리즘의 다양한 평가 기준을 설명해주세요.

답변:

CPU 스케줄링 알고리즘은 여러 가지 평가 기준을 기반으로 평가됩니다. 주요한 평가 기준은 다음과 같습니다:

CPU 이용률: CPU가 작업을 처리하는 시간의 비율로 시스템 성능을 나타냅니다.
처리량: 단위 시간당 처리되는 프로세스의 개수를 나타내며 시스템의 처리 능력을 평가합니다.
총 처리 시간: 모든 프로세스의 실행이 끝날 때까지 걸리는 시간을 측정하여 시스템의 효율성을 평가합니다.
대기 시간: 프로세스가 준비완료 큐에서 대기하는 시간의 총합으로 응답성을 나타냅니다.
응답 시간: 대화형 시스템에서 요청 후 첫 응답이 오기까지 걸린 시간을 측정하여 사용자 경험을 평가합니다.

질문:
다양한 스케줄링 알고리즘에는 어떤 종류가 있을까요?
CPU 스케줄링 알고리즘은 어떤 기준에 따라 다양한 종류로 나뉘어질까요?
간단히 스케줄링 알고리즘의 종류와 특징을 설명해주세요.

답변:

CPU 스케줄링 알고리즘은 주요 기준에 따라 다음과 같이 나뉘어집니다:

선점 스케줄링: 운영체제가 프로세스의 실행을 중단하고 다른 프로세스에게 CPU를 할당하는 방식입니다. 우선순위, 라운드 로빈 등이 있습니다.
비선점 스케줄링: 한 번 CPU를 할당받은 프로세스는 CPU 사용이 종료될 때까지 계속 실행되는 방식입니다. FCFS, SJF 등이 있습니다.
주요 선점 스케줄링 알고리즘:

Priority Scheduling (우선순위 스케줄링): 우선순위에 따라 프로세스를 스케줄링하는 방식입니다.
Round Robin (라운드 로빈): 시간 할당량에 따라 프로세스를 순환하면서 CPU를 할당하는 방식입니다.
Multilevel-Queue (다단계 큐): 다양한 큐를 사용하여 우선순위에 따라 프로세스를 할당하는 방식입니다.
주요 비선점 스케줄링 알고리즘:

FCFS (First Come, First Serve): 도착한 순서대로 프로세스를 처리하는 방식입니다.
SJF (Shortest Job First): CPU 버스트 타임이 가장 짧은 프로세스를 우선 처리하는 방식입니다.
HRN (Highest Response-ratio Next): 우선순위를 계산하여 실행 중인 프로세스의 평균 응답률을 고려하여 스케줄링하는 방식입니다.