랄뚜기의 코딩일기

Multiprocessor Scheduling Multicore processor의 등장으로 multiprocessor-scheduling이 필요하게 되었다. 우리는 threads를 활용하여 여러 개의 CPU들에 jobs을 schedule 해주어야 한다. Single CPU with cache Cache에는 main memory에 있는 popular data들을 복제하여 저장해놓는다. Cache는 Main Memory에 비해 접근이 빠르다. Cache coherence CPU 0과 CPU 1이 data D를 다룬다고 할 때, 각각의 cache들은 private한 성질을 가지고 있으므로, CPU 1은 update 된 D'가 아닌 D를 가져오게 된다. 따라서 CPU에서 update data를 cache에서 ..

Switching 네트워크는 기기들의 연결로 구성된다. 기기의 수와 상관없이, 우리는 한 기기와 다른 한 기기를 연결하는데 문제를 가지고 있다. 이 문제를 해결하기 위해서 Switching이 필요하다. Switched network는 switches라고 불리는 일련의 interlinked nodes로 구성되어 있다. Switching에는 circuit switching, packet switching이 있다. Paket switching은 virtual-circuit approach와 datagram approach로 나누어진다. Circuit-Switched Networks circuit-switched network는 physical links로 이어진 a set of switches를 포함한다. 두..

Transmission media Transmission media는 physical layer 밑에 위치해 있고 physical layer에 의해 control 된다. 따라서 우리는 transmission media는 layer zero에 속해 있다고 할 수 있다. Transmission media는 Guided(wired), Unguided(wireless)로 나누어진다. Guided Media Guided Media는 twisted-pair cable, coaxial cable 그리고 fiber-optic cable로 이루어져 있다. wired 하기 때문에 당연히 physical limits가 존재한다. Twisted-Pair Cable Twisted-Pair Cable은 구리와 같은 conduct..

MSS는 위에 그림에서 L,R,LR 중 하나의 경우로 존재할 것이다. Divide-and Conquer로 Recursive하게 풀면 O(NlogN)에 풀 수 있다. https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 위 문제를 풀 때 사용했던 방법이다. 이해 할 때 참고하면 좋다. 2차원 배열의 MSS를 구하는 문제이다. 크기가 n*n의 2차원 배열에는 약 1/4*n^4개의 subrectangles가 있다. 단순하게 모든 경우의 수를 더하는 것은 가로 세로 ..

NFA->DFA NFA->DFA (2) 𝜀-closure가 없는 경우 State Minimization Example ( State Minimization ) Regular Grammar -> Regular Expression 주어진 Grammar G에 의해 생성되는 Language L(G)가 무엇인지를 알기 위해서 Regular Grammar를 Regular Expression으로 변환 Regular grammar를 coefficient가 regular expression으로 구성된 방정식인 regular expression equation으로 바꾸고 solution을 구함 Regular Expression -> Finite Automata

Automata Automata를 분류하는데 2가지 방법이 있다. 1. 현재 state에서 다음 state의 갯수에 따른 분류 - Deterministic automata : 하나의 입력을 받았을 때 다음 state는 유일 - Non-deterministic automata : 하나의 입력을 받았을 때 다음 state가 2개 이상 2. 기능적인 측면에서의 분류 - 인식기(accepter) : 입력된 결과에 대해 accept/reject 등을 표시 - 변환기(transducer) : 주어진 입력에 대응하는 새로운 문자열 출력 Finite Automata 어떤 알파벳 ∑로 부터 만들어지는 문자열의 특별한 것들을 받아들이는 시스템의 수학적 모델로서, 그 시스템에서 변화할 수 있는 상태가 유한개인 것. 컴파일러..

Multi-Level Feedback Queue(MLFQ) MLFQ의 목적은 turnaround time을 optimize하고 프로그램의 실행시간을 모르는 상태에서 response time을 minimize하는 것이다. MLFQ를 배우기 전에 알아야 할 개념이 있는데 short job은 반복적으로 CPU권한을 포기하는 job이고(ex : repeat I/O), long job은 CPU를 굉장히 intense하게 사용하는 job이다. fork(A,B,C,D)를 했다고 가정하자. A와 C는 프로그램이 완료 또는 interrupt가 2ms 정도에 이루어지고, B는 16ms, C는 64ms 정도에 이루어진다고 하자. 처음 들어온 A,B,C,D 모두 Q4에 들어가 순서대로 2ms씩 실행되게 된다. A와 C는 실행..

Scheduling Metrics Scheduling Metrics에는 Performance Metric과 Fairness Metric이 있다. 참고로 밑에 예시들은 I/O input이 없는 경우이다. First In, First Out(FIFO) 먼저 오는 것이 먼저 실행되는 방식이다. 위와 같이 먼저 온 것의 실행시간이 긴 경우 Average turnaround time이 늘어나게 되고, convey effect가 발생할 수 있다. Convey Effect Convey Effect란, 예를 들어서 cpu intensive한 p1과 I/O를 많이 실행하는 p2~p10이 있다고 할 때, p1이 먼저 run할 경우에 p2~p10에서 SSD를 사용해야 하지만 p1이 실행 되는 긴 시간 동안에 SSD는 IDL..

Switching algebra는 or가 +로 표현되서 유도하기가 처음엔 힘들다... 많이 연습하자... p14a 증명하는 것을 보면 distributive를 두번하면 식이 바뀔 수 있다는 것을 알 수 있다. i여기서 중요하게 생각 할 부분은 1을 (A+A')로 만들었다는 것이다. Proof of DeMorgan's Laws 드모르간 법칙을 증명할 때는 일단 드모르간 법칙이 맞다는 가정하에 A+A'=1과 A.A'=0이 성립하는지 확인하면 된다.

Multiplexing Multiplexing이란 한 data link에 여러가지 signal들을 한번에 보내는 기술을 말한다. n개의 input이 MUX에서 합쳐져서 1개의 link를 타고 이동한 뒤 DEMUX에서 다시 n개로 갈라진다. Multiplexing방식은 위와 같이 나뉜다. Frequency-Division Multiplexing n개의 input을 받을 때, 각각 n개의 signal에 고유의 빈도수를 가진 modulator을 이용하여 치환하고 합친다. Wavelength-Division Multiplexing input들을 레이저의 서로 다른 파장(색)을 이용하여 modulation하는 방식이다. Time-Division Multiplexing 여러개의 input을 시간끼리 그룹으로 묶어 ..