CSE 전공노트

지난 글에서까지 메모리 관리에 대한 공부를 해보았습니다. 메모리 관리의 핵심은 다중 프로그래밍을 실현하기 위해 메모리에 많은 프로세스들을 동시에 유지할 수 있도록 하는 것입니다. 하지만 메인 메모리를 공부하면서 공부했던 방식은 모두 프로세스가 실행되기 위해 메모리로 올라와야 한다는 것을 전제로 합니다. 하지만 가상 메모리(Virtual Memory)를 사용하면 프로세스 전체가 다 메모리로 올라오지 않아도 실행이 가능합니다. 1. 가상메모리? 가상 메모리를 이용하면 프로그램이 실제 물리 메모리보다 큰 메모리 공간을 요구하더라도 사용이 가능하다는 장점이 있습니다. 가상 메모리는 물리 메모리로부터 사용자 관점의 논리 메모리를 분리시켜 메인 메모리를 균일한 크기의 저장 공간으로 구성된 엄청나게 큰 배열로 추상화..

이번 글에서는 지난 글에서 공부한 페이징의 남은 부분들에 대해서 공부해보도록 하겠습니다. 1. 페이지 보호 (Page Protection) 페이지 테이블을 만들 때, 메모리 보호를 위해서 각 페이지들에 추가적인 비트들을 부여하여 사용할 수 있습니다. 첫 번째로는 Read-write/Read-only를 나타내는 비트입니다. 당연히 Read-write 모드일 때만 데이터를 수정할 수 있으며 Read-only 모드에서는 읽을 수만 있습니다. 두 번째는 Valid-invalid bit입니다. 이 비트가 valid로 설정되어 있으면, 해당 페이지가 프로세스의 논리 주소 공간 안에 있는 합법적인 페이지라는 것을 나타냅니다. 운영체제는 이 비트를 통해서 해당 페이지에 접근을 허용할 것인지 말지를 결정합니다. 예를 들..

이번에 공부해 볼 내용은 페이징입니다. 바로 앞의 글에서는 하나의 프로세스가 하나의 파티션을 할당받는 연속적인 메모리 할당에 대해서 공부해보았습니다. 하지만 메모리는 비연속적인 물리적 주소 공간을 할당해 줄 수도 있습니다. 그리고 이런 비연속적인 할당을 통해 external fragmentation을 예방할 수 있습니다. 1. 페이징 (Paging) 페이징의 기본적인 방법은 다음과 같습니다. 물리 메모리(physical memory)는 프레임(frame)이라고 불리는 일정한 크기의 고정된 사이즈의 블록들로 나누어집니다. 그리고 논리 메모리(logical memory)는 페이지(page)라고 불리는 프레임과 같은 사이즈의 블록으로 이루어집니다. 그리고 논리 주소는 페이지 번호(page number)와 페이..

이번 글에서는 메인 메모리에 대해서 공부해보도록 하겠습니다. 메모리는 어떤 값을 저장하는 1차원 배열이라고 볼 수 있습니다. CPU는 주소 값을 통해 메모리의 특정 위치에 접근할 수 있습니다. 프로세스가 하나뿐일 때는 그 프로세스가 메모리를 모두 사용해도 되지만, 프로세스가 두 개 이상일 경우 이 메모리 자원들을 어떻게 나누어서 쓸 것인가는 중요한 이슈입니다. 우선은 메모리 주소의 할당부터 하나씩 차근차근 공부해 나가 보도록 하겠습니다. 1. 주소 할당 (Address Binding) 프로그램은 원래 디스크에 저장되어 있습니다. 이 프로그램이 실행되기 위해서는 메인 메모리로 올라와서 프로세스가 되어야 합니다. 그리고 프로세스는 실행될 때 메모리에 적재해 놓은 명령어와 데이터에 접근하여 사용하게 됩니다. ..

Deadlock에 대해 마지막으로 공부해 볼 내용은 바로 Deadlock Avoidance, 즉 교착상태 회피입니다. Deadlock Avoidance의 가장 핵심 아이디어는 어떤 자원을 요청할 때, 추가적인 정보를 제공하도록 요구하는 것입니다. 즉, 각각의 프로세스들이 어떤 자원을 어떤 순서로 사용할 것이라는 것을 이미 시스템이 알고 있다면, 미래에 Deadlock이 발생하지 않기 위해 어떤 프로세스가 대기를 해야 하는지 결정할 수 있을 것입니다. 이러한 방법으로 Deadlock의 발생 조건 4가지 중 적어도 하나 이상을 성립하지 않게 만들어줄 수 있습니다. 1. Safe State (안전 상태) 시스템이 안전하다는 말은 시스템이 어떤 순서로든 프로세스들이 원하는 모든 자원을 Deadlock 없이 차례..

지난번 글에서 Deadlock의 정의가 무엇인지, 또 어떤 상태일 때 Deadlock이 성립하는지에 대해 알아보았습니다. 이번 글에서는 Deadlock을 어떻게 처리해 주어야 하는지에 대해서부터 살펴보겠습니다. 1. Deadlock 처리 방법 Deadlock 문제를 처리하는 데에는 3가지 방법이 존재합니다. 1. 시스템이 Deadlock에 걸리지 않도록 Deadlock을 예방하거나 피하는 프로토콜들을 사용한다. 2. 시스템이 Deadlock이 걸리고 나면 이를 탐지하고, 회복시키는 방법을 사용한다. 3. Deadlock에 관한 사항을 무시하고, Deadlock이 일어나지 않기를 바란다. 마지막 방법은 굉장히 무책임한 방법으로 보이지만, 사실 Windows나 Linux 등 대부분의 운영체제들은 세 번째 방..

다중 프로그래밍 환경에서는 여러 프로세스들이 한정된 자원을 사용하려고 서로 경쟁하는 상황이 발생할 수 있습니다. 마치 아래의 그림과 같은 상황을 말합니다. 이를 Deadlock (교착상태)이라고 합니다. 이번 글에서는 이 Deadlock에 대해서 상세하게 살펴보고자 합니다. 1. Deadlock의 정의 우선 시스템은 유한한 개수의 자원(resource)들로 이루어집니다. 여기서 자원이라 함은, 예를 들면 CPU나 파일들, 또는 입출력 장치들을 뜻하며, 프로세스들은 이런 자원들을 사용하고자 할 때 요청(Request)을 보내야하고, 사용을 완료하면 방출(Release)을 해 주어야 합니다. 요청을 했을 때 자원이 이미 다른 프로세스에 의해 사용되고 있는 등의 이유로 허용이 되지 않으면, 자원을 얻을 수 있..

지난 글에서 큐에 대한 대략적인 개념을 공부했습니다. 하지만 앞에서 공부했던 대로 큐를 구현하게 되면 문제가 한 가지 존재합니다. 바로 add와 delete를 반복적으로 계속 수행하다 보면 front와 rear는 계속 증가하게 될 것이고, 그러면 아래의 그림과 같이 배열에 안쓰는 부분이 계속 증가하여 공간을 낭비하게 됩니다. 그래서 front와 rear가 너무 커지게 되면 이것을 다시 앞으로 당겨주는 작업이 필요하게 됩니다. 하지만 아무래도 이러한 작업이 번거롭다 보니 circular queue (원형 큐)라는 것이 등장합니다. 원형 큐는 위의 그림과 같은 형태로 큐의 양 쪽 끝을 이어놓은 형태입니다. 이런 형태로 구현을 하면 굳이 뒤로 밀린 front와 rear를 앞으로 당기지 않고 계속 순환하면서 큐..

오늘은 큐에 대해서 공부해보려고 합니다. 큐는 앞에서 살펴본 스택과는 달리 삽입과 삭제가 다른 방향으로 나오는 형태의 리스트를 뜻합니다. 먼저 삽입된 데이터가 먼저 나오는 형태입니다. 이 때문에 First-In-First-Out (FIFO) list라고도 부릅니다. 스택에서는 top을 이용해서 배열을 관리하는 것처럼, 큐에서는 front, rear 두 개의 변수를 이용합니다. front는 큐의 앞 쪽 끝을 가리키고, rear는 큐의 제일 뒤 쪽 끝을 가리키게 됩니다. 기본적인 형태는 다음과 같습니다. front와 rear는 -1로 초기화하여 선언합니다. 데이터가 추가될 때마다 제일 뒤를 가리키는 변수인 rear가 1씩 증가하고, 데이터가 삭제될 때마다 가장 앞을 가리키는 변수인 front가 1씩 증가합니..

스택은 삽입과 삭제가 리스트의 한쪽 끝에서만 일어나는 자료구조입니다. 스택에 뭔가를 추가하는 것을 push라고 하고, 삭제하는 것을 pop이라고 합니다. 스택은 전형적인 후입선출 (Last-In-Frist-Out)의 형태로써, 아래의 그림처럼 구현됩니다. Push를 실행하게 되면 가장 위에 데이터를 쌓아 올리고, pop을 실행하면 가장 위에서부터 데이터를 삭제하게 됩니다. 스택은 C로 구현하면 다음과 같이 구현할 수 있습니다. 스택은 1차원 배열을 이용하여 구현을 하게 됩니다. #define MAX_STACK_SIZE 100 //Stack의 최대 사이즈 typedef struct { int key; // 변수는 더 추가해도 상관없습니다. 변수가 하나밖에 없다면 굳이 구조체를 만들지 않고 구현해도 됩니다...