[운영체제]Ch.10 프로세스 스케줄링

프로세스 스케줄링

어떤 프로세스에게 어떤 방식으로 running을 부여하는가? 운영체제의 가장 중요한 역할 이것을 프로세스 스케줄링, CPU 스케줄링이라고 부름

프로세스 스케줄링의 개념을 제대로 이해하고, 스케줄링 알고리즘을 알아볼것

프로세스 스케줄링

프로세스 스케줄링이랑 그림에서 보는것처럼 메모리상에 존재하는 여러개의 프로세스중에서 CPU에서 돌아갈 프로세스를 선택하는것.

이런 스케줄링이 있으므로 컴퓨터시스템에서 다중프로그래밍, 멀티태스킹, 시분할 기능이 가능하다. 여러개의 프로세스가 CPU를 사용하여 CPU이용률을 높일 수 있는 좋은 수단이다.

• CPU에서 실행 될 프로세스를 선택하는 일
  • 다중 프로그래밍 및 시분할 기능을 실현하기 위한 핵심 수단
• 프로세스 스케줄링의 효과
  • 많은 수의 프로세스가 활성화되어 CPU 이용률을 높임
  • 프로세스들 사이에서 CPU를 빈번하게 교체
  • 한 순간에는 하나의 프로세스만 CPU를 사용

스케줄러

이런 스케줄링도 어떠한 소프트웨어에 의해 이루어 지는데, 운영체제의 일부인 스케줄러가 담당한다. 운영체제에서 가장 핵심적인 부분이다. 마이크로 커널에서도 반드시 커널로써 구현해야 할것이 바로 스케줄러 실제로 구현하는데 있어서는 어떤 프로세스를 어떤 방식으로 선택할것인가가 제일 중요한 설계 요소. => 스케줄링 정책, 스케줄링 알고리즘

• 운영체제에서 프로세스 스케줄링을 담당하는 부분
  • 스케줄링 큐에서 상태를 전이할 프로세스를 선택하는 것
  • 스케줄링 정책 혹은 스케줄링 알고리즘 필요
• 스케줄러 종류(스케줄링의 일반적인 구분)
  • 장기 스케줄러 (long term scheduler)
    • cpu를 어떻게 사용하냐가 아닌 컴퓨터 시스템을 어떻게 사용할것인가? 하는 스케줄링임.
    • 현대 컴퓨터 시스템에선 거의 의미가 없음.
    • 작업(job) 스케줄러
  • 단기 스케줄러 (short term scheduler)
    • 여기가 중요함.
    • CPU 스케줄러
  • 중기 스케줄러 (medium term scheduler)
    • 스와핑 기능이 추가된 CPU 스케줄러
    • 메모리가 모든 프로세스를 수용할만큼 크지 않기때문에 가상메모리를 사용한다. 가상메모리는 하드디스크를 메모리마냥 사용하는것임. 많이 사용되는 프로세스는 cpu에 올리고 빈도가 떨어지는건 하드디스크의 가상메모리에 올리게 된다.
    • 어떤 프로세스가 메모리에 있을 수 있고, 하드에 있을 수 있는데, 메모리와 하드디스크를 어떻게 번갈아 가면서 사용하게 하느냐? 는 중기 스케줄러에서 관여함.

스케줄링 큐

운영체제가 이해하는 프로세스는 PCB가 된다. 스케줄링 큐라는것은 PCB들의 링크드리스트로써 각각 연결하고 있는 자료구조. 큐처럼 먼저 들어온것이 먼저 나가는 형태임.

• 스케줄링을 위한 프로세스들의 대기열 자료구조
  • 프로세스 제어블록(PCB)들의 리스트
• 스케줄링 큐의 구성
  • Job queue: 시스템 안에 존재하는 프로세스들의 집합
  • Ready queue: 메모리 상에 존재하며 실행 준빅 ㅏ되어 있는 프로세스들의 집합
  • Device queue: 입출력 장치의 사용을 기다리는 프로세스들의 집합
• 프로세스 상태 전이와의 관계
  • 프로세스들은 스케줄러의 결정에 따라 여러 큐(queue) 사이를 옮겨 다니며 원하는 작업을 완료한다.

CPU 스케줄링이 발생하는 상황

이러한 상황을 이해해야하는 이유는, 어떤 정책에 따라 어떻게 프로세스를 선택해서 할당할것인가 중 어떻게 선택에 해당함

곧 프로세스의 상태가 변경이 되는데 running인 상태가 비워지는 상황임. 총 4가지의 상황이 있음

• 실행(running) 상태에서 대기(wait) 상태로 전환될 때, cpu를 놀게하는게 아니라 ready중에 running으로 바꿀 프로세스를 선택한다.
  • 입출력 요청 등으로 프로세스가 스스로 중단(block)
• 실행(running) 상태에서 준비(ready) 상태로 전환될 때
  • 타이머 등에 의한 인터럽트
• 대기(wait) 상태에서 준비(ready) 상태로 전환될 때
  • running 상태가 비워지는게 아닌데, 스케줄링이 실행된다.
    • 어떤 프로세스가 ready로 갔는데 현재 running중인 프로세스보다 우선순위가 더 높을수도 있다. 그럴때 우선권을 뺏는 경우가 생기기 때문.
  • 입출력 완료 인터럽트
• 프로세스가 종료할 때

선점 스케줄링 (Preemptive scheduling)

어떤 프로세스가 CPU를 점유하고있는데 스케줄러가 강제로 CPU를 점유하고 다른 프로세스에게 CPU를 할당해주는 방식 현재 작동중인 프로세스는 계속 CPU를 사용하고싶은데 스케줄러가 강제로 뺏고 새로운 프로세스를 할당하는 방식.

• 운영체제의 판단에 따라 현재 실행 중인 프로세스를 강제로 중단시키고 CPU 스케줄링을 실행
  • 인터럽트 발생시 (timer, 입출력 완료)
• 각 프로세스의 빠른 응답을 지원
• 기다리고 있는 프로세스에게 동작 기회를 더 많이 준다.
• 빈번한 문맥 교환(context switch)을 위한 커널코드가 실행되기 때문에 너무 빈번하게 선점하게되면 시스템이 느려지는 비용(overhead) 증가
• 실시간 시스템에서의 전형적인 스케줄링 방식
  • 대부분의 최신 운영체제에서도 채용되는 방식

선점 스케줄러 구현 시의 어려움

어떤 프로세스가 예상치 못하게 중단되고 다시 복구할때 문제가 없도록 예전 상황을 복구시켜줘야 한다.

프로세스가 불완전한 상태에서 선점 될 때 문제가 없도록 주의해야한다.

비선점 스케줄링 (nonpreemptive scheduling)

강제로 종료하는것이 아니라 현재 사용중인 프로세스가 자발적으로 종료할 때 까지 기다리는 방식임.

합리적인것처럼 보이지만 전체 입장에서는 별로

응답시간이 빨라야 하는 대화식 운영체제에는 어울리지 않는다.

• 현재 실행 중인 프로세스가 자발적으로 CPU 사용을 중단하는 경우에만 CPU 스케줄링을 수행
  • 입출력 요청이나 프로세스의 종료 시
• 대화식(interactive) 다중 프로그램 환경을 구현하기는 어려움
  • 짧은 CPU burst를 가진 프로세스가 긴 CPU burst를 가진 프로세스의 CPU 사용이 끝나기를 기다려야 한다.

스케줄링 평가 기준(criteria)

시스템 중심 관점

• CPU 이용률 (Utilization)
  • 시스템 기준에서는 CPU 이용률을 극대화 시키는것이 좋은 스케줄링 알고리즘이다.
  • CPu가 실제로 프로세스를 실행하는 busy 시간의 비율
  • 일반적으로 40% ~ 90%
• 처리율 (throughput)
  • 컴퓨터는 프로세스를 실행시켜주는 기계이고 좋은 기계가 될려면 단위 시간내 많은 프로세스를 처리해야한다.
  • 단위 시간 동안에 완료된 프로세스의 개수가 높을수록 좋다.

사용자(프로세스) 중심 관점

• 총 실행 시간
  • 나한테 얼마나 많은 CPU 시간을 줬는가?
  • 한 프로세스가 시작부터 실행이 완료되기까지의 전체 시간
  • 짧으면 짧을수록 좋은 스케줄링
  • 메모리 적재, ready queue에서 대기, CPU 실행, 입출력 처리 등의 합
• 대기 시간
  • 한 프로세스가 ready queue에서 대기한 시간의 합
  • 낮을수록 좋음
• 응답 시간
  • 내 프로그램에 대한 첫번째 응답이 올 때까지의 시간
  • 프로세스의 요청에 대한 응답이 시작되기까지의 시간
    • 프로세스의 시작부터 첫 CPU 실행까지의 시간
  • 대화형(interactive) 시스템에서 중요한 기준

일반적으론 처리율이 높다고 응답시간이 빠르다고 보장하기 어렵다. 그러므로 앞으로 스케줄링 알고리즘을 볼 때 처리율 측면에선 얼마나 좋은가? 응답 시간 측면에선 얼마나 좋은가? 로 판단할 수 있어야 한다.