5.1.1 CPU-I/O 버스트 주기(CPU-I/O Burst Cycle)

Slides:



Advertisements
Similar presentations
Lee Hoon Copyright(c) 2008 LeeHoon All rights reserved. 제7강제7강.
Advertisements

폭력. 폭력이란 무엇인가 우상의 눈물 물리적인 폭력 ( 최기표 ) VS 지능적인 폭력 ( 임형우, 담임선생님 )
1 박 2 일 !!! 인천마장초등학교 유수아. 1 박 2 일 멤버 인기순 위 1 위 이승기 2 위 엄태웅 3 위 은지원 4 위 김종민, 이수근 ※인터넷에서 본것이기 때문에 사람에따라 서 다를 수 있다. ※
석관중앙교회 5남전도회 석 관 중 앙 교 회 회원 소식 통권 05-04호 발행일 : 2005년 04월 회 장 : 장진호 집사
OS 소개 Introduction 설계목표 기본 용어 Resource Management History.
지역사회복지론 1조. 요양보호시설에 대해서 황성국 임재형 이동영
- 예∙결산 및 기본재산 운영 신뢰도 제고를 위한 실태점검, 결산지원사업 -
Chapter 1. 운영체제의 개요 이태호.
Mar OSEK/VDK Woo Dong Kyun.
소프트웨어와 운영체제.
제 4 장 프로세스 Section 1 프로세스의 개념 Section 2 프로세스 스케줄링
제 2장 컴퓨터 구조.
정보통신실습 및 특강(5)
I 문학의 개념과 역할 1. 문학의 개념 (1) 언어 예술로서의 문학 (2) 소통 활동으로서의 문학
4. 목적론적 윤리와 의무론적 윤리 01. 경험주의와 이성주의 01. 경험주의와 이성주의 02. 결과론적 윤리와 공리주의
Operating Systems Overview
운영체제 레프토 (4장 CPU 스케줄링) b반 박상수.
Uniprocessor Scheduling
제 2 장 프로세스 관리 2.1 개요 프로세스 스케줄링은 준비완료(ready) 상태에 있는 프로세스들 중 어느 것을 중앙처리장치에 할당시킬 것인가를 결정 중앙처리장치 처리율(throughput)의 최대화와 반환 시간(turnaround time)의 최소화 2.2 프로세스.
5.1.1 CPU-I/O 버스트 주기(CPU-I/O Burst Cycle)
제 5 장 프로세스 스케줄링.
운영체제 (Operating Systems)
프로세스 관리.
6장 단일 프로세서 스케줄링.
컴퓨터 과학 개론 √ 원리를 알면 IT가 맛있다 컴퓨터 과학도를 위한 첫 전공서 ehanbit.net.
1. 스케줄링 개요 [그림 6-16] 프로세스의 반환, 대기, 반응 시간
디스크 스케줄링 채상훈.
임베디드 운영체제 (리눅스 중심) Lecture #2.
운영체제 (Operating System) (하드웨어와 응용 프로그램 사이의 인터페이스 역할을 담당하는 시스템 소프트웨어)
04 CPU 스케줄링 CPU Scheduling
2.2 CPU 스케줄링의 목적과 유형 스케줄링의 목적
DSP와 TMS320F28X의 이해
운영체제와 Windows XP 초등 ICT 교육 방법론 2013년 1학기.
Ch. 8 교착상태 (Deadlocks) 29-Nov-18.
MicroC/OS-II 1. Miscellaneous
운영체제 (OS: Operating System)
CPU스케줄링(CPU Scheduling) ~
Chapter 5. CPU 스케줄링 (CPU Scheduling)
Chapter 10. Interrupt.
Multiprocessor and Real-time Scheduling
Multiprocessor and Real-time Scheduling
운영체제 (Operating System)
Chapter 5. CPU 스케줄링 (CPU Scheduling)
Lecture #3 프로세스(Process).
디스크 스케줄링 C 최 은 선.
제3,4,5장 프로세스, 스레드 관리 CPU 스케줄링.
Operating system #5 Disk Scheduling
Chapter 10. 파일 시스템 인터페이스(File System Interface)
6 단일 프로세서 스케줄링.
제5장 CPU스케줄링(CPU Scheduling)
제10,11,12장 파일시스템 디스크 스케줄링.
개항기 조선과 동아시아 박 범 한국역사입문Ⅱ.
운영체제(Operating System)
Part 5. MS-SQL Server Basic
운영체제 (Operating Systems) (Memory Management Strategies)
제 10장 운영체제.
디스크 스케줄링 C 박상수.
제7강 PC정비사 1급(필기) Lee Hoon Copyright(c) 2008 LeeHoon All rights reserved.
운영체제 발표자료 B반 최민웅.
제 2장 프로세스 관리와 CPU 스케줄링 2.1 프로세스의 개념 2.2 CPU 스케줄링의 목적과 유형
Chatpter 09 입출력 시스템과 디스크 관리 01 입출력 시스템 관리 02 디스크의 구조와 스케줄링 03 RAID 요약
제4장 CPU 스케줄링 이나현.
기술 진화와 진보.
운영체제 학번 : 이름 : 이원석 반 : 2B.
제4장 CPU 스케쥴링 운영체제 1-C반 박소라.
제5장 주일정계획.
Lecture #7 CPU Scheduling.
5.1 개요 고정 헤드 디스크 유동 헤드 디스크 드럼 플로피디스크
컴퓨터 개론 √ 원리를 알면 IT가 맛있다 쉽게 배우는 컴퓨터 기본 원리 한빛미디어 교재출판부.
CPU 스케줄링 장우영.
Presentation transcript:

5.1.1 CPU-I/O 버스트 주기(CPU-I/O Burst Cycle) 제 5 장 중앙처리장치 스케쥴링 5.1 기본 개념 (Basic Concepts) 다중 프로그래밍의 목적: CPU 활용의 극대화 한 순간에 실행 상태인 프로세스는 하나 나머지는 dispatch될 때까지 대기→ CPU 스케쥴링 5.1.1 CPU-I/O 버스트 주기(CPU-I/O Burst Cycle) 프로세스는 대개 CPU 버스트와 I/O버스트를 반복 (CPU burst에서 시작하여 CPU burst에서 종료) 그림 5.1 버스트 분포를 CPU 스케쥴링에 활용

5.1.2 CPU 스케쥴러 (CPU Scheduler) 준비 큐는 PCB들의 FIFO 큐, 우선순위 큐, 트리... 5.1.3 선점 스케쥴링 (Preemptive Scheduling) CPU 스케쥴링(프로세스 선택)은 언제 가능?  (1) “실행” -> “대기” (예: I/O를 요청, 자식의 종료 대기) (2) “실행” -> “준비” (예: 인터럽트 발생) (3) “대기” -> “준비” (예: I/O 종료) (4) 수행 종료

비선점(nonpreemptive) 스케쥴링 1,4 완료 후 1과 4에 한하여 스케쥴링 (예: MS Window 3.1) no timer, 하드웨어와 거의 무관 선점(preemptive) 스케쥴링 문제: 공유 데이터 변경 중 선점 “일관성” 문제 발생 : 6장 공유 데이터가 커널 데이터인 경우 문제가 심각 대안 임계 구역(critical section)에서는 선점 불가 시스템 호출이나 I/O가 완료될 때까지 선점을 유보

5.1.4 디스패처 (Dispatcher) 디스패처: 선택된 프로세스에 CPU제어를 넘기는 모듈 가능한 한 빨라야 한다 문맥 교환, 사용자 모드로 전환, 이전 위치로 이동 디스패치 지연: “중단” 이후 (다른 프로세스의) “수행 시작” 에 걸리는 시간

5.2 스케쥴링 기준 (Scheduling Criteria) (1) CPU 이용률 (2) 처리율(throughput): 시간 단위 당 완료된 프로세스 수 (3) 반환(turnaround) 시간: 완료 시간  진입 시간 (4) 대기(waiting) 시간 : 준비 큐에 있었던 시간 (5) 응답(response) 시간(대화식 시스템) : 요청 후 최초 응답까지의 시간 스케쥴링의 목적 CPU 활용과 처리율의 극대화 반환, 대기, 응답 시간의 극소화 1~5를 평균적으로 최적화하거나 분산이 작아지게 대화식의 경우에는 분산의 최소화가 더욱 중요 본 교재에서는 “대기 시간” 중심으로 비교

5.3 스케쥴링 알고리즘 (Scheduling Algorithms) 5.3.1 선입 선처리 (First-Come First-Served) 스케쥴링 FIFO 큐로 구현 평균 대기 시간이 상당히 길어질 수 있다(not optimal) p. 142 Gant 차트 작업의 진입 순서에 따라 평균 대기 시간에 큰 차이 비선점 방식임  : 일단 CPU를 할당받으면 수행 종료나 I/O 시에만 CPU 양도 시분할 시스템에서는 사용 곤란

5.3.2 최소 작업 우선 (Shortest-Job-First) 스케쥴링 각 프로세스의 “다음 CPU 버스트 시간” 이 기준 시간이 같으면 FCFS 알고리즘 적용 평균 대기 시간이 가장 짧다(optimal) 평균 대기 시간 계산 예 (143 페이지 참조) SJF 알고리즘의 문제점 “다음 CPU 버스트 시간”의 예측이 어려움 단기 스케쥴링에 활용하기 어려움 일괄 처리 시스템의 장기 스케쥴링에 주로 활용

(대기시간) 선점 : ((10-1) + (1-1) + (17-2) + (5-3)) / 4 = 6.5 프로세스 도착시간 버스트 시간 P1 0 8 P2 1 4 P3 2 9 P4 3 5 P1 P2 P4 P1 P3 0 1 5 10 17 26 (대기시간) 선점 : ((10-1) + (1-1) + (17-2) + (5-3)) / 4 = 6.5  비선점 : ((8-1) + (12-3) + (17-2)) / 4 = 7.75

n+1 = tn + (1–)tn-1 +... + (1–)jtn-j +... + (1–)n+10 단기 스케쥴링에 활용하기 위해 “예측”을 시도 지수 평균(exponential average) 그림 5.3  SJF는 선점(최소 잔여 시간 우선)/비선점 방식 모두 가능 n+1 = tn + (1–) n  n+1 = tn + (1–)tn-1 +... + (1–)jtn-j +... + (1–)n+10

n+1 = tn + (1–)(tn-1 + (1- ) n-1) CPU버스트(ti): 6 4 6 4 13 13 13 … “추정”(i) :10 8 6 6 5 9 11 12 … n+1 = tn + (1–)(tn-1 + (1- ) n-1)

5.3.3 우선순위(Priority) 스케쥴링 각 프로세스에 우선순위 부여(SJF도 한 종류) 우선 순위가 같으면 FCFS 적용 우선 순위 내부적(수량으로 측정 가능) 시간 제한, 메모리 요구량, 개방 파일의 수, 평균 I/O버스트 : 평균 CPU버스트... 외부적(정책적으로 주어지는 것들) 프로세스의 중요도, 예치액... 무한 대기(indefinite blocking) / 기아(starvation)  우선 순위가 낮은 프로세스가 무한히 대기하는 현상 해결 → aging 기법(일정 시간마다 우선 순위를 높임)

5.3.4 라운드 로빈(Round-Robin) 스케쥴링 시분할 시스템에 적합, FCFS에 “선점”을 가미 일정한 시간(time quantum/slice)마다 준비 큐(순환 큐)의 다른 프로세스에 CPU 할당 평균 대기 시간은 비교적 긴 편 RR의 성능은 시간 할당량의 크기와 밀접한 연관 크면, FCFS 작으면, "처리기 공유(processor sharing)” 문맥 교환 횟수 증가 (그림 5.4) “시간 할당량 >> 문맥 교환 시간”이 바람직 P1 P2 P3 P1 P1 P1 P1 P1 0 4 7 10 14 18 22 26 30

[그림 5.6] 반환시간은 시간할당량에 따라 다양함을 예시

할당량 ① 1 2 3 4 1 2 4 1 2 4 1 4 1 4 1 4 4 ② 1 2 3 4 1 2 4 1 4 4 ③ 1 2 3 4 1 4 4 …… 2의 입장 3의 입장

*전체적 평균 효율(FCFS) vs. 형평성(RR)  시간 할당량이 크다고 반드시 평균 반환 시간이 감소하지는 않음 그림 5.5 그러나 할당량이 너무 작으면 문맥 교환 시간 증가 -> 반환 시간 증가 평균 반환 시간을 줄이려면, 많은(약80%) 버스트(프로세스)가 할당량 내에 종료 *전체적 평균 효율(FCFS) vs. 형평성(RR) 

5.3.5 다단계 큐 (Multilevel Queue) 스케쥴링 프로세스의 특성에 따라 (그룹별) 우선 순위 부여 (예) 후면 작업 vs. 전면 작업 준비 큐를 여러 개 (우선 순위에 따라) : 그림 5.6 기억장치 요구량, 우선 순위, 유형에 따라 하나의 큐에 “영구 할당” 각기 다른 스케쥴링 알고리즘 적용 가능 (예) 전면 작업은 RR, 후면 작업은 FCFS 서로 다른 큐간에는 “고정 우선 순위-선점” 알고리즘 적용 (상위 큐가 모두 비어야 하위 큐가 실행)

5.3.6 다단계 피드백 큐 (Multilevel Feedback Queue) 스케쥴링 가장 일반적, 가장 복잡 (큐의 개수, 큐별 알고리즘, 상하 이동 시기...) 상황에 따라 준비 큐를 바꿈 CPU 사용 시간을 기준으로 하는 예 I/O-bound, 대화식 프로세스는 상위 큐로 이동 하위 큐에 오래 있으면 상위 큐로 이동: 기아 방지(aging) 알고리즘 처음 오면 최상위 큐를 할당 상위 큐가 비어야만 하위 큐의 프로세스 실행 실행 중 상위 큐에 새 프로세스가 오면 CPU 양도 선점 스케쥴링 최하위 큐는 FCFS

5.5 실시간 (Real-Time) 스케쥴링 5.4 다중 프로세서 (Multiple-Processor) 스케쥴링 동종(homogeneous) 시스템 하나의 준비 큐로 부하 공유(load sharing) 각 프로세서에 별도의 스케쥴링 알고리즘 적용 가능 비대칭(asymmetric) 다중처리: 한 프로세서만 OS 수행, 구조 간단 이기종(heterogeneous) 시스템 (분산 환경) 별도의 대기 큐 (기계어가 다르므로): 스케쥴링 복잡 5.5 실시간 (Real-Time) 스케쥴링 경성(hard) 실시간 시스템 시간 내에 마칠 수 있으면 요구 접수, 아니면 거절 보조 기억 장치/가상 기억 장치 사용 곤란

연성(soft) 실시간 시스템 디스패치 지연(그림 5.8)의 최소화 방안 실시간 작업은 최상의 우선 순위 (우선 순위 스케쥴링) 다른 작업의 피해(starvation) 멀티미디어, 고속 대화형 그래픽 등에 적합 디스패치 지연(그림 5.8)의 최소화 방안 선점 지점(preemption point) 시스템 호출 중간중간에 실시간 프로세스 대기 여부 점검 커널 전체를 선점 가능하게 커널 데이터 구조의 “보호”가 필요 “우선 순위 역전” 가능 => 우선 순위 상속

5.6 알고리즘의 평가 (Algorithm Evaluation) OS 구현 시 스케쥴링 알고리즘의 선택 기준 5.6.1 결정성 모형화 (Deterministic Modeling) 미리 정해진 작업 부하에 대해 각 알고리즘 비교 평가는 간단하지만 비현실적 5.6.2 큐잉 모형 (Queueing Model) 큐잉 네트워크 분석(수학적으로) 서버: CPU(+대기 큐), I/O 시스템(+장치 큐) 도착률, 서비스율 -> 이용율, 평균 큐 길이, 평균 대기 시간

5.6.3 모의 실험 (Simulations) 5.6.4 구현 (Implementation) 리틀(Little)의 공식: n =   W (n: 평균 큐 길이, : 평균 도착율, W: 평균 대기시간) 한계: 복잡한 분포 계산, 분포가 비현실적(근사치) 5.6.3 모의 실험 (Simulations) 컴퓨터 모델을 프로그래밍으로 흉내(난수 발생기...) 추적 테이프(trace tape):실제 시스템을 모니터하여 작성 문제점: 비용, 프로그래밍 작업의 복잡도 5.6.4 구현 (Implementation) 알고리즘을 구현하여 OS에 넣고 돌려봄 정확한 평가 가능, 가장 많은 비용