Etc./CS

[CS 스터디] CPU 스케줄링

Jonnie 2022. 5. 20. 12:45

CPU 스케줄링

스케줄링

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

  • 오버헤드는 줄이고 사용률은 향상시켜야 하며 기아 현상을 해결해야 함
    • 기아 현상: 어떤한 우선 순위로 작업을 처리할 때 우선순위가 낮은 작업은 영원히 처리되지 않는 현상

목표

  1. 일괄처리 시스템(Batch System): 가능하면 많은 일을 수행. 시간(time) 보단 처리량(throughout)이 중요
  2. 대화형 시스템(Interactive System): 사용자가 컴퓨터 앞에서 대화형으로 동작하기 때문에 빠른 응답 시간, 적은 대기 시간이 중요
  3. 실시간 시스템(Real-time System): 시간 제약 조건, 즉 기한(deadline) 맞추는 것이 중요

선점/비선점 스케줄링

선점 스케줄링(Preemptive Scheduling)

하나의 프로세스가 CPU를 할당받아 실행하고 있을 때, 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법

  • 주로 빠른 응답시간을 요구하는 대화식 시분할 시스템에 사용
  • 선점으로 인한 많은 오버헤드 발생
  • 선점을 위해 시간 배당을 위한 인터럽트용 타이머 클럭(Clock) 필요

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

이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법

  • 모든 프로세스에 대한 요구를 공정하게 처리
  • 일괄 처리 방식에 적합
  • 중요 작업이 기다리는 경우가 발생할 수 있음
  • 응답시간(처리시간) 예측 용이

스케줄링이 발생할 수 있는 프로세스 상태

  • 비선점 스케줄링: I/O or Event Wait, Exit
  • 선점 스케줄링: Interrupt, I/O or Event Completion
  • 프로세스 상태
    • New: 프로세스 생성 중프로세스를 생성하고 있는 단계로, 커널 공간에 PCB가 만들어진 상태이다.
    • Ready: 프로세스가 CPU를 기다리는 상태프로세스가 메모리에 적재된 상태로, 실행하는데 필요한 자원을 모두 얻은 상태이다.
    • Running: 프로세스가 CPU를 할당받아 명령어를 수행 중인 상태일반적으로 CPU가 하나이기 때문에 여러 프로세스가 동시에 실행되어도 실제로 실행 중인 프로세스는 매 시점 하나뿐이다.
    • Waiting: 프로세스가 어떤 사건(event)이 완료되기를 기다리는 상태프로세스가 실행되다가 할당받은 CPU를 반납하고 특별한 event가 완료되길 기다린다. (ex. I/O 작업)
    • Terminated: 프로세스의 실행 종료프로세스의 실행이 완료되고 할당된 CPU를 반납한다.
  • 프로세스 상태 전이
    • 승인(Admitted) : 프로세스 생성이 가능하여 승인받는 것
    • 스케줄러 디스패치(Scheduler Dispatch) : 준비 상태에 있는 프로세스 중 하나를 선택하여 실행시키는 것
    • 인터럽트(Interrupt) : 예외, 입출력, 이벤트 등이 발생하여 현재 실행 중인 프로세스를 Ready 상태로 바꾸고, 해당 작업을 먼저 처리하는 것
    • 입출력 또는 이벤트 대기(I/O or Event wait) : 실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우, 입출력/이벤트가 모두 끝날 때까지 Waiting 상태로 만드는 것
    • 입출력 또는 이벤트 완료(I/O or Event Completion) : 입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것

CPU 스케줄링 척도

  1. CPU Utilization(이용률, %): CPU가 수행되는 비율
  2. Throughput(처리율, jobs/sec): 단위시간당 처리하는 작업의 수(처리량)
  3. Turnaround time(반환시간): 프로세스의 처음 시작 시간부터 모든 작업을 끝내고 종료하는데 걸린 시간(CPU, waiting, I/O 등 모든 시간을 포함) 반환시간은 짧을 수록 좋음
  4. Waiting time(대기시간): CPU를 점유하기 위해서 Ready Queue에서 기다린 시간(다른 큐에서 대기한 시간은 제외)
  5. Response time(응답시간): 작업이 처음 실행되기까지 걸린 시간. 일반적으로 대화형 시스템에서 입력에 대한 반응 시간을 말함

CPU 스케줄링 종류

선점 스케줄링

  1. Priority Scheduling (우선순위 스케줄링)
    • 정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
    • 우선 순위가 낮은 프로세스가 무한정 기다리는 기아 현상이 생길 수 있음
    • Aging 기법으로 Starvation 문제 해결 가능
      • Aging 기법: 한 번 양보하거나 기다린 시간에 비례하여 일정 시간이 지나면 우선순위를 한 단계씩 높여 가까운 시간 안에 자원을 할당받도록 하는 기법
  2. Round Robin
    • FCFS(FIFO)에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum 만큼 CPU를 할달 받음
      • Time Quantum (or Time Slice) : 실행의 최소 단위 시간
    • 할당 시간(Time Quantum)이 크면 FCFS와 같게 되고, 작으면 문맥 교환(Context Switching) 잦아져서 오버헤드 증가
  3. Multilevel-Queue (다단계 큐)다단계 큐 우선순위
  • 작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 기법 (Ready Queue를 여러 개 사용)
  • 우선순위가 낮은 큐들이 실행 못하는 걸 방지하고자 각 큐마다 다른 Time Quantum을 설정 해주는 방식
  • → 우선순위가 높은 큐는 작은 Time Quantum 할당. 우선순위가 낮은 큐는 큰 Time Quantum 할당.
  • 우선순위가 낮은 하위 단계 큐의 작업은 실행 중이더라도 상위 단계 큐에 프로세스가 도착하면 CPU를 뺏기는 선점 방식
  1. Multilevel-Feedback-Queue (다단계 피드백 큐)다단계 피드백 큐
    • 다단계 큐에서 자신의 Time Quantum을 다 채운 프로세스는 밑으로 내려가고 자신의 Time Quantum을 다 채우지 못한 프로세스는 원래 큐 그대로
      • Time Quantum을 다 채운 프로세스는 CPU Burst 프로세스로 판단하기 때문
        • CPU Burst 프로세스
    • 짧은 작업에 유리, 입출력 위주(Interrupt가 잦은) 작업에 우선권을 줌
    • Aging 기법을 활용해 하위단계 큐의 프로세스를 상위단계로 이동 가능
    • 처리 시간이 짧은 프로세스를 먼저 처리하기 때문에 Turnaround 평균 시간을 줄여줌

다단계 큐 vs 다단계 피드백 큐

다단계 큐 다단계 피드백 큐

큐 사이 이동 불가능 가능
기아현상 발생 가능 에이징을 통해 예방 가능

비선점 스케줄링

  1. FCFS (Fist Come First Served, FIFO)
    • 큐에 도착한 순서대로 CPU 할당
    • 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐
  2. SJF (Shortest Job First)
    • 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
    • FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리
  3. HRN (Highest Response-ratio Next)
    • 우선순위를 계산하여 점유 불평등을 보완한 방법(SJF의 단점 보완)
    • 우선순위 = (대기시간 + 실행시간) / (실행시간)
    • 우선 순위 계산 결과값이 높은 것부터 우선 순위 부여. 대기시간이 긴 프로세스일수록 계산 결과값이 높게 나옴
    작업 대기시간 서비스시간
    A 5 20
    B 40 20
    C 15 45
    D 20 20 
    A의 우선순위 : (5+20)/20=1.25
B의 우선순위 : (40+20)/20=3
C의 우선순위 : (15+45)/45=1.3333
D의 우선순위 : (20+20)/20=2

B의 우선순위가 가장 높고, A의 우선순위가 가장 낮음

출처.

다단계/다단계 피드백 큐 스케줄링 https://itdexter.tistory.com/394

프로세스 생명주기 https://www.uname.in/252

프로세스 상태 오류 수정 https://dokhakdubini.tistory.com/457

https://tonylim.tistory.com/169

CPU 스케줄링 척도 https://velog.io/@codemcd/운영체제OS-6.-CPU-스케줄링



저작자표시

'Etc. > CS' 카테고리의 다른 글

[CS 스터디] OSI 7계층  (0) 2022.06.14
[CS 스터디] SQL Injection  (0) 2022.05.27
[CS 스터디] IPC (Inter Process Communication)  (0) 2022.05.20
[네트워크] 네트워크 모델  (0) 2022.05.12
[네트워크] Wireshark를 이용하여 사용된 프로토콜 확인하기  (0) 2022.05.10

'Etc./CS'의 다른글

  • 현재글[CS 스터디] CPU 스케줄링

관련글

티스토리툴바