전체 글
자료구조 · C++로 구현한 덱
덱 (Deque) 덱은 Double-Ended Queue의 약자이며, 양쪽에서 원소의 삽입과 삭제가 가능한 선형 자료구조이다.큐와 스택을 합친 형태라고 생각하면 된다. 원형 큐(Circular Queue)와 비슷하게 구현하므로, 이전 글을 참조. 한쪽에 push 하고 같은 쪽에서 pop 하면, 스택처럼 사용할 수 있다.한쪽에 push 하고 반대쪽에서 pop 하면, 큐처럼 사용할 수 있다. Deque C++ 구현 소스코드 #include using namespace std; const int MAX = 1e5; class Deque { private: int data[MAX]; int index_front; int index_back; public: Deque(); bool empty(); void pus..
자료구조 · C++로 구현한 스택
스택 (Stack) 스택은 후입선출(LIFO; Last in First out) 방식의 선형 자료구조이다.후입선출이란, 나중에 들어간 것이 먼저 나온다는 뜻이다. 즉, 스택은 나중에 들어간 데이터를 먼저 처리하는 자료구조이다. Stack C++ 구현 소스코드 #include using namespace std; const int MAX = 1e5; class Stack { private: int data[MAX]; int index; public: Stack(); bool empty(); void push(int x); void pop(); int top(); int size(); }; Stack::Stack() { index = -1; } bool Stack::empty() { return index ..
자료구조 · C++로 구현한 큐
큐 (Queue) 큐는 선입선출(FIFO; First in First out) 방식의 선형 자료구조이다. 선입선출이란, 먼저 들어간 것이 먼저 나온다는 뜻이다. 즉, 큐는 먼저 들어간 데이터를 먼저 처리하는 자료구조이다. Queue C++ 구현 소스코드 #include using namespace std; const int MAX = 1e5; class Queue { private: int data[MAX]; int index_front; int index_back; public: Queue(); bool empty(); void push(int x); void pop(); int front(); int back(); int size(); }; Queue::Queue() { index_front = 0;..
운영체제 · 교착상태 (데드락)
교착상태 (Deadlock) 운영체제(또는 소프트웨어)에서 자원을 사용할 때, 두 개 이상의 작업이 순차적으로 상대방의 작업이 끝나기를 기다리면서, 아무것도 진행되지 않는 상태를 말한다. 교착상태 발생 조건 ✓ 교착상태는 다음 네 가지 조건이 모두 성립될 때 발생한다.상호 배제 (Mutual exclusion) : 한 번에 하나의 프로세스만 공유 자원을 사용할 수 있다.점유 대기 (Hold and wait) : 각 프로세스가 하나의 자원을 점유하고 있으면서, 다른 프로세스가 사용하고 있는 자원을 추가로 점유하기 위해 대기한다.비선점 (No preemption) : 각 프로세스는 다른 프로세스가 사용하고 있는 자원을 강제로 빼앗을 수 없다.순환 대기 (Circular wait) : 각 프로세스는 순환적으로..
운영체제 · 스핀락
스핀락 (Spinlock) ✓ 정의 : 임계 구역에 진입이 불가능할 때, 진입 가능할 때까지 루프를 돌면서 진입을 재시도하는 방식으로 구현된 락✓ 임계 구역에 진입하기 위해서는 락(Lock)이 필요하기 때문에, 락을 획득할 때까지 해당 프로세스(스레드)가 돌고 있다(Spin)는 것을 의미한다.✓ 스핀락은 바쁜 대기(Busy waiting)의 한 종류이다.✓ 스핀락은 운영체제의 스케줄링을 지원받지 않기 때문에, 해당 프로세스(스레드)에 대한 Context switch가 일어나지 않는다. ✓ 장점 : 임계 구역 진입을 짧은 시간 내에 할 수 있다면, Context switch를 하지 않아도 되므로 효율적이다.✓ 단점 : 오랜 시간 동안 스핀락을 진행하고 있다면, 스레드의 대기 시간이 길어지므로 비효율적이다...
운영체제 · 세마포어, 뮤텍스
세마포어와 뮤텍스의 차이점 ✓ 세마포어 : Signaling mechanism / 일종의 카운터로서 크리티컬 섹션에 프로세스(스레드)가 동시에 N개 접근할 수 있다. 카운터 값이 0과 1로만 제한되면 Binary semaphore이며, 그 이상의 값을 가지면 Counting semaphore이다.✓ 뮤텍스 : Locking mechanism / 락(Lock)을 가진 하나의 프로세스(스레드)만 크리티컬 섹션에 접근할 수 있다. Binary semaphore로 구현될 수 있다. 세마포어 (Semaphore) ✓ 각 프로세스에 제어 신호를 전달하여 순서대로 작업을 수행하도록 하는 동기화 기법이다.✓ 세마포어 S는 P와 V 연산으로만 접근 가능한 카운터 변수이며, 0 이상의 값을 가질 수 있다.✓ S의 값이 0..
운영체제 · 프로세스 동기화
프로세스 동기화 (Process Synchronization) ✓ 정의 : 협력하는 프로세스 사이에서 실행 순서 규칙을 정하여 공유 자원의 일관성을 보장하는 것✓ 프로세스가 서로 협력하며 공유 자원을 사용하는 상황에서, 경쟁 조건이 발생하면 공유 자원을 신뢰할 수 없게 만들 수 있다. 이를 방지하기 위해 프로세스들이 공유 자원을 사용할 때 특별한 규칙을 만드는 것이 프로세스 동기화이다. ✓ 경쟁 조건 (Race Condition) : 여러 프로세스(또는 스레드)가 공유 자원에 동시에 접근할 때, 공유 자원에 대한 접근 순서에 따라 실행 결과가 달라질 수 있는 상황✓ 임계 구역 (Critical Section) : 여러 프로세스(또는 스레드)가 자원을 공유하는 상황에서, 하나의 프로세스(스레드)만 접근할 ..
운영체제 · CPU 스케줄링
CPU 스케줄링 (CPU Scheduling, Processor Scheduling) ✓ 정의 : CPU(프로세서)를 사용하려 하는 프로세스들 사이에서 우선순위를 관리하는 일✓ 작업 처리율과 CPU 이용률을 향상시키기 위해 필요한 기법이다.✓ 비선점 스케줄링과 선점 스케줄링으로 나뉜다. 비선점 스케줄링 (Non-preemptive Scheduling) ✓ 정의 : 어떤 프로세스가 사용 중인 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링✓ 일괄 처리 시스템에 적합하며, 응답 시간 예측이 쉬운 장점이 있다.✓ 중요한 작업(짧은 작업)이 중요하지 않은 작업(긴 작업)을 기다리는 경우가 발생할 수 있는 단점이 있다. ✓ FCFS 스케줄링 (First-Come First-Served Schedu..