(9) CPU 스케줄링

탱구리·2025년 6월 18일

Computer System

목록 보기
9/10

CPU 스케줄러

여러 프로세스의 상황을 고려하여 CPU와 시스템 자원의 배정을 결정

Selects from processes in ready queue, and allocates a CPU core to one of them.

CPU 스케줄링의 단계

  • 고수준 스케줄링 (장기 스케줄링, 작업 스케줄링, 승인 스케줄링)
    전체 시스템의 부하를 고려하여 작업을 시작할지 말지 결정

    • 시스템 내의 전체 작업 수를 조절하는 것
    • 어떤 작업을 시스템이 받아들일지/거부할지 결정
    • 시스템 내에서 동시에 실행 가능한 프로세스의 총 개수가 정해짐

  • 중간 수준 스케줄링
    시스템에 과부하가 걸려서 전체 프로세스 수를 조절해야 한다면 이미 활성화된 프로세스 중 일부를 보류 상태로 보냄

    • 중지/활성화로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막음
    • 저수준 스케줄링이 원만하게 이루어지도록 완충하는 역할

  • 저수준 스케줄링 (단기 스케줄링)
    실제 작업을 수행

    • 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정

CPU 스케줄링의 목적

CPU 스케줄링의 방식

  • 비선점형
    한 프로세스가 CPU를 할당 받으면 스스로 반납할 때까지 CPU 점유

    • 선점형 스케줄링보다 스케줄러의 작업량 ↓, 문맥 교환에 의한 낭비도 ↓
    • 기다리는 프로세스가 많아 처리율이 떨어짐
    • 일괄 작업 방식 스케줄러에 사용

  • 선점형
    CPU 사용 중에도 더 높은 우선순위를 가진 프로세스가 오면 강제로 CPU를 뺏길 수 있음

    • 대부분의 저수준 스케줄러가 이 방식을 사용
    • 문맥 교환의 오버헤드가 多
    • 시분할 방식 스케줄러에 사용

프로세스 우선수위

커널 프로세스의 우선순위 > 일반 프로세스의 우선순위

  • CPU 집중 프로세스
    수학 연산과 같이 CPU를 많이 사용하는 프로세스로, CPU 버스트가 많은 프로세스

  • 입출력 집중 프로세스 ⭐
    저장장치에서 데이터를 복사하는 일과 같이 입출력을 많이 사용하는 프로세스로, 입출력 버스트가 많은 프로세스

입출력 집중 프로세스의 우선순위 > CPU 집중 프로세스의 우선순위

  • 전면 프로세스 (상호작용 프로세스) ⭐

    • GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스
    • 현재 입출력을 사용하는 프로세스
    • 사용자와 상호작용이 가능

  • 후면 프로세스 (일괄 작업 프로세스)

    • 사용자와 상호작용 X
    • 사용자의 입력 없이 작동

전면 프로세스의 우선순위 > 후면 프로세스의 우선순위

준비 상태의 다중 큐

프로세스는 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입됨

한 번에 하나의 프로세스를 꺼내어 CPU 할당

프로세스의 우선순위를 배정하는 방식

  • 고정 우선순위 방식

    • OS가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 X
    • 구현하기 쉬우나 시스템 변화에 대응하기 어려워 작업 효율 ↓

  • 변동 우선순위 방식

    • 프로세스 작업 중간에 부여받은 우선순위가 변함
    • 구현 어렵지만 시스템 효율성 ↑

대기 상태의 다중 큐

시스템 효율을 높이기 위해 대기 상태에서는 같은 입출력을 요구한 프로세스끼리 모아 놓음

여러 개의 PCB를 동시에 꺼내어 준비 상태로 옮김
대기 큐에서 동시에 끝나는 인터럽트를 처리하기 위해 인터럽트 벡터라는 자료구조 사용

다중 큐

  1. 🔄 준비 → 실행 (디스패치)
    운영체제의 스케줄러가 Ready 큐에서 하나를 골라 CPU를 할당합니다.

  2. ⏱ 실행 → 준비 (타임아웃)
    할당된 시간이 지나면 다시 Ready 상태로 돌아갑니다.

  3. 🖥 실행 → 대기 (입출력 요청)
    입출력(I/O)을 요청하면 해당 작업을 기다리기 위해 대기 상태로 전환됩니다.

  4. ✅ 대기 → 준비 (입출력 완료 인터럽트)
    입출력이 끝나면 인터럽트가 발생해서 다시 Ready 상태로 이동합니다.

스케줄링 알고리즘 평가 기준

  • CPU 사용률
  • 처리량
  • 대기 시간: 프로세스가 생성된 후 실행되기 전까지 대기하는 시간
    • 평균 대기 시간
      모든 프로세스 대기 시간의 합프로세스의 수\frac{모든\,프로세스\,대기\,시간의\,합}{프로세스의\,수}
      예시:
  • 응답 시간: 첫 작업을 시작한 후 첫 번째 출력(반응)이 나오기까지의 시간
  • 실행 시간: 프로세스 작업이 시작된 후 종료되기까지의 시간
  • 반환 시간: 대기 시간을 포함하여 실행이 종료될 때까지의 시간

FCFS 스케줄링

First-Come, First-Served (선입선출)

준비 큐에 도착한 순서대로 CPU 할당하고, 해당 프로세스가 완료될 때까지 CPU를 점유하는 비선점형 방식
큐가 하나라 모든 프로세스의 우선순위가 동일함

현재 작업 중인 프로세스가 I/O 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율 ↓

⚠️ 콘보이 효과 : 실행 시간이 긴 프로세스가 먼저 오면, 뒤따르는 짧은 프로세스들이 오래 대기

SJF 스케줄링

Shortest Job First (최단 작업 우선 스케줄링)

준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU 할당하는 비선점형 방식

📣 콘보이 효과 완화 → 시스템 효율 ↑

OS가 프로세스 종료 시간을 정확하게 예측하기 어려움

⚠️ 아사(starvation) 현상 : 작업 시간이 길다는 이유만으로 계속 뒤로 밀려 공평성이 현저히 떨어짐

➡️ 에이징(나이 먹기) : 아사 현상의 완화 방법
프로세스가 양보할 수 있는 상한선(몇 살까지 양보 가능?)을 정하는 방식
프로세스가 자신의 순서를 양보할 때마다 나이를 한 살씩 먹음

HRN 스케줄링

Highest Response Ratio Next (최고 응답률 우선 스케줄링)

서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링을 하는 비선점형 알고리즘

📣 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려하여 아사 현상을 완화

대기 시간이 긴 프로세스의 우선순위를 높임으로써 CPU를 할당받을 확률을 높임

but 여전히 공평성이 위배되어 많이 사용 X

우선순위=대기 시간+CPU 사용 시간CPU 사용 시간우선순위 = \frac{대기\,시간 + CPU\,사용\,시간}{CPU\,사용\,시간}

라운드 로빈 스케줄링

선점형 알고리즘 중 가장 단순하고 대표적인 방식

한 프로세스가 할당받은 시간(타임 슬라이스)동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다림

프로세스들이 작업을 완료할 때까지 게속 순환하면서 실행

효과적으로 작동하려면 문맥 교환에 따른 추가 시간을 고려하여 타임 슬라이스를 적절히 설정해야 함

⚠️ 타임 슬라이스가 큰 경우 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보여 FCFS(선입선출) 스케줄링과 다를 게 없음

⚠️ 타임 슬라이스가 작은 경우 문맥 교환이 너무 자주 일어나게 됨

➡️ 타임 슬라이스는 되도록 작게 설정하되 문맥 교환에 걸리는 시간을 고려하여 적당한 크기로 하는 것이 중요함

SRT 우선 스케줄링

Shortest Remaining Time

기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아있는 작업 시간이 가장 적은 프로세스를 선택

남은 실행 시간이 가장 짧은 프로세스에게 CPU를 우선 할당하는 선점형 방식

현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더적은프로세스와 문맥 교환을 해야 하므로 SJF 스케줄링에는 없는 작업이 추가됨

⚠️ OS가 프로세스 종료 시간을 예측하기 어렵고 아사 현상이 일어나기 때문에 잘 이용하지 X

우선순위 스케줄링

프로세스 중요도에 따른 우선순위를 반영한 스케줄링 알고리즘

비선점형/선점형 방식에 모두 적용 可

SJF(비): 작업 시간이 짧은 프로세스에 높은 우선순위 부여
HRN(비): 작업 시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순위 부여
SRT(선): 남은 시간이 짧은 프로세스에 높은 우선순위 부여

  • 고정 우선순위 알고리즘
  • 변동 우선순위 알고리즘

⚠️ 준비 큐에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스에 먼저 CPU를 할당하므로 공평성을 위배하고 아사 현상을 일으킴

⚠️ 준비 큐에 있는 프로세스의 순서를 무시하고 프로세스의 우선순위를 매번 바꿔야 하기 때문에 오버헤드가 발생하여 시스템 효율성 ↓

다단계 큐 스케줄링

우선순위에 따라 준비 큐를 여러 개 사용
고정형 우선순위 사용
상단 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작됨

다단계 피드백 큐 스케줄링

📣 프로세스가 CPU를 한 번씩 할당받아 실행될 때마다 프로세스의 우선순위를 낮춤 → 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제 완화

*우선순위가 낮아진다 할지라도 커널 프로세스가 일반 프로세스 큐에 삽입되지는 X

우선순위에 따라 타임 슬라이스 크기가 다름
우선순위가 낮아질수록 CPU를 얻을 확률이 적어지므로 한번 CPU를 잡을 때 많이 작업하라고 낮은 우선순위의 타임 슬라이스를 크게 함
마지막 큐(우선순위 최하위)에 있는 프로세스는 무한대의 타임 슬라이스를 얻음 (마지막 큐는 FCFS 스케줄링 방식으로 동작)

profile
탱구리
이전 포스트

(8) 스레드

다음 포스트

(10) 공유자원

0개의 댓글