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

📌 CS 핵심 용어 간단 용어정리!
CS 적 의미는 차이가 있지만 큰틀에서는 비슷한 의미로 이해할 수 있는 용어

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

CPU는 한정된 자원으로 최대한 성능을 이끌어내기 위해 프로세스를 잘 배정해 CPU를 적절하고 효율적으로 사용해야 한다

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

스케쥴링의 단위

CPU , I/O Burst Cycle

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

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

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

스케쥴링 종류

[선점 스케쥴링(Preemptive Scheduling)]

: 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를 강제로 할당(회수)해야 하므로   선점 스케쥴링 이 발생