랄뚜기의 코딩일기

Paging : Linear Tables 32-bit address를 space를 사용하고 4KB의 page table을 사용한다면 Page table의 크기는 2^32/2^12*32=4MByte의 크기를 차지하게 된다. 이 page table의 크기는 너무 크다. Page size의 크기를 늘린다면 어떻게 될까? page table은 1MB로 줄어들게 되지만 page frame 안에서의 공간이 남아돌기 때문에 internel fragmentation이 발생한다. 또 각각의 page table이 linear하기 때문에, 언제 사용될지 모르는 낭비되는 공간이 발생하게 된다. Hybrid Approach : Paging and Segment Page Table에서 저렇게 남는 공간이 있는 걸 어떻게 해결 할..

페이지 테이블을 이용하게 되면 메모리를 flexble하게 사용할 수 있으므로 메모리 효율이 올라간다. 하지만 logical address를 physical address로 변환시키기 위해서 page table에 접근하고 page table에 있는 physical address를 확인 후에 다시 physcial address로 접근해야 한다. 따라서 2번의 메모리 접근이 일어나기 때문에 성능이 내려가게 된다. 이를 해결하기 위해서 MMU에 TLB(Translation Lookaside Buffer)를 넣어서 만약 TLB에 cache되있어 hit가 일어난다면 바로 physical address에 접근할 수 있게 한다. TLB는 하드웨어의 cache라고 생각하면 된다. 32-bit address를 4KB의 p..

위와 같은 문제가 있다고 하자. 위 식을 divde-and-conquer로 풀게 되면 1 (i=0,j>0) P(i,j)= 0 (i>0,j=0) (P(i-1,j)+P(i,j-1))/2 이 되고 T(n) = 2*T(n-1) + c가 되므로 O(2^n)이 되게 된다. 이를 해결하기 위해서는 중복된 값을 계산하지 않는 Dynamic Programming을 사용하면 된다. Source에서 sink까지 갈 때, 어떻하면 최댓값으로 갈 수 있을까? 경우의 수는 총 2^n*2^m으로 exponential하다. 하지만 직전의 것과만 비교하면 경우의 수가 n*m개로 줄게 된다. DP에서는 직전값들끼리 비교를하기 때문에 초깃값을 설정해주어야 한다. 2,3번은 초기값을 넣어준다는 말이다. 1 번은 직전것들끼리 비교하여 최댓값..

Access Control Wireless LANs에는 CSMA/CD이 다음과 같은 이유로 적용되지 않는다. 1. Wireless hosts는 보내고 받는 것을 동시에 할 충분한 전력이 없다. 2. Hidden station이 collision detection을 막는다. 3. Stations들 간의 거리가 멀 수 있다. IEEE 802.11 project IEEE는 wireless LAN을 IEEE 802.11로 정의하였다. wireless Ethernet이라고 불리기도 한다. 몇몇 나라에서는 WiFi(wireless fidelity)를 wireless LAN의 동의어라고 하지만 WiFi는 WiFi Alliance에만 특정하므로 아니다. Architecture standard는 basic service..

Recursive-descent parsing(재귀적 하강 구문 분석) Input string을 parsing하기 위해 recursive procedure를 사용한다. - Nonterminal symbols에 대한 프로시저 및 Terminal symbols에 대한 프로시저를 각각 작성한 다음 이를 통합함으로써 구현한다. - Terminal symbol에 대한 프로시저는 production rule에 있는 terminal symbol과 input symbol이 같은지 비교하여 같은 경우 다음 input symbol을 읽게 한다. - Nonterminal symbol에 대한 프로시저는 현재의 input symbol를 생성할 수 있는 적절한 생성 규칙이 선택되도록 작성한다. 먼저 현재의 입력 기호를 보고 시작..

FIRST 즉, Nonterminal A로부터 유도되어 첫 번째 나타나는 터미널 기호들의 집합이라고 할 수 있다. Nullable Nonterminal 𝜀으로 유도되지 않으므로 nullable하다. Ringsum and FIRST Ringsum에서 A에 𝜀이 포함이 되면 빠지는 개념은 매우 중요한 개념이므로 주의하자. FOLLOW FOLLOW(A)는 어떤 문장 형태에서 논터미널 기호 A다음에 나오는 터미널 기호들의 집합이다. Sentential form에서 nonterminal A 다음에 나오는 terminal symbols의 set. $는 입력 문자열의 끝을 나타내는 symbol. FOLLOW(A) 1. 만약 A가 시작 기호이면 $는 FOLLOW(A)에 속한다. 2. 만약 B->ɑAβ,β≠𝜀인 생성규칙..

Pushdown Automata finite automata와 다른 점은 stack symbol T와 ,start symbol of stack z0가 추가되었다는 점이다. 문제를 풀 때, δ(q0,주어진 값,z0)로 시작한다. 결과가 하나라면 deterministic push-down automata DPDA가 되고 하나 이상이라면 non-deterministic push-down automata NPDA가 된다. Extended Transition Fuction of PDA Syntax Analysis 스캐너에 의해 생성된 토큰을 입력으로 받아 주어진 문법에 맞는지를 검사하고, 문법에 맞으면 파스 트리를 출력하고 맞지 않으면 에러를 출력 Syntax analysis를 담당하는 도구를 syntax ana..

Selection of Both Maximum and Minimum Elements #define _CRT_SECURE_NO_WARNINGS #include #include struct Result { int minValue, maxValue; }; struct Result MAXMIN(int A[], int l, int r) { struct Result ret; if (l == r) { ret.minValue = ret.maxValue = A[l]; return ret; } else if (r - l == 1) { ret.minValue = (A[l] A[r] ? A[l] : A[r]); return ret; } stru..

Insertion Sort void insert_sort(int *A, int n){ int i,j,tmp; for(i =1;i0)&&(tmp

Full Adder Gate delay A가 바뀐다고 해서 바로 X가 바뀌는 것이 아니다. Gate 안에서 연산이 되므로 값이 바뀔 때마다 delay가 발생한다. 따라서 무작정 값을 바꾸자마자 원하는 값을 확인하는 것이 아니라 싱크를 맞춰서 값을 가져와야한다. 이를 하지않으면 이상한 값을 가져올 수 있다. 위는 full adder의 time delay를 나타낸 것이다. 회로를 보면 6개의 Gate delay가 일어나는 것을 알 수 있다. 수식적으로 보면 XOR을 하는데 3Gate Delay가 일어남으로 Sum은 6Gatedelay가 일어난다는 것을 알 수 있다.(단, a,b가 먼저 계산) 또, Cout은 a*b는 먼저 계산되지만 a⨁b가 일어날 때까지 기다리므로 무시한다. Cin*a⨁b가 일어나고 이 값..