728x90
반응형

Chapter 11 CPU 스케줄링

1. CPU 스케줄링 개요

프로세스 우선순위/ 스케줄링 큐/ 선점형과 비선점형 스케줄링

 

CPU 스케줄링(CPU scheduling)

  • 운영체제가 프로세스에게 공정하고 합리적으로 CPU 자원을 배분하는 것
  • 컴퓨터 성능하고 직결

프로세스 우선순위

프로세스마다 우선순위가 다름

-> 우선순위 ↑ 프로세스 = 빨리 처리해야 하는 프로세스(ex. 입출력 프로세스)

 

프로세스는 실행 상태, 대기 상태 반복하며 실행

  • 입출력 집중 프로세스(I/O bound process)
    • 입출력 작업 ↑ 프로세스
    • ex. 비디오 재생, 디스크 백업 작업
    • 실행 상태 < 입출력 위한 대기 상태
    • *입출력 버스트 ↑ 프로세스
  • CPU 집중 프로세스(CPU bound process)
    • CPU 작업 ↑ 프로세스
    • ex. 복잡한 수학 연산, 컴파일, 그래픽 처리
    • 실행 상태 > 입출력 위한 대기 상태
    • *CPU 버스트 ↑ 프로세스

  • 입출력 버스트(I/O burst): 입출력장치 기다리는 작업
  • CPU 버스트(CPU burst): CPU 이용하는 작업

=> 프로세스 중요도 맞게 프로세스가 CPU 이용 -> 우선순위(priority) 부여

프로세스의 PCB에 우선순위 명시, PCB에 적힌 우선순위 기준 -> 먼저 처리할 프로세스 결정


스케줄링 큐(scheduling queue)

운영체제가 매번 모든 PCB 검사하여 먼저 자원 이용할 프로세스 결정 -> 비효율적

=> (CPU 사용하고 싶은 프로세스/ 메모리에 적재되고 싶은 프로세스/ 특정 입출력장치 사용하고 싶은 프로세스) 줄 세움

-> 스케줄링 큐로 구현하고 관리(효율적 스케줄링)

*큐: 선입선출(First In First Out) 자료 구조 But, 스케줄링에서 반드시 X

  • 준비 큐(ready queue)
    • CPU를 이용하기 위해 기다리는 줄
  • 대기 큐(waiting queue)
    • 입출력장치 이용하기 위해 기다리는 줄


선점형과 비선점형 스케줄링

  • 선점형 스케줄링(preemptive scheduling)
    • 하나의 프로세스가 자원 사용 O -> 운영체제) 자원 강제로 빼앗아 다른 프로세스에 할당
    • 하나의 프로세스가 자원 사용 독점 X
    • 프로세스마다 정해진 시간만큼 CPU 사용, 타이머 인터럽트 발생 -> 운영체제) 자원 빼앗아 다음 프로세스에 할당 
    • (+) 한 프로세스의 자원 독점 막고 프로세스들에 자원 골고루 배분 O
    • (-) 문맥 교환 과정에서 오버헤드 발생할 수 있음
  • 비선점형 스케줄링(non-preemptive scheduling)
    • 하나의 프로세스가 자원 사용 O -> 종료 or 스스로 대기 상태 전에 다른 프로세스가 끼어들 수 X
    • 하나의 프로세스가 자원 사용 독점 O
    • (+) 문맥 교환 과정에서 발생하는 오버헤드 ↓
    • (-) 모든 프로세스 골고루 자원 사용 X

2. CPU 스케줄링 알고리즘

선입 선처리 스케줄링/ 최단 작업 우선 스케줄링/ 라운드 로빈 스케줄링
/ 우선순위 스케줄링/ 다단계 큐 스케줄링/ 다단계 피드백 큐 스케줄링

선입 선처리 스케줄링(FCFS; First Come First Served Scheduling)

  • 준비 큐에 삽입된 순서대로 프로세스 처리(비선점형 스케줄링 방식)
  • CPU를 먼저 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식
  • 공정해보이지만, 프로세스가 기다리는 시간 ↑ 확률 O
  • 호위 효과(convoy effect): CPU 버스트가 ↑ 프로세스가 준비 큐 앞에 오면 그 뒤에 ↓ 프로세스도 기다려야 함
    • ex. 프로세스 A: 17ms/ B: 5ms/ C: 2ms -> 프로세스 C는 2ms 실행하기 위해 22ms(17 + 5) 기다려야 함

최단 작업 우선 스케줄링(SJF; Shortest Job First Scheduling)

  • 준비 큐에 삽입된 프로세스 중 CPU 이용 시간의 길이가 가장 ↓ 프로세스부터 실행
  • 비선점형 스케줄링 알고리즘
    • But, 선점형으로 구현 O -> 선점형 최단 작업 우선 스케줄링: 최소 잔여 시간 우선 스케줄링

라운드 로빈 스케줄링(round robin scheduling)

  • 선입 선처리 스케줄링 + 타임 슬라이스
    타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
    • 타임 슬라이스 ↑ -> ~= 선입 선처리 스케줄링 => 호위 효과
    • 타임 슬라이스 ↓ -> 문맥 교환에 발생하는 비용 ↑ => CPU) 프로레스 처리 < 프로세스 전환
  • 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용(선점형 스케줄링) 

최소 잔여 시간 우선 스케줄링(SRT; Shortest Remaining Time)

  • 최단 작업 우선 스케줄링 알고리즘(: 작업 시간 ↓ 프로세스부터 처리)
    + 라운드 로빈 알고리즘(: 정해진 타임 슬라이스만큼 돌아가며 CPU 사용)
  • => 정해진 타임 슬라이스만큼 CPU 사용, 다음 프로세스는 남아있는 작업 시간 가장 ↓ 프로세스 선택

우선순위 스케줄링(priority scheduling)

  • 프로세스에 우선순위 부여, 가장 ↑ 우선순위 가진 프로세스부터 실행
    • 우선순위 같은 프로세스 -> 선입 선처리
  • 최단 작업 우선 스케줄링(: 작업 시간 ↓ 프로세스에 ↑ 우선순위)
    , 최소 잔여 시간 우선 스케줄링(: 남은 시간 ↓ 프로세스에 ↑ 우선순위)
    => 우선순위 스케줄링의 일종
  • (-) 기아(starvation) 현상: 우선순위 ↓ 프로세스는 (준비 큐에 먼저 삽입되었어도) 실행 계속 연기될 수 있음
  • (해결) 에이징(aging): 오랫동안 대기한 프로세스 우선순위 높이는 방식

다단계 큐 스케줄링(multilevel queue scheduling)

  • 우선순위별로 준비 큐를 여러 개 사용(우선순위 스케줄링의 발전된 형태)
  • 우선순위 가장 ↑ 큐에 있는 프로세스 먼저 처리, 비면 그 다음 우선순위 큐에 있는 프로세스 처리
  • (+) 프로세스 유형별로 우선순위 구분하여 실행
  • (+) 큐별로 타임 슬라이스 여러 개 지정, 다른 스케줄링 알고리즘 사용
  • (-) 프로세스들이 큐 사이 이동 X(= 기아 현상) -> (해결) 다단계 피드백 큐 스케줄링

다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)

  • 다단계 큐 스케줄링의 발전된 형태
  • 프로세스들이 큐 사이를 이동 O -> 에이징 기법(: ↓ 우선순위 큐에서 오래 기다리는 프로세스 -> 점차 우선순위 ↑ 큐로 이동)
  • 새로 준비 상태가 된 프로세스 O -> 우선순위 가장 ↑ 우선순위 큐에 삽입, 일정 시간(타임 슬라이스) 동안 실행
    • IF. 프로세스가 해당 큐에서 실행 끝 X -> 다음 우선순위 큐에 삽입되어 실행
  • => CPU를 비교적 오래 사용해야 하는 CPU 집중 프로세스 자연스럽게 우선순위 ↓
    , CPU를 비교적 적게 사용하는 입출력 집중 프로세스들 자연스럽게 우선순위 ↑ 큐에서 실행

출처

 

[한빛미디어] 혼자 공부하는 컴퓨터 구조+운영체제

좋은 개발자는 컴퓨터를 분석의 대상으로 바라볼 뿐, 두려워하지 않는다!‘전공서가 너무 어려워서 쉽게 배우고 싶을 때’, ‘개발자가 되고 싶은데 뭐부터 봐야 하는지 모를 때’ ‘기술 면접

hongong.hanbit.co.kr

 

728x90
반응형
김앩옹