[05] CPU 스케줄링

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를 많이 사용하는 프로세스 들의 경우 자연스레 우선순위가 낮아짐...
• 에이징 방식을 통해 기아 현상을 해결