랄뚜기의 코딩일기

Telephone Network Telephone network는 1800년대 후반에 처음 사용되었다. 모든 network가 음성을 보내기 위한 analog system이었다. Computer시대가 도래하고, 목소리 외에 다른 정보들을 옮기기 시작했다. Major Components Telephone network에는 local loops, trunks, switching offices 이렇게 3가지 구성요소가 있다. Telephone network는 end offices, tandem offices 그리고 regional offices와 같은 여러 단계의 switching offices가 있다. LATAs 1984년도에 미국은 200개 이상의 local-access transport areas(LATA..

Ethernet Protocol data-link layer와 physical layer는 local과 wide area network의 영역이다. IEEE Project 802 서로 다른 장비들이 통신 할 수 있도록 Computer Society는 1985년에 Project 802라는 기준을 만들었다. Ethernet Evolution Ethernet LAN은 1970년대에 만들어졌다. Standard Ethernet(10 Mbps), Fast Ethernet(100 Mbps), Gigabit Ethernet(1 Gbps), 그리고 10Gigabit Ethernet(10 Gbps)를 거쳤다. Standard Ethernet Standard Ethernet은 10Mbps의 original Ethernet..

Grammar Conversion Ambiguous grammar를 unambiguous로 변환. 즉, Syntax analysis의 효율이 나쁜 문법을 효율이 좋은 문법으로 변환한다는 것이다. Conversion method - Elimination of useless production rules - Elimination of epsilon production rules - Elimination of single production rules - Elimination of left-recursion - Left-factoring Elimination of useless production rules Uesless production rule - useless symbol를 가지고 있는 producti..

Concept of paging Paging은 각각의 address space를 fixed-size로 나누어 page로 나누는 것이다. Paging에서, physical memory도 page frame이라는 것으로 나누어진다. Process 마다 있는 page table은 virtual address를 physical address로 변환할 줄 알아야한다. Advantages Of Paging Flexibility : address space를 효과적으로 사용할 수 있게 도와준다. Simplicity : page와 page frame이 같은 size를 가지고 있고, 할당하기도 쉽고 가지고 있기도 쉽다. 여기서 중요한 점은 logical address에서는 contiguous하다는 것이다. Common ..

Segmentation Segment는 그저 address space의 contiguous한 부분일 뿐이다. Segmentation은 OS에게 각각의 segments(Code(Data), Stack, Heap)를 다른 physical memory에 위치 시킬 수 있게 해준다. 따라서 사용되지 않은 virtual address 공간에 physical memory를 채우는 일을 피할 수 있다. Segmentation Implementation MMU는 프로세스마다 다른 Segment Table을 가지고 있다. 각각의 segment는 그들만의 base and bound, protection bits를 가지고 있다. 0x0240은 segement가 0 이므로 Base 0x2000을 더해줘 physical add..

Virtual Address Space 만약 molloc, free() 등과 같은 함수를 읽게 되면 syscall이 발생하여 brk,sbrk,mmap과 같은 기능을 하게 된다. malloc() sizeof() free() Forgetting To Allocate Memory 언뜻 보면 위에 코드가 맞는 것 처럼 보이지만 *dst는 unallocated되어있기 때문에 *src의 내용을 받을 공간이 없다. 미리 *dst에 공간을 할당해주면 된다. 문제는 적게 할당을 하더라도 error없이 잘 돌아간다는 것이다. 이런 에러는 나중에 일일이 다 뜯어서 고쳐야하므로 주의하도록하자. 공간만 할당하고 안에 내용을 넣지 않은 채로 접근하는 것도 문제가 된다. Memory Leak heap 영역에 메모리를 다 사용했다면..

SUM-OF-PRODUCT와 PRODUCT-OF-SUM은 위와 같은 관계를 가지고 있다. PRODUCT-OF-SUM을 Karnaugh Map을 가지고 구할 때, F=Pos이면 F'=Sop라는 것을 활용하여 구하면 된다. Example x'yz'+x'yz+xy'z'+xy'z+xyz Example에 식을 Karnaugh Map에 Mapping시키면 위와 같다. implicant를 위와 같이 묶으면 어떻게 될까? 111이 011 또는 101로 묶이는 경우가 있기 때문에 prime implicant가 아니므로 안된다. 따라서 위 처럼 x'y+xy'+xz 또는 x'y+xy'+yz 로 나타낼 수 있다. 참고로 모든 implicant가 Essential prime implicant이다. 해당 Karnaugh Map은..

Random Access random-access는 data가 오면, 받는 이가 자신의 상태에 따라 사용할지 말지를 결정한다. ALOHA ALOHA는 radio LAN을 위해 디자인 되었지만, shared medium이면 모두 적용할 수 있다. Medium이 여러개의 station사이에 있고 동시에 data를 받게 된다면, potential collisions이 발생하여 data는 충돌하고 망가질 것이다. CSMA collision을 최소화하기 위해, CSMA가 개발되었다. Carrier sense multiple access(CSMA)는 medium의 상태를 사용하기 전에 확인해야 한다. Access modes 다양한 CSMA가 다른 알고리즘을 shared medium에 전송을 시작할 때를 결정하기 위..

DLC Services Data link control(DLC)는 인접한 node들 간의 통신 절차이다. Data link control은 framing, flow 그리고 error control이 있다. Framing Data-link layer는 각각의 frame이 다른 frame과 구분이 될 수 있도록 frame에 bit를 넣어야한다. Data-link layer에서 Framing은 보내는 이와 목적지의 주소를 더하므로써 한 source에서 메시지를 분리해 낸다. 목적지 주소는 packet이 어디로 갈지 정의한다. 보내는 이의 주소는 recipient가 receipt를 acknowlege하게 도와준다. Flow and Error Control Data-link control sublayer의 한가지..

Divide : pivot element를 선택하고, pivot을 기준으로 subarray를 나누기 때문에 시간복잡도는 O(n)이다. Conquer : subarray를 recursive하게 정렬해준다. tree의 깊이에 비례하므로 시간복잡도는 O(logn)이고 subarray의 크기를 m1과 m2라고 했을 때, conquer의 비용은 T(m1)+T(m2)가 된다. combine : 할 필요가 없다.(O(1) or 0) void quick_sort(int *n, int left, int right){ int pivot; if(right-left>0){ //divide pivot=partition(n,left,right); //conquer quick_sort(n,left,pivot-1); quick_so..