CSE 전공노트

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; // 변수는 더 추가해도 상관없습니다. 변수가 하나밖에 없다면 굳이 구조체를 만들지 않고 구현해도 됩니다...

오늘은 프로세스 동기화의 마지막 남은 부분들에 대해서 알아보겠습니다. 구체적으로는 Mutex Lock과 Semaphore에 대해 중점적으로 알아보고자 합니다. 1. Mutex Locks 바로 전의 글에서 하드웨어를 통한 동기화 기법인 test_and_set이나 compare_and_swap의 경우에도 문제점이 있다는 점에 대해서 공부했었습니다. 그래서 운영체제의 설계자들은 이러한 문제를 해결하기 위해 다시 소프트웨어 툴을 개발합니다. 그리고 이 중에 가장 간단한 도구가 바로 Mutex Lock입니다. 아마 리눅스에서 쓰레드를 공부해 보았다면 한번쯤은 사용해 보았을 것이라 생각됩니다. Mutex는 Mutual Exclusion을 뜻하고, 모든 프로세스는 Critical section에 들어가기 위해 loc..

바로 앞의 글에서 확인할 수 있듯이 Peterson's Solution과 같이 코드적으로 완벽해보이는 소프트웨어적인 알고리즘들도 결국 컴파일러의 동작 순서 등의 이유와 맞물려 예상치 못하게 잘 못 동작할 수 있다는 것을 알 수 있었습니다. 사실 프로세서가 하나 뿐인 시스템 (single-processor system)에서는 어떤 공유 변수가 변경되는 동안은 interrupt 발생을 허용하지 않는 방법을 사용하여 쉽게 처리할 수 있기는 합니다. CPU 스케쥴링을 멈춤으로써 아예 Race condition 문제를 발생하지 않게 하는 것입니다. 하지만 이것은 multiprocessor system에서는 사용이 불가능하며, 또 실시간 처리가 필요한 시스템에서는 사용이 불가능합니다. Multiprocessor s..

프로세스 동기화 파트에서는 앞에서 잠깐 설명한 적이 있는 Race Condition에 관한 문제를 다루게 됩니다. 프로세스들은 병렬적으로 실행이 될 수 있기 때문에 여러 프로세스가 공유하고 있는 데이터의 무결성에 문제를 야기할 수 있습니다. Race Condition에 대해서 먼저 알아보도록 하겠습니다. 1. Producer-Consumer Problem 가장 쉽게 Race Condition에 대해서 알아볼 수 있는 모델이 바로 생산자-소비자 모델입니다. 위 그림과 같은 모델에서 A와 B는 버퍼를 공유하고 있고, A는 공유하고 있는 버퍼에 데이터를 채워 넣기만 하고, B는 데이터를 가져가기만 합니다. 버퍼가 가득 차있으면 A는 버퍼에 빈 공간이 생길 때까지 대기하여야 하고, 버퍼가 텅 비어있다면, B는 ..

지난 글에 이어 이번에도 CPU 스케쥴링에 대해 공부해 보겠습니다. 이번엔 스케쥴링의 기준과 스케쥴링 알고리즘에 대해 알아보는 시간을 갖도록 하겠습니다. 1. 스케쥴링 기준 (Scheduling Criteria) CPU의 스케쥴링 알고리즘들은 서로 다른 특성을 가지고, 서로 다른 포인트에 집중하여 스케쥴링을 진행합니다. 그래서 특정 상황에서 스케쥴링 알고리즘을 선택하기 위해서는 각 알고리즘들의 특성들을 이해하고 있어야 합니다. 스케쥴링 알고리즘을 비교하여 선택하기 위해서는 여러 가지 기준들이 필요하며, 이 기준들에 따라 선택되는 알고리즘이 크게 바뀔 수 있기 때문에, 최선의 알고리즘을 선택하기 위해서는 명확한 기준을 세우는 것이 중요합니다. 여기서는 6가지 기준에 대해 알아보겠습니다. 1. CPU Uti..