페이징은 메모리 관리기법 중 불연속 할당의 방법의 하나이다. 본 포스팅에서는 페이징 기법의 종류, 구조 및 구현 방법에 대해서 다룬다. Page Table 페이징은 하나의 프로그램을 구성하는 주소 공간을 같은 크기(4 kB) 여러 단위로 쪼개놓은 형태라서 연속 할당처럼 논리 주소를 Base Register와 Limit Register만으로 간단히 주소 변환할 수 없기 때문에 페이지 테이블(Page Table)을 사용하여 주소를 변환한다. 페이지 테이블은 어떤 페이지가 어떤 프레임에 가야하는지 가리키는 매핑 테이블(Mapping Table)이다. 몇 번 페이지가 어떤 프레임에 대응되는지는 이미 정해져 있기 때문에 페이지 번호만큼 오프셋(Offset)1하면 바로 물리적 메모리 주소로 변환할 수 있다. ...
메모리는 주소를 통해 접근하는 매체로 프로그램이 실행되려면 논리적인 주소(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 상태에 빠지면 어떤 프로세스가 먼저 희생(또는 종료)하지 않는 이상 끝나지 않는다. ...
모니터(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)를 활용하여 다음과 같이 극복할 수 있다. ...
본 포스팅에서는 앞선 포스팅에서 다룬 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을 최소화하기 위하여 각 프로세스를 어떤 큐에 넣을 것인지와 개별 큐에 어떤 알고리즘을 선택할 것인지 결정해야 한다. ...
일반적인 CPU 스케줄링 알고리즘에 대한 포스팅이다. 여기서 일반적이라함은 단일 프로세서(CPU)･스레드(Thread), 비실시간(Unreal-time)을 의미한다. FCFS (First-Come First-Served) 가장 쉽게 떠올릴 수 있는 솔루션으로 큐(Queue)에 도착한 순서대로 처리하는 스케줄링이다. 마치 인간 세계에서 은행에 먼저 도착한 사람의 볼 일이 끝날 때 까지 뒤에 있는 사람이 기다려야 하는 것과 같은 방식이다. 순전히 선착순으로 먼저 도착한 프로세스는 볼 일이 끝날 때까지 CPU를 보장받는다. 즉, 비선점형(Non-Preemptive)이다. 문제점 (Problem) 꽤 공정하지만 앞에 어떤 프로그램이 있느냐에 따라 기다리는 시간에 대한 영향이 크기 때문에 그다지 효율적이지 않다. 같은 프로그램들이 실행되어도 도착 순서에 따라서 평균 대기 시간(Averaging waiting time)이 크게 차이 나기 때문이다. ...