선점 스케쥴링(Scheduling)

오늘은 스케쥴링에 대해 공부한것에 대해 정리를 해보았다.

 

먼저 스케쥴링과 밀접한 관련이 있는

# CPU를 잘 사용하기 위한 프로세스 배정에 관해 정리한 내용이다.

● CPU는 한정된 자원으로 최대의 성능이 중요!
그렇기에 CPU를 적절하고 효율적으로 사용해야함!

● ex) OS는 실행 대기중인 프로그램(프로세스)들에게 
CPU자원 배정을 적절히 하여 시스템의 성능을 끌어올릴 수 있음!
(결국 처리는 CPU!)

CPU자원 배정에 대한
● 공통배정조건 3가지 : 오버헤드↓ / 사용률↑ / 기아 현상↓
    ● 오버헤드: 프로세스가 자원낭비 못하게
    ● 사용률: 프로세스가 최대한 자원 많이받아 빠른 처리
    ● 기아 현상 : 프로세스가 자원 못 받지 않게

 

기아현상은 우선순위 스케쥴링과 밀접한 연관이 있어보인다.

● 목표에 따른 배정조건 :
1. 배치 시스템 : 가능하면 많은 일을 수행. / 시간(time)보다 처리량(throughout)이 중요 
2. 대화형 시스템 : 빠른 응답 시간(time) / 적은 대기시간이 중요
3. 실시간 시스템 : 실시간(time)즉, 최소 응답시간(dead line)중요

 

여기서 배치가 뭐길래 처리량이 중요한가했는데

"사람이나 물자 따위를 일정한 자리에 나누어 두는" 배치 가 아니라

영어였다 . . . Batch = 일괄이라는뜻 

 

바로 이해가 됐다 일괄처리!

은행 정산 시스템이 떠올랐고 그런 경우 응답시간보다는

처리량에 포커스를 맞추니까 ! 

 

• 대화형 시스템은 당연히 최우선으로 빠른 응답 시간을 요구할걸로 보이고

 

• 실시간은 최우선까진 아니여도 일정 주기로 데드라인을 넘지않으면서 하는 꾸준한 응답으로 이해가 된다.

● 정책에 따라 3가지로 나뉨
1. CPU이용률을 최대화
2. 오버헤드를 최소화
3. 모든프로세스가 공평하게 분배 

 

공통 조건으로 다 필요하긴 하지만

정책에 따라 특화하는 부분에대한 걸로 이해했다.

1. 스케쥴링(CS 면접 단골 질문)

1-1 스케쥴링 소개

1-1-1. 스케쥴링의 단위
! Cycle ! 싸이클이다
● CPU Burst 
- # 프로세스 사용중에 연속적으로 CPU를 사용하는 구간을의미(실제 CPU를 사용하는 스케쥴링 단위)
● I/O Burst
- # 프로세스 실행에서 I/O 작업이 끝날때까지 Block되는 구간을 의미 

 

/ 입력대기 (I/O Burst) / CPU 실행 CPU Burst  / 출력 대기(I/O Burst) /

   

Burst가 폭발하는 느낌이니까 폭발적으로(연속적으로) 사용하는 구간에 대한 네이밍으로 받아들였다.

CPU Burst 는 말그대로 CPU를 연속적으로 사용하는 구간이고

I/O Burst는 CPU사용이 Block되는 구간인걸로 이해했다

 

프로세스 실행은 CPU실행 ↔ 입/출력 대기 반복

 

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

 

CPU이용률 = 늘리면 좋은 

처리량          =  늘리면 좋은 

총 처리 시간 =  줄이면 좋은 

대기 시간      =  줄이면 좋은 

응답 시간      = 줄이면 좋은 

이렇게 이해했다.


1-2 스케쥴링 종류

# 선점 스케쥴링(Preemptive Scheduling)
OS가 CPU의 사용권을 선점 및 강제 회수하는 경우 (처리 시간 예측 어려움),
(OS가 나서서 CPU사용권을 '선점'하고, 
특정 요건에 따라 각 프로세스의 
요청이 있을 때 프로세스에게 분배하는 방식)

● 가장 자원이 필요한 프로세스에게 CPU를 분배, 상황에 따라 강제로 회수함

● 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합 / 긴급 프로세스 제어 가능 
(대화식 시분할 시스템에서는 꾸준하면서 최대한 빠른 응답을 줘야하는게 관건이기때문에 CPU상황마다
CPU사용권에 대해 최우선 처리를 하는게 좋기때문이라고 보여진다.)

 

원할때 CPU의 자원을 바로 쓸 수 있는 우선권!

대화형 시스템같은 경우 어떠한 이벤트가 발생하면

거기에 대응하는  최우선으로 빠른응답시간을 확보해야하기 때문에

이 선점하는 스케쥴링을 이용할 수 있겠다고 이해했다.

 

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

특징
1. 정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
2. 우선 순위가 낮은 프로세스가 무한정 기다리는 기아 현상 발생 가능
3. Aging 방법으로 기아현상 문제 해결 가능
미리 주어진 프로세스의 우선순위에 따라 스케쥴링하는 방식
(SJF(Shortest Job First Scheduling) 도 Priorty Scheduling의 일종)

우선순위를 부여하면서 처리하는방식은

장점의 고점이 높을 수 있다고 생각했지만

역시 그만큼 단점으로

우선순위가 낮은 프로세스는 할당되지 않기도하는

기아현상이 발생하는 스케쥴링 방법으로 보인다.

그래도 이를 방지하기 위한 해결법이 있기에 괜찮은 스케쥴링 방법인것같다.

Aging -> 노화 -> 사람은 시간이 지날수록 나이가 드는것처럼

기다리는 시간에 따라 우선순위가 증가하는 방법으로 이해했다.

-> 우선순위가 같을시 FCFS(First Come Fist Served)를 적용

먼저온게 먼저 처리되는

[스케쥴링 예시]
프로세스  버스트 시간 우선 순위 턴어라운드 시간 대기 시간
  P1                    10             3                 16            6            
  P2                     1              1                  1             0            
  P3                     2              4                  18          16            
  P4                     1              5                  19          18            
  P5                     5              2                   6           1   
  평균                   -              -                   12          8.2   
       /P2/    P5     /         P1        /   P3  /P4/

         1        6                16             18    19

예시에서 알 수 있는 정보
1. 턴어라운드 시간 : 앞 순 버스트시간 + 자기 버스트 시간
2. 대기시간        : 앞 순의 버스트시간의 합 or 턴어라운드시간 - 자기버스트시간 

 

확실히 우선순위가 높은 프로세스는 대기 시간 없이 빠르게 처리되지만

우선순위가 낮은 프로세스는 대기시간이 앞 순 버스트시간의 합만큼 그대로 누적이 되버리는것을 볼 수있다. 

 

정말 우선순위를 나눠야 할 경우에 쓰면 좋을것같다.

우선순위보다 전체적인 작업이 계속 돌아가야하는 상황?이라면  

좋은 방법으로 볼 수 없을것같다.

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

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

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

● 시간 할당량이 중요
# 너무 작으면 =  빈번한 문맥 전환(Context Switching)이 발생
# 너무 길면   =  FCFS와 다를 바 없어짐

[스케쥴링 예시]
시간 할당량 3ms
프로세스  도착 시간 버스트 시간 턴어라운드 시간 대기 시간
  P1                0                  5                   14                    6            
  P2                1                  3                    5                     0            
  P3                2                  8                   20                   16            
  P4                1                  6                   17                   18      
  평균             -                   -                    14                   8.5
         /P1 /P2 /P3 /P4 /P1/P3 /P5 /P3/
           3    6    9    12  14  17  20  22  

 

시간할당량이 중요한 스케쥴링 방법 답게

시간 할당량 3ms 기준으로 고루고루 할당받는 모습이 보인다.

중간 중간 3ms보다 적은 버스트시간이 남은경우에는 2ms씩이라던지

남은 만큼만 버스트하고 사라지고 다음으로 넘기는 등

계속 시간 할당량을 기준으로 

회전하는 스케쥴링 방법으로 이해했다.

 

 몇가지 우선순위를 두고 빠르게 처리해야할 작업에서는 부적합 하겠지만

고루고루 처리해야할 상황?에 어울리는 스케쥴링으로 보인다.

1-2-3 Multilevel-Queue(다단계 큐)
# 준비완료 큐를 여러개의 큐로 분류해 
- 각 큐가 각각 다른 스케쥴링 알고리즘을 가지는 방식
- 메모리 크기, 우선순위, 유형 등 프로세스 특성에 따라
  하나의 큐에 영구적으로 할당 됨
- 따라서 큐와 큐 사이에도 스케쥴링이 필요
- 우선순위 방식 or 시분할 방식으로 함

1. 우선순위 방식
# 고정 우선순위의 선점형 방식으로 구현, 
따라서 우선순위에 따른 큐의 스케쥴링은 절대적임
[예시] 
1-1 우선순위가 높은 Forground Queue
● 대화형 프로세스를 위한 큐
● Roung Robin

1-2 우선순위가 낮은 Background Queue
● 연산작업을 처리하는 프로세스 큐
● FCFS

-> Forground큐가 비어있지 않는 한!
Background큐는 먼저 실행될 수 없음!
Background큐가 먼저 실행중이라도!
Forground큐에 프로세스가 들어오면 선점됨!

 

한가지 종류가 아닌 여러 상황에 맞게 대응해야하는 경우 쓰면 아주 좋을것 같은 스케쥴링으로 보인다. 

각 큐가 우선순위가 필요한것은 우선순위 스케쥴링으로 대응하고 연산작업에 대해서는 FCFS로 대응하고

상당히 좋아보인다. 하지만 그만큼 리스크가 있는건지 궁금하다. 스케쥴링에 대해 더 알아봐야겠다.