[쉽게 배우는 운영체제 2판] 4. CPU 스케줄링

 

 

 

1. 스케줄링의 개요

1. 레스토랑 관리자의 스케줄링

• CPU 스케줄러 == 프로세스 스케줄러
• 스케줄링은 여러 프로세스의 상황을 고려하여 CPU와 시스템 자원을 어떻게 배정할지 결정하는 일.

2. CPU 스케줄링

• 각 프로세스마다 다양한 상황과 순서, 속도를 고려해야 한다.

고수준 스케줄링 (승인 스케줄링, 장기 스케줄링, 작업 스케줄링)

• 시스템 내의 전체 작업 수를 조절하는 것 : 받아들일지 / 거부할지
• 전체 시스템의 부하를 고려하여 작업을 시작할지 말지, 전체 프로세스 수( 멀티프로그래밍 정도 )가 결정된다. 
• 가장 큰 단위
• 1개 또는 여러개의 프로세스로 이루어진다.
• 시스템 과부화 우려

저수준 스케줄링 (단기 스케줄링)

• 가장 작은 단위
• 어떤 프로세스에 CPU를 할당할지, 어떤 기준으로 타임 슬라이스를 정할지
• 실행 상태에 있는 프로세스를 대기 상태로 보내며, 대기 상태의 프로세 스를 준비 상태로 보내는 것

중간 수준 스케줄링

• 시스템의 부하를 조절하려면 고수준보단 중간이 낫다.
• 중지와 활성화로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막는다.
• 일부 프로세스를 중지 상태로 옮김으로써 나머지 프로세스가 원만하게 작동하도록 지원한다.
• 완충하는 역할

 

3. 스케줄링의 목적

• 모든 프로세스가 공평하게 작업하도록 하는 것
• 우선순위 배정이 중요하다.
• 공평성: 자원을 공평하게 배정 (효율을 위해 공평성 희생: 운영체제 프로세서 > 일반 프로세스)
• 효율성: 유효 자원이 있는 곳이 우선순위
• 안정성: 프로세스부터 자원을 보호해야 한다.
• 확장성: 안정정으로 작동하고 자원이 늘어나면 반영해야 한다.
• 반응 시간 보장: 응답이 없어도 시간 안에 프로세스의 요구에 반응해야 한다.
• 무한 연기 방지

 

 

 

 

 

 

 

2. 스케줄링 시 고려 사항

• 우선적으로 CCPU에 할당할지 결정

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

• 선점형 스케줄링
  • 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식
  • 인터럽트 처리
  • 문맥교환, 낭비
  • 빠른 응답 시간, 대화형 시스템이나 시분할 시스템에 적합
  • 저수준 스케줄
• 비선점형 스케줄링
  • 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식이다.
  • 스케줄러의 작업량이 적고 문맥교환에 의한 낭비도 적다
  • CPU 사용 시간이 짧은 여러 프로세스가 오랫동안 기 다리게 되어 전체 시스템의 처리율이 떨어진다.
  • 일괄 작업 시스템
  • 시스템 백업 프로세스

 

 

2. 프로세스 우선순위

• 커널 우선순위 > 사용자 프로세스
• 우선순위가 높다 == 더 빨리 자주 실행된다. == CPU를 먼저, 더 오래 차지한다.
• 일반 프로세스의 우선순위는 사용자가 조절할 수 있다 (다른 프로세스에도 영향을 준다.)

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

• 프로세스: 생성 -> 준비 -> 실행 -> 대기 -> 완료
• CPU 버스트: CPU를 할당받아 실행하는 작업, 수학연산 (CPU 집중 프로세스)
• 입출력 버스트: 입출력 작업, 저장장치에 데이터 복 (입출력 집중 프로세스)
• 입출력 집중 프로세스 먼저 실행, 입출력이 오기 전까지 다른 프로세스가 CPU 점유
• 사이클 훔치기: 입출력 집중 프로세스 가 CPU 집중 프로세스보다 실행 상태에 먼저 들어가는 경우

 

4. 전면 프로세스와 후면 프로세스

• 전면 프로세스: GUI 를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스를 말한다
  • 입력과 출력, 사용자와 상호작용이 가능하다.
• 후면 로세스: 사용자와 상호작용이 없는 프로세스다
  • 일괄 작업 프로세스
• 전면 프로세스는 사용자의 요구에 즉각 반응해야 하지만 후면 프로세스는 상호작용이 없다.
• 전면 프로세스의 우선순위가 후면 프로세스보다 높다.

 

5. 정리

• 우선순위 높음: 커널 프로세스, 전면 프로세스, 대화형 프로 세스, 입출력 집중 프로세스
• 우선순위 낮음: 일반 프로세스, 후면 프 로세스, 일괄 작업 프로세스, CPU 집중 프로세스

 

 

 

 

 

 

 

3. 다중 큐

• CPU 스케줄러가 관리

1. 준비 상태의 다중 큐

• 프로세스 제어블록에 프로세스 중요도가 표시된다.
• CPU 스케줄러는 모든 프로세스 제어 블록을 뒤져서 우선순위가 가장 높은 프로세스에 CPU를 할당한다.
• 한번에 하나의 프로세스를 꺼내어 CPU를 할당한다.
• 우선순위에 따라 여러 큐를 만들기
• 우선순위 배정 방식
  • 고정 우선순위 방식: 구현은 쉽지만, 시스템의 변화에 대응하기 어려워 작업 효율이 떨어진다.
  • 변동 우선순위 방식: 구현은 어렵지만, 시스템 효율성을 높일 수 있다.

 

2. 대기 상태의 다중 큐

• 대기상태는 입출력이 완료되기를 기다리 프로세스들이 모여있다.
• 대기 상태에서는 같은 입출력을 요구한 프로세스끼리 모아놓는다
• 여러 개의 프로세스 제어 블록을 동시에 떠내어 준비 상태로 옮긴다.
• 입출력이 동시에 끝나면 여러 개의 인터럽트가 한꺼번에 처리된다. -> 인터럽트 벡터 필요
• 인터럽트 벡터: 동시에 완료된 입출력 정보와 처리 방법이 담겨 있는데, 이 정보에 따라 완료된 프로세스 제어 블록은 모두 준비 상태로 이동한다.

 

 

 

 

4. 스케줄링 알고리즘

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

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

• CPU 사용률: 사용된 시간을 측정
• 처리량: 단위 시간당 작업을 마친 프로세스수
• 대기 시간: 생성후 실행되기 까지의 시간
• 응답 시간: 얼마만에 반응하는지
• 반환 시간: 사용하던 자원을 모두 반환하는데 걸리는 시간

 

• 성능비교 == 평균 대기 시간 ( 모든 프로세스의 대기 시간을 합한 뒤 프로세스의 수로 나눈 값 )

2. FCFS 스케줄링 (선입선출 스케줄링) - 비선점형

• 큐에 도착한 순서대로 CPU할당받는 비선점형 (우선순위 동일)

• 성능: {P1(0) + P2(30-3) +P3(48-6)} % 3 = 23초 
• 평가: 단순하고 공평 / CPU를 차지하 면 다른 프로세스들은 하염없이 기다리느라 시스템의 효율성이 떨어진다.
  • 콘보이 효과 or 호위 효과 : 컨베이어 벨트에 작업물이 한 줄로 늘어서 있 을 때 앞의 작업이 오래 걸려서 뒤의 작업이 지연되는 현상

3. SJF 스케줄링 (최단 작업 우선 스케줄링) - 비선점형

• 실행 시간이 가장 짧은 작업부터, 
• 콘보이 효과 완화

• 성능:{ P1(0) + P2(30-6) + P3(39-3) } % 3 = 20초
• 평가: 평균 대기 시간이 줄었지만..
  • 프로세스의 종료 시간을 정확하게 예측하기 어렵다. (사용자와의 상호작용)
    • 프로세스가 자신의 작업시간을 운영체제에 알려주면 된다. -> 정확한 시간을 알기 어렵다.
  • 공평성에 위배된다: 계속 양보하다 보면 아사현상 or 무한 봉쇄현상이 일어난다, 작업시간이 길다는 이유로 계속 뒤로 밀린다.
    • 에이징: 양보의 상한선을 정한다. 

4. HRN 스케줄링 (최고 응답률 우선 스케줄링) - 비선점형

• 아사 현상 해결, 
• 서비스를 받기 위해 기다린 시간과 CPU사용 시간을 고려함. (대기 시간 고려)
• 성능: P1 -> P3 -> P2
  • P2 ( (27 + 18) %18 = 2.5) < P3 ( 가（24 + 9）% 9 = 3.67)
  • (0 + 24 十36）% 3 = 20초

• 평가: 아사현상을 완화하고, CPU 할당 받을 활률을 높인다.
  • 여전히 공평성이 위배되어 있다.

5. 라우드 로빈 스케줄링 - 선점형

• 한 프로세스가 할당받은 시간(타임 슬라이스)동안 작업을 하다가 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식
• 완료 될떄까지 계속 순환한다.

• 성능
  • 총 대기 시간은 0(P1) +  7(P2) + 14(P3) + 19(P1) + 19(P2) +  8(P1)= 67밀리초이고,
  • 평균 대기 시간은 67 %3 = 22.33밀리초다.
• 평가: 콘보이 효과 줄어듬
  • 문맥교환이 있음

 

6. SRT 우선 스케줄링 - 선점형

• SJF 스케줄링 + 라운드 로빈 스케줄링
• 최소 잔류 시간 우선 스케줄링
• 남은 작업 시간이 적은 프로세스에 CPU먼저 할당

• 성능:
  • 0(P1) + 4(P3) + 16(P2) + 27(P1) = 47밀리초이고,
  • 평균 대기 시간은 47 % 3 = 15.66밀리초다.
• 평가: 
  • 남은 시간을 주기적으로 계산하고 문맥교환을 한다
  • 종료 시간을 예측하기 어렵고 아사현상이 일어난다.

7. 우선순위 스케줄링

• 프로세스 중요도에 따른 우선순위
• IF 작업시간이 짧은 프로세스의 우선순위를 높게 설정

• 성능 : 이 경우 총 대기 시간 과 평균 대기 시간은 SJF 스케줄링과 같다.
• 모두 구현 가능 
  • (비선점형 방식) SJF 스케줄링: 작업 시간이 짧은 프로세스에 높은 우선순위를 부여한다.
  • (비선점형 방식)HRN 스케줄링: 작업 시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순 위를 부여한다.
  • (선점형 방식)SRT 스케줄링: 남은 시간이 짧은 프로세스에 높은 우선순위를 부여한다
• 평가: 우선순위는 시스템의 효율성보다 프로세스의 중요도에 따라 정해진다.
  • 준비 큐에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스 에 먼저 CPU를 할당하므로 공평성을 위배하고 아사 현상을 일으킨다는 문제
  • 우선순위를 매번 바꿔야 하기 때문에 오버헤드가 발생

8. 다단계 큐 스테줄 - 선점형

• 우선순위에 따라 준비 큐를 여러 개 사용
• 우선순위에 따라 다단계로 나뉘며, 각각의 큐는 라운드로빈으로 운영 (타임 슬라이스 조절)
• 고정형 우선순위
• 우선순위와 작업 형태를 고려하여 스케줄링 할 수 있다.
• 그러나, 상위 큐 프로세스의 작업이 끝나기 전에 하위 큐 프로세스의 작업을 할 수 없다

 

9. 다단계 피드백 큐 스케줄링

• 우선순위를 가진 여러 개의 큐
• 변동 우선순위 알고리즘
• CPU를 사용한 후 프로세스의 우선순위가 낮아진다.
  • CPU를 사용한 후의 프로세스는 원래의 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.
  • 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화한다.
•  우선순위에 따라 타임 슬라이스의 크기가 다르 다는 것이다
  • 우선순위가 낮아질수록 해당 큐의 타임 슬라이가 커진다  
  • 우선순위가 낮은 프로세스가 우선순위가 높은 프로세스보다 Chapter 04 CPU스케줄링 229 CPU를 얻을 확률이 여전히 낮은것을 극복 

 

 

 

5. 인터럽트 처리

1. 인터럽트의 개념

• 인터럽트는 입출력 뿐만 아니라 시스템 보호에 매루 중요한 역할을 한다.
• 이벤트 드리븐: 버튼이 눌리면 프로세스에 알려준다.
• 인터럽트: 입출력을 요청하고 입출력이 완료되면 이벤트를 발생기켜 알린다.
• 사용 중인 메모리 영역을 침범하면 CPU에 있는 메모리 관련 레지스터가 인터럽트를 발생시켜 해당 프로세스를 강제 종료한다.

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

• 동기적 인터럽트(사용자 인터럽트): 프로세스가 실행 중인 명령어로 인해 발생
  • 프로그램의 문제 발생 (다른 사용자의 메모리 접근, 오버플로나 언더 플로)
  • 의도적인 프로세스 중지 ( ctrl + c )
  • 입출력 장치 같은 주변장치의 조작에 의한 인터럽트
  • 살술 연산 중인 인터럽트 ( 0으로 나눔)
• 비동기적 인터럽트: 실행 중인 명령어와 무관하게 발생
  • 하드디스크 읽기 오류
  • 하드웨어 오류 (메모리 불량)
  • 사용자가 직적 작동 (키보드 / 마우스 인터럽트)

3. 인터럽트 처리 과정

• 인터럽트에는 해당 인터럽트가 발생하면 어떤 일을할지도 정의되어 있다.
• 인터럽트 번호(IRQ)와그 번호에 붙어 있는함수의 쌍으로 이루어져 있다: 인터럽트를 식별한다.

• 인터럽트는 한순간에 여러 개가 동시레 발행하기도 한다.
• 인터럽트 벡터: 동시에 발생하는 인터럽트를 하나로 묶어서 처리하는 개념, 인터럽트롸와인터럽트 핸들러가 일대일로 연결된 자료구조이다.

1. 인터럽트 발생 -> 실행중인 프로세스 일시 정지 + 현재 상태 정보를 임시 저장
2. 인터럽트 컨트롤러가 인터럽트의 처리 순서 결정 (우선순위)
3. 인처럽트 핸들러(미리 정의된 함수)가 실행된다.
4. 인터럽트 벡터에 연결된 핸들러가 인터럽트 처리를 마치면 일시 정지된 프로세스가 다시 실행 되거나 종료된다
5. 발생한 인터럽트가 입출력 완료라면 일시 정지된 프로세스가 다시 실행되고. 다른 프로세스의 메모리 영역 침범이나오류라면 종료된다.

4. 인터럽트와 이중 모드

• 프로세스
  • 커널 프로세스: 커널 모드
  • 사용자 프로세스: 사용자 모드
• 사용자 프로세스가 커널의 기능을 사용하려면 시스템 호출로 커널 프로세스에 작업을 요청한다. 
• 사용자 프로세스는 시스템 호출을 요청한 후 대기 상태로 전환되고 커널 프로세스는 요청받은 작업을 처리한다.
• 사용자 모드에서 커널 모드로 전환된다. 
• 이중 모드: 운영체제가 두 모드를 전환하며 일 처리하는 것, 운영체제가 자원을 보호하기 위해 사용하는 기법, 커널 모드에서만 접근하도록 
• API: 시스템 호출하는 방법, API와 다양한 함수를 이용하면 사스템 호출로 시스템 자원에 접근할 수 있다.

• 사용자가 커널에 진입하는 경우
  • 시스템 호출을 사용한 경우 - 자발적
  • 인터럽트를 발생시킨 경우 - 비자발적 : 잘못된 명령을 수행하여 동기적 인터럽트가 발생한 것으로 프로세스가 강제 종료된다.

 

 

 

 

---

출처 : 조성호 , 『IT CookBook, 쉽게 배우는 운영체제(2판)』한빛아카데미(2023).