1. Project Introduction

이번 프로젝트는 Producer-Consumer 패턴으로 상당히 널리 알려져 있는 패턴이기에, 대부분의 개발자들이 기본적으로 이해하고 있는 내용이다. 따라서 이번 프로젝트에서는 생산자와 소비자 스레드 사이에서 발생하는 문제들을 해결하고 멀티스레딩이 가능하도록 하는 것이 목적이다.

이번 프로젝트에서 사용되는 기본 코드에서의 생산자 스레드는 파일에서 라인을 읽어 공유 버퍼에 저장을 한다. 소비자 스레드는 공유 버퍼에서 문자열을 가져와 화면에 라인을 출력한다. 이후, 다수의 소비자 스레드를 이용해 파일에 있는 알파벳의 수를 계산하여 최종적으로 출력하는 것이 이번 프로젝트의 목표이다.

2. Project Goals

이번 프로젝트의 목표는 두 개 이상의 concurrent한 스레드들이 공유된 자원에 접근하려고 할 때 동기화 메커니즘이 없이 접근하려는 현상인 race condition을 해결하여 멀티 스레딩이 가능하도록 하는 것이다. 따라서 다수의 스레드들이 명령을 수행함에 있어 생기는 동기화 문제와 임계영역 문제 등을 파악하고, 해당 문제를 해결할 수 있는 소프트웨어적인 방법을 알아보고 고안하여, 구현하는 것을 이번 프로젝트의 목표로 한다.

3. Concepts used in CPU simulation

프로세스란, 운영체제에서 실행되는 프로그램의 최소 단위라고 보면 된다. 즉, 1개의 프로그램을 가리킬 때 보통 1개의 프로세스를 의미하는 경우가 많다.

그렇다면 이 프로세스들은 어디에서 실행될까? 바로 CPU의 코어에서 실행되며 한 번에 한 개의 연산을 수행한다.

근데 CPU가 한 번에 한 가지 연산 밖에 못한다면, 도대체 어떻게 웹서핑을 하면서 음악을 듣고, 게임을 하는 등 여러 가지 일들을 한 번에 할 수 있었을까? 방법은 바로 컨텍스트 스위칭(Context switching) 이라는 기술에 숨어 있다.

컴퓨터에서 프로그램이 실행될 때, 사용자가 보기에는 프로그램이 연속적으로 작동하는 것처럼 보이지만 실제로는 그렇지 않다. 아래 그림을 보면 CPU 코어 하나에서 프로그램들이 어떻게 실행되는지 알 수 있다.

보다시피, 프로그램 하나가 연속적으로 작동하는 것이 아니라, 프로그램 하나가 잠시 실행되었다가, 다른 프로그램으로 스위칭 되는 것을 볼 수 있다. 즉, CPU 는 한 프로그램을 통째로 실행시키는 것이 아니라, 이 프로그램 조금, 저 프로그램 조금씩 골라서 차례를 돌며 실행시킨다는 것을 알 수 있다.

정확히 말하면, CPU는 명령어들을 실행할 뿐, 어떤 프로그램을 실행시키고, 얼마 동안 실행 시키고, 또 다음에 무슨 프로그램으로 스위칭할지는 운영체제의 스케쥴러(scheduler)가 알아서 결정하게 된다.

※ Thread

CPU 코어에서 돌아가는 프로그램 단위를 쓰레드 (thread) 라고 부른다. 즉, CPU 의 코어 하나에서는 한 번에 한 개의 쓰레드의 명령을 실행시키게 된다.

한 개의 프로세스는 최소 한 개 쓰레드로 이루어져 있으며, 여러 개의 쓰레드로도 구성될 수 있다. 이렇게 여러 개의 쓰레드로 구성된 프로그램을 멀티 쓰레드 (multithread) 프로그램이라 한다.

쓰레드와 프로세스의 가장 큰 차이점은 프로세스들은 서로 메모리를 공유하지 않는다. 다시 말해, 프로세스1 과 프로세스2 가 있을 때, 프로세스1 은 프로세스2 의 메모리에 접근할 수 없고, 마찬가지로 프로세스2 도 프로세스1 의 메모리에 접근할 수 없다.

프로세스는 서로의 메모리를 접근할 수 없지만, 같은 프로세스 내에 Thread끼리는 메모리를 공유한다.
하지만 쓰레드의 경우는 다르다. 만일 한 프로세스 안에 쓰레드1 과 쓰레드2 가 있다면, 서로 같은 메모리를 공유하게 된다. 따라서 Thread1 과 Thread2는 같은 변수에 접근할 수 있다.

※ 멀티 프로세싱(Multi-processing)

멀티 프로세싱은 한마디로 말해 '두개 이상, 다수의 프로세서가 협력적으로 작업을 동시에 처리하는 것'이다.

프로세서는 대략적으로 CPU라고 생각하면 된다. 각각의 프로세서가 하나의 작업만을 처리하는 것이 아니라 다수의 작업을 처리하며, 하나의 작업은 하나의 프로세서에 의해 처리되는 것이 아니라 다수의 프로세서에 의해 처리된다.

멀티 프로세싱의 장점으로는 여러 개의 프로세스가 처리되어야 할 때 동일한 데이터를 사용한다면 이러한 데이터를 하나의 디스크에 두고 모든 프로세서가 이를 공유하도록 한다면 비용적으로 저렴하다.

또한, 만약 하나의 프로세서가 하나의 작업만을 처리한다면 특정 프로세서가 고장이 났을 때 해당 작업은 정지된다. 하지만 멀티 프로세싱을 할 경우 특정 프로세서가 고장나도 다른 프로세서들은 자신의 일을 수행할 수 있다.

※ 멀티 프로그래밍(Multi-programming)

멀티 프로그래밍이란, 특정 프로세스 A에 대해서 프로세서가 작업을 처리할 때 낭비되는 시간동안 다른 프로세스를 처리하도록 하는 것 입니다.

예를 들어 A라는 프로세스를 처리 중에 있을 때 입출력 이벤트가 발생했는데 프로세서가 입출력 이벤트에 대한 응답을 위해 무작정 대기하고 있다면 프로세서의 자원을 낭비하는 결과를 초래한다. 프로세서, CPU는 한 번에 하나의 프로세스만 처리하도록 되어있기 때문에 A 프로세스에 대한 입출력 이벤트에 대한 응답을 대기하는 동안 아무 일도 하지 않기 때문이다.

멀티 프로그래밍은 이렇게 낭비되는 시간동안 프로세서가 다른 프로세스를 수행할 수 있도록 하는 것이다.

※ 멀티 태스킹(Multi-tasking)

멀티 태스킹이란 다수의 Task를 운영체제의 스케줄링에 의해 번갈아 가면서 수행하는 것이다. 프로세서가 각각의 Task를 조금씩 자주 번갈아가면서 처리하기 때문에 사용자는 마치 동시에 여러 Task가 수행되는 것처럼 보게 된다. 위에서 말한 멀티프로그래밍과의 차이점으로는, 멀티프로그래밍은 프로세서의 자원이 낭비되는 것을 최소화하기 위한 것이며 멀티 태스킹은 일정하게 정해진 시간동안 번갈아가면서 각각의 Task를 처리하는 것이다.

※ 멀티 스레딩(Multi-threading)

일반적으로 하나의 프로세스는 하나의 스레드를 가지고 작업을 수행하게 된다.
하지만 멀티 스레드(multi thread)란 하나의 프로세스 내에서 둘 이상의 스레드가 동시에 작업을 수행하는 것을 의미한다.

또한, 멀티 프로세스(multi process)는 여러 개의 CPU를 사용하여 여러 프로세스를 동시에 수행하는 것을 의미한다.

멀티 스레드와 멀티 프로세스 모두 여러 흐름을 동시에 수행하다는 공통점을 가지고 있지만 멀티 프로세스는 각 프로세스가 독립적인 메모리를 가지고 별도로 실행되지만, 멀티 스레드는 각 스레드가 자신이 속한 프로세스의 메모리를 공유한다는 점이 다르다.

멀티 스레드는 각 스레드가 자신이 속한 프로세스의 메모리를 공유하므로, 시스템 자원의 낭비가 적으며 하나의 스레드가 작업을 할 때 다른 스레드가 별도의 작업을 할 수 있어 사용자와의 응답성도 좋아진다.

※ 상호배제(Mutual Exclusion)

상호 배제는 동시에 실행되는 프로세스들이 임계 영역(Critical Section)에 동시에 들어가지 않도록 하는 것이다. 임계 영역(Critical Section)은 공유 자원에 접근하는 프로세스의 영역으로 즉, 프로그램 코드 중에서 공유 자원에 접근하는 부분의 코드를 의미한다.

예를 들면, 어떤 프로그램이 파일의 이름을 변경하는 기능이 있을 때, 파일의 이름을 변경하는 코드가 있는 곳이 임계 영역이다. 파일은 여러 프로그램이 사용할 수 있는 공유 자원이다. 2개의 프로그램이 동시에 한 파일의 이름을 변경하려고 하면 예측할 수 없는 결과가 생길 수 있다. 2개의 프로그램이 동시에 파일의 이름을 변경하는 임계 영역에 들어가지 못하도록 하는 기법이 상호 배제이다.

⦁ 상호 배제(Mutual Exclusion)는 다음과 같은 방법들이 있다.

• Lock
• Semaphore
• Monitor
• Message Passing
• Tuple Space

⦁ 상호 배제는 하드웨어로 구현될 수도 있고 소프트웨어로 구현될 수도 있다. 하드웨어에 의한 방법은 주로 CPU 명령어에서 지원한다.

⦁ 상호 배제를 순수하게 소프트웨어만으로 구현하기 위해서는 조금 복잡한 알고리즘이 필요하다. 소프트웨어로 구현할 수 있는 상호 배제 알고리즘은 다음과 같다.

• Dekker 알고리즘
• Peterson 알고리즘
• Lamport's bakery 알고리즘
• Szymanski 알고리즘
• Taubenfeld's black-white bakery 알고리즘

⦁ 상호 배제가 제대로 동작하지 않을 때 다음과 같은 문제가 생길 수 있다.

• Deadlock : 2개의 프로세스가 동시에 공유 자원을 얻기 위해 2개의 프로세스가 모두대기하는 상태
• Starvation : 프로세스가 공유 자원을 절대 얻을 수 없는 상태
• Priority Inversion : 우선 순위가 높은 프로세스가 공유 자원을 얻는데 우선 순위가 낮아지는 것

※ 피터슨(Peterson) 알고리즘

peterson algorithm이란 상호 배제를 위한 병렬 프로그래밍 알고리즘으로서, 공유 메모리를 활용하여 여러 개의 프로세스가 하나의 자원을 함께 사용할 때 문제가 발생하지 않도록 해준다. 코드를 살펴보면 결국 마지막에 결정된 turn의 값이 두 개의 프로세스 중에 어떤 게 공유된 자원을 먼저 사용할지 결정시키는 알고리즘이다.

※ 데커(Dekker) 알고리즘

※ 결정성과 경쟁 조건

1) 병행 프로세스(Concurrent Process)

두 개 이상의 실행 중인 프로그램이라는 의미로 서로 관련 없이 독립적으로 수행하는 독립적 병행 프로세스와 상호 관련성으로 갖고 비동기적으로 수행 하는 비동기적 병행 프로세스로 나뉨

2) 결정성

• 두 프로세스 간에 선행관계가 없으면 독립적이고 병행 실행 가능
• 순서를 어떻게 조합하는 가에 의해 시스템의 활동 순열이 결정
• 결정성 : 상대적인 실행 순서에 관계없이 항상 주어진 입력에 대해서 같은 결과를 내는 것.

3)경쟁 조건(race condition)

두 개 이상의 프로세스들이 공유 기억장치를 공유하고, 어떤 프로세스가 언제 실행하느냐에 따라 결과가 달라질 수 있는 상황. 경쟁 조건이 있는 프로그램은 다른 순서로 실행하게 되면 그 결과를 예측할 수 없다.