스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제

Slides:



Advertisements
Similar presentations
자료구조: CHAP 7 트리(1) 순천향대학교 컴퓨터공학과 하 상 호.
Advertisements

1. 자료구조 개념 (1) 자료구조의 개요 1) 자료구조 ① 일련의 자료들을 조직하고 구조화하는 것 ② 자료의 표현과 그것과 관련된 연산 2) 자료구조에 따라 저장공간의 효율성과 프로그램의 실행시간이 달라짐 3) 어떠한 자료구조에서도 필요한 모든 연산들을 처리하는 것이.
어서와 Java는 처음이지! 제2장 자바 프로그래밍 기초.
Chapter 7 ARP and RARP.
6.9 Redundant Structures and the Unit Load Method
Internet Computing KUT Youn-Hee Han
8. 파일 인덱스: 탐색트리 (Search Tree)
두벌식 자판과 완성형 코드가 잘못된 까닭과 속내
3 장 stack and queue.
Chapter 7. Binary Search Trees - 보충 자료-
Internet Computing KUT Youn-Hee Han
제 6장 프로세스 간 동기화 및 통신 6.1 개요 6.2 병행 처리의 문제점
정 의 학습의 일반적 정의 기계학습(Machine Learning)의 정의
기본 컴퓨터 프로그래밍 Lecture #6.
시스템 생명 주기(System Life Cycle)(1/2)
6장 트리.
Internet Computing KUT Youn-Hee Han
Internet Computing KUT Youn-Hee Han
쉽게 배우는 알고리즘 3장. 정렬Sorting
시스템 생명 주기(System Life Cycle)(1/2)
CHAP 7:트리.
강의 #7 트리(Tree).
쉽게 배우는 알고리즘 5장. 검색트리
출처: IT CookBook, 컴퓨터 구조와 원리 2.0 제 12장
Linux/UNIX Programming
Chapter 9 – 구조형과 리스트 처리 Outline 9.1 자신 참조 구조형 9.2 선형 연결 리스트 9.3 리스트 연산
[INA240] Data Structures and Practice
제 5장. Context-Free Languages
Chapter 8. AVL Search Trees
C언어 응용 제 10 주 트리.
Dynamic Programming.
1과목 데이터베이스 강사 이 민 욱.
Chapter 2. Finite Automata Exercises
자료구조 과제 풀이(6,7,8차) Yong-hwan Kim
IT CookBook, 자바로 배우는 쉬운 자료구조
Tree & Heap SANGJI University Kwangman Ko
CHAP 7:트리 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
AVLTree vs 편향 Tree.
스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제
자료구조(SCSC) Data Structures
CHAP 7:트리 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
Ch.06 Branch-and-Bound (분기한정법) (Ch.05-7 포함)
adopted from KNK C Programming : A Modern Approach
Inferences concerning two populations and paired comparisons
Dynamic Programming.
문제 다음의 서술적 언어로 표현된 요구사항을 DFD로 완성하시오
스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제
자료구조: CHAP 7(2) 트리 순천향대학교 컴퓨터공학과 하 상 호.
XML-II (eXtensible Markup Language) DTD/DOM
그래프와 트리 (Graphs and Trees)
CHAP 8:우선순위큐.
CHAP 12 : 탐색.
CHAP 12 : 탐색 C로 쉽게 풀어쓴 자료구조 생능출판사 2011.
0-1 Knapsack – 개선된 BFS 기반 알고리즘
이산수학(Discrete Mathematics)
알고리즘(Algorithm) 유비쿼터스 컴퓨팅학과 교수 송 창근
Chapter 9. Multilevel Indexing and B-Trees
점화와 응용 (Recurrence and Its Applications)
이산수학(Discrete Mathematics)
탐색 선형 탐색, 이진 탐색, 이진 탐색 트리.
Chapter 07 트리.
-아/어 드릴까요? 문 열어 드릴까요? 네, 감사합니다. Sogang Korean 2A UNIT 7 “-아/어 드릴까요?”
I/O Management and Disk Scheduling
트리 (Logical) Data Structures Linear list Tree Graph Linear structures
자료구조 자료구조의 개요 배열 선형 리스트 스택 큐 트리.
MST – Kruskal 알고리즘 (추상적)
Introduction to Computer System 컴퓨터의 이해 3: 데이터 표현
Windows System Programming
[CPA340] Algorithms and Practice Youn-Hee Han
알고리즘 강의 슬라이드 7 정렬문제 알고리즘 해석 강의 슬라이드 #7
Presentation transcript:

스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제 임의의 작업(Task)이 서비스를 받기 위해 대기하는 시간 + 실제 서비스를 받는 시간 스케줄링 문제 모든 작업의 전체 시스템 내부시간이 최소화 되도록 일정을 구성하는 문제

스케줄링 (Scheduling) 스케줄링 문제 t1=5, t2=10, t3=4 Example: 3개의 작업이 있고, 각 작업에 소요되는 시간이 5, 10, 4이다. t1=5, t2=10, t3=4 [t1,t2, t3]: 5+(5+10)+(5+10+4) = 39, [t1, t3, t2]: 5+(5+4)+(5+4+10)=33, [t2, t1, t3]: 10+(10+5)+(10+5+4) = 44, [t2, t3, t1]: 10+(10+4)+(10+4+5)=43, [t3, t1, t2]: 4+(4+5)+(4+5+10) = 32, [t3, t2, t1]: 4+(4+10)+(4+10+5)=37.

스케줄링 (Scheduling) 스케줄링 문제를 위한 탐욕알고리즘 정리 4.3 작업시간별로 작업을 비내림차순으로 정렬한다. 시간복잡도: W(n)(nlgn)  why? 정리 4.3 시스템 내부의 총 시간이 최소가 되도록 하는 유일한 스케줄은 작업시간별로 작업을 비내림차순으로 짠 스케줄이다. 작업시간별로 작업을 비내림차순으로 정렬한다. while (답을 구하지 못했음) { 다음 작업을 스케줄에 넣는다; //선택절차&적정성 점검 if (작업이 더 이상 없다) // 해답 점검 답을 구했음; }

마감시간 있는 스케줄링 마감시간(deadline)이 있는 스케줄링 문제: 각 작업을 끝내는 데 1의 단위시간이 걸림 각 작업마다 마감시간과 작업 후 발생하는 이익이 할당되어 있음 임의의 작업에 대한 초기 시작 시간: 시점 1 마감시간(deadline): 작업이 반드시 시작되어야 하는 마지 노선 시간 “작업 T1의 마감시간이 2이다”의 의미  작업 T1은 시점 1 혹은 2에 시작 가능 “작업 T2의 마감시간이 1이다”의 의미  작업 T2는 시점 1에만 시작 가능 총 이익을 최대가 되게 작업의 스케줄을 짜는 문제

마감시간 있는 스케줄링 마감시간이 있는 스케줄링 문제: Example: 작업의 마감시간과 이익이 다음 표와 같다고 하자. 이 경우의 가능한 스케줄과 총 이익은 오른쪽과 같다. 최적 스케줄: [4, 1] 이익이 가장 큰 작업 4는 최적 스케줄에 포함되었지만 두 번째로 이익이 큰 작업 2는 포함되지 않았다. 그 이유는 작업 4와 작업 2의 마감시간 (시점 1)이 같아 둘 중 하나만 포함할 수 있기 때문이다.

마감시간 있는 스케줄링 마감시간이 있는 스케줄링 문제를 위한 탐욕알고리즘 작업을 이익이 큰 것 부터 차례로 정렬 (비올림차순)한다. S = ; while (답을 구하지 못했음) { 다음 작업을 선택; //선택절차 if (이 작업을 추가하면 S가 적절하다.) //적정성 점검 이 작업을 S에 추가; if (작업이 더 이상 없다) // 해답 점검 답을 구했음; } 마감시간에 맞추어서 작업을 시작할 수 있다.

마감시간 있는 스케줄링 마감시간이 있는 스케줄링 문제를 위한 탐욕알고리즘 예제 4.4

허프만 코드 Representation of characters in computer 7 bits/char (ASCII) 2 bytes/char (KSC Hangul) 2 bytes/char (UNICODE) Isn’t there more efficient way to store text? Huffman Code: 문자들로 이루어진 데이터 파일을 코드화 하는 방법 중 하나 Data compression based on frequency  Huffman Code Binary coding (0과 1만 사용, 즉 이진 코딩) Variable length coding (가변 길이 이진 코딩) Assign short code for characters used frequently

허프만 코드 고정 길이 이진 코딩 vs. 가변 길이 이진 코딩 최적 이진 코딩 문제(Optimal Binary Code) 텍스트 파일의 문자 집합: {a, b, c} 고정길이 이진 코딩 a: 00, b: 01, c: 11 ababcbbbc  000100011101010111 (18 비트) 가변길이 이진 코딩 b가 가장 빈번하게 나온다는 것을 안다고 가정  b를 0으로 코딩 a: 10, b:0, c:11 (주의: a를 01로 코딩할 수 없음. Why?) ababcbbbc  1001001100011 (13 비트) 최적 이진 코딩 문제(Optimal Binary Code) 주어진 파일에 있는 문자들을 이진 코드로 표현하는 데 필요한 비트의 개수가 최소가 되는 이진 문자 코드를 찾는 문제

허프만 코드 Huffman code는 prefix code (전치 코드) 문자 코드가 서로 다른 길이를 가질 수 있다. 즉, 한 문자의 코드워드가 다른 문자의 코드워드의 앞부분이 될 수 없다. {b, a, c}={0, 10, 11} : prefix code {a, b}={01, 011} : not prefix code 전치 코드의 장점 전치 코드는 Leaf가 코드 문자로 구성된 이진 트리 (Binary Tree)로 표현 가능 인코딩되어 있는 것을 디코딩할 때 (즉, 복원할 때) 1-pass 에 디코딩이 가능

허프만 코드 Huffman code의 예 문자 집합 {a, b, c, d, e, f}에 대한 3가지 코드법 각 코드법을 사용한 결과 인코딩 파일의 총 비트 수 C1: 16 * 3 + 5 * 3 + 12 * 3 + 17 * 3 + 10 * 3 + 25 * 3 = 255 C2: 16 * 2 + 5 * 5 + 12 * 4 + 17 * 3 + 10 * 5 + 25 * 1 = 231 C3: 16 * 2 + 5 * 4 + 12 * 3 + 17 * 2 + 10 * 4 + 25 * 2 = 212 C3 방법이 가장 효율이 좋다.

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code) 최적 코드에 해당하는 이진 트리를 구축하여 최적이진문자 코드(Huffman code)를 만드는 문제

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code) priority queue 이용 [알고리즘] Top Priority – 빈도수가 가장 작은 문자 내부적으로는 heap으로 구현하는 것이 가장 좋다. [알고리즘] priority_queue 에 낮은 빈도수부터 오름차순으로 저장 priority_queue 에서 차례로 두 개를 선택 left와 right child에 배치하고 두 빈도수를 가진 새로운 root 노드를 만들어 binary subtree 를 생성 두 빈도수의 합을 priority_queue 에 삽입 더 이상 진행할 수 없을 때까지 반복 시간 복잡도: Θ(n lgn)

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code) [의사코드] 노드 타입 선언 우선순위 큐 PQ에 있는 nodetype 객체들을 가리키는 n개의 포인터를 다음과 같이 배열한다. PQ의 각 포인터 p에 대해

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code) [의사코드] 복잡도 분석: insert(PQ, r)에서 (lgn)시간 필요. 그러므로 전체적으로 (n lgn) 의 효율을 지님

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code) I:1 S:1 Y:1 A:2 b:2 M:3 Y:1 1 A:2 b:2 M:3 A:2 b:2 Y:1 S:1 I:1 2 3 1 M:3

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code) M:3 3 A:2 b:2 4 Y:1 2 I:1 S:1 1 1 Y:1 2 1 I:1 S:1 A:2 b:2 4 1 M:3 6 Y:1 S:1 I:1 2 3 1

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code) 10 4 6 M:3 A:2 b:2 3 Y:1 2 I:1 1 4 6 1 1 M:3 A:2 b:2 3 1 Y:1 2 1 I:1 S:1

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code)

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code) Another Example 1 1 1 1 1 문 자 1 문 자 빈 도 A 2 B 18 C 9 D 30 E F 36 1 1 1 1 문 자 빈 도 원래(ASCII) 크기 압축된 크기 차이 A 2 7*2=14 4*2=8 6 B 18 7*18=126 2*18=36 90 C 9 7*9=63 4*9=36 27 D 30 7*30=210 2*30=60 150 E 3*9=27 36 F 7*36=252 2*36=72 180 계 104 728 240 488

Appendix

Priority Queue What is Priority Queue? 응급실에서 환자 치료의 예 Priority Queue 큐: 먼저 온 사람을 먼저 치료 스택: 나중에 온 사람을 먼저 치료 우선순위 큐 (Priority Queue) : 우선순위가 높은 사람 (예: 위급한 사람)을 먼저 치료 Priority Queue an abstract data type supporting the following three operations: - add an element to the queue with an associated priority - Remove and return the element from the queue that has the highest priority - (optionally) peek at the element with highest priority without removing it Data Structure

Priority Queue Priority Queue vs. Stack/Queue 스택과 큐 스택과 큐는 시간에 따라 자료구조를 조직화 시간을 포함한 여러 가지 가치를 우선순위로 가지는 자료구조  우선순위 큐 우선 순위 큐는 각 노드에 “우선순위 값” 필드가 필요. 우선순위 큐는 스택이나 큐 보다 일반적인 구조 큐나 스택은 우선순위 큐의 특수한 형태로서 시간에 그 우선순위를 부여한 것임 따라서 우선순위 필드가 불필요 Priority Queue Stack Queue Data Structure

Priority Queue Heap is an excellent structure to implement priority queue Data Structure

Heap Heap: a binary tree structure with the properties … 주의할 특징 The tree is complete or nearly complete Root의 키가 왼쪽자식과 오른쪽 자식의 키보다 크거나 같다. 키: Priority The subtrees are in turn heaps 지원되는 연산: Insertion, Deletion, (optionally)Peek 주의할 특징 왼쪽 자식과 오른쪽 자식 사이에는 어느 쪽 키가 크던 상관이 없다. Data Structure

Heap Heap의 속성 A heap is a special kind of tree. It has two properties that are not generally true for other trees: [Completeness] - The tree is (nearly) complete, which means that nodes are added from top to bottom, left to right, without leaving any spaces. [Heapness] - The item in the tree with the highest priority is at the top of the tree, and the same is true for every subtree. (nearly) Data Structure

Heap Examples of Heaps Invalid heaps (Why?) Data Structure

Heap 정렬 관점에서… BST는 약한 의미로 정렬. Heap도 약한 의미로 정렬. 왼쪽 자식 키보다 오른쪽 자식 키가 크다. 부모의 키가 자식의 키보다 우선 순위가 높다 왼쪽 자식 키와 오른쪽 자식 키는 무관하다. Heap Binary search tree Data Structure