HJW's IT Blog

IPv4 Address Exhaustion > IPv4의 주소는 거의 다 소진됨 > 해결방안 : >> DHCP(Dynmic Host Configuration Protocol) >> NAT(Network Address Translation) >> IPv6(IP version 6) DHCP: Dynamic Host Configuration Protocol > 목표: Host 들이 네트워크 접속시 동적으로 IP를 할당 받을 수 있도록 >> 사용중인 주소 renew 가능 >> Connected 된 동안만 주소를 hold --> reusable >> 동작방식은 다음과 같다 >> DHCP 는 IP 주소 이외에도 다음 사항들을 반환 가능 >> 클라이언트의 first hop router address >> DNS 서버..

네트워크 계층 > 네트워크 계층은 전송 계층의 세그먼트를 보내는 호스트에서 받는 호스트로 전달한다. > 송신측에서는 segment 들을 암호화 하여 datagram으로 만든다. > 수신측에서는 받은 segment들을 transport layer 로 전달한다. > 네트워크 계층의 세가지 주요 동작 >> Forwarding: 패킷을 라우터의 입력에서 올바른 출력으로 옮긴다 >> Routing: 패킷이 송신지에서 수신지로 가는 경로를 정한다 >> Connection Setup: 데이터그램들이 송신되기 전, end-host 와 중간 라우터들은 가상의 연결을 설정한다 > 네트워크 서비스 모델 >> One Datagram >>> Guaranteed Delivery under 40 msec >> Flow of Dat..

Link-State Routing Algorithm > Dijkstra's Algorithm >> 네트워크상 모든 노드가 링크 비용을 알고 있다 >> 가장 적은 비용이 드는 path (한 노드에서 다른 모든 노드로) >> Iterative >> Notation 바로 옆에 있는것이 아니라면 무한대> > O(n^2) --> 더 효율적이게 O(nlogn)에 가능 Distance Vector Algorithm > Bellman-Ford Equation (DP) > Dx(y) = x 에서 y 로 가는 예상 최소 비용 > node x 에 대해: >> neighbor v 에게 비용이 알려져 있다 > Distance Vector Algorithm 의 Key Idea >> 일정한 시간이 지나면 각 노드는, 각자의 dis..

메모리에 저장되는 정보 분류 1. 프로그램 내에 역할에 따라 >> Program Instructors >> Constants >> Variables 2. 보호 상태에 따라 >> Readable and Writables: variable >> Read-Only: Code, constants >> Data 와 Code 공유에 중요 3. Binding Time ( 언제 공간이 할당 되는가?) >> Static: 프로그램이 실행 되기 전 - 코드, 전역변수 등... >> Dynamic: 프로그램 실행 도중 - 스텍, Dynamic storage 등... Uniprogrammed System 에서의 Memory Management > OS 는 정해진 크기의 메모리를 가진다 > 한번에 하나의 프로세스만 single..

Deadlock Avoidance: Motivation > '///' 와 '\\\'는 두 프로세스가 동시에 IO를 접근함 > 모든 path는 위 혹은 오른쪽 > 'Unsafe' : OS 가 이 box에 들어오게 되면, 결국 deadlock이 발생함으로 들어가선 안된다. > state t 일때, unsafe 한 공간은 피해야 한다(위가 아닌 오른쪽으로 감으로써) > State t 일때, OS는 request를 허락할 지 정해야 한다 > Good choice: Avoid Deadlock > 이를 수행하기 위해선, 미리 어떤 자원들이 필요할 지 알아야 한다. Deadlock Avoidance: Safe and Unsafe States > (a) 는 safe 한 상태: 할당되는 순서가 deadlock 없이 모든..

IP Fragmentation, Reassembly > 네트워크 링크는 MTU(Maximum Transfer Size)를 가지고 있다 > 큰 IP datagram은 네트워크 상에서 나누어진다 (fragmented) > 하나의 datagram이 몇개의 datagram이 된다 > 끝에서 다시 reassemble > 같은 datagram 출신인것은 ID를 통해 identify > IP header를 사용해 순서를 정함(offset) > Fragment Length 의 합이 원래 datagram lentgh의 합보다 큰 이유는 header 때문. > 위에선 header = 20 byte > flagflag = 0 : 뒤에 더 없다, flagflag = 1: 뒤에 더 있다. IP Addressing: Intro ..

CPU Schduling > 5 State Transition > Ready-Queue에 있는 프로세스 선택 -> CPU에 올린다 > 모든 프로세스가 메모리에 올라가 있다고 가정, 실행 중인 프로세스는 CPU에 올라가있다 가정 > Multiprogramming 에서 필수적(CPU utilization) > Non-Preemptive Scheduling > 프로세스가 "Terminated" 일때 다음 프로세스 실행 > 프로세스가 "Running" 에서 "Blocked" 되었을 때 실행 > 프로세스 우선순위가 더 높은 프로세스가 있다 하더라도 현제 프로세스가 종료가 되어야 함 > CPU Scheduling Goals > CPU 가 결정하는 사항 > 프로세스가 얼마나 실행될 지 > 어떤 순서로 프로세스가 실행..

Semaphore --> 큰 개념 두가지: lock, 통신(동기화) --> 공유 자원을 여러 스레드에서 사용할 때 충돌을 방지하기 위함 --> 여러 스레드가 공유자원을 서로 액세스 할 때 문제 발생 위 코드는 자판기를 producer-consumer 문제로 모델링 한 것이다. --> 자판기에는 emptySlot 이 100개 있다. (콜라를 담을 수 있는 슬롯) --> DeliveryPerson() 은 자판기에 콜라를 넣는다.(emptySlot이 가득 차지 않았을 경우) --> DeliveryPerson() 은 콜라를 하나 넣을때 마다 semaphore를 하나 감소. (emptySlot 감소) --> ThirstyPerson() 은 콜라를 뽑아 마시는 사람. --> ThirstyPerson() 은 자판기가..

TCP Flow Control sender 가 rcv 에게 자신이 수용할 수 있는 데이터 양을 알려주어, sender 특이 데이터를 조절하는 기능 즉, 강제로 송신측의 데이터 전송을 줄이는것 rwnd: Rcv가 sender에게 전송 가능한 윈도우의 크기를 나타내는 변수 rcv가 rwnd를 계산하여 sender에게 알리면 sender는 rwnd 이상의 데이터 전송 x Sender: Last-Byte-Sent - Last-Byte-Acked = "In-Flight Data" Rcv: Last-Byte-Rcvd - Last-Byte-Read = Data in Receiver Buffer RcvBuffer - (Last-Byte-Rcvd - Last-Byte-Read) = rwnd Sender 는 ("In-Fl..

크루스칼 알고리즘이란 최소 신장 트리를 찾는 그래프 알고리즘 중 하나이다. 이때, 그래프는 무방향이다. 최소 신장트리(Minimum Spanning Tree: MST)란 모든 정점을 포함하면서 그래프의 모든 간선의 가중치 합이 최소인 트리를 의미. --> 사이클 없이 모든 노드가 연결되어야 한다. 동작원리 --> 그래프의 모든 간선을 오름차순 정렬 --> 가중치가 가장 작은 간선 선택 --> 이 간선이 최소 신장 트리에 이미 포함되어 있는지 확인 --> 포함되어 있지 않다면 해당 간선을 MST에 추가 풀이 1: --> 각 질의마다 크루스컬 알고리즘을 돌리며 연결 되는 순간 에지의 가중치 값이 질의의 답 c --> 이때 크루스컬 알고리즘에 O(|E|log|V|) 시간, 총 Q의 질의 가 있으므로 O(Q|E..