본문 바로가기

Computer Science108

[Computer Networking] Network Layer : Packet Switching, Loss and Delay Packet Switching- Store-and-forward  대부분의 패킷 스위치(라우터 등)은 저장-후-전달 전송 방식을 이용한다.  저장-후-전달은 스위치가 출력 링크로 패킷의 첫 비트를 전송하기 전에 전체 패킷을 받아야 함을 의미한다.   그림에서 라우터는 패킷1의 일부분을 받았지만 라우터는 저장-후-전달을 채택하고 있기 때문에 수신한 비트를 전송할 수 없다. 대신에 그 패킷의 비트를 먼저 버퍼에 저장한 후 라우터가 패킷의 모든 비트를 수신한 후에만 출력 링크로 그 패킷을 전달하기 시작한다. - Packet Queueing  각 링크에 대해 패킷 스위치(라우터 등)은 출력 버퍼(큐)를 갖고 있으며 그 링크로 송신하려고 하는 패킷을 저장하고 있다.  도착하는 패킷이 한 링크로 전송되어야 하는데 .. 2024. 8. 15.
[Data Structures] Hash Table (해시 테이블) HashingHashing은 데이터의 삽입, 삭제, 조회를 상수 시간에 수행하기 위해 사용되는 기술이다. Hash TableHash Table은 Key와 Value를 포함하는 고정된 길이의 배열이다. Hash FunctionHash function은 각각의 Key를 Hash Table의 특정 셀에 맵핑한다. 이는 가능한 계산하기 간단해야 하며, Collision(충돌, 후술 할 것)을 최소화 하도록 설계되는 것이 좋다. 또한 Hash Function의 값은 Uniform한 분포를 따라야 한다. Implementation of Simple Hash Table주민번호가 key이고 주민 객체가 value인 간단한 Hash Table을 구현할 것이다.다음은 Person의 ADT와 구현체이다.#define STR.. 2024. 8. 15.
[Computer Networking] Transport Layer : TCP (3) (Transmission Control Protocol) Congestion  한 라우터에 데이터가 몰릴 경우, 자신에게 온 데이터를 모두 처리할 수 없게 된다. 이런 경우 호스트들은 또 다시 재전송을 하게 되고 결국 혼잡만 가중시켜 오버플로우나 데이터 손실을 발생시키게 된다. 이러한 상황을 피하기 위해 송신촉에서 보내는 데이터의 전송 속도를 강제로 줄이게 되는데, 이러한 작업을 혼잡 제어라고 한다. TCP Congestion Control : AIMDAdditive Increase : 패킷 손실이 일어나기 전까지 전송률을 증가시킨다.Multiplicative Decrease : 패킷 손실이 일어난다면 전송률을 반으로 깎는다.   혼잡 제어는 cwnd로 표시되는 혼잡 윈도우(Congestion Window)를 추적한다. 이는 TCP 송신자가 네트워크로 트래픽을.. 2024. 8. 14.
[Operating System] Memory Management (1) (메모리 관리) Binding of Instructions and Data to Memory- Compile time Binding : 프로세스가 메모리 내에 들어갈 위치를 컴파일 타임에 미리 알 수 있다면 컴파일러는 절대 주소를 포함하는 절대 코드를 생성할 수 있다. 그러나 만일 이 위치가 변경되어야 한다면 이 코드는 다시 컴파일 되어야 한다. - Load time Binding : 프로세스가 메모리 내 어디로 올라오게 될지를 컴파일 시점에 알지 못하면 컴파일러는 일단 이진 코드를 상대 주소를 포함하는 재배치 가능 코드(Relocatable code)로 만들어야 한다. 이렇게 만들어진 재배치 가능 코드는 시작 주소가 변경되면 아무 때나 사용자 코드를 다시 적재하기만 하면 된다. - Execution time Bindi.. 2024. 8. 12.
[Computer Algorithms] LCS (Longest Common Subsequence, 최장 공통 부분 수열) LCS (Longest Common Subsequence)  두 수열 또는 문자열이 주어졌을 때, 가장 긴 공통 부분 수열(문자열)을 구하는 알고리즘이다.  이 알고리즘은 2차원 DP로 구현할 수 있는데, DP[i][j]는 첫 번째 수열의 i번째, 두 번째 수열의 j번째 원소까지의 LCS의 길이이다.  DP 테이블은  DP[i + 1][j + 1] = max({dp[i][j + 1], dp[i + 1][j], dp[i][j] + (A[i] == B[j])})로 갱신할 수 있다.- DP[i + 1][j + 1] = DP[i][j + 1] : 첫 번째 문자열을 i + 1개로 늘려도 늘리기 전과 LCS의 길이가 차이가 나지 않을 때- DP[i + 1][j + 1] = DP[i + 1][j] : 두 번째 문자열.. 2024. 8. 11.
[Data Structures] Graph (그래프) Graph그래프란 노드와 간선으로 이루어진 자료구조이다.노드 : 각 점을 나타낸다. 노드는 때로 정점이라고도 불린다.간선 : 노드들 사이를 연결하는 선을 의미한다. 두 노드를 연결하는 관계를 나타낸다. 그래프는 크게 두 유형으로 나눌 수 있다.1. 방향 그래프(Directed Graph) : 간선에 방향이 있는 그래프2. 무방향 그래프(Undirected Graph) : 간산에 방향이 없는 그래프 Directed Graph방향 그래프에서 간선 {u, v}가 있다고 하자.노드 u는 v를 향하지만 v는 u를 향하지 않는다. - in-degree : 노드로 들어오는 화살표의 개수- out-degree : 노드에서 나가는 화살표의 개수- 방향 그래프에서 in-degree의 합과 out-degree의 합은 같고 .. 2024. 8. 10.
[Computer Networking] Transport Layer : TCP (2) (Transmission Control Protocol) TCP flow control (흐름 제어)- 애플리케이션 계층에서 TCP 소켓 수신 버퍼에서 데이터를 읽는 속도가 데이터가 도착하는 것보다 비교적 느리다면, 송신자가 점점 더 많은 데이터를 빠르게 전송함으로 수신 버퍼에 오버플로가 발생할 것이다.- 이처럼 TCP는 송신자가 수신자의 버퍼를 오버플로시키는 것을 방지하기 위해 애플리케이션에게 흐름 제어 서비스를 제공한다. 흐름 제어는 송신자가 보내는 속도와 수신자가 읽는 속도를 일치시키는 서비스다.- TCP는 송신자가 수신 윈도우라는 변수를 유지하여 흐름제어를 제공한다. 수신 윈도우는 수신 측에서 가용한 버퍼 공간이 얼마나 되는지를 송신자에게 알려주는 데 사용된다. TCP는 전이중(full-duplex)이므로 연결의 각 측의 송신자는 별개의 수신 윈도우를 .. 2024. 8. 9.
[Operating System] Deadlocks (교착 상태) Deadlock  두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태로 무한히 다음 자원을 기다리게 되는 상태를 말한다. 데드락의 발생 조건다음 4가지가 모두 성립해야 데드락이 발생한다. 1. Mutual Exclusion : 자원은 한번에 한 프로세스만 사용할 수 있다.2. No Preemption : 다른 프로세스에 할당된 자원은 사용이 끝날 때 까지 강제로 빼앗을 수 없다.3. Hold and Wait : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 한다.4. Circular Wait : 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 한다. Resource-All.. 2024. 8. 7.
[Computer Architecture] Cache Memory (캐시 메모리) Principle of Locality  큰 메모리에서 대부분의 메모리 접근을 빠르게 하는 것은 불가능하다. 프로그램이 어떤 특정 시간에 주소 공간 내의 비교적 작은 부분만을 접근한다는 것이 지역성의 원칙이다.- Temporal Locality (시간적 지역성) : 한번 참조된 항목은 곧바로 다시 참조되는 경향이 있다.- Spatial Locality (공간적 지역성) : 어떤 항목이 참조되면 그 근처에 있는 다른 항목들이 곧바로 참조될 가능성이 높다. Memory Hierarchy- 컴퓨터의 메모리를 메모리 계층구조로 구현함으로써 지역성의 원칙을 이용할 수 있다. 이는 서로 다른 속도와 크기를 갖는 여러 계층의 메모리로 구성되어 있다.- 가장 빠른 메모리는 더 느린 메모리보다 비트당 가격이 비싸기 때문.. 2024. 8. 6.
[Data Structures] Heap (힙) Priority Queue (우선순위 큐)  우선순위 큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료 구조이다. 우선 순위 큐는 배열이나 연결 리스트로 구현할 수 있지만 데이터의 수가 많아지면 노드의 수에 비례해서 성능이 저하되기 때문에 가장 좋은 성능을 이끌어 내기 위한 힙이라는 자료구조를 사용한다. Heap (힙)  힙은 완전 이진 트리이다. Max Heap(최대 힙)은 모든 노드에 저장된 값이 자식 노드에 저장된 값보다 크거나 같고, Min Heap(최소 힙)은 모든 노드에 저장된 값이 자식 노드에 저장된 값보다 작거나 같다. - 이진 힙의 구조   힙은 완전 이진 트리 이기 때문에 원소가 배열에 저장된다. - Insertion  원소를 삽입할 때에는 트리 마지막에 삽입을 .. 2024. 8. 6.
[Computer Networking] Transport Layer : TCP (1) (Transmission Control Protocol) TCP (Transmission Control Protocol)- TCP는 애플리케이션 프로세스가 데이터를 다른 프로세스에게 보내기 전에, 두 프로세스가 서로 '핸드셰이크'를 먼저 해야 하므로 연결지향형이다.- TCP 연결은 전이중 서비스를 제공한다. 만약 호스트 A의 프로세스와 호스트 B의 프로세스 사이에 TCP 연결이 있다면, 애플리케이션 계층 데이터는 B에서 A로 흐르는 동시에 A에서 B로 흐를 수 있다.- TCP 연결은 항상 단일 송신자와 단일 수신자 사이의 점대점이다. 단일 송신 동작으로 한 송신자가 여러 수신자에게 데이터를 전송하는 멀티캐스팅은 TCP에서 불가능하다. TCP Segment Structure- UDP 처럼 헤더는 상위 계층 애플리케이션으로부터 다중화와 역다중화를 하는 데 사용하는.. 2024. 8. 4.
[Computer Algorithms] LIS (Longest Increasing Subsequence, 최장 증가 부분 수열) LIS (Longest Increasing Subsequence)말 그대로 가장 긴 증가하는 부분 수열이다. 수열에서 LIS를 구하는 방법은 두 가지가 있다.1. DP를 이용한 방법 -> 시간 복잡도 O(N^2)2. 이분 탐색을 이용한 방법 -> 시간 복잡도 O(N * logN) Finding LIS using DP- LIS의 길이 구하기 (DP)문제 링크 : https://www.acmicpc.net/problem/11053#include #include #include #include #include #include #define endl '\n'using namespace std;int N;vector A, DP;int maxVal = 0;void input(){ cin >> N; A.r.. 2024. 8. 3.
[Computer Architecture] Pipelining and Hazards (파이프라이닝과 해저드) Pipelining여러 명령어가 중첩되어 실행되는 구현 기술 Five Stages of Instruction- IF : 메모리에서 인스트럭션 패치 - ID : 인스트럭션 해독 및 레지스터 읽기 - EX : 연산 수행 및 주소 계산 - MEM : 메모리 읽기/쓰기 - WB : 레지스터에 쓰기 Hazards다음 사이클에 실행되어야 할 인스트럭션이 실행될 수 없는 상황을 Hazard라고 한다. - Structure Hazards : 같은 클럭 사이클에 실행하기를 원하는 명령어의 조합을 하드웨어가 지원할 수 없기 때문에 발생 ex) IF와 MEM - Data Hazards : 어떤 단계가 다른 단계가 끝나기를 기다려야 하기 때문에 파이프라인이 지연되어야 하는 경우 발생 - Control Hazards : 다른 .. 2024. 8. 1.
[Data Structures] AVL Tree (AVL 트리) AVL Tree일반적인 이진탐색 트리의 경우 노드가 한 방향으로 쏠릴 경우 연결리스트와 동일해져 이진 탐색 트리의 장점을 잃게 된다. 이를 개선하기 위해 트리의 균형을 유지하는 트리가 AVL 트리이다. Balance FactorAVL 트리에서는 균형의 정도를 표현하기 위해 Balance Factor라는 것을 사용하는데 이는 왼쪽 서브 트리와 오른쪽 서브 트리의 height의 차이로 계산된다.  LL 회전Balance Factor가 2인 노드가 있을 때, 그 노드의 왼쪽 자식 노드의 왼쪽 서브트리에 노드가 추가된 경우를 LL 상태라고 한다. 이러한 경우에는 LL 회전을 통해 트리의 균형을 맞춘다.LL 회전을 일반화 하면 다음과 같다.서브 트리 x 왼쪽에 노드가 추가된다면 LL회전을 수행하게 된다. 이때 k.. 2024. 7. 31.
[Computer Networking] Transport Layer : UDP (User Datagram Protocol) UDP (User Datagram Protocol)  UDP는 트랜스포트 계층 프로토콜이 할 수 있는 최소 기능으로 동작한다.- 다중화/역다중화 기능과 간단한 오류 검사 기능을 제외하면 IP에 아무것도 추가하지 않는다.- 애플리케이션 프로세스로부터 메시지를 가져와서 다중화/역다중화 서비스에 대한 출발지 포트 번호 필드와 목적지 포트 번호 필드를 첨부하고 다른 두 필드를 추가할 후에 최종 세그먼트를 네트워크 계층으로 넘겨준다.- 세그먼트가 수신 호스트에 도착하면, UDP는 세그먼트의 데이터를 해당하는 애플리케이션 프로세스로 전달하기 위해 목적지 포트 번호를 사용한다.- UDP는 세그먼트를 송신하기 전에 송신 트랜스포트 계층 개체들과 수신 트랜스포트 계층 개체들 사이에 핸드셰이크를 사용하지 않는다. 이런 이.. 2024. 7. 31.

티스토리툴바