스케줄링 (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} : no 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) [의사코드] 노드 타입 선언 초기화 1: nodetype 객체들을 가리키는 n개의 포인터 p에 대해 초기화 2: n개의 nodetype 객체들을 우선순위 큐 PQ에 삽입한다.

허프만 코드 최적 이진 코딩 문제(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 is an excellent structure to implement priority queue 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 (Binary Search Tree)는 약한 의미로 정렬. Heap도 약한 의미로 정렬. 왼쪽 자식 키보다 오른쪽 자식 키가 크다. Heap도 약한 의미로 정렬. 부모의 키가 자식의 키보다 우선 순위가 높다 왼쪽 자식 키와 오른쪽 자식 키는 무관하다. Heap Binary search tree Data Structure