본문 바로가기

Archived(CSE)

 (49)
Chap 8. Memory Management - Memory address 접근 - Memory address binding(compile, loading, execution) - physical vs logical address(execution만 다르다), MMU(메모리 접근 처리) - Static vs Dynamic linking(장점- 유지보수, 메모리 관리, 단점 - one time cost) - Swapping(메모리와 디스크 교환), Context Switching time - Contiguous Memory Allocation, 고정/가변 사이즈(first, best, worst fit) - Fragmentation(내부외부) -> Segmentation(내부 단편화 해결 가능) - Paging(외부 단편화 해결가능), page #,..
Chap 7. Deadlock - Deadlock의 개념(모든 프로세스가 다른 프로세스의 이벤트를 기다리는 상태) - Deadlock의 조건(Mutual Exclusion, Hold and wait, Non preemption, Circular wait) - Resource allocation graph(자원, 프로세스, 관계) - Deadlock 대처 방안 3가지 (예방 & 회피, 탐지 & 회복, 그냥 두기) - Deadlock 예방(조건 4가지에 대해 각각, circular만 현실적으로 가능) - Deadlock 회피(RAG alg, 뱅커스 alg) RAG는 cycle 형성 x -> 데드락 발생x 뱅커스 alg은 RAG가 multiple instance에서 사용이 불가능하기에 등장 새로운 요청이 있을 경우, safe state인지..
Chap 6. 레지스터와 카운터 - 레지스터 개념(저장 기능의 flipflop), 카운터 개념(숫자를 세는 flipflop 집합) - 레지스터(4 bit 저장, 병렬), Shift 레지스터(직렬, 병렬, JK, T), 만능 Shift 레지스터 - 카운터 분류(binary, non binary // Ripple, Synchronous) - 리플 카운터(ff의 출력값이 다음 ff의 클럭으로 들어온다) 이진, BCD - 동기 카운터(동시에 값이 바뀔 수 있다) 이진, BCD, 병렬, ETC(링, 존슨) - HDL 표현하기
Chap 5. 동기 순차논리 조합논리회로에서 저장 기능을 포함한 순차논리에 대한 단원 - 순차 논리회로의 개념(저장 기능 추가) - Latch, FlipFlop 개념(latch는 레벨 트리거, FF는 엣지 트리거) SR latch, S'R' latch, D latch // D ff, JK ff, T ff - 순차 논리회로 사용개념(상태도, 상태표, 상태식, 출력식) ff은 특성표와 특성식 - 순차 논리회로 분석하기(diagram이 주어졌을 때 분석해서 어떤 기능인지 파악) - HDL로 표현하기(initial, always // = 블락킹, 상태 축소 > 상태 할당 > binary state table 표현 > flipflop 선정 > IO equation 정리 > logic diagram)
Chap 4. Greedy Approach - Greedy Approach 는 말 뜻 그대로, 욕심이 많다. 미래를 생각하지 않고 현재만 생각(Locally optimal) - ex) 우리나라 동전은 Greedy Approach로 큰 화폐 단위로부터 locally optimal하게 고르면 잘 골라짐 - MST는 minimum Spanning Tree의 약자로, 최소 weight로 모든 node를 연결하는 트리 형성하기 (참고로 Spanning tree는 1) Sub graph, 2) Cover vertex, 3) Tree 의 조건을 만족해야함) - MST를 만드는 대표적인 두 가지 방법 Prim 알고리즘, Kruskal 알고리즘 - Prim's Alg 는 출발 노드(1)로 부터 가장 작은 값을 고르고, 또 연결된 노드를 포함하여 연결되있는 edg..
Chap 3. Dynamic Programming - Merge sort를 접근하는 데 있어 Divide and Conquer는 적절하다, recursive도 맞을 수 있지만 overlapping이 문제가 되기에 bottom up으로 올라가는 게 맞을 수 있다 - XX로 시작되지 않는 문자열 나열하기는 Qk = 2Qk-1(Y~,Z~) + 2Qk-2(XY~, XZ~) - Binomial coefficient 조합값 찾기 nCk = n-1Ck-1 + n-1Ck - Floyd's Algorithm은 AFSP(All Fair Shortest Path) 찾기 문제이다. - 기본적인 접근법은 Dynamic Programming, 핵심 아이디어는 K를 거치느냐 안거치느냐 - Dk[i,j] (i~j로 가는 경로 중 k 이하 node를 거치는 경로) 를 다음과 같은 경..
Chap 2. Divide and Conquer - Divide and Conquer의 기본은 Binary search를 예로 들 수 있다(시간복잡도와 call-by-value) - Merge sort 또한 Divide and conquer(계속 반으로 갈라서 한 개가 되면 크기 비교하며 합치기) - online은 실시간으로 넣는것(hash), offline은 input 다 넣고 처리 - inplace sort는 배열 제자리에서 처리하는가, stable은 같은 값들을 위치 조정하지 않는가 - stable은 특히 주의 깊게 보기(stable이 좋긴 하지만 실제 제약과 소모값이 있어서 unstable이 빠르긴함) - quick sort 또한 Divide and conquer(pivot 기준으로 ++와 -- 하면서 비교하기) - quick sort가 빠른 ..
Chap 6. Synchronization - Bounded-Buffer problem(Producer/Consumer 간에 같은 버퍼 공간 사용 시, Instruction이 Atomic X -> Race Condition 문제 발생) - Synchronization이 필요한데, Multi-Thread 에서는 변수 공유를 하기에 더욱 필요, Kernel의 경우 선점문제 - Critical Section 문제(ES-CS-ES-RS), 솔루션의 3가지 요구사항(상호배제, 진행, 기다림 제한) - Strict Alternation(상호배제는 o, Progress는 x(원하지 않더라도 반복)) - Peterson's Algorithm(flag, turn 두 가지 변수를 활용해 원하는지도 체크, 나올 때 flag false 준다) - 상호 배제(무조건 하..

티스토리툴바