[운영체제/OS] 04장 CPU 스케줄링

1. 스케줄링의 개요

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

 

스케줄링의 단계

• 고수준 스케줄링(high-level, long-term, job scheduling)
  • 전체 시스템 부하를 고려하여 전체 작업 수를 조절하는 것
    • 작업(1개 또는 여러 개의 프로세스)을 수용할지 거부할지를 결정 → 승인 스케줄링(admission scheduling) → 멀티 프로그래밍 정도(degree of multiprogramming)
    • 메인 프레임과 같은 큰 시스템에서 규모가 큰 일괄 작업을 처리할 때 사용
• 저수준 스케줄링(low-level, short-term scheduling)
  • 어떤 프로레스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정 → 단기 스케줄링
    • 실행 상태, 대기 상태, 준비 상태,로 보내는 것을 결정
  • 실제 작업이 이루어짐

• 중간 수준 스케줄링 (middle level scheduling)
  • 프로세스가 활성화된 후에도 여러 이유로 시스템에 과부하가 걸릴 수 있는 경우 시스템 부하를 조절
  • 중지(suspend)와 활성화(active)로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 방지
    • 보류 상태 결정 → 저수준 스케줄링이 원만하게 이루어지도록 완충하는 역할 수행

---

스케줄링의 목적

• 공평성: 모든 프로세스가 자원을 공평하게 배정받아야 하며, 자원 배정 과정에서 특정 프로세스가 배제되어서는 안 됨
• 효율성: 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 함
• 안전성: 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 함
• 확장성: 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 하며 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야 함
• 반응 시간 보장: 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 함
• 무한 연기 방지: 특정 프로세스의 작업이 무한히 연기되어서는 안 됨

 

 

---

2. 스케줄링 시 고려 사항

 

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

선점형 스케줄링(preemptive scheduling) ** → 빼앗기 가능

• 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 OS가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식
• ex) 인터럽트 처리 → CPU가 인터럽트를 받으면 현재 실행 중인 작업을 중단하고 커널을 깨워 인터럽트를 처리
• OS가 필요하다고 판단하면 실행 상태에 있는 프로세스 작업을 중단시키고 새로운 작업을 시작할 수 있는 방식
• 하나의 프로세스가 CPU를 독점할 수 없기 때문에 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합
• 문맥 교환 같은 부가적인 작업으로 낭비 생김
• 대부분의 저수준 스케줄러는 선점형 스케줄링 방식을 사용
• 선점형 스케줄링 방식의 스케줄러에 존재하는 비선점형 프로세스 → 시스템 백업 프로세스 (중요도 매우 낮음)

 

비선점형 스케줄링(non-preemptive scheduling)

• 어떤 프로세스가 실행 상태에 들어가 CPU를 사용하면 그 프로세스가 종료되거나 자발적으로 대기 상태에 들어가기 전까지는 계속 실행되는 방식
• 선점형 스케줄링보다 스케줄러의 작업량이 적고 문맥 교환에 의한 낭비도 적음
• CPU 사용 시간이 긴 프로세스 때문에 CPU 사용 시간이 짧은 여러 프로세스가 오랫동안 기다리게 되어 시스템의 처리율이 떨어짐
• 과거의 일괄 작업 시스템에서 사용하던 방식

 

 

 

---

프로세스 우선순위(process priority)

• 커널 프로세스의 우선 순위가 일반 프로세스보다 높음(일반 프로세스: 유저가 생성시킨 프로세스)
• 시스템에는 다양한 우선순위의 프로세스가 공존 → 우선순위가 높은 프로세스가 CPU를 먼저, 더 오래 차지

 

 

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

CPU 집중 프로세스 (CPU burst process)

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

입출력 집중 프로세스 (I/O burst process)

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

 

 

우선순위 배정

• 스케줄링 할 때 입출력 집중 프로세스의 우선순위를 CPU 집중 프로세스보다 높이면 시스템의 효율이 향상
• 사이클 훔치기

 

전면/후면 프로세스

1. 전면 프로세스(foreground process)
   • GUI를 사용하는 운영체제에서 화면의 맨 앞에 높인 프로세스
   • 현재 입력, 출력을 사용하는 프로세스 → 사용자의 요구에 즉각 반응해야 함
   • 사용자와 상호작용이 가능한 상호작용 프로세스
2. 후면 프로세스(background process)
   • 시스템의 경우 background로 실행 (웹서버 → 클라이언트의 요청이 있는 경우, 압축 프로그램 - 사용자 입력 없이 작동하는 일괄 작업 프로세스)

• 커널: 시스템의 안전성과 관련 있음
• 대화형, 입출력 집중: 사용자와의 상호작용이 있는 프로세스

 

---

3. 다중 큐

준비 상태의 다중 큐(multi-queue)

• 준비 상태에서 우선순위에 따라 여러 개의 큐를 만들면, 프로세스에 CPU를 할당하는데 효율적
• CPU스케줄러는 우선순위가 가장 높은 큐(0번 큐)의 맨 앞에 있는 프로세스 6에 CPU 할당
• 스케줄링 알고리즘 → 준비 큐를 몇 개로 나눌지, 여러 개의 준비 큐에 있는 프로세스 중 어떤 프로세스에 CPU를 할당할지 결정

 

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

1. 고정 우선순위 방식
   • OS가 프로세스의 우선순위를 부여하면 프로세스가 끝날때까지 바뀌지 않음
   • 구현이 쉽지만, 시스템의 상황이 시시각각 변하므로 시스템 변화에 대응하기 어려워 작업 효율 떨어짐
2. 변동 우선순위 방식
   • 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식
   • 구현이 어렵지만 시스템 효율을 높임

 

 

대기 상태의 다중 큐

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

• 0번인 HDD부터 시작해서 LAN에 대한 준비 상태가 끝나 ready queue로 옮겨 가는 상황

 

준비 상태의 다중큐 VS 대기 상태의 다중 큐

• 준비 큐 → 한 번에 하나의 프로세스를 꺼내 CPU를 할당
• 대기 큐 → 여러 PCB을 동시에 꺼내 준비 상태로 옮김
  • 많은 입출력장치가 있어 입출력이 동시에 끝날 경우 여러 개의 인터럽트가 한꺼번에 처리됨
  • 인터럽트 벡터 자료구조 사용

---

4. 스케줄링 알고리즘 **

• (프로세스 다음으로 중요!!)

 

스케줄링 알고리즘 종류

구분 종류

비선점형 알고리즘	FCFS 스케줄링, SJF 스케줄링, HRN 스케줄링
선점형 알고리즘	라운드 로빈(RR) 스케줄링, SRT, 스케줄링, 다단계 큐 스제쿨링, 다단계 피드백 큐 스케줄링
둘다 가능	우선순위 스케줄링

 

스케줄링 알고리즘의 선택 기준

• CPU 사용률(CPU utilization)
  • 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
  • 가장 이상적인 수치는 100% 미만이지만, 실제로 여러가지 이유로 90%에도 못 미침
• 처리량(throughput)
  • 단위 시간당 작업을 마친 프로세스의 수
  • 이 수치가 클수록 좋은 알고리즘임
• 대기 시간
  • 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간
• 응답 시간
  • 프로세스 시작 후 첫번째 출력, 반응이 나올 때까지 걸리는 시간
• 반환 시간
  • 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간
  • 대기 시간 + 실행 시간

 

 

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

• 대기시간: 프로세스 생성 후 실행되기 전까지 대기하는 시간
• 응답시간(response time): 첫 작업을 시작한 후 첫번째 출력(반응)이 나오기까지의 시간
• 실행시간(execution time): 프로세스 작업이 시작된 후 종료되기까지의 시간
• 반환 시간(turn-around time): 대기 시간을 포함해 실행이 종료될 때까지의 시간
• 평균 대기 시간 (AWT, Average Wait Time) : 모든 프로세스의 대기 시간을 합한 뒤 프로세스의 수로 나눈 값
• 평균 반환 시간 (ATT, Average Turn-around time)

 

---

FCFS(First Come First Served) 스케줄링

FCFS의 스케줄링 동작 방식 (FIFO 자료구조 방식)

• 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식
• 한 번 실행되면 그 프로세스가 끝아냐만 다음 프로세스를 실행 가능
• 큐가 한 개라 모든 프로세스는 우선순위가 동일

 

FCFS의 성능

FCFS 스케줄링의 평가

• 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어짐
• 현재 작업중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어짐(콘보이 효과)
• 실제 시스템에서는 많이 활용하지 않음

---

 

SJF(Shortest Job First) 스케줄링

• 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식
• 최단 작업 우선 스케줄링
• 콘보이 효과(무조건 대기해야 하는 상황)를 완화하여 시스템의 효율성을 높임

 

• 시작지점: P1은 대기하지 않고 바로 실행됨, 이후 P3가 P2보다 더 짤은 실행시간 을 가지고 있으므로 먼저 시작됨 (대기 시간 단축 가능)
• FCFS보다 3초 좋은 성능을 보임

 

SJF 스케줄링의 평가

• 작은 작업을 먼저 실행하여 시스템의 효율성이 좋아짐
  • 먼저 도한 큰 작업으로 인해 작은 작업이 지연되는 FCFS 스케줄링보다 평균 대기시간이 줄어듬

단점들

1. 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려움
   • 사용자와의 상호작용이 빈번이 발생하기 떄문 (사용자의 입력을 위해 대기)
   → 프로세스가 작업 시간을 직접 알려주어 해결 가능
2. 공평성 위배
   • 작업 시간이 길다는 이유만으로 계속 뒤로 밀려 공평성이 현저히 떨어짐 (starvation, 아사, 굶주림 현상, 무한 봉쇄 infinite blocking)
   ⇒ 에이징(나이먹기)
   • 프로세스가 양보할 수 있는 상한선을 결정하는 방식
   • 프로세스가 자신의 순서를 양보할 때마다 나이를 한 살씩 먹어 최대 몇 살까지 양보하도록 규정하는 것

 

---

우선순위(priority) 스케줄링 - 비선점

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

 

우선순위 스케줄링의 평가

• 준비 큐에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스를 먼저 CPU를 할당하므로 공평성을 위배하고 아사 현상을 발생
• 프로세스의 우선순위를 매번 바꿈으로써 오버헤드가 발생하여 시스템의 효율성 저하

 

---

우선순위 스케줄링 - 선점

• 프로세스의 중요도에 따른 우선순위를 반영한 스케줄링 알고리즘
• 중간에 우선순위가 더 높은 프로세스가 큐에 들어오면, 언제든지 CPU를 선점하여 처리
• 문제점
  • 이 경우에도 아사 현상 발생 → P1 : 우선순위가 높은 프로세스가 들어올 때 뒤로 밀리게 됨
  • 오버헤드 →큐 내에서의 sorting에 대한 오버헤드는 줄일 수 있지만, 원래 점유하고 있던 프로세스를 레디큐로 다시 보내야 하면서 context-switching 오버헤드는 무시할 수 없다

• 대기시간
  • P1: 3초~30 : 27
  • P2: 6~15: 9
  • 평균 대기시간 AWT = (27+9+0)/3 = 12 ms

고정 우선순위 알고리즘

• 한 번 우선순위를 부여 받으면 종료될 때까지 우선순위가 고정
• 단순하게 구현 가능, 시시각각 변하는 시스템의 상황을 반영하지 못해 효율성 저하

변동 우선순위 알고리즘

• 일정 시간마다 우선순위가 변하여 일정 시간마다 우선순위를 새로 계산하고 이를 반영
• 복잡하지만 시스템 상황을 반영하여 효율적인 운영 가능

 

---

 

HRN(Highest Response Ratio Next) 스케줄링

• SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘
• 최고 응답률 우선 스케줄링
• 서비스를 받기 위해 기다린 시간, CPU 사용 시간을 고려하여 스케줄링을 하는 방식
• 프로세스의 우선순위를 결정하는 기준

HRN 스케줄링의 평가

• 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려해 아사 현상을 완화
• 대기 시간이 긴 프로세스의 우선 순위를 높임으로써 CPU
• 할당받을 확률을 높임
• 여전히 공평성에 위배되어 많이 사용하지 X

 

 

---

라운드 로빈(RR: Round-Robin) 스케줄링

• 한 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식
• 선점형 알고리즘 중 우선순위가 적용도지 않은 가장 단순하고 대표적인 스케줄링 방
• 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행
• 프로세스가 CPU를 일정 시간동안 사용한 후 다른 프로세스에 주어야 하기 때문에 앞의 긴 작업을 무작정 기다리는 콘베이 효과가 줄어듦

 

라운드 로빈 스케줄링의 평가

• 타임슬라이스 크기와 문맥 교환
  • 라운드 로빈 스케줄링이 효과적으로 작동하려면 문맥 교환에 따른 추가 시간을 고려하여 타임 슬라이를 적절히 설정해야 함
• 타임 슬라이스가 큰 경우
  • 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보여져 FCFS 스케줄링과 다를 것이 없음
    • ex) 비디오 플레이어, 워드 프로세서가 동시에 실행된다고 가정할 때 비디오가 끊겨 보이고 워드 프로세서의 반응 속도 매우 느릴 것
• 타임 슬라이스가 작은 경우
  • 매우 작은 값으로 설정 시 여러 프로그램이 동시에 실행되는 것처럼 느껴지겠지만, 시스템의 전바적인 성능 저하
  • 문맥 교환이 너무 자주 일어나 문맥 교환에 걸리는 시간이 실제 작업 시간보다 상대적으로 커지며, 문맥 교환에 많은 시간을 낭비하여 실제 작업을 못하는 문제가 발생
    • 유닉스 OS에서는 타임 슬라이스가 대략 100밀리초

 

---

SRT(Shortest Remaining Time) 우선 스케줄링

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

 

SRT 스케줄링의 평가

• 현재 실행중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야 하므로 SJF스케줄링에는 없는 작업이 추가됨
• 가장 대기 시간이 짧은 알고리즘이지만, OS가 프로세스의 종료 시간을 예측하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 x

 

 

---

다단계 큐 스케줄링

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

 

다단계 피드백 큐 스케줄링

• 오늘 날의 운영체제가 cpu 스케줄링을 위해 일반적으로 사용하는 방식 (변동 우선순위 알고리즘의 전형적인 예)
• 프로세스가 CPU를 한 번씩 할당받아 실행될 때마다 프로세스의 우선순위를 낮춤으로써, 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화
• 우선순위가 낮아진다고 할지라도 커널 프로세스가 일반 프로세스의 큐에 삽입되진 않음
• 우선순위에 따라 타임 슬라이스의 크기가 다름 (우선순위가 낮을수록 타임 슬라이스의 크기가 다름)
• 우선순위가 낮아질수록 해당 큐의 타임 슬라이스가 커짐 (보상 정책)
• 마지막 큐에 있는(우선순위가 가장 낮은) 프로세스는 무한대의 타임슬라이스를 얻음
  • 마지막 큐는 들어온 순서대로 작업을 마치는 FCFS 스케줄링 방식으로 동작

 

---

인터럽트 처리

1. 인터럽트의 개념

• 순차적 프로그래밍(sequential programming)
  • 폴링 작업: 운영체제가 주기적으로 입출력장치를 확인하여 입출력 요청 여부를 확인하여 처리
• 이벤트 드리븐(event-driven)
  • 입출력 요청, 완료 시 이벤트 발생 시켜 이 사실을 알리는 인터럽트

 

2. 동기적, 비동기적 인터럽트

• 동기적 인터럽트(synchronous interrupt)
  • 실행 중인 명령어로 인해 발생
  • 프로그램 상 문제 때문에 발생하는 인터럽트(다른 사용자의 메모리 영역에 저근, 오버 플로나 언더플로 발생)
  • 작업자가 의도적으로 프로세스 중단을 위해 발생시킨 인터럽트(Ctrl+C)
  • 입출력 장치 등 주변 장치의 조작에 의한 인터럽트
  • 산술 연산 중 발생하는 인터럽트(0으로 나눔)
• 비동기적 인터럽트(asynchronous interrupt)
  • 하드디스크 읽기 오류
  • 메모리 불량 등 하드웨어적인 오류
  • 키보드 인터럽트, 마우스 인터럽트

 

3. 인터럽트 처리 과정

• 인터럽트 번호와 번호에 붙어있는 함수의 쌍으로 구성
• ex) 윈도우 화면의 최소화 버튼 - 창을 작게 만드는 함수ㅇ 정의
• IRQ(인터럽트 번호) : 인터럽트 식별
• 인터럽트 벡터
  • 각 인터럽트를 처리하는 함수가 연결되어 있음
  • 인터럽트 핸들러**: 인터럽트 발생 시 어떤 일을 처리할 것인지 함수에 정의되어 있음**

1. 인터럽트 발생 시, 현재 실행 중인 프로세스는 일시 정지 상태로 변환
   • 재시작을 위해 현재 프로세스 관련 정보를 임시로 저장
2. 인터럽트 컨트롤러가 실행되어 인터럽트의 처리 순서 결정
   • 여러 인터럽트 동시에 발생시 인터럽트의 우선순위를 고려하여 중요한 인터럽트부터 처리하도록 순서 결정
3. 먼저 처리할 인터럽트가 결정되면, 인터럽트 벡터에 등록된 인터럽트 핸들러가 실행됨
   • 인터럽트 핸들러: 인터럽트 처리를 위해 미리 정의된 함수
   • 인터럽트 백터: 인터럽트와 인터럽트 핸들러를 일대일로 연결한 자료구조
4. 인터럽트 벡터에 연결된 핸들러가 인터럽트 처리를 마치면, 일시 정지된 프로세스가 다시 실행되거나 종료
   • 입출력 완료의 경우 → 일시 정지된 프로세스가 다시 실행됨
     • 다른 프로세스의 메모리 영역 침범, 오류 의 경우 종료

 

4. 인터럽트와 이중 모드

• 커널 모드(커널 프로세스 실행 상태)
• 사용자 모드(사용자 프로세스 실행 상태)
• 이중모드(dual mode): 사용자 모드에서 커널 모드로 전환되어, 운영체제가 두 모드를 전환하며 일처리를 하는 것
  • 사용자 모드가 하드디스크 입출력, 프로세스 생성과 같이 커널 기능을 사용하려면 시스템 호출을 이용해 커널 프로세스에 작업 요청 필요
  • 시스템 호출을 요청 후, 대기 상태로 전환되고 커널 프로세스는 요청받은 작업을 처리함

→ OS가 자원을 보호하기 위해 사용하는 기법 (커널이 시스템 호출으를 통해서만 자원에 접근하도록 제한)

→ 다양한 방법으로 시스템 호출 사용을 위해 OS는 **API(Application Programming Interface)**를 제공

 

 

사용자가 커널 모드로 진입하는 경우

1. 시스템 호출 사용

• 시스템 호출에 의한 커널 모드 진입 (자발적)

1. 인터럽트 발생

• 비자발적.
• 잘못된 명령을 수행하여 동기적 인터럽트 발생하여 프로세스가 강제 종료됨