[운영체제론] Chapter 2.4 Scheduling(스케줄링)

본 게시글은 하단 책을 읽고 학습한 내용을 제 생각으로 요약, 정리한 글입니다.

운영체제론 3/E(3판)(CD1장포함)

https://books.google.co.kr/books/about/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C%EB%A1%A0_3_E_3%ED%8C%90_CD1%EC%9E%A5%ED%8F%AC%ED%95%A8.html?id=Y5quQQAACAAJ&redir_esc=y

1. 스케줄링(Scheduling)

1) 스케줄링 알고리즘

• 정의) CPU가 multiprogramming으로 동작할 때 여러 프로세스나 스레드가 ready 상태인 경우 실행할 프로세스를 선택하는 스케줄러(운영체제의 일부분)의 알고리즘

• 흐름
• 과거 배치(batch) 시스템과 timesharing 시스템 시절
• CPU 희귀해서 현명한 스케줄링 알고리즘 개발에 많은 힘 쏟음
• 개인용 컴퓨터(Personal Computers)의 등장
• 하나의 활성화된 프로세스만 존재하고 CPU 빨라져 스케줄링을 심각하게 생각할 필요 없어짐
• 고성능 workstation이나 서버 컴퓨터
• 다수의 프로세스가 CPU 놓고 경쟁해서 스케줄링이 다시 문제가 됨.

2) Process Switching (== Context Switching)

• 정의) 실행 중인 프로세스를 바꾸는 것
• Running 상태의 프로세스를 끌어내리고 Ready 상태의 프로세스를 Running으로 끌어올리는 거.

• 특징) expensive함(시간 많이 걸림) → 스케줄링 잘해야함

• 과정
• 사용자 모드에서 커널 모드로 전환
• 프로세스 테이블에 현재 프로세스의 상태를 store함
• 스케줄링 알고리즘 실행해 새 프로세스 선택
• 새 프로세스의 저장 상태를 load해옴
• 새 프로세스 수행

2. 프로세스의 행동 양태

1) 프로세스 행동

• 정의) 프로세스는 두 가지 행동을 반복함
• 계산 행위: 프로세스가 계산 수행
I/O 행위: 프로세스가 I/O 기다림
• 프로세스가 파일 읽거나 쓰기 위해 시스템 호출하고(I/O 요청),
• 프로세스가 외부 장치가 작업(I/O)을 마칠 때까지 대기 상태로 있는 것.
• 외부 장치가 아닌 CPU가 작업하는 건 I/O가 아닌 계산 행위로 간주함.
• ex) CPU가 비디오 램에 비트 복사해 화면 갱신 → CPU를 사용해서 계산행위임

• 버스트: 일정 시간 동안 계산이나 I/O를 수행하는 행위
• CPU 버스트: 계산 수행
• I/O 버스트: I/O 수행(CPU 사용하지 않고 I/O 요청하고 block상태로 가 기다리고 있는 것)

• 프로세스 행동(CPU 버스트 길이)에 따라 프로세스가 a, b타입으로 나뉨

2) a타입: CPU-바운드 프로세스(Compute-bound Process)

• 정의) 긴 CPU 버스트 가져서 대부분의 시간을 계산에 소비하는 프로세스

• 특징) I/O 버스트가 드물게 나타남

3) b타입: I/O-바운드 프로세스

• 정의) 짧은 CPU 버스트 가져서 대부분의 시간을 I/O 기다리며 소비하는 프로세스

• 특징) I/O 버스트가 빈번히 나타남
• CPU 빨라질 수록 짧은 CPU 버스트 가지게 되어 I/O 바운드가 됨 (CPU>디스크)
• I/O 바운드 프로세스는 가능한 빨리 실행시켜 디스크 요청 발생시켜 디스크 바쁘게 일하게 하는게 좋음

• 주의)
• I/O 버스트가 길어서 I/O 바운드인게 아님 (I/O 버스트는 a, b 거의 동일함)
• I/O 요청 사이에 적은 계산(CPU 버스트 짧음)을 해서 I/O 바운드임

3. 스케줄링이 언제 발생하는가

• 스케줄링 결정을 내려야 하는 시점

1) 프로세스 생성할 때 → 새로운 놈(생성되어 ready로 들어옴)과 기존 놈 중 선택

• 부모 프로세스가 fork해서 자식 프로세스가 생성됨(fork 시스템콜 하면 클론 생김)
• 스케줄링은 부모 프로세스를 계속 실행할 것인지, 자식 프로세스를 실행할 것인지 결정해야 함(둘다 Ready상태임)

2) 프로세스 종료할 때 → 대체할 놈 선택

• 프로세스가 더 이상 존재하지 않아 수행할 수 없어, Ready 상태의 다른 프로세스가 선택되어 Running 상태로 가야 함.

3) 프로세스 Block될 때 → 대체할 놈 선택

• 프로세스가 I/O, 세마포어 등과 같은 무언가 때문에 Block 상태로 가면, Ready 상태의 다른 프로세스가 선택되어 Running 상태로 가야 함.

4) I/O 인터럽트가 발생했을 때 → 새로운 놈(block에서 나와 ready로 들어옴)과 기존 놈 중 선택

• I/O 완료되면 I/O 인터럽트가 발생함
• I/O 기다리며 블록되어 있던 프로세스가 이제 실행될 준비가 되어 Ready 상태로 옴
• 새로 Ready로 온 프로세스 실행할지, 인터럽트 발생 당시 실행하던 프로세스 선택할 지 결정해야함
• 일반적으론 인터럽트 때문에 억울하게 중지된 기존 놈 선택

4. 스케줄링 알고리즘의 카테고리

1) Clock Interrupt 처리 방법에 따라 나눈 스케줄링 알고리즘

• Clock Interrupt
• 하드웨어 클록이 주기적인 clock interrupt 발생시킴.
• 매 clock interrupt 혹은 k번째 clock interrupt마다 스케줄링 결정 이루어짐.

1. nonpreemptive(비선점) 스케줄링 알고리즘: Clock Interrupt 처리x
• 정의) 수행 프로세스는 (I/O 요청하거나 다른 프로세스 기다리기 위해) block되거나 자발적으로 CPU 내놓을 때까지 계속 수행함.
• 수 시간동안 계속 수행해도 강제 중단 안됨
• Clock interrupt 발생하지 않아도 문제 없음.

2. preemptive(선점형) 스케줄링 알고리즘: Clock Interrupt 처리o
• 정의) 수행 프로세스는 할당된 시간을 넘지 않는 범위에서 수행함.
• 할당된 시간 다 되면 중단됨(Ready로 끌어내려짐). 스케줄러가 다른 프로세스를 Running으로 올림.
• 할당된 시간 다 됐을 때 스케줄러가 CPU 제어 회복해서 위의 동작 하려면 Clock interrupt가 꼭 발생해야 함.

2) 스케줄링 알고리즘을 필요로 하는 환경

1. 배치(Batch) 시스템
• 정의) nonpreemptive나 긴 시간 주기의 preemptive 알고리즘 사용해 각 프로세스가 오랫동안 CPU 사용할 수 있게 해줌.
• 특징)
• process switch 줄여서 성능 향상 (CPU가 대부분 시간을 프로세스 수행하는 데 사용해서)
• 공평함
• 은행, 보험회사 등 정기적인 작업 수행 (빠른 응답 필요 x)

2. 대화식(Interactive) 시스템
• 정의) preemptive 알고리즘 필수로 사용해 한 프로세스가 CPU 독점하는 것 방지함.
• 특징)
• 프로그램 버그로 다른 프로세스가 영원히 수행 불가능하게 되는 상황 막음
• 다수 사용자와 interaction할 때 각 사용자의 프로세스를 빠르게 switching해줘야 사용자 입장에서 차례가 빨리빨리 와서 interaction 잘된다고 느낌
• 서버 (다수 사용자가 빠른 응답 원함)

3. 실시간(Real time) 시스템 [참고]
• 정의) 프로세스는 자기가 오래 수행되지 않을 거란걸 알고서 보통 알아서 일 끝나면 블락함. preemptive 없어도 됨

5. 스케줄링 알고리즘의 목표

1) 모든 시스템에서 공통 목표

• 공평함
• 각 프로세스에게 CPU를 공평하게 할당함

• 정책 집행(Policy enforcement)
• 정책(ex. 공평함)이 잘 지켜지고 있는지 확인함

• 균형(Balance)
• 시스템의 모든 부분이 바쁘게 유지함

2) 배치(Batch) 시스템에서 목표

• 성능(Throughput)
• 시간 당 처리되는 job의 수를 최대화
• ex) 한 시간에 완료된 job의 수

• 반환시간(Turnaround time)
• job이 시스템에 제출된 때부터 종료까지 걸리는 시간을 최소화

• CPU 이용률(CPU utilization) [참고]
• CPU가 항상 활용되도록 함

3) 대화식(Interactive) 시스템에서 목표: 사용자와 계속 interaction함

• 응답시간(Response Time)
• 요청(Request)에 응답(Response)하는데 걸린 시간 최소화
• 요청(Request)을 빨리하는게 중요

• 비례(Proportionality) [참고로만]
• 사용자의 기대를 만족시킴

4) 실시간(Real time) 시스템에서 목표

• 마감시간 만족(Meeting Deadline)
• 데드라인 만족시켜서 데이터 손실을 방지함
• ex) 미사일 조절에서 데드라인 놓치면 미사일이 엉뚱한데로 날아감

• 예측 가능(Predictability)
• 멀티미디어 시스템(오디오 디코딩, 비디오 디코딩)에서 품질 저하를 방지함
• 사용자의 품질에 대한 예측 만족시켜야 함.

6. 배치(Batch) 시스템의 스케줄링 알고리즘

• 배치 시스템과 대화식 시스템의 차이점
• 배치: 사용자와 상호작용 x
• interactive: 사용자와 상호작용 o

1) 선입선출 (First-Come First-Served) → [nonpreemptive]

• 정의) (Ready큐에서) 먼저 온 프로세스가 먼저 처리(서브)함

• 특징)
• nonpreemptive(비선점): 한 번 수행하면 block되거나 자발적으로 내놓을 때까지 수행됨
• 프로세스들은 요청한 순서대로 CPU 할당받음 → 공평함
• 이를 위해서 Ready 상태의 프로세스들을 한 줄로 세워둠
• Ready 큐의 맨 앞에 애를 Running으로 올림
• 새로 Ready상태가 된 애는 Ready 큐의 맨 끝에 들어감

• 장점) 이해하기 쉽고 프로그램이 쉬움

2) 최단작업우선(Shortest Job First) → [nonpreemptive]

• 정의) (Ready큐에서) 작은 job(실행시간 짧은 job)부터 먼저 수행함

• 특징)
• nonpreemptive
• 실행 시간이 미리 알려졌을 경우 적용 가능
• 최적화(최소화)된 평균 turnaround time(반환시간) 제공함
• 여러 job의 turnaround time(job의 제출~종료 걸리는 시간)들의 평균
• job의 반환시간(turnaroud time) ≠ job의 실행시간
ex) a, b, c, d 네 개의 job. 각각 실행시간은 8, 4, 4, 4분. 도착시간은 0, 0, 0, 0, 0분

• (a) 순서대로 실행
• a,b,c,d 반환시간은 각각 8, 12, 16, 20분
• 평균 반환시간은 (8+12+16+20)/4 = 14분
• (b) 최단작업우선 순으로 실행
• a,b,c,d 반환시간은 각각 4, 8, 12, 20분
• 평균 반환시간은 (4+8+12+20)/4 = 11분
• 최적의 평균 반환시간임
• 단, 모든 job의 도착시간이 같을 때(모든 job이 동시에 존재할 때)만 최단작업우선이 최적임
• 그렇지 않으면 최단작업우선 써도 최소값 보장 안됨
• ex) a, b, c, d, e 각각 실행시간은 2, 4, 1, 1, 1분. 도착시간은 0, 0, 3, 3, 3분
• (a) 최단작업우선 순으로 실행 (a,b,c,d,e)
과정
• 0분 → a, b가 도착함
• a 2분 실행 → 2분에 끝남 (0~2)
• b 4분 실행 → 6분에 끝남 (0~6)
• 3분 → c,d,e가 도착함. 허나 b가 아직 수행 중이라 기다려야함
• 6분 → b 수행 끝남
• c 1분 실행 → 7분에 끝남 (3~7)
• d 1분 실행 → 8분에 끝남 (3~8)
• e 1분 실행 → 9분에 끝남 (3~9)
• a,b,c,d,e 반환 시간(도착~종료까지 걸린 시간)은 각각 2, 6, 4, 5, 6분
• 평균 반환시간은 (2+6+4+5+6)/5 = 23/5 = 4.6
• (b) 반례 (b,c,d,e,a)
과정
• 0분 → a, b가 도착함
• b 4분 실행 → 4분에 끝남 (0~4)
• 3분 → c, d, e가 도착함. 허나 b가 아직 수행 중이라 기다려야함
• 4분 → b 수행 끝남
• c 1분 실행 → 5분에 끝남 (3~5)
• d 1분 실행 → 6분에 끝남 (3~6)
• e 1분 실행 → 7분에 끝남 (3~7)
• a 2분 실행 → 9분에 끝남 (0~9)
• a,b,c,d,e 반환 시간은 각각 4, 2, 3, 4, 9분
• 평균 반환시간은 (4+2+3+4+9)/5 = 22/5 = 4.4

3) 최단잔여시간우선(Shortest Remaining Time Next) [preemptive]

• 정의) 프로세스의 남은 실행시간이 가장 짧은 프로세스를 택함

• 특징)
• 최단작업우선의 preemptive 버전
• 실행시간 미리 알고 있어야함
• Ready큐에서 실행시간 짧은 job부터 수행함
• 단, 중간에 새로운 job이 들어오면 새로운 job의 실행시간과 현재 Running 상태 job의 남은 실행시간을 비교함. 새로 들어온 job의 실행시간이 더 짧으면 기존 job 끌어내리고 새로운 job을 Runnign에 올림.
• Running 상태의 job은 항상 그 누구보다 실행시간 짧음. 누가 새로 들어와도 남은 실행시간이 걔보다 짧음.

7. 대화식(Interactive) 시스템의 스케줄링 알고리즘

1) 라운드 로빈 스케줄링(Round-Robin Scheduling)

• 정의) 각 프로세스에게 똑같은 시간할당량(Quantum) 줘서 프로세스들이 돌아가면서 수행되게 함

• 특징)
• preemptive
• process switch가 언제 일어나는가
• 프로세스의 할당 시간이 끝나면 Ready 큐의 끝으로 보냄
• 할당 시간 끝나기 전에 프로세스가 block되거나 종료됨
• 시간할당량(Quantum)의 길이에 따른 파급효과
• Quantum 길이 너무 짧으면
• process switch가 빈번히 발생해 CPU 효율이 떨어짐
• ex) 할당시간 4msec동안 작업 수행하고, process switch가 1msec 걸린다면
• 20% CPU 시간이 관리에 소모되어 낭비됨
• Quantum 길이 너무 길면
• interective request에 대해 Response time(응답 시간)이 느려짐
• ex) 할당시간 100msec동안 작업 수행하고, process switch가 1msec 걸린다면
• 낭비되는 시간은 1%뿐이지만
• 50개 프로세스가 Ready 큐에 놓이고 모든 프로세스가 자신의 할당시간을 전부 수행한다면, 마지막 프로세스는 100*50msec = 5sec를 기다려야함. 응답이 너무 느림. (여러 프로세스가 빠른 응답 요구하는 서버 시스템의 경우 나쁨)

2) 우선순위 스케줄링(Priority Scheduling)

• 정의) 각 프로세스에게 우선순위를 부여해 가장 높은 우선순위 가진 프로세스부터 수행함

• 특징)
• preemptive (Interactive OS에서 쓰는 경우 독식 막기 위해)
높은 우선순위의 프로세스가 무한히 수행되는 것을 막는 법
• 방법 1) 클록 인터럽트마다 현재 실행 중인 프로세스의 우선순위 낮춤. 언젠가 Ready상태의 가장 높은 우선순위 가진 프로세스한테 밀려 switch 일어남.
• 방법 2) 각 프로세스는 최대 할당 가능한 시간을 가짐. 할당 시간 다 소비하면 다음으로 우선순위 높은 프로세스로 switch 일어남.
• 우선순위 부여하는 법
• 정적: 프로세스 수행 전 사용자의 지위, 가치에 따라 우선순위 부여
• 프로세스 사용자의 위치가 무엇이느냐에 따라 우선순위 달리 줌
• 돈 많이 주는 사용자의 프로세스에게 높은 우선순위 줌
• UNIX의 nice 커맨드 실행한 사용자의 프로세스의 우선순위 낮춤
• 동적: 프로세스 수행 도중 I/O-bound 프로세스에게 높은 우선순위 부여
I/O-bound 프로세스는 CPU 필요로 하면 CPU 즉시 할당함 [참고로만 알기]
• I/O 요청을 빨리 발생시켜서 계산 수행과 I/O가 병렬로 실행될 수 있게 하기 위함
• CPU 버스트가 짧아서 CPU 조금밖에 안쓰니 우선순위 높게 주는 게 더 좋다는 철학
• 빨리 쓰고 빨리 나가는 애를 굳이 시스템에 오래남아있게 할 필요가 없음
I/O bound 프로세스에게 좋은 서비스(높은 우선순위) 제공하는 알고리즘 [참고만 하기]
• 우선순위를 1/f로 줌
• f: 프로세스가 사용하고 남은 할당 시간 비율
• 상대적으로 I/O bound process일 가능성 높은 프로세스에게 CPU-bound process일 가능성 높은 프로세스보다 높은 우선순위 할당함
• ex) 할당 시간이 50msec이고, x msec 소비한 채 I/O 요청한 경우
• 1msec 소비 (CPU 버스트가 짧음)
• 상대적으로 I/O 바운드 프로세스
• 남은 할당 시간 비율: 1/50 → 우선순위 50 할당받음
• 25msec 소비 (CPU 버스트가 김)
• 상대적으로 CPU 바운드 프로세스
• 남은 할당 시간 비율: 25/50 → 우선순위 2 할당받음
• 50msec 소비 (CPU 버스트 매우 김)
• CPU 바운드 프로세스
• 남은 할당 시간 비율: 50/50 → 우선순위 1 할당받음

• ex) 4개의 우선순위 클래스



• 우선순위 클래스: 프로세스들을 그룹으로 묶어, 그룹마다 우선순위 부여한 것 (클래스 간에 우선순위 스케줄링)
• 각 클래스 내에선 라운드 로빈(Round-Robin) 스케줄링(Ready 상태 프로세스들을 시간 할당해서 돌아가면서 수행) 써줌
• 우선순위 4인 클래스에 프로세스 전부 수행해 비게 되면, 우선순위 3인 클래스의 프로세스를 라운드 로빈 형태로 수행
• 낮은 우선순위 클래스는 기아 발생해 수행 못할 수도 있음

3) 우선순위 스케줄링 사용한 시스템 예시: CTSS

• CTSS 정의) 우선순위 클래스 쓰는 방식을 응용한 다단계 큐(Multiple Queue) 방식 사용한 시스템

• CTSS의 문제점과 해결책
• 문제1) process switch 매우 느림
• 해결1) CPU-bound 프로세스에게 큰 할당시간(Quantum) 줌 → process switch 줄임
• But 문제2) 모든 프로세스에게 큰 할당시간 부여하면 응답 시간이 길어짐
• 해결2) 우선순위 클래스 설정

• 구체적인 해결 방법 (우선순위 클래스)
• 가장 높은 우선순위 클래스: 1 Quantum씩 실행
• 두 번째로 높은 우선순위 클래스: 2 Quantum씩 실행
• 세 번째로 높은 우선순위 클래스: 4 Quantum씩 실행
• 프로세스는 본인한테 할당된 Quantum 다 썼는데도 CPU 사용하고 있으면 클래스가 한 단계 강등됨.

• 특징)
• I/O 안하고 response time(응답 시간) 구애 안 받는 CPU-bound 프로세스
• CPU 버스트 길어서 퀀텀 다 될 때까지 계속 Running이라 점점 단계 내려감
• 우선순위 낮은 단계로 내려감
• 장점) 적은 switch로 큰 quantum 받음
• 짧은 Interactive한 I/O-bound 프로세스
• CPU 버스트 짧아서 퀀텀 다 되기도 전에 I/O 요청해서 Block 상태로 감
• 언젠가 I/O가 완료되어 Ready로 갈 때 강등되지 않고 원래 단계로 가서 큐 끝에 줄 섬.
• 우선순위 높은 단계에 남아있게 됨
• 장점) 응답시간 줄임
• 오리지널 우선순위 클래스와 차이점
• 우선순위 클래스: quantum 다 된 프로세스는 다시 같은 단계의 큐에 줄 섬
• 다단계 큐: quantum 다 된 프로세스는 아래 단계의 큐에 줄 섬
• 요구하는 quantum이 짧거나 짧은 quantum만에 IO요청해서 블락된 프로세스는 계속 높은 단계에 있을 수 있음
• 요구하는 quantum이 길고 IO요청 잘 안하는 프로세스는 낮은 단계로 내려감

• 예시) 총 100 Quantum 필요로 하는 cpu-bound 프로세스
• 100 Quantum 거의 다 혹은 다 쓸 때 동안 IO 요청 안함
• 1 quantum 쓰고 아래 클래스로 강등되어 2 quantum 쓰고, 4 quantum 쓰고 함
• 총 100 quantum을 써야하기에 7단계까지 내려가면 끝남
• 1, 2, 4, 8, 16, 32, 64(의 37) → 1+2+4+8+16+32+37 = 100
• 순수한 라운드 로빈으로 1 quantum마다 process switch했으면 100번인데, 위 방법은 process switch 7번만 하면 됨.
• initial loading 횟수까지 포함해서 7번임!
• 결과적으론 CPU-bound 프로세스를 높은 우선순위 클래스에 넣어주면, 적은 switch만으로 큰 quantum을 줄 수 있음 (문제 1 해결: CPU-bound에게 큰 할당 시간 줌)
• 긴 CPU-bound 프로세스는 아래 단계로 내려가 우선순위가 낮아져 점점 덜 수행됨.
• 짧고 interactive한 프로세스들만 높은 단계에 남아있게 되어 자주 수행됨. (문제 2 해결: 우선순위 클래스 이용해 긴 프로세스는 우선순위 낮추고, 짧은 프로세스는 우선순위 높게 유지해 응답시간 줄임)

• 예시 2) 총 100 Quantum 필요로 하는 프로세스
• 100 quantum 쓰는 동안 10 quantum마다 io 요청함 (CPU burst: 10 quantum)
• 1,2,3단계에서 각각 1, 2, 4 퀀텀 쓰고서, 4단계에 왔을 때 3퀀텀(총 10퀀텀 씀)만 쓰고 I/O 요청하고 Block됨
• 4단계가 쓸 수 있는 8퀀텀을 다 안 썼기에 I/O 끝나서 Ready로 돌아올 때 4단계로 다시 돌아올 수 있음.
• Q) 다시 Running될 때 4단계의 8퀀텀을 사용가능한가, 아님 아까 쓰고 남은 5퀀텀만 사용가능한가??? A) 8퀀텀 사용 가능함.

• 예시 3) 총 10 퀀텀 필요로 하는 프로세스
• 10 퀀텀 쓰는 동안 2퀀텀마다 io 요청함
• 1단계에서 1퀀텀 쓰고, 2단계 Ready 큐로 강등됨
• Running될 때 2단계에서 1퀀텀만 쓰고 I/O 요청해서 Block 됨
• 2단계가 쓸 수 잇는 2퀀텀을 다 안썼기에 I/O 끝나고 Ready로 돌아올 때 2단계 Ready 큐로 다시 돌아옴
• 1) Running될 때 2단계에서 2퀀텀 쓰고 I/O 요청해서 Block 되면
• I/O 끝나고 Ready로 돌아올 때 2단계 Ready 큐로 다시 돌아옴 ?? 확실 x
• 2) 만약 Running될 때 2단계에서 2퀀텀 쓰고 I/O 요청 안하면(퀀텀 더 쓰고 싶어하면)
• 3단계 Ready 큐로 강등됨

4) 최단프로세스순번(Shortest Process Next)

• 정의) 과거 행동양태를 기반해 계산한, 예상 실행시간이 가장 짧은 프로세스를 먼저 실행함

• 특징)
• 배치 시스템의 최단작업우선(Shortest Job First)의 interactive system 버전
• interactive 프로세스의 각 명령 실행을 하나의 Job으로 간주해 최단 작업 먼저 실행시키면 전체 응답 시간 최소화할 수 있음. 단, 실행시간을 알아야 함
• 대화식 프로세스: 명령 실행, 명령 기다림 반복
• 평균 응답시간을 최소화함

• 실행시간 아는 법: 과거 행동을 기반으로 예상 실행 시간을 추정함. Aging 기법 사용
• ex) 시스템에 로그인한 터미널 여러 개 있음
• 각 터미널에서 사용자가 command 치고 실행하고, command 치고 실행함
• 터미널 입장에선 명령 수행이 반복적으로 일어남
• 시스템 입장에선 여러 터미널 각각에 수행 앞두고 있는 프로세스가 있는 거임
• 이들의 실행시간을 추정해야함. 가장 짧을 것으로 예측되는 프로세스를 수행
• 각 터미널의 command의 실행시간을 어떻게 예측할까
• 터미널에서 전해 수행되었던 command 실행시간을 바탕으로 해서 추정함
• Aging기법 사용

• Aging 기법
• 정의) 이전 예상치와 현재 측정된 값을 가중 평균해 연속적으로 다음 값을 예상하는 기법
• 공식) a * T0 + (1 - a) * T1 → a * 추정 + (1-a) * 실제
• T0 : 예상했던 실행시간
• 실행할 command의 실행추정시간
• T1: 실제로 측정된 실행시간
• 실제로 실행해본 command의 실행시간
• ex) 최초 추정시간t0, 실제 실행시간 t1인 프로세스의 다음 추정 시간 구하는 법
• a = 1/2
• a = 1/2 → 전 추정치와 실제 실행시간이 반반씩 영향 미침
• a < 1/2 → 실행시간이 더 많은 영향 미침
• a > 1/2 → 전 추정치가 더 많은 영향 미침
• 다음 추정 시간 t0 / 2 + t1 / 2
• 추정 시간 나열

a=1/2	추정시간	실행시간
ㅤ	t0	t1
ㅤ	t0/2 + t1/2	t2
ㅤ	t0/4 + t1/4 + t2/2	t3
ㅤ	t0/8 + t1/8 + t2/4 + t3/2	t4
ㅤ	t0/16 + t1/16 + t2/8 + t3/4 + t4/2	t5

• 실제 계산

a=1/2	추정시간	실행시간
ㅤ	20	30
ㅤ	20/2 + 30/2 = 25	35
ㅤ	25/2 + 35/2 = 30	40
ㅤ	30/2 + 40/2 = 35	ㅤ

추정 시간, 실행 시간 더하고 2로 나눈 것과 같음

5) 보장 스케줄링(Guaranted Scheduling)

• 정의) 각 프로세스가 생성된 이후 CPU 얼마나 사용했는지 추적해 CPU 사용 가장 못한 프로세스를 꼴지 벗어날 때까지 수행함

• 특징)
• N개의 프로세스가 돌고 있다면 각 프로세스는 CPU의 1/N씩 공평하게 할당받도록 보장함
• CPU 사용량 추적하는 법



• actual CPU time consumed: 지금까지 CPU 쓴 시간 합한 것
• CPU time entitled: 한 프로세스 당 할당되는 CPU 시간 (모든 프로세스에게 동일)
• ratio가 0.5라면 본인에게 주어진 시간의 반만 사용한 것임

6) 복권 스케줄링(Lottery Scheduling)

• 정의) 복권 랜덤하게 발행해서 티켓 갖고 있는 프로세스 선택함

• 특징)
• f 비율의 티켓 가지면 f비율만큼의 자원 가짐
• 즉각적으로 반응
• 티켓 교환 가능

7) 공평-몫 스케줄링(Fair-Share Scheduling)

• 정의) 소유자 고려

8. 실시간(Real time) 시스템에서 스케줄링

• 정의) deadline까지 외부 이벤트에 대해 적절히 반응해야 하는 시스템

• 특징)
• 너무 늦게 도착하는 응답은 응답 하지 않은 것과 마찬가지로 매우 나쁨
• ex) 음악, 비행기 자동항법, 자동화 공장의 로봇 제어, 중환자실 환자 감시
• 프로그램을 여러 프로세스로 쪼개어 실시간 성질을 성취함
• 프로세스들은 행동이 예측 가능하고 미리 알려져 있음
• 프로세스들은 짧은 시간동안 활동하고 초 단위 이내에 수행 마침

• 실시간 시스템의 분류
• 경성 실시간(Hard Real Time)
• 데드라인 절대 놓치면 안됨
• 비행기 자동항법, 자동화 공장의 로봇 제어
• 연성 실시간(Soft Real Time)
• 데드라인 놓치는거 바람직하진 않지만 허용은 됨
• 음악

• 실시간 시스템이 응답해야 하는 이벤트
• 주기적인 것(Periodic): 규칙적인 간격으로 발생함
• 비주기적인 것(Aperiodic): 예측불가하게 발생함

• 스케줄가능(Schedulable)한 실시간 시스템의 기준
• 상황: 주기적인 이벤트
• m개의 이벤트가 존재
• 각 이벤트 i는 Pi의 주기마다 발생하고, 처리에 Ci초의 CPU time이 필요함
• 주어진 상황은 아래 같을 때만 (모든 이벤트) 처리 가능함.



• 각 프로세스에 의해 사용되는 cpu의 fraction의 합이 1이하일 때. 시간/주기의 합
• 이 기준 충족하는 실시간 시스템은 Schedulable 하다고 함.
• ex) 주기적인 이벤트 3개
• m=3
• 각 이벤트 처리에 필요한 시간 Ci : 50, 30, 100 msec
• 각 이벤트의 주기 Pi : 100, 200, 500 msec
• 50/100 + 30/200 + 100/500 = 0.5 + 0.15 + 0.2 = 0.85 ≤ 1 이므로 Schedulable함
• 그림



• 서연이(검정)는 100초마다 발생하는데 처리해주는데 50초씩 걸려
• 기우(빨강)는 200초마다 발생하는데 30초씩 걸려
• 채연이(파랑)는 500초마다 발생하는데 100초씩 걸려
• 채연이를 기준으로 500초 동안 서연이는 250초 썼을 거고, 기우는 75초 썼을 거야. 채연이는 100초 써서 총 425 쓰게 돼. (85%씀)
• 문제
• 주기가 1000 msec인 네 번째 이벤트 넣고 싶음. 여전히 Schedulable하려면 어떤 조건을 만족해야하는가?
• 0.85 + x/1000 ≤ 1
• x ≤ 150
• 네 번째 이벤트가 150 msec 내에 처리 가능하면 됨

9. 정책(policy) vs 메커니즘

• 정의) 스케줄링 정책과 스케줄링 메커니즘를 분리함

• 특징)
• 무엇이 허용되느냐와 그것이 어떻게 행해지느냐를 분리
• 정책은 user process가, 메커니즘은 kernel이 함
• 이전까진 kernel이 다했음
• 스케줄링 알고리즘이 인자를 가지도록 만들어져 사용자 프로세스가 인자를 선택해 제공함

• ex) DBMS. 자식 프로세스를 많이 만듬
• 자식 프로세스의 중요도에 대해 부모 프로세스가 완벽히 알고 있음.
• 이를 인자로 전달해 반영할 수 있음
• 앞서 배운 스케줄러들은 사용자 프로세스의 입력 받아들이지 않았음

10. 스레드 스케줄링(Thread Scheduling)

1) 유저레벨 스레드 스케줄링

• 상황
• 프로세스 A의 스레드 A1, A2, A3.
• 각 스레드의 CPU burst가 5msec
• 프로세스의 퀀텀은 50msec

• 유저 레벨 스레드 스케줄링



• 스레드가 5msec씩 수행하고 CPU thread illd 콜함
• 스레드들끼리 서로 양보하면서 수행
• 스레드가 io 요청하면 커널은 프로세스마 봐서 프로세스 전체가 중지됨
• 유저 레벨에서 스케줄링 일어나서 성능 좋음

2) 커널레벨 스레드 스케줄링

• 커널 레벨 스레드 스케줄링



• 커널 자체가 스레드 하나 하나의 존재를 알고 스케줄함
• 스레드가 io 요청해도 해당 프로세스의 다른 스레드 수행 가능함
• 커널이 스레드를 스케줄링 하는 거라 전체 프로세스를 중지시키지 않음
• 유저 레벨과의 차이점