💻CS

    [Network] 네트워크 계층 6

    앞선 글에서 봤던 count-to-infinity를 해결하는 방법 중의 하나로는 poisoned reverse라는게 있다. 라우팅 정보를 되돌려 주기는 하되, 기존의 정보가 아니라 무한대의 값으로 전달해주어 경로가 사용될 수 없다고 인식하도록 만들어준다. 즉, 경로를 역행하여 값들이 수시로 변경되던 예시를 방지할 수 있다. Hierarchical Routing 네트워크의 스케일이 큰 경우는 계층화(hierarchical routing)를 시킨다. 이전 글 들에서 link state, distance vector 알고리즘들을 통해 라우터들을 연결시켰었다. 이 때 잠시 말했었던 부분이 있는데, 바로 하나의 네트워크 내부에서만 이러한 알고리즘을 쓰고 외부 네트워크들을 연결하는데에는 다른 알고리즘을 사용한다고 ..

    [OS] 12. Process Synchronization and Mutual Exclusion 5

    그 유명한 세마포어(Semaphore)에 대해 알아봅시다. Semaphore 다익스트라씨가 또 만듬...(대단하신 분,,) 가장 핵심은 이전에 고질적인 문제였던 busy waiting 문제 해결했다는 것! 음이 아닌 정수형 변수(S)를 사용하며 spinlock과 동일하게 초기화 연산, P(검사), V(증가)연산으로만 접근이 가능하다. 하지만 spinlock과 다른 점이 있다! 세마포어는 임의의 S 변수 하나에 ready queue 하나를 할당한다는 것이 큰 차이이다. 우선 세마포어는 두 가지로 구분할 수 있다. Binary semaphore S가 0 혹은 1의 값만 가지는 경우 상호배제(Mutual Exclusion)나 프로세스 동기화를 목적으로 사용 Counting semaphore S가 0이상의 정수..

    [Network] 네트워크 계층 5

    지난번에 이어서 distance vector 알고리즘에 대해 알아볼 것이다. 이전 글에서 봤듯이, 본인과 인접한 부분에 대한 정보만 알고, 나머지 정보들은 이웃에 의해 전달받아야 한다. 그렇기 때문에 Distance vector 알고리즘의 핵심은 이웃에게 정보를 받아 이를 기반으로 정보를 업데이트한다는 것이 된다. 이러한 구조에서, x로부터 z로의 최단 경로를 구하기 위해서는 min(C(x,y) + Dy(z), C(x,z) + Dz(z))의 식으로 값을 구해낼 수 있다. y를 거쳐서 가는 경우 z로 바로 가는 경우 이 두 가지 경우 중 최소값을 가지는 경우를 선택하여 정보를 업데이트 해주는 것이다. 이러한 계산 과정이 반복되며 정보는 계속 업데이트 되고 더 이상 값이 바뀌지 않는(stable)한 상태가 ..

    [OS] 11. Process Synchronization and Mutual Exclusion 4

    SW와 HW적인 여러 해결책들이 등장함에도 Busy waiting 문제가 해결되지 않았던 것을 볼 수 있다. 이제는 OS차원에서의 해결방법을 살펴보자. 먼저 스핀락(spinlock)에 대해 먼저 알아보자. 스핀락은 정수형 변수로서 초기화, P(), V() 연산으로만 접근 가능하다. 이러한 연산들은 atomic한 연산이며 OS에서 preemption이 발생하지 않도록 보장해준다. swift 코드로 한 번 봐보자. (임의로 짬..!) // P 연산 - S라는 물건을 계속 빼내는 것 func P(S: inout Int) { while S

    [OS] 10. Process Synchronization and Mutual Exclusion 3

    이번엔 하드웨어 쪽에서의 해결책을 살펴보자. Synchronization Hardware TestAndSet(TAS) instruction test와 set을 한 번에 수행하는 기계어이다. Machine instruction (한 번에 수행됨) 실행 중에 interrupt를 받지 않는다 (preemption 안됨!) 여기서 TAS는 값을 반환하고, 값을 바꿔준다. swift로는 약간 이런 느낌..? func TAS(_ target: inout Bool) -> Bool { var temp = target // 이전 값 기록 target = true // 값 변경 return temp // 값 반환 } 즉 초기에는 lock이 false여서 while문을 패스하는데, 이 때 TAS(lock)이 false를 뱉..

    [Network] 네트워크 계층 4

    이전에 포워딩 테이블은 라우팅 알고리즘에 의해서 만들어진다고 했었다. 이번 강의에서는 라우팅 알고리즘에 대해서 알아볼 것이다. Routing Algorithms 라우터의 주 역할 중 하나는 포워딩이었다. 포워딩이라는 것은 패킷 내 헤더의 목적지 정보를 보고 포워딩 테이블내 가장 적합한 엔트리와 매칭해서 연결시켜주는 것이다. 즉 A를 B로 보내기 위해 중간에 거쳐야하는 관문 정도로 보면 될 것 같다. 이제는 네트워크를 그림으로만 보지 않고 노드와 간선으로 이루어진 네트워크 그래프로 볼 것이다. 노드는 라우터고, 간선은 링크라고 보면 된다. 이 네트워크 그래프를 보는 이유가 뭘까?? 바로 앞서 말했듯이 포워딩 테이블을 만들기 위해서이다. 어? 그럼 포워딩 테이블의 엔트리는 어떻게 구성해야 좋은거지?? 예를 ..