학부생 정리 노트

CH 8 - 3

Page Buffering Page performance를 향상하고 더 간단한 page replacement를 할 수 있게 해줌 대체된 페이지가 사라지는 대신 공백으로 채워 page를 읽거나 변형된 page list로 채워 page write를 도움 Replacement Policy and Cache Size 큰 cache일 수 록 page 대체는 큰 영향을 줌, page buffer을 사용해 향상 가능 대체될 page frame이 cache안에 있다면 cache블록과 page의 값은 사라짐 Resident Set Management OS는 main memory에 얼마나 많은 page가 들어갈지 정해야함 어느 정도 이상에선 page 할당량이 크게 page fault에 영향을 끼치지 않음 Resident ..

CH8 - 2

Associative Mapping TLB는 오직 page table entry 일부 만을 가지고 있으므로 page number로 TLB로 index 어려움 page table entry뿐만 아니라 page number를 각각의 TLB는 가지고 있어야 함 Processor는 HW를 통해 TLB entry에 맞는 page number가 있는지 알 수 있음 Page Size – 대부분 4KB Page size가 작을 수 록 internal Fragmentation이 줄어듦 그러나 각 process에 더 많은 page를 필요로 하게 되어 더 큰 page table이 생김 secondary-memory의 특성상 더 큰 page size를 효율 적인 데이터 전송을 위해 선호함 Main memory가 커지며 add..

CH8 - 1

Hardwarew and Control Structures Memory management에는 두가지 특징이 있음 1. 모든 메모리 참조는 logical address에서 physical address로 runtime중 변환된다. 2. 계속해서 실행될 필요 없는 process는 여러 조각을 나뉠 수 있다. 이로 인해 모든 page 혹은 fragment는 실행 중에 꼭 main memory에 없어도 된다. Execution of a Process OS는 프로그램의 일부(Resident set)를 main memory로 가져옴 Interrupt는 main memory에 없는 주소를 참조할 때 발생함 OS는 process를 blocking state로 전환함 Logical address를 가진 process가..

CH 7 Memory Management

Uniprogramming system main memory는 OS(resident monitor, kernel)를 위한 부분과 Program을 위한 부분 2가지로 나눠짐. User part는 적절하게 나뉘어져 여러 process를 처리할 수 있어야하며, 동적으로 memory management에 의해 일어남. 메모리 관리 방법 Frame : 메인 메모리의 정적인 블록. Paging : secondary memory의 정적인 길이의 블록 사용 Segmentation : 동적인 길이의 블록 사용 Memory Partitioning Memory Management는 프로세스를 메인 메모리로 옮겨 processor에서 실행 vistual memory를 포함하며, segmentation과 paging에 의해서 ..

NP

Finding lower bound Ex) ZB item을 정렬하고자 한다 2가지 접근법 더 효율적인 알고리즘을 개발한다 더 효과적인 알고리즘이 없다는 것을 증명한다. 연구 방법 더 효율적인 알고리즘을 새로운 디자인을 활용해 개발한다. 더 좋은 lower bound를 computational analysis를 활용해 찾아낸다. 만약 더 빠른 알고리즘을 찾지 못하면? (NP문제) 1. 느린 알고리즘을 사용해 optimal을 얻는다. 2. Optimal solution을 포기하고 approximate solution을 채택한다. 3. Massive 병렬화 : Super com, GPUs, 분산처리 => 새로운 Design : Parallel arlgorithms Problem categories and cl..

Branch and bound : TSP

Traveling salesman problem CS분야에서 가장 보편적으로 사용되는 optimization Prob BF부터 모든 알고리즘 사용가능 Bound function h-value : TSP >= min. outgoing/incoming edges of node A/B, => 가장 min edge로 출입한다. => h < h* h1 : 무조건 제일 작은 outgoing edges로 연결되는 것을 추정 h2 : h1을 활용하되, 이미 지나온 노드는 배제하여 추정 V1: starting ndoe(fixed) H= (v2) min(7,8,7) + (v3) min(4,7,16) + (v4) min(11,9,2) + (v5) min(18,17,4) = 7 + 4 + 2 + 4 = = 1 H3 : 일반적..

Backtracking – knapsack

Promising function 1. Weight > W : stop, not expand, nonpromising 2. (Subset sum) - weight + w(next) 0/1 KS에서는 기준점이 변한다. (Best profit) ==> 다이아몬드 + 금 A 집합 -> 금 + 큐빅 A 집합 nonpromising ===> Nonpromising function == Bounding function Bound function = 지금까지의 profit(g) + 남은 아이템 이익의 최대 추정치(예측, h) bound function = g + h < Best (..

Greedy vs DP

Greedy가 중요한 이유 자연스럽고 간단하고 빠르고 간단한 implementation, heuristic(지식 기반) idea Test-bed : 실험에 기준점을 제공, 가장 먼저 접근하는 전략 optimal할 가능성이 높음 – 증명 필요 Knapsack Problem 제약 조건이 있는 문제에서 어떤 것이 가장 optimal할지 정의 S (객체, 문제 구성요소 object), W (제약 조건), P (가치), Sack size(제약 한도) S의 부분 집합 중 P가 가장 최대가 되는 A 구하기, sum of W

CH6. Concurrency-2

Deadlock and Starvation Deadlock 여러 프로세스가 같은 자원을 탐할 때 영구적인 block현상이 발생, 효율적인 해결법이 없음, 예측 불가능 Reusable 자원 – 한 프로세스가 사용해도 사라지지 않는 메모리 등 Comsumable 자원 – 한 번 사용하고 나서 사라지는 interrupt, signal 등 이유 - Mutual exclusion, Hold-and-Wait, No preemtion, Circular wait 등의 이유로 발생 해결법 - 방지, 회피, 감지 세 분류로 나뉨 방지법 – Deadlock의 원인을 차단하는 강력한 방식 indirect방식 : Mutual exclusion, Hold-and-Wait, No preemtion의 발생을 차단 direct방식 :..

CH5. Concurrency

Mutual Exclusion and Synchronization Multiple process multiprogramming multiprocessing distributed processing Concurrency interleaving과 overlapping 처리가 중요, Uniprocessor의 경우에는 프로세스의 실행 속도를 알 수 없어 OS가 interrupt와 scheduling을 잘 처리해야함 OS는 여러 프로세스를 추적할 수 있고, 자원 할당 및 보호, 프로세스와 산출물이 속도와 관계없이 잘 실행 될 수 있도록 해야함. Race condition 데이터를 입출력할 때, 다른 프로세스와의 순서에 영향을 받음 resource competition 여러 프로세스가 같은 자원을 탐할 때 발생, ..

CH4. Threads

resource ownership 프로세스는 가상 주소 공간을 process image 보관을 위해 가짐 Scheduling&Execution 다른 프로세스가 남긴 실행 경로를 따름, OS가 주로 관리 Multithreading 하나의 process를 여러 개의 thread로 실행 resource는 process나 task가 관리 각 Thread는 실행상태, 실행스택, 정적 저장공간, 자원 접근 권한, thread context, control block(멀티 쓰레드의 경우)를 가짐 Thread의 사용으로 적은 시간으로 생성, 실행, switch를 하여 효율을 높일 수 있음 프로세스를 중단, 종료하면 모든 thread가 영향을 받음, scheduling과 dispatch는 thread가 진행 Thread..

CH3. Process Description and Control

Process Program code와 data set으로 구성되며 더하여 Identifier state 등등이 있다. Process control Block process elements를 포함하고 있어 interrupt로 인해 문제가 생기지 않도록 하며 OS에 의해 관리된다. Process States TRACE – instruction의 실행 시퀀스, 프로세스의 동작 특정 가능 Dispatcher – 다른 processor로 권한을 넘기는 작은 프로그램 Suspended Process Swapping을 통해 프로세스의 일부 혹은 전체를 main memory에서 disk로 옮기는 것. DISK IO가 일반적으로 빨라 성능을 보통 향상시키나 IO 작업이므로 역효과의 가능성도 있음 Suspend된 pro..