운영체제 리뷰 3 -CPU 스케줄링

참고 자료 : 혼자 공부하는 컴퓨터구조 + 운영체제
사진 출처 : Operating System Concepts 10E

1. CPU 스케줄링 개요

<CPU 스케줄링이란>

1. 개요

• 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것

2. 가장 공정한 방법?

• 프로세스마다 우선순위를 생각해서 스케줄링 해야함
  • ex) 입출력 작업이 많은 프로세스는 CPU 작업이 많은 프로세스보다 우선순위가 높다.
    • 입출력 작업이 많은 프로세스는 대기하는 시간이 길다.
    • 즉, 미리 입출력 작업을 빠르게 끝내버리고 CPU 작업이 많은 프로세스에게 CPU를 몰빵하는 것

<프로세스 우선순위>

1. 개요

• PCB에 저장되어 우선순위 높은 것 부터 실행

2. 우선순위를 찾는 방법

• 매번 모든 프로세스의 PCB를 찾아서 우선순위 높은 것을 찾는 것은 너무 낭비이고 오래걸린다.
  -> 스케줄링 큐 이용

<스케줄링 큐>

1. 개요

• 프로세스 마다 요구하는 자원들을 그에 따라 큐에 정리함
• 같은 큐 내에서도 우선순위 별로 처리한다
  • cf)스케줄링 큐에서 큐는 반드시 FIFO는 아니다.

2. 준비 큐

• CPU를 이용하기 위해 기다리는 큐

3. 대기 큐

• 입출력장치를 이용하기 위해 기다리는 큐
• 같은 장치를 요구한 프로세스들은 같은 큐에서 대기
  • ex) 프린터 대기 큐, 하드디스크 대기 큐

4. 그렇다면

• 현재 진행중인 프로세스보다 우선순위가 높은 프로세스가 ready queue에 들어오면 누구를 먼저 실행할 것인가?
  -> 선점형 비선점형 스케줄링으로 결정

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

1. 개요

• 현재 한 프로세스가 실행중인데, 다른 프로세스가 너무 급해서 CPU를 할당해달라고 할 때
  -> 현재 사용중인 프로세스로부터 CPU 자원 빼앗기
  -> 현재 사용중인 프로세스 끝날 때 까지 기다리기

2. 선점형 스케줄링 (preemptive)

• 프로세스마다 정해진 시간은 모두 지키고, 타이머 인터럽트 발생했을 때 CPU 넘겨주기
• 장점)
  • 한 프로세스의 독점을 막음
  • 프로세스들에 골고루 자원 배분 가능
• 단점)
  • context switching이 많기 때문에 오버헤드 발생 가능

3. 비선점형 스케줄링 (non-preemptive)

• 현재 진행중인 프로세스의 CPU 할당을 빼앗아서 급한 프로세스에게 바로 넘겨주기
• 장점)
  • context switch 오버헤드 적다
• 단점)
  • 모든 프로세스에게 골고루 자원 배분 못할 수 있다.

2. CPU 스케줄링 알고리즘

<선입 선처리 (First Come First Served>

• ready queue에 삽입된 순서대로 처리하는 비선점 스케줄링
• 동작방식
  • 먼저 CPU를 요청한 프로세스부터 CPU 할당
• 단점)
  • 프로세스들이 기다리는 시간이 매우 길어질 수 있다.
  • ex) 먼저 실행된 프로세스의 실행시간이 길 때, 매우 오래 기다려야함

<최단 작업 우선 (Shortest Job First)>

• FCFS의 단점을 해결한 방식
• CPU 사용시간이 가장 짧은 프로세스부터 처리하는 방식
  • 비선점형 스케줄링
  • CPU 시간이 긴 프로세스를 나중에 실행하기

<라운드 로빈 (Round Robin)>

• FCFS + 타입 슬라이스 를 사용하는 방식
  • 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
  • 타임 슬라이스의 크기를 잘 정하는 것이 중요
• 동작 방식
  • 큐에 삽입된 순서대로 프로세스들이 CPU를 이용하다가 정해진 시간 만큼만 사용
  • 만약 정해진 시간동안 못 끝냈다면, 다시 큐의 맨 뒤에 삽입

<최소 잔여 시간 우선 (Shortest Remaining Time)>

• SJF + Round Robin 방식
• 동작 방식
  • 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스는 남은 작업 시간이 가장 적은 프로세스 선택

<우선순위>

• 동작방식
  • 프로세스들에 우선순위 부여하고 우선순위 높은 프로세스부터 실행
  • 우선순위 같은 프로세스는 FCFS로 스케줄링
• SJF, SRT 스케줄링을 포함하는 개념

cf) Starvation

• Starvation 현상이 발생할 수 있다는 근본적인 문제점 존재
  • 우선순위가 높은 프로세스만 계속 실행되고, 낮은 프로세스는 계속 연기된다.
• 해결방안
  • aging 기법 : 오랫동안 대기한 프로세스의 우선순위를 높여주는 방식

<다단계 큐 (Multilevel queue)>

• 우선순위 스케줄링의 발전된 형태
• 우선순위별로 준비 큐를 여러개 사용하는 스케줄링 방식
  • 큐가 여러 개이므로, 각자 다른 스케줄링 방식을 쓸 수 있다.
• 동작방식
  • 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
  • 우선순위가 가장 높은 큐가 비어있으면 그 다음 우선순위 큐에 있는 프로세스 처리
• 문제점
  • 큐 간의 이동이 불가능 하므로,
  • 결국 우선순위가 낮은 큐는 계속 실행을 못하는 starvation 발생 가능

<다단계 피드백 큐 (Multilevel feedback queue>

• 다단계 큐 스케줄링의 발전된 형태
• 큐 간의 이동이 가능한 다단계 큐 스케줄링
• CPU를 많이 써야할수록 우선순위가 낮아진다.
• 동작방식 (아래 사진 참고)
  참고 : quantum = 8 이 우선순위가 가장 높은 것
  • 8의 quantum 동안 프로세스가 끝나면 ok
  • 8의 quantum 동안 프로세스가 끝나지 않으면 CPU를 더 써야하는 것이므로 우선순위를 하나 내려준다.
  • 반복하다보면, CPU 집중 프로세스는 우선순위가 낮아지고, IO 집중 프로세스의 우선순위는 높아진다.
• 다단계 피드백 큐에서도 aging 기법 사용 가능