[OS] CPU Scheduling(CPU 스케듈링)

2024.01.03 - [Computer Science/Operation System] - [OS] 프로세스 & 쓰레드(Process & Thread)

[OS] 프로세스 & 쓰레드(Process & Thread)

2024.01.08 - [Computer Science/Operation System] - [OS] Context Switching & Muti Thread, Muti Process

[OS] Context Switching & Muti Thread, Muti Process

 

 

이전 포스팅에서는 CPU에 프로세스가 도달하기전 메모리에 어떤식으로 저장되는지, 어떻게 교환되는지, 메모리에 축적된 프로세서와 그와 관련된 여러가지 용어를 살펴보았다. 이번에는 running(실행) 상태에서 프로세스가 Dispatcher될때를 살펴보려고 한다.

 

# Process Status(프로스세스 상태)

위에서 언급한 running(실행) 상태를 언급했다. 그러면 Running 상태말고 어떤 상태들이 있을까?

 

https://gyoogle.dev/blog/computer-science/operating-system/CPU%20Scheduling.html

 

상태(Status)는 5가지로 시분할시스템을 나눌 수 있다.

• New(생성)
• Ready(준비)
• Running(실행)
• Waiting(대기)
• Termianted(종료)

상태 전이 또한 6가지로 나뉜다.

• Admitted(승인)
• Scheduler Dispatch(스케듈러 디스패치)
• Interrupt(인터럽트) : 선점형
• I/O Wait 또는 Event Wait(입출력 대기 또는 이벤트 대기) 
• I/O Completion 또는 Event Completion(입출력 완료 또는 이벤트 완료)
• Exit(종료)

이렇게 상태(Status)와 상태전이가 있다.(최신의 운영체제는 프로세스단위가 아닌 커널 수준에서 스레드를 스케듈링 하게된다.)

 

※ Dispatch

Dispatch는 "(특별한 이유를 위해)보내다", "발송"하다라는 의미가 있는데 CPU의 스케듈러 쪽으로 Ready 상태에 있는 프로세스나 쓰레드를 Running 상태로  "대기가 끝나 준비 상태이니 특파로 보낸다"라는 의미로 이해하면 될거같다. 종종 Dispatch라는 단어가 나오기 때문에 정리를 해둔다.

 

# CPU Scheduling(CPU 스케듈링)

원 주제로 돌아와서 CPU를 스케듈링 한다는 의미는 무엇인가? 과거의 옛날의 PC는 프로세서(CPU와 같은 것)가 제한적인 환경이었다. 지금에서야 우리는 8CORE, 멀티 스레드 와 같은 기술의 혁신으로 엄청난 CPU를 활용하고 있지만, 한정된 자원으로 최고의 효율을 뽑아내야하는 과거와는 달랐다. 현재도 마찬가지로 자원을 많이 쓰는 프로세스가 있기때문에 역시 효율적으로 사용해야하며 멀티 태스킹도 해야한다.

즉, CPU 이용률을 극대화 하기 위한 방법이다.

 

먼저, CPU 스케듈링의 결정은 아래의 4가지 조건에서 발생될 수 있다.

1. 프로세스가 실행(Running) 상태에서 대기(Waiting) 상태로 전환될 때(I/O Wait 상태 전이)
2. 프로세스가 대기 (Waiting) 상태에서 준비(Ready) 상태로 전환될 때( I/O Completion 상태 전이)
3. 프로세스가 실행 (Running)  상태에서 준비(Ready) 상태로 전환될때(Interrupt 상태전이)
4. 프로세스가 종료(Terminated) 될 때(Exit 상태 전이)

 방법은 두가지로 나뉠 수 있다. 

• Preemitive(선점형) : 시분할 시스템에서 타임 슬라이스가 소진되었거나, 인터럽타나 시스템 콜로 종료시에 더 높은 우선순위 프로세스가 발생되었을때 강제적으로 CPU 자원을 회수한다. 위에 스케듈링 결정 조건에서는 1번과 2번에 해당단다.
• Non-Preemitive(비선점형):   이해하기 쉽게 CPU 자원이 한 프로세스가 할당되면 프로세스가 종료되던 대기상태로 전환되어 CPU 자원에 자리가 있게 될때까지 점유된다. 3번 4번에 해당되게된다.

 

# Non - Preemitive(비선점형) 스케듈링

먼저 비선점형 스케듈링부터 알아보자. 다시 설명하자면 이미 어떤 프로세스가 CPU를 갖고 있다면 반납 즉, 사용이 끝날때까지 기다리는 스케듈링 기법이다. 

이렇게 된다면 여러가지 장점이 있다. 응답시간을 예측할 수 있게되며 Batch System, 일괄처리 방식이 적합하게 된다.  또한, 인터럽트를 허용하지 않는다.

 

아래는 비선점 스케듈링의 알고리즘이다.

• FCFS(First Come First Served, FIFO)

  

  
  
  • Ready Queue에 도착한 순서대로 CPU 할당
  • 실행시간이 짧은게 뒤로 갈수록 가면 평균 대기 시간이 길어짐 (Convey Effect)
• Non-Preemitive SJF(Shortest Job First) - 최소 작업 우선 스케듈링

  

  • 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
  • 선점형 비선점형 두가지 모두 구현할 수 있
  • FCFS의 개선, 평균 대기 시간 감소, Short 작업에 유리
  • 긴 작업을 짧은 작업을 종료할 때 까지 대기해야함(Starvation), 하나의 프로세스의 CPU Burst time 예측 불가

※ CPU Burst time

It is the amount of CPU time the process requires to complete its execution.

(실행이 완려되는데 필요한 CPU 시간)

 

https://www.baeldung.com/cs/cpu-scheduling#:~:text=Burst%20time%2C%20also%20referred%20to,or%20unit%20of%20a%20job.

 

※ Starvation(기아 현상)

특정 프로세스가 계속해서 CPU자원을 사용하지 못하는 경우

• HRN(Highest Response-ratio- Next)

  

  • 우선순위를 계산하여 점유 Starvation을 방지(Non-Preemitive SJF 단점 보완)
  • 대기시간이 올라갈수록 응답률이 높아진다.
  • 우선순위의 기준은 (대기시간 + CPU Burst Time) / ( Burst Time)

    

    https://itdexter.tistory.com/393

 

https://itdexter.tistory.com/393

 

#  Preemitive(선점형) 스케듈링

비선점형 스케듈링과 스케듈링 방법에 대해서 살펴보았다. 선점형과 비선점형의 큰 차이는 인터럽트를 허용하느냐에 따라 다르다. 인 인터럽트를 허용하게 되면서 우선순위가 생기고 이에 따른 스케듈링을 진행하게 된다. 인터럽트 허용에 따른 Context Switching에 따른 OverHead가 발생하게 된다. 또한, Starvation이 발생할 수도 있게 된다.

 

아래는 선점형 스케듈링 알고리즘이다.

• Round Robin(RR, 라운드 로빈) 스케듈링

  

  • 시분할 시스템을 위해 설계된 알고리즘
  • Time Quantum(시간단위)로 CPU를 할당, 우선순위를 두지 않음
  • 시간 단위 동안 수행후 ReadyQueue의 가장 뒤로 가게 됨
  • OverHead가 크지만(시간단위로 프로세스가 변경되기 때문), Response Time 짧음 ➡️ 실시간 시스템 유리

 

※ Round Robin

어원은 리그전과 같은 의미이다. 모두가 한번씩 경기를 치른다의 의미를 갖고 있기때문에 이번에 공부하는 라운드로빈의 스케듈링도 마찬가지로 시간 단위로 모두에게 CPU를 주게 된다. Load Balancer 알고리즘에서도 라운드 로빈 방식이 사용된다. Load Balancer에서는 시간단위가 아닌 서버 단위로 동작하게 된다.

※ Time Quantum

타임 퀀텀은 시간 단위이고 보통은 10ms ~ 100ms 정도이다.

• SRTF(Shortest Remaining Time First) 스케듈링 - 최소 잔류 시간 우선 스케듈링

  

  • 선점형  SJF(Shortest Job First) - 최소 작업 우선 스케듈링
  • 각 프로세스의 남은 시간을 따져 보고 남은시간이 가장 짧은 프로세스에게 CPU를 줌(쉽게 말해, 자기들끼리 막 진행하다가 짧은 프로세스가 들어오면 우선으로 할당해 준다는 것이다.)
  • 새로운 프로세스가 올때만 Context Swithcing으로 인한 OverHead 발생
  • Starvation이 발생
• MutiLevel Queue (MLQ) 스케듈링(다단계 큐 스케듈링)

  

  • Ready Queue를 여러 개로 분리하며 Queue마다 우선순위를 설정
  • 우선순위가 낮은 Queue에서 작업을 진행하더라도 상위 단계에 Queue에 작업이 도착하면 선점
  • Queue마다 FCFS나 RR등 독자적 스케듈링 사용
  • 프로세스 성격에따라 우선순위가 부여됨
  • Queue들 간의 이동이 불가 ➡️ 유연성이 떨어짐
  • Starvation이 발생
• MutiLevel feedback Queue(MLFQ) 스케듈링(다단계 피드백 큐 스케듈링)

  

  • MLQ 스케듈링과 동적으로 프로세스의 우선순위가 변경됨
  • 프로세스별 Time Quantum이 아니라 Queue 별로 Time Quantum으로 진행하며 단계가 내려갈 수록 Time Quantum이 증가
  • CPU Burst 는 낮은 우선순위 Queue , I/O Burst 높은 우선순위 Queue로 큐간 이동 가능 (동적 변경)
  • 가장 최하위 우선순위 큐는 FCFS로 진행
  • 맨 아래의 큐에서 대기 시간이 길어질 경우 다시 상위 큐로 이동(Aging 기법)

※ MLQ  VS. MLFQ

위에 내용을 살펴보아도 알겠지만, 둘의 가장 큰 차이는 큐간 프로세스 이동이 가능한가 불가능한가의 차이이다. MLQ에서는 다른 큐로 프로세스간 이동이 불가하지만 MLFQ에서는 동적으로 우선순위가 변경되면 큐간 프로세스가 변경될 수 있다. MLFQ는 이로써 Starvation을 예방 할 수 있다.

# 평가기준

선점형, 비선점 스케듈링 기법을 살펴보았다. 그렇다면 평가 지표는 어떻게 될까? 뭐가 좋고 뭐가 나쁜지는 알아야 좋다 나쁘다를 이야기 할 수 있다.

 

• CPU Utilization(사용률) : 전체 시스템 기간 중 CPU가 작업을 처리하는 시간의 비율
• Throughput (처리량) : CPU가 단위 시간당 처리하는 프로세스 개수
• Response Time(응답 시간) :  시분할(대화식) 시스템에서 요청 후 응답이 오기 시작할때의 시간
• Wait Time(대기 시간) : Process가 Ready Queue에서 대기하는 시간의 총합
• Turnaround Time(반환 시간) : Process가 시작해서 끝날때가지 걸리는 시간 

 

대게 시험을 보면 해당 스케듈링의 시간과 우선순위를 맞추는 문제들이 많이 나온다. 시간이 되면 문제를 한번 풀어봐도 좋을거같다.(이론과 문제풀이는...다르니깐 )

 

# 현재는....??

 흠.... CPU 스케듈링을 공부하면서 우리가 사용하는 Linux의 CPU 스케듈링은 어떤건가 싶어서 자료를 검색다. CFS(Completely Fair Scheduling)이라는 알고리즘을 활용한다. 이는 위에 작성된 내용처럼 딱딱한 규칙(?)이 따로 없이 각 Task(작업)마다  CPU처리시간을 비율로 할당하게 된다. 뭐 이걸 기준으로 하는 Nice라는 값의 단위룰 활용하며 우선순위를 주는거 같은데.... 아직 주니어인 나로써는 살짝 이해하기가 힘들다. 리눅스 파트에서 다뤄야할 내용이지 않을까?

 

아무튼... 멀티 스레드, 멀티 프로세서도 많이 활용하면서 스레드 스케듈링도 따로 있고 OS는 공부하면 공부할 수록 재미있는거 같다는 생각이 많이든다(아직까지는!!), 포스팅 하면서도 즐겁다