Process vs. Thread 프로세스 (Process) 실행 중인 프로그램으로, 디스크로부터 메모리에 적재되어 운영체제로부터 주소 공간, 파일, 메모리 등을 할당 받음 함수의 매개변수, 복귀 주소, 로컬 변수와 같은 임시 자료를 저장하는 프로세스 스택과 전역 변수들을 저장하는 데이터 섹션, 프로세스 실행 중에 동적으로 할당되는 메모리인 힙을 포함 특정 프로세스에 대한 중요한 정보를 저장하고 있는 운영체제의 자료구조를 PCB(Process Control Block)라고 하며, 운영체제는 프로세스의 생성과 동시에 고유한 PCB를 생성하여 프로세스를 관리 스레드 (Thread) 프로세스의 실행 단위. 한 프로세스 내에서 동작되는 여러 실행 흐름으로 프로세스 내의 Heap, Data, Code 영역을 공유..

Segment Tree 배열 A[1], ..., A[N]이 있을 때, 아래 문제를 생각해보자. [문제 1] 순서쌍 (i, j)에 대하여 A[i], ... ,A[j] 중 최솟값을 찾는 경우를 생각해보자. A[i]부터 A[j]까지 순회하면서 찾는 것이 가장 단순한 방법일 것이다. 이 경우 시간 복잡도는 O(N)이 된다. 그러나 이러한 연산이 Q개 주어지고 N과 Q의 범위가 1부터 10만이라면, 시간 복잡도가 O(NQ)이므로 오랜 시간이 걸릴 것이다. [문제 2] 구간 [l, r] (l ≤ r)이 주어진다. (1) A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력한 뒤, (2) i번째 수를 v로 바꾼다. 이 과정을 M번 반복한다. (1)번 과정은 O(N), (2)번 과정은 O(1)..

CPU Scheduling CPU를 사용하려고 하는 프로세스들 사이의 우선순위를 관리하는 작업 - 자원을 어떤 프로세스에 얼마나 할당하는지 정책을 만드는 것 프로세스들에게 자원을 최대한 공평하게 배분하며 처리율과 CPU 이용률을 증가시키고, 오버헤드, 응답시간(Response time / Turnaround time), 대기시간을 최소화하기 위한 기법 선점형 스케줄링(Preemptive Scheduling) 과 비선점형 스케줄링(Non-preemptive / Cooperative Scheduling) 이 있음 메모리에 여러 개의 프로세스를 올려놓고(다중 프로그래밍), CPU의 가동시간을 적절히 나누어(시분할) 각각의 프로세스에게 분배하여 실행 [참고] 스케줄러의 종류와 특징 종류 특징 장기 스케줄러 (L..

Deadlock '교착 상태'라고도 하며, 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생 데드락이 발생할 수 있는 경우: Process 1과 Process2가 Resource 1, 2를 둘 다 얻어야 한다고 가정할 때, 서로 원하는 Resource가 상대 Process에게 할당되어 있기 때문에 두 프로세스가 무한정 기다리게 된다. 교착 상태의 조건 한 시스템 내에서 다음의 네 가지 조건이 동시에 성립할 때 발생 따라서, 아래의 네 가지 조건 중 하나라도 성립하지 않도록 만든다면 교착 상태 해결 가능 조건 설명 상호 배제 (Mutual exclusion) - 자원은 한 번에..

Union-find? 그래프 알고리즘의 일종으로써, 상호 배타적 집합(Disjoint Set)이라고도 한다. 여러 노드가 존재할 때, 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다. 아래의 2가지 연산으로 이루어져 있다. Find: 노드 x가 어떤 집합에 포함되어 있는지 찾는 연산 Union: 노드 x와 노드 y가 포함되어 있는 집합을 합치는 연산 Union-find는 크루스칼 알고리즘에서 원소 간의 연결 여부를 판단하는 데에 사용한다. 구현 구현은 트리를 이용하며, parent[i]를 노드 i의 부모 노드라고 정의하고 초기화를 해준다. 이 때, parent[i] = i일 경우, 루트 노드임을 의미한다. int parent[MAX_SIZE];..