6-CPU-스케줄러

CPU는 기계어 명령을 실제로 수행하는 중앙처리장치

프로그램이 시작되어 메모리에 올라가면 프로그램 카운터라는 이름의 레지스터가 현재 CPU에서 수행할 코드의 메모리 주소값을 갖음 CPU는 프로그램 카운터가 가리키는 주소의 기계어 명령을 하나씩 수행 한편, CPU는 시스템 내에 하나밖에 없으므로 여러 프로그램이 동시에 실행되는 시분할 환경에서 효율적으로 관리 되어야하는 자원

기계어 명령은 보통

  • CPU 내에서 수행되는 명령

  • 메모리 접근을 필요로 하는 명령

  • 입출력을 동반하는 명령

입출력 작업

  • 키보드로 입력 받기

  • 처리 결과 모니터에 출력

  • 디스크에서 파일 데이터 읽거나 쓰기

    이와 같은 입출력 작업은 CPU나 메모리 접근 명령에 비해 시간이 오래걸림

    또한, 입출력 명령은 특권 명령으로 규정하여 사용자 프로그램이 직접 수행할 수 없고 OS를 통해 서비스 대행

사용자 프로그램의 수행과정을 보면, CPU와 I/O 작업의 반복

  • 사용자 프로그램이 CPU를 할당받아 직접 빠른 명령 수행(add, 메모리 접근하는 Load, store) = CPU 버스트

  • I/O 요청이 발생하여 커널에 의해 입출력 작업 진행 = I/O 버스트

    I/O 바운드 프로세스 : I/O 요청이 빈번하여 CPU 버스트가 짧게 나타나는 프로세스

    CPU 바운드 프로세스 : 반대

CPU 스케줄링이란

  • 이와 같이 CPU를 사용하는 패턴이 상이한 여러 프로그램이 동일한 시스템 내부에서 함께 실행되기 때문에 필요

  • 예컨대, CPU버스트가 짧은 프로세스는 대화형 작업으로 사용자와 인터랙션 해가며 프로그램 실행 시킴

    • 이런 얘들은 CPU의 빠른 서비스를 필요로 함. 대화형 작업이므로 빠른 응답이 중요해서

    • 따라서 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 사용할 수 있도록 스케줄링 필요

    • 이는 바꾸어 말하면 CPU 스케줄링시, I/O 바운드 프로세스에게 우선순위를 높여주는 것이 바람

6.1 스케줄러

CPU 스케줄러는 준비 상태에 있는 프로세스들 중 어떤 프로세스에게 CPU 할당할지 결정하는 OS의 코드

  • 어떤 프로세스가 CPU 할당 받고 기계어 명령 수행 중에 타이머 인터럽트 발생시 CPU 스케줄러 호출

  • CPU 스케줄러는 준비 큐에서 CPU 기다리는 프로세스 중 하나 선택하여 CPU 할당

  • 이 밖에 CPU 스케줄링이 필요한 경우 1. 실행 상태에 있던 프로세스가 I/O 요청 등에 의해 봉쇄상태로 바뀐 경우 2. 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀐 경우 3. I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트 발생하고, 이 프로세스의 상태가 준비상태로 바뀌는 경우 4. CPU에서 실행 상태에 있는 프로세스가 종료된 경우

CPU 스케줄링 방식은

  1. 비선점형 방식

  2. 선점형 방식

비선점형 방식

CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지 CPU를 뺏기지 않는 방법

  • 1,4번

선점형 방식

프로세스가 CPU를 계속 사용하기를 원해도 뺏을 수 있는 스케줄링 방법

  • 뺏는 방법: 할당 시간을 부여하고 타이머 인터럽트 발생

  • 2,3번

6.2 디스패처

CPU 이양 작업 하는 커널 모듈 디스패처

6.3 스케줄링 성능 평가

시스템 관점

  • CPU 활용도: 전체 시간 중 CPU가 명령을 수행 시간의 비율

  • 처리량: 주어진 시간 동안 CPU 버스트를 완료한 프로세스의 개수

사용자 관점

  • 소요 시간: 프로세스가 CPU 요청시점부터 CPU 버스트가 끝날 때까지 걸린 시간

    • 준비큐에서 기다린 시간 + 실제로 CPU를 사용한 시간

    • 예컨대, CPU 사용하다가 I/O 연산을 위해 CPU 자진 반납시, CPU 사용하기 위해 준비큐 들어온 시간 ~ CPU 자진 반납까지

  • 대기 시간: CPU 버스트 기간 중 준비큐에서 기다린 시간의 합

    • 한 번의 CPU 버스트 중에도 준비큐에서 기다린 시간이 여러번 발생할 수 있음.

    • 이 떄 대기시간이란 이번 CPU 버스트가 끝나기까지 준비 큐에서 기다린 시간의 합

  • 응답 시간: CPU 요청 시점부터 처음으로 CPU 얻을 때까지 기다린 시간

    • 준비 큐에 들어온 후 첫번째 CPU 획득까지 기다린 시간

6.4 스케줄링 알고리즘

6.4.1 FCFS

프로세스가 준비 큐에 도착한 순으로 CPU 할당하는 방식

문제점

  • CPU 버스트가 긴 프로세스가 CPU 버스트가 짧은 프로세스 여러개 보다 먼저 도착할 경우

  • 평균작업시간 길어짐

    • CPU 버스트 짧은 프로세스들이 잠깐씩 CPU 할당받고 I/O 수행하면, 대기시간과 I/O장치 활용도 높아짐

  • 이와 같이 먼저 도착한 프로세스의 성격에 따라 평균 대기시간이 크게 달라짐

6.4.2 SJF

CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU 할당

  • 평균 대기시간 이 가장 짧은 최적 알고리즘

  • 비선점형

  • 선점형

    • SRTF(Shortest Remaining Time First)

프로세스들이 준비 큐에 도착하는 시간이 불규칙한 환경에서는 선점형 방식이 프로세스들의 평균 대기시간 최소화

  • 반면, 일련의 프로세스들이 준비 큐에 한번에 도착하고 그 후에 따로 도착하지 않는 환경에서는 둘다 비슷

일반적인 시분할 환경에서는 중간에 새로운 프로세스가 도착하는 경우가 많으므로 선점형이 평균 대기시간 가장 많이 줄임

프로세스의 CPU 버스트 시간을 미리 알 수 없는 문제

  • 예측을 통해 CPU 버스트 시간 구함. 예측치가 가장 짧은 프로세스에게 CPU 할당

165p 참고

문제점 평균 대기 시간을 최소화하지만, 시스템에서 평균을 줄이는 것은 항상 좋은 방식 아님

  • Starvation(기아): 버스트가 짧은 CPU에게만 CPU 할당시, 버스트가 긴 프로세스는 준비 큐에 서서 무한 정 기다리는 문제 발생

6.4.3 우선순위 스케줄링

준비 큐에서 기다리는 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU 할당

  • 우선순위 값을 표시

우선순위 값 결정 기준은 여러가지

  • CPU 버스트 시간을 우선순위로 정하면 SJF 알고리즘과 동일

우선순위도 선점형, 비선점형으로 나뉨

문제점

  • 기아 현상 발생

해결책

  • againg 기법 사용

  • 기다리는 시간 길어지면 우선순위 조금씩 높임

6.4.4 라운드 로빈 스케줄링

시분할 시스템의 성질을 가장 잘 활용한 새로운 스케줄링

  • 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한

  • 프로세스는 단지 준비 큐 뒤로 가서 자기 차례 기다림

  • 할당시간이 너무 길면 FCFS와 같은 결과 나옴

    • CPU 버스트 시간이 매우 긴 프로세스가 모든 작업을 수행할 만큼 할당 시간을 길게 설정한 경우

  • 할당시간이 너무 짧으면 CPU 사용하는 프로세스가 너무 빈번하게 교체되어 문맥 교환 오버헤드가 커짐

  • 이질적인 프로세스가 같이 실행되는 환경에서 효과적

  • n개의 프로세스가 준비큐에 있고 할당시간이 q일 때

    • 모든 프로세스는 (n-1)q시간 내에 적어도 한번은 CPU 할당 받음

장점

  • 대화형 프로세스의 빠른 응답 시간 보장

  • CPU버스트가 긴 프로세스에게 특별히 불이익 없음

    • 각 프로세스 대기시간은 그 포레스의 CPU 버스트 시간에 비례

할당시간이 만료되어 CPU 회수하는 방법은 타이머 인터럽트

비교

  • SJF 스케줄링은 평균 대기 시간에서는 가장 우수

    • 하지만 CPU 버스트 시간이 짧은 프로세스에게만 유리

    • CPU 버스트 시간이 긴 프로세스들은 전체 시스템의 성능 향상 시키기 위해 희생해야함

    • 일부의 희생을 통해 전체 성능 향상시키는 방법으로, 형평성을 간과

  • 라운드 로빈은 공정한 스케줄링 방식

  • CPU 버스트 시간을 작은 단우로 나누어 실행

    • CPU 사용양이 적으면 소요 시간 짧아짐

    • 반대로 사용양 많으면 소요시간도 거기에 비례해서 증가

    • 대기시간도 마찬가지

SJF는 평균 대기시간, 평균 소요 측면에서 좋은 결과 / 하지만 프로세스 간 대기시간, 소요시간 편차가 크며 평균 응답시간 지나치게 길어지는 문제 round robin은 평균 대기시간과 평균 소요시간이 FCFS보다 비효율적, 하지만 평균 응답시간은 더 짧아짐.

172P에 문제 예제 있음

6.5 멀티레벨 큐

준비큐를 여러 개로 분할해 관리하는 스케줄링 기법.

  • 즉, 프로세스들이 CPU를 기다리기 위해 한 줄로 서는 것이 아닌 여러 줄로 서는것

문제점

  • CPU는 하나밖에 없어서 어떤 줄에 서 있는 프로세스를 우선적으로 스케줄링 할지

  • 또한 프로세스가 도착 했을 때 어느 줄에 세워야 할지 결정하는 메커니즘 필요

  • 성격이 다른 프로세스는 별도 관리

    • 프로세스 성격에 맞는 스케줄링 적용하기 위해 준비 큐를 별도로 둠

    • 예컨대 빠른 응답을 필요로 하는 대화형 작업과

    • 그렇지 않은 작업을 별도의 큐에 줄을 세우고 대화형 작업이 기다리고 있다면 이들에게 우선적 CPU 할당

    • 대화형 작업이 없을 때 나머지 작업에게 CPU 할당

  • 위 예제와 같이 대화형 작업을 담기 위한 전위 큐(foreground queue)

  • 계산 위주의 작업 후위큐(back-ground queue)로 분할 운영

---->|전위큐 - 라운드 로빈|---->
---->|후위큐 - FCFS     |---->

전위큐는

  • 응답시간을 짧게하기 위해 라운드 로빈 스케줄링

후위큐는

  • FCFS를 사용해 context switching 오버헤드 줄임.

    • 계산 작업이라 응답시간이 큰 의미 없음

또 다른 스케줄링이 필요 큐 자체에 대한 스케줄링

여러 개의 준비 큐에 대해 어느 큐에 먼저 CPU를 할당할지 스케줄링 필요 1. 가장 쉽게 생각할 수 있는 고정 우선순위 방식

  • 큐에 고정적인 우선순위를 부여

  • 즉, 전위 큐에게 프로세스 우선적 CPU 할당

  • 후위 큐는 전위 큐가 비어있을 경우에만 CPU 할당 가능

  1. 타임 슬라이스 방식

  2. 큐에 대한 기아 현상 해소

  3. 각 큐에 대한 CPU 시간을 적절한 비율로 할당

6.4 멀티 레벨 피드백 큐

CPU를 기다리는 프로세스를 여러 큐에 줄 세운다는 측면에서 멀티레벨 큐와 동일

차이점: 프로세스가 하나의 큐에서 다른 큐로 이동가능하다는 점

  • 프로세스들의 다양한 성격을 반영해 구현 가능

    • 예컨대, 우선순위 스케줄링에서 기아 현상을 해결하기 위해 aging 기법을 멀티레벨 피드백 큐 방식으로 구현 가능

    • 우선순위가 낮은 큐에서 오래 기다렸으면 우선순위가 높은 큐로 승격시키는 방식

큐를 정의 하는 요소들

  • 큐의 수

  • 각 큐의 스케줄링 알고리즘

  • 프로세스를 상위 큐로 승격시키는 기준

  • 프로세스를 하위 큐로 강등시키는 기준

  • 프로세스가 도착했을 때 들어가는 큐를 결정하는 기준

멀티 레벨 피드백 큐 돌아가는 방식

----> 라운드 로빈 ----------->
                         |
라운드 로빈  <-------------|
(할당 시간 10) -->
|
|------> FCFS --------->

라운드 로빈을 한층 더 발전 시켜 프로세스의 CPU 작업 시간을 다단계로 분류, 작업 시간이 짧은 프로세스일수록 더욱 빠른 서비스가 가능하도록 함

작업시간이 긴 프로세스에 대해 문맥 교환없이 CPU 작업에만 열중할 수 있는 FCFS 방식 채택

6.4.7 다중 처리기 스케줄링

6.4.8 실시간 스케줄링

시분할 시스템은 작업 처리가 빠를 수록 좋지만 특정 시간 이내에 처리하지 못했다고 해서 심각한 상황 ㄴㄴ

  • 작업에 데드라인 존재하지 않음

이와 달리 실시간 시스템에서는 각 작업마다 주어진 데드라인 존재(이 안에 끝내야함)

  1. hard real-time system

  2. soft real-time system

1번은

  • 미사이 발사, 원자로 제어 등 정확히 지켜야 하는 시스템

  • 정해진 시간 안에 작업이 완료되도록 스케줄링 해야함

2번은

  • 데드라인 존재하지만 안지켰다고 해서 심각한 상황 발생 ㄴㄴ

  • 멀티미디어 스트리밍 시스템이 대표적, 시간당 정해진 프레임 수만큼의 서비스가 안이뤄지면 화면 중간에 끊김

  • 근데 이게 치명적인 결과 초래 ㄴㄴ

Previous5-process-관리Next8-가상메모리

Last updated

Was this helpful?