Computer Science

1. Paging Paging이란 프로그램을 일정한 크기의 페이지 단위로 나눠서 실제 메모리에 불연속적으로 할당하는 방법을 말한다. 페이지는 4KB, 8KB, 16KB, 32KB 등으로 설정되지만 일반적으로는 페이즈의 크기를 4KB로 사용한다. 이 글에서도 4KB로 생각하면 된다. 페이지 크기가 줄어들수록 내부 조각이 적어지지만 페이지 테이블의 크기가 증가하고 반대로 페이지 크기가 크면, 내부 조각이 많이 생기지만 페이지 테이블의 크기는 줄어든다. 여기서 페이지(Page)와 프레임(Frame) 두 가지 용어를 먼저 알고 가자. 페이지(Page) : 논리적인 메모리(프로세스의 가상 주소)를 일정한 크기로 나눈 것 프레임(Frame) : 실제 물리적인 메모리(RAM)를 일정한 크기로 나눈 것 페이지는 가상 ..

Contiguous allocation 1. 고정 분할 방식 이름 그대로 메모리를 분할해놓고, 프로그램이 분할된 메모리의 크기와 맞으면 할당하고 크기가 안맞으면 크기가 맞는곳에 할당을 하는 방식이다. 프로그램 A를 보면 분할 1의 크기에 맞기 때문에 할당할 수 있다. 하지만 프로그램 B를 보면 분할 2의 사이즈보다 크다. 그렇기 때문에 분할 2를 건너뛰고 프로그램A와 크기가 맞는 분할 3 메모리에 할당되게 된다. 이때 분할2번은 건너 뛰게 되는데 이를 "외부 조각"이라고 부른다. 분할 3 내부에서도 프로그램 B가 분할 3메모리를 다 채우지 못했는데, 채우지 못한 부분을 "내부 조각"이라고 부른다 보면 알겠지만 상당히 비효율적이고, 내부 조각, 외부 조각이 발생할 수 있다. 2. 가변 분할 방식 가변 분할..

1. Address Binding? 하나의 프로그램이 실행되기 위해서는 프로그램 코드가 어셈블리어로 컴파일되고, 어셈블리어가 기계어로 변환되어 프로세스가 만들어져 메인 메모리에 적재되면 해당 프로세스의 명령어들은 Physical address를 가지게 된다. CPU가 메인 메모리에 적재된 프로세스 명령어를 실행하기 위해서는 Logical address를 알아야 하기 때문에 Physical address에 매핑된 Logical address를 알아내서 프로세스를 처리한다. 이때 Logical address와 Physical address를 매핑하는 과정이 바로 Address Binding이다. Symbolic address VSLogical address VS Physical address Symbolic..

1. Deadlock이란? 두개 이상의 프로세스나 스레드가 서로의 작업이 끝나기만을 기다리며 무한정 대기하며 자원을 얻지 못하는 상태. 2. Deadlock 해결 방법 Deadlock을 해결하는 방법은 간단히 아래와 같이 요약해볼 수 있다. 1. Deadlock 예방 : Deadlock이 발생하기 이전에 데드락 발생원인 중 하나를 제거함으로써 Deadlock을 예방하는 방법 2. Deadlock 회피 : 각 프로세스가 프로세스를 실행하는데 필요한 정보를 추가적으로 받아서 Deadlock을 일으키지않는다고 판단되면 자원을 할당해주는 방법 3. Deadlock 탐지 : 교착 상태가 발생했을 때마다 복구 기법을 활용하여 시스템을 회복시키는 방법. 4. Deadlock 무시 : 그냥 데드락이 일어날 때 까지 방..

1. Atomic이란? Atomic의 Atom은 원자라는 뜻이며, 원자란 물질을 구성하는 더 이상 쪼개질 수 없는 가장 작은 단위를 말한다. 프로그래밍에서의 Atomic한 실행이란 어떤 연산이 분할되지 않고 한번의 연산으로 실행되는 것을 의미한다. 설명에 앞서 이 글에서는 프로세스, 스레드를 합쳐서 프로세스 라고만 지칭할 것이다. 가장 대표적으로 Atomic한 연산이 필요한 곳은 Critical Section에 대한 연산이다. 멀티 프로세스 환경에서 여러개의 프로세스가 임계영역에 있는 임의의 count라는 데이터에 접근해서 연산을 할 때 프로그래밍 언어에서는 단지 count++;한줄로 끝나지만 코드가 컴파일 되면 기계어로 번역되어 아래와 같이 약 3단계로 구분된다. count = 1이라고 가정// mov..

트리의 순회 방법에 대해 알아보기에 앞서 트리에 대한 기본적인 배경지식은 아래의 포스팅을 참고하면 좋을 것 같다. https://go2gym365.tistory.com/274 [자료구조] Tree & Binary Tree 1. Tree / 트리 한개 이상의 노드로 이루어진 유한 집합이며, 비선형 자료구조이다. 하나의 루트 노드 아래에 0개 이상의 자식 노드로 구성된다. 그리고 그 자식 또한 0개 이상의 자식 노드를 가지 go2gym365.tistory.com 1. 전위 순회 / PreOrder 순회 순서 : [ 루트 노드(부모 노드) > 왼쪽 노드 > 오른쪽 노드] 순서로 방문한다. 위의 그림에서 전위 순회한 결과 : [1 > 2 > 4 > 8 > 5 > 3 > 6 > 7 ] 2. 중위 순회 / InOr..

트리에 대한 기본적인 배경지식은 아래의 포스팅을 참고하면 좋을 것 같다. https://go2gym365.tistory.com/274 [자료구조] Tree & Binary Tree 1. Tree / 트리 한개 이상의 노드로 이루어진 유한 집합이며, 비선형 자료구조이다. 하나의 루트 노드 아래에 0개 이상의 자식 노드로 구성된다. 그리고 그 자식 또한 0개 이상의 자식 노드를 가지 go2gym365.tistory.com 1. Node 구조체 노드는 값과 자식 노드로 left, right노드를 가지고 있다. struct Node { int data; Node* left; Node* right; Node() { left = nullptr; right = nullptr; } }; 2. Binary Tree Cl..

1. Tree / 트리 한개 이상의 노드로 이루어진 유한 집합이며, 비선형 자료구조이다. 하나의 루트 노드 아래에 0개 이상의 자식 노드로 구성된다. 그리고 그 자식 또한 0개 이상의 자식 노드를 가지고있고 무한히 반복가능하다. 컴퓨터의 디렉터리 구조가 대표적인 트리 구조로 이루어져 있다! 1-2. Tree 용어 루트 노드(root node) : 부모가 없는 노드. 트리에는 오직 하나의 루트 노드만이 존재한다. 리프 노드, 단말 노드(leaf node, terminal node) : 자식이 없는 최말단 노드 내부 노드, 비단말 노드(internal node, nonterminal node) : 단말 노드를 제외한 나머지 노드 가지, 링크(branch, link, edge) : 노드와 노드를 연결하는 선...

1. 동기화 문제란? 여러 프로세스 또는 여러 스레드가 동시에 실행될 때 발생하는 데이터 일관성 문제를 동기화 문제라고 한다. 대표적으로 공유 메모리에 여러 스레드가 동시에 접근해서 값을 변경할 때 연산 결과 출력이 예상치 못한 값으로 나오는 공유 메모리 동기화 문제(Race condition)를 대표적인 동기화 문제로 볼 수 있다. 2. Race Condition / 경쟁 상태 여러개의 프로세스 또는 스레드가 하나의 공유 자원에 동시에 접근할 때 생기는 문제를 말한다. 아래 코드를 보면 스레드 두개를 선언하고 전역으로 선언한 sum이라는 변수에 스레드 두개가 동시에 접근하여 sum이라는 전역 변수에 값을 1씩 증가시키는 코드이다. 뇌버깅을 돌려보면 두개의 스레드에서 1씩 30000번씩 증가시키기 때문에..

1. Quick sort 분할 정복 테크닉을 사용한 매우 빠른 시간 복잡도를 가진 정렬 알고리즘이다. 정렬 로직 수행 간 초기 정렬 상태를 보장하지 않는 불안정 정렬이다. 추가 메모리 공간을 필요로 하지 않는다. 시간 복잡도 : O(NlogN) Quick sort의 로직 동작 과정 주어진 배열의 범위 내에서 하나의 값(Pivot)을 기준으로 정하고, pivot 왼쪽에는 pivot보다 작은 값들이 오른쪽에는 pivot보다 큰 값들이 오도록 정렬한다. pivot을 기준으로 나뉜 배열은 정렬된 순서는 보장하지 않기 때문에 각각 배열에서 새로운 pivot을 설정하여 다시 분할해서 재귀 호출 한다. 1,2번의 과정을 배열을 분할할 수 없을 때 까지 반복한다. Quick sort 장/단점 장점 - pivot과 거리..