Posts

메모리는 주소를 통해 접근하는 매체로 프로그램이 실행되려면 논리적인 주소(Logical Address)의 값이 물리적인 주소(Physical address)에 올라가야 한다. Memory Management 파트에서는 이와 같이 프로세스를 물리적인 메모리에 할당하고 관리하는 방법에 대하여 다룬다. 주소 바인딩(Address Binding)이란? 프로그램이 실행되려면 프로그램이 컴퓨터 메모리 어디에 올라갈지 메모리 주소를 결정되어야 한다. 즉, 논리적 주소(Logical address)를 물리적 주소(Physical address)로 주소 변환해주어야 하는데 이와 같이 주소를 결정(변환)하는 것을 주소 바인딩이라고 한다. Symbolic Address: 코딩 시 직접 논리적 주소(메모리 번지수)를 지정하기 보단 변수를 선언하여 메모리를 할당하는데 이처럼 직접적인 메모리 주소 대신 변수로 선언한 것(주소)을 말한다. Logical Address(= Virtual Address): 프로세스마다 독립적으로 가지는 주소 공간(Address space)으로 CPU가 보는 주소이다.1 각 프로세스마다 0번지부터 시작한다. Physical Address: 실제 물리적인 메모리에 올라가는 위치(주소)이다. 하위 주소 부분에는 운영체제(Kernel)가 올라가고, 상위 주소 부분에는 여러 프로그램들이 올라간다. Binding Process Symbolic Address → Logical Address(Compiled) → Physical Address ...

Deadlock(교착상태)이란 프로세스들이 서로가 가진 자원을 기다리며 Block된 상태를 말한다. 예를 들어 프로세스 A, B, C가 있고 자원1 1, 2, 3이 있을 때, 각각의 프로세스는 작업을 수행하기 위하여 지정된 2개의 자원이 필요하다고 가정하자. 이러한 조건속에서 A가 1을 가지고 있는 상태에서 2를 요청(Request)하고, B는 2를 가지고 있는 상태에서 3을 요청하고, C는 3을 가지고 있는 상태에서 1을 요청한다면 프로세스는 서로의 자원을 기다리며 멈추게 된다. Deadlock 상태에 빠지면 어떤 프로세스가 먼저 희생(또는 종료)하지 않는 이상 끝나지 않는다. ...

NoSQL이란 SQL이 아니라는 명칭에서 느껴지는 오해와 달리 Not-only SQL이라는 뜻으로 ‘SQL뿐만이 아니다’ 라는 뜻으로 Relational 방식과 달리 SQL만을 사용하지 않는 데이터베이스 시스템을 말한다.1 엄격한 2차원 매트릭스인 Relational Database 같은 정보 구조가 아닌 데이터(Key-Value, JSON, XML, Graph 등)를 처리하기 위하여 주로 사용한다. 분산 환경(Cluster)에서 실행할 목적으로 만들어진 경우가 많기 때문에 Relational 모델을 사용하지 않으며 대부분 오픈 소스이다. 21세기 이후에 개발된 시스템만을 NoSQL이라 칭하므로 유사한 목적과 구조를 갖지만 과거에 개발된 Data warehouse(OLAP)은 NoSQL에 해당하지 않는다. ...

모니터(Monitor)란? 세마포어(Semaphore)와 같은 추상적인 개념으로서, 동시 수행(Concurrency) 중인 프로세스 사이에서 추상형 데이터 타입(Abstract data type)의 안전한 공유를 보장하기 위하여 언어(Language) 수준에서 지원하는 High level synchronization construct이다. 유용성 세마포어가 비교적 쉽게 Critical section에 접근할 수 있도록 돕긴 하지만, 프로그래머가 코딩을 잘못하여 버그(Bug)가 생기면 검증이 어려운. 즉, 정확성(Correctness) 입증이 어려운 단점이 있다. 예를 들어 P(), V() 연산의 순서가 뒤바뀌거나(Mutex issue), P() 연산 후 V() 연산을 해야 하는데 다시 한 번 P() 연산(Deadlock issue)을 하는 등 단 한 번의 실수라도 있을 경우 시스템에 치명적인 영향을 준다. ...

본 포스팅은 Bounded-Buffer Problem(Producer-Consumer Problem), Readers & Writers Problem, Dining-Philosophers Problem의 내용과 솔루션에 대하여 다룬다. Bounded-Buffer Problem (Producer-Consumer Problem) 순환하는 유한한 거공유 버퍼(Bounded Circular-Buffer)에 생산자 프로세스(Producer process)와 소비자 프로세스(Consumer process)에 대한 문제이다. 생산자는 데이터를 생산하여 Buffer에 집어넣는 프로세스이고, 소비자 프로세스는 Buffer에 있는 데이터를 꺼내 쓰는 프로세스를 의미한다. 각 프로세스가 여러 개라고 가정할 때 공유 버퍼에는 다음과 같은 문제가 발생한다. 생산자의 공유 버퍼에 대한 데이터 입력 및 조작 경합(또는 소비자의 데이터 꺼내기 경합) 공유 버퍼의 유한함으로 인한 버퍼 Full 또는 Empty 문제 버퍼에 데이터가 가득찬 상태에서 생산자 프로세스가 도착한 경우나, 공유 버퍼가 텅 빈 상태에서 소비자 프로세스가 도착한 경우가 이에 해당한다. 위의 문제는 세마포어(Semaphore)를 활용하여 다음과 같이 극복할 수 있다. ...

본 포스팅은 빅오(Big-O) 표기법이 필요한 이유를 알고리즘 성능 분석 측면으로부터 점근적 표기법 필요성까지 순차적으로 접근하여 빅오(O), 빅오메가(Ω), 빅세타(Θ) 표기법에 대한 내용까지 다룬다. 다만 알고리즘 성능 척도로 주로 시간 복잡도를 활용하기 때문에 공간 복잡도는 다루지 않는다. 알고리즘의 분석 알고리즘 분석은 정확도에 대한 정확성 분석1과 효율성에 대한 성능 분석2으로 나눌 수 있다. 성능 분석은 다시 시간(속도)적인 측면과 공간(메모리)적인 측면으로 구분할 수 있다. 이것을 시간적 성능, 공간적 성능이라 칭하고 싶으나 성능(Performance)은 컴퓨터 시스템의 사양이나 프로그래밍 언어에 따라 수준의 차이가 나기 때문에 일정하지 않다. 따라서 이러한 조건에 관계없이 항상 일정한 기준으로 분석하기 위하여 복잡도(Complexity)라는 용어를 사용한다. ...

본 포스팅에서는 앞선 포스팅에서 다룬 Process synchronization 문제를 해결하기 위한 방법들을 추상화한 방법으로 중요한 개념인 세마포어(Semaphore)에 대하여 다룬다. Semaphore란 무엇인가? 사전적 의미로 수기 신호라는 뜻으로 세마포어(Semaphore)는 컴퓨터 자원의 신호등의 역할을 한다. 세마포어는 보다 구체적으로 두 가지 역할을 하는데 Mutex(Mutual Exclusion) 문제를 해결하고 어떠한 공유 자원을 획득하고 반납하는 작업을 처리해준다. 이해에 주의해야할 점은 Process synchronization을 해결하는 소프트웨어적인 방법처럼 어떠한 알고리즘의 구현(Implementation)을 말하는 것이 아니라 추상적인 개념을 의미한다는 점이다. 세마포어는 변수 S(Semaphore)와 자원을 획득하는 P(), 자원을 반납하는 V() 연산으로 구성된다. ...

본 포스팅은 프로세스 동기화(Process synchronization) 시 공유 데이터(Shared data)를 다룰 때 Race condition을 발생시키지 않기 위하여 필요한 중요한 개념인 Critical section에 대한 내용과 Critical section에서 발생할 수 있는 문제를 해결하는 소프트웨어적인 접근과 하드웨어적인 접근에 대한 내용을 다룬다. Critical-Section이란? 공유 데이터에 접근하는 코드를 말하며 임계 구역이라고도 한다. 공유 데이터(Shared data) 부분이 Critical section이 아니라 공유 데이터에 접근하는 코드가 Critical section이라는 점에 주의한다. P1 과 P2 에서 접근하려는 Shared data x=2 가 Critical section이 아니라 공유 데이터 x 에 접근하려는 P1 의 코드 x = x + 1 과 P2 의 코드 x = x - 1 이 Critical section이다. ...

Process Synchronization 문제란? 상호 다른 프로세스(Process) 또는 프로세서(Processor)가 공유 데이터(Shared memory)에 동시 접근(Concurrent access)할 때 발생하는 데이터의 불일치성(Inconsistency) 문제이다. 예를 들어 프로세스 A와 B가 어떤 주소공간을 부분적으로 공유하는데 프로세스 A가 공유 데이터를 증가시키는 수정을 하다가 프로세스 B로 컨텍스트 스위치가 발생하였고, 마침 B도 같은 데이터를 증가시키는 수정한 뒤 CPU를 A에게 돌려주었다. 이때 해당 데이터는 ‘2’만큼 증가하여야 하지만 A는 컨텍스트 스위치 시점의 데이터를 수정하기 때문에 결과적으로 ‘1’ 증가하게 되는 데이터 불일치 문제를 야기한다. ...

본 포스팅에서는 큐(Queue)가 여러 개인 경우와 다중 프로세서(CPU)･스레드(Thread) 스케줄링, 실시간(Real-time) 스케줄링에 대한 내용을 다룬다. 멀티레벨 큐(Multilevel Queue) CPU를 기다리는 레디 큐(Ready Queue)가 한 줄이 아닌 여러 줄인 경우 각 큐에는 우선 순위가 존재한다. 아래 이미지는 멀티레벨 큐의 한 예시이다. (단일 CPU인 경우) CPU를 쓸 수 있는 프로세스는 어느 한 줄에서 나온 Job뿐이므로 우선 순위가 낮은 Queue에서는 Starvation 현상이 발생할 수 있다. 각 큐는 독립적인 스케줄링 알고리즘을 갖는다. 따라서 Starvation을 최소화하기 위하여 각 프로세스를 어떤 큐에 넣을 것인지와 개별 큐에 어떤 알고리즘을 선택할 것인지 결정해야 한다. ...