컴퓨터 구조

[05] CPU 스케줄링

BGK97 2024. 4. 17. 15:25

CPU 스케줄링 개요

CPU 스케줄링이란?

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

프로세스 우선순위

  • 만약, 모든 프로세스를 동일하게 순차적으로 실행시킨다면
    • 언뜻 보면 합리적인 것 같지만 급하게 수행되어야 하는 프로세스가 있는 경우, 효율적이지 못하게 됨
    • 이를 우선순위가 다르다고 함
    • 우선 순위가 높을 수록, 빠르게 처리해야하는 프로세스임
  • 대부분의 프로세스들은 CPU와 입출력장치를 모두 사용하며 실행
    • 실행과 대기를 반복...
    • 예시로, 워드 프로세서가 있는데
      • CPU를 사용하여 명령어를 실행
      • 사용자로 입력받은 내용을 보조기억장치에 저장
      • CPU를 사용하여 명령어를 실행
      • 사용자가 입력한 내용을 화면에 출력

입출력 집중 프로세스와 CPU 집중 프로세스

  • 프로세스는 종류마다 입출력장치 이용 시간, CPU 이용 시간이 다름
  • 비디오 재생이나 디스크 백업 등 입출력 작업이 많은 것들을 입출력 집중 프로세스
  • 수학 연산, 컴파일, GUI 처리 등은 CPU 집중 프로세
  • 입출력 집중 프로세스는 실행 상태보다 입출력 대기시간이, CPU 집중 프로세스는 대기시간보다 실행시간이 긴 특징
  • 이 두개가 모두 동일한 빈도로 CPU를 사용하면 비합리적이지 않을까?
    • 따라서 운영체제는 프로세스의 중요도와 상황에 맞게 적절한 우선순위를 부여함
    • 이 우선순위는 PCB에 적혀있음

CPU 버스트와 입출력 버스트

  • CPU 버스트
    • CPU를 이용하는 작업
  • 입출력 버스트
    • 입출력장치를 기다리는 작업
  • 프로세스는 일반적으로 이 둘을 반복하며 실행TIP - 우선순위 직접 확인하는 법
  • 유닉스 체계 운영체제는 명령 프롬포트에서 ps -el 명령을 통해 확인 가능
  • Window 운영체제는 Process Explorer 라는 소프트웨어에서 확인이 가능

스케줄링 큐

  • 우선순위가 PCB에적혀있으나, CPU가 일일이 확인하는 것은 비효율적
  • 이런 이유로 프로세스들은 줄을 세워서 관리하는데, 이를 스케줄링 큐 라고 함
  • 이 때의 큐는 FIFO의 방식이 아님!

  • 운영체제가 관리하는 큐는 준비큐와 대기큐로 구성
  • 준비 큐
    • CPU를 이용하고 싶은 프로세스들의 줄
  • 대기 큐
    • 입출력장치 이용을 위해 대기상태에 있는 프로세스들의 줄
  • 줄을 세워도, 우선순위가 높은 프로세스가 들어오면 먼저 수행(VIP 개념)
  • 해당 프로세스 차례가 되면 준비큐에서 디스패치를 통해 실행상태에 옮김

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

  • 선점형 스케줄링
    • 남보다 앞서서 차지한다는 뜻
    • 프로세스가 이미 CPU를 사용하고 있더라도, 운영체제가 강제적으로 프로세스의 자원을 뺏어 다른 프로세스에게 할당할 수 있음
    • 프로세스가 자원을 독점할 수 없음
    • 장점
      • 급한 프로세스가 끼어들어 작업을 처리하며, 독점을 막고 프로세스들에게 골고루 자원 배분이 가능
    • 단점
      • 문맥 교환중 오버헤드가 발생할 가능성이 있음
  • 비선점형 스케줄링
    • 프로세스가 자원을 사용하고 있다면 끝날때 까지나 대기상태 전까지는 아무도 간섭할 수 없음
    • 하나의 프로세스가 자원 독점이 가능함
    • 장점
      • 문맥교환 횟수가 적어 오버헤드의 가능성이 적음
    • 단점
      • 하나의 자원이 독점하여 급한 프로세스가 일 처리를 못함

CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘의 종류

  • 선입 선처리 스케줄링
  • 최단 작업 우선 스케줄링
  • 라운드 로빈 스케줄링
  • 최소 잔여 시간 우선 스케줄링
  • 우선순위 스케줄링
  • 다단계 큐 스케줄링
  • 다단계 피드백 큐 스케줄링

선입 선처리 스케줄링

  • FCFS 스케줄링이라고도 함
  • First Come FIrst Served Scheduling
  • 준비 큐에 삽입된 순서대로 프로세스를 처리 (비선점형)
  • 요청한 프로세스부터 CPU를 할당
  • 가장 공정해보이나 기다리는 시간이 가장 길어질 수도 있는 알고리즘
  • 이렇게 오래 기다리는 것을 호위 효과라고 함

최단 작업 우선 스케줄링

  • SJF 스케줄링이라고도 함
  • Shortest Job First Scheduling
  • CPU 작업시간이 가장 짧은 프로세스부터 실행
  • 비선점형 스케줄링이지만, 선점형으로 구현 가능함
  • 선점형으로 구현한 것이 최소 잔여 시간 우선 스케줄링임

라운드 로빈 스케줄링

  • Roud-Robin Scheduling
  • 선입 선처리 스케줄링에 타임 슬라이스가 추가
  • 타임 슬라이스
    • 프로세스가 CPU를 사용할 수 있는 정해진 시간
  • 타임 슬라이스 내에 완료되지 못한 작업들은 다시 큐의 맨 뒤에 삽입되어 대기 시간을 거침
  • 이때 끝나는 시점에 문맥교환이 이루어짐

 

최소 잔여 시간 우선 스케줄링
  • SRT 스케줄링
  • Shortest Remaining Time Scheduling
  • 최단 작업 우선 스케줄링과 라운드 로빈 알고리즘을 합친 것
  • 타임 슬라이스만큼 CPU를 사용하되, 다음 프로세스로 가장 작업시간이 적게 남아있는 프로세스가 선택
우선순위 스케줄링
  • 우선순위가 높은 프로세스가 선택
  • Priority Scheduling
  • 넓은의미로 보면, 최단 작업, 최소 잔여 시간 우선 스케줄링이 포함
  • 근본적인 문제가 있음
    1. 우선순위가 낮은 프로세스는 먼저 삽입 되더라도 계속 높은 프로세스만 실행되니 뒤로 밀림
    2. 필요한 순간이 오더라도 우선순위가 낮게 설정되어있어 쓰지를 못함

  • 이를 해결하기 위해 에이징이라는 방법을 사용
  • 에이징
    • 오래 대기한 프로세스의 우선 순위를 점차 높이는 방식
    • 10번 -> 9번 -> 8번....
    • 언젠가는 낮은 우선순위 프로세스가 1번이 되어 실행이 될 것임
다단계 큐 스케줄링
  • 우선순위 스케줄링의 발전 형태
  • 우선순위별로 준비 큐를 여러개 사용
  • 큐에 우선순위를 부여하고, 우선순위가 높은 순서대로 수행
  • 이후 우선순위가 높은 큐가 비면, 그 다음 큐에서 작업 수행
    • 우선순위가 비교적 높아야하는 입출력 집중 프로세스
    • 비교적 낮아도 상관없는 CPU 집중 프로세스
    • 이러한 프로세스들을 적당하게 큐에 삽입하여 우선순위를 유형별로 구분하여 실행하기 편리함
  • 타임 슬라이스를 여러개 지정 가능(큐 별로)
  • 큐마다 다른 스케줄링 알고리즘을 사용할 수 있음
  • 기아 현상 해결
다단계 피드백 큐 스케줄링
  • 다단계 큐 스케줄링의 발전 형태
  • 프로세스들이 큐 사이를 이동할 수 있음
  • 나머지는 동일하다.
  • CPU를 많이 사용하는 프로세스 들의 경우 자연스레 우선순위가 낮아짐...
  • 에이징 방식을 통해 기아 현상을 해결