Search
🤔

Philosophers

Created
2021/07/13
tag
42서울
42Seoul
Philosophers
Synchronization
Mutex
Semaphore
Thread
Process

Subjects

1. Philosophers?

1) 소개

42의 다른 Subject에 대해서 참고서를 만들 때, 각 Subject가 정확히 무엇을 구현하는 것인지 언급한적이 없었다. 우선 Subject의 목적이 과제 이름만으로 굉장히 뚜렷하거나, 평가를 진행하는 도중 가시적으로 볼 수 있는 것들이 두루 있어서 파악이 용이하기 때문이었다. 또한 Subject에 대해서 알아두면 좋은 것들 혹은 부수적인 요소만 담고 싶었기 때문에, Subject가 어떤 것인지에 대해서는 직접 파악하길 바라는 마음이 더 컸다. 하지만 Philosophers에 대해서는 왜 Subject의 이름이 Philosophers이며, 무엇을 구현하는지에 대해서 간단히 짚고 넘어가고 싶었다.
Philosophers에서 다루는 문제는 컴퓨터 사이언스에서 꽤나 유명한 식사하는 철학자 문제 (Dining Philosophers Problem)으로 불린다. 해당 문제는 운영체제의 동기화 (Synchronization)에 대한 고전적인 문제에 대해 설명하기 위해 1960년대에 제시되었다. 식사하는 철학자 문제에서 제시된 상황은 다음과 같다.
비슷한 종류로 Consumer-Producer Problem, Readers-Writers Problem 등이 있다.
5명의 철학자가 원형 식탁에서 식사를 하려할 때, 각 철학자 사이에는 젓가락이 하나씩 놓여 있다. 따라서 5개의 젓가락이 존재하는 것이고, 이 젓가락은 쌍으로 존재하는 것이 아니기 때문에 철학자가 식사를 하기 위해선 철학자 양 옆에 존재하는 젓가락들을 모두 잡아야 식사를 할 수 있다. 문제에 따라 명명법이 다를 수 있는데, 각 철학자는 EATING, THINKING, SLEEPING과 같은 3가지의 상태를 유지할 수 있다. 각 철학자는 EATING 뒤엔 SLEEPING이 되고, 적절한 시간만큼의 SLEEPING 뒤엔 THINKING이 되며 EATING을 기다린다. 식사하는 철학자 문제동기화에 대한 고전적인 문제인 만큼 어느 부분에서 문제가 생기는지 알아보자.

2) 문제점

do { ... THINKING ... wait(chopstick[i]) wait(chopstick[(i + 1) % 5]) ... EATING ... signal(chopstick[i]); signal(chopstick[(i + 1) % 5]) ... SLEEPING ... } while (1);
C
복사
i 번째 철학자가 i, i + 1번 젓가락을 얻어야 식사가 가능하다고 했을 때, 위 코드와 같이 i 번째 철학자의 식사 진행을 위해 하나씩 젓가락을 잡는다고 해보자. 이와 같은 i번의 젓가락을 잡은 뒤에 i + 1번 젓가락을 잡는 방법은 모든 i 번째 철학자가 i번의 젓가락을 잡았을 때 2개의 젓가락을 얻지 못해 교착 상태 (Deadlock)에 빠지는 모습을 볼 수 있다.
교착 상태에 대해선 추후에 따로 설명된다.

3) 개선안

위 문제를 해결할 수 있는 방법은 3가지가 있다.
1.
젓가락의 수보다 적은 수의 철학자를 유지한다.
2.
젓가락을 하나씩 잡는 것이 아니라 양쪽 젓가락을 모두 사용할 수 있을 때 동시에 두 젓가락을 잡는다.
3.
i 번째 철학자가 홀수 index라면 i번 젓가락을, 짝수 index라면 i + 1번 젓가락을 잡도록 한다.
/* ** i 번째 철학자가 식사를 할 준비가 되었는지 확인한다. ** 양 옆의 철학자가 식사를 하고 있지 않아 젓가락을 모두 이용할 수 있다면, 철학자가 take_chopsticks에서 wait하지 않도록 signal을 보낸다. ** 주어진 조건을 만족하는 경우에는 philo[i]의 값이 1이므로 take_chopsticks에서 Block되지 않고 EATING 할 수 있다. */ check(int i) { if (state[i] == THINKING && state[LEFT] != EATING && state[RIGHT] != EATING) { state[i] = EATING; signal(philo[i]); } } /* ** mutex를 통해 i 번째 철학자의 상태를 변경한다. ** check를 통해 양쪽 철학자의 상태를 확인한다. ** i 번째 철학자는 자신이 식사를 할 수 있을 때까지 기다린다. */ take_chopsticks(int i) { wait(mutex); state[i] = THINKING; check(i); signal(mutex); wait(philo[i]); } /* ** mutex를 통해 i 번째 철학자의 상태를 변경한다. ** check를 통해 왼쪽 철학자와 오른쪽 철학자의 양 옆을 확인한다. ** 둘 중 식사가 가능한 철학자에게 check 내부에서 signal을 보낸다. */ put_chopsticks(int i) { wait(mutex); state[i] = SLEEPING; check(LEFT); check(RIGHT); signal(mutex); } /* ** Solution */ do { ... THINKING ... take_chopsticks(i) ... EATING ... put_chopsticks(i); ... SLEEPING ... } while (1);
C
복사
제시된 방법들 중 두 번째 해결 방법을 예시로 들면 위 코드와 같이 나타난다. 얼핏 보기에는 i 번째 철학자를 기준으로 L, R, LL, RR 모두 check에 걸려 상태 확인 및 signal 수행으로 동기화에 문제가 없어 보임에도 불구하고, 이와 같은 방법들이 해결 방법이 아니라 개선안인 이유는 제시된 방법들이 교착 상태에 대한 해결은 가능할지라도 기아 상태 (Starvation)까지 해결하지는 못하기 때문이다. Philosophers에서는 철학자가 일정 시간 EATING을 하지 못하면 죽게 되므로 기아 상태에 대한 해결도 필요하다. 따라서 코드를 작성할 때 교착 상태의 해결을 위해 위와 같은 방법을 이용하더라도 반드시 기아 상태에 대한 고민이 동반되어야 한다.
기아 상태의 해결 방법들 중 하나로는 한 차례 굶었던 철학자에게 우선권을 주는 방안도 있다.

4) 고려할 점

식사하는 철학자 문제, Consumer-Producer Problem, Readers-Writers Problem동기화의 고전적인 문제들이 시사하는 점들은 결국 아래의 사항들과 같다. 멀티 프로세싱 혹은 멀티 쓰레딩은 많은 장점을 가져다 주지만, 결국 자원을 공유해야 하는 입장에서는 동기화가 필수적으로 요구되고 그 과정에서 고려해야 하는 여러 이슈들이 있다는 것을 잊어서는 안 된다.
1.
Data Consistency가 확보되는가?
2.
Deadlock이 발생하는가?
3.
Starvation이 발생하는가?
4.
Concurrency의 제공이 원활한가?
Philosophers에 대한 이해가 되었다면, 이를 구현하는데 요구되는 개념들과 각 함수들에 대해 알아볼 것이다. 특히 프로세스와 쓰레드와 관련된 내용들을 확실히 익힌 뒤에 구현에 임하도록 하자.

2. Thread

1) Context Switch

운영체제에 의하여 프로세스가 스케줄링 된다고 했을 때, 해당 운영체제가 동작하는 환경이 단일 코어라고 가정해보자. 하나의 코어에는 하나의 작업만이 존재할 수 있으므로, 모든 프로세스를 처리하기 위해선 하나의 프로세스를 처리하고 그 다음 프로세스가 처리하는 식의 프로세스 간의 전환이 요구된다. 이와 같은 처리 되는 프로세스의 전환을 Context Switch라고 부른다.
Context Switch는 프로세스에게 할당된 Time Quantum이 모두 소진되거나, I/O 호출과 같은 Interrupt에 의해 발생한다. Context Switch의 발생이 기존에 수행하던 작업에서 새로운 작업으로 넘어가는 것을 의미하므로, 새로운 작업을 불러올 수도 있어야 할 뿐만 아니라 기존에 수행하던 작업이 추후에 이어서 수행될 수 있도록 저장될 수도 있어야 한다. 이와 같은 과정은 KernelDispatcher라는 곳에서 담당하며, PCB (Process Control Block)이라는 자료구조를 이용하여 이뤄진다.
Time Quantum은 프로세스가 한 번에 처리될 수 있는 시간 총량을 의미한다. 일반적으로 프로세스에게 할당되는 Time Quantum은 사용자가 체감하지 못할 정도로 작다. 덕분에 한 번에 하나의 프로세스 밖에 처리하지 못하는 상황임에도 사용자는 모든 프로세스가 동시에 처리되는 것처럼 느끼게 된다.
Context Switch는 비록 프로세스 간 발생하는 것이지만, 쓰레드 간의 전환인 Thread SwitchContext Switch와 크게 다를 것이 없으므로 이에 대한 이해는 필수적이다. 현재 처리 중인 프로세스를 PoldP_{old}라 하고, 처리하려는 프로세스를 PnewP_{new}라고 했을 때, Context Switch에 대한 흐름은 위 그림과 같다. 그림에서 볼 수 있듯, Context SwitchInterrupt에 의해 발생하지만 프로세스의 기록 자체는 시스템 콜에 기반하는 것을 알 수 있다. 시스템 콜 호출에 따라 PoldP_{old}의 내용을 PCBoldPCB_{old}에 기록한 후, 처리하려는 프로세스의 흐름을 PCBnewPCB_{new}에서 읽어와서 PnewP_{new}를 실행하게 되는 식으로 Context Switch가 이뤄진다.
Context Switch 자체는 위에서 언급된 것처럼 Dispatcher에 의해서 처리되는데, 이는 곧 Dispatcher의 호출로부터 시작된다. Dispatcher의 호출은 Interrupt에 의해 발생한다. Dispatcher를 호출하는 InterruptPreemptive SchedulingNon-Preemptive Scheduling으로 나뉜다. Time Quantum을 모두 소진하여 운영체제 권한으로 프로세스의 권한을 뺏으면서 발생하는 InterruptPreemptive Scheduling이고, I/O 호출과 같이 프로세스가 스스로 CPU 점유를 포기하면서 발생하는 InterruptNon-Preemptive Scheduling이다.
PCB라는 자료구조는 운영체제마다 다를 수 있지만, 대체적으로 위 그림과 같은 내용들이 포함된다. 현재 처리하는 프로세스가 PCBoldPCB_{old}를 사용하고 새로 처리하려는 프로세스가 PCBnewPCB_{new}를 사용했던 것을 통해 PCB라는 자료구조는 프로세스마다 갖는다는 것을 알 수 있다. 각 프로세스가 이용하는 PCBKernel이 사용하는 메모리 공간에 위치하게 된다.
Kernel도 메모리 상에 존재하는 조금 특별한 하나의 프로세스이다. 다수의 PCB가 존재하여 모두 메모리에 올리지 못하는 경우에 대해서는 일반적인 프로세스의 처리 기법과 동일하게 처리되는데, Virtual AddressDemanding Page 기법을 통해 이를 해결할 수 있다. 따로 찾아보는 것을 추천한다.
Context Switch에 따라 PCB에 저장하는 내용들은 한 프로세스의 상태 (State) 정보들이다. 기본적으로 State의 저장 자체가 여러 차례의 메모리 참조를 요구하기 때문에 꽤나 많은 CPU 연산을 손해볼 뿐만 아니라, State의 크기가 크면 클수록 Context Switch를 위한 CPU 연산의 손해는 더욱 커지게 된다. 이와 같은 현상은 특히 프로세서의 구조에도 큰 영향을 받는다.
CPU 연산의 손해라 표현하는 이유는 Context Switch가 없다면 State 정보를 읽어오는 시간만큼 프로세스 처리에 자원을 사용할 수 있기 때문이다. 물론 Context Switch가 없으면 안 되지만, 과도한 Context Switch는 바람직하지 않으므로 지양해야 한다. Context Switch는 결코 값 싼 연산이 아니다.
CISC 구조를 가진 프로세서의 경우에는 Instruction들이 복잡하게 구성되어 있으므로, 처리하고자 하는 연산이 대체적으로 단일 Instruction으로 표현된 경우가 많다. 효율은 좋을 수 있지만 Instruction이 복잡하게 구성되어 있으므로 CPU 클럭 속도는 저하된다는 특성이 있다. 또한 Instruction이 복잡하다는 얘기는 곧 회로가 복잡하다는 것이므로 물리적인 공간을 상대적으로 더 많이 차지함으로써 Register 용량도 저하된다는 특성이 있다. 그럼에도 Context Switch 측면에서 생각해보면, State를 표현하고자 하는 Instruction 묶음이 Compact 할 수 있기 때문에 RISC에 비해 상대적으로 적은 양의 Instruction으로 표현될 수 있다.
RISC 구조를 가진 프로세서의 경우에는 Instruction들이 간단하게 구성되어 있으므로, 처리하고자 하는 연산이 대체적으로 Instruction의 조합으로 표현된 경우가 많다. 비록 반복적인 Instruction이 있을 수는 있지만, Instruction이 간단하므로 CPU 클럭 속도가 높아서 빠른 수행 속도를 낼 수 있다는 특성이 있다. 이는 Register에 대해서도 상대적으로 용량을 절약할 수 있다는 특성과 직결된다. 하지만 Context Switch 측면에서 생각해보면, State를 표현하고자 하는 Instruction 묶음이 무거워짐에 따라 CISC에 비해 오버헤드가 존재하게 된다.
Context Switch의 연산 소모량이 프로세서에 따라 다를 수 있지만, 프로세서의 구분 없이 분명한 것은 Context Switch는 결고 가볍지 않다는 것이다. 추가적으로 프로세서의 구분 없이 분명한 사항이 있는데, 시스템 콜 도중에는 Context Switch가 발생하지 않는다는 것이다. 이는 Context SwitchPCB에 대한 작업을 하는 도중에는 Context Switch가 발생하지 않는다는 것도 포함된다.
시스템 콜 호출 도중에 Context Switch가 일어나지 않는다는 것이 Interrupt를 받지 않는다는 것은 아니므로 헷갈리지 않도록 주의하자.
Context Switch에 대해서는 어떤 맥락의 작업인지 이해가 되었겠지만, 시스템 콜Interrupt 등 부수적인 용어들이 많이 나왔으므로 이에 대해서 알아보도록 하자.

2) CPU 실행 모드

1. User Mode & Kernel Mode

기본적으로 프로세스에서 Instruction을 수행하기 위해 CPU를 사용할 때, 해당 프로세스가 User Mode인지 Kernel Mode인지에 따라 CPU의 실행이 달라진다. 이는 I/O 혹은 프로세스와 관련된 시스템 단의 연산들을 User Mode의 프로세스가 제어하고 관리하지 못하도록, 시스템을 보호하기 위해 CPU의 실행 모드가 구분되어 있는 것이다. 이렇게 구분된 Mode를 하드웨어 단에서 인식하고, 수행하려는 Instruction이 적절한 Mode에서 이뤄지는지에 따라 실행 여부가 갈리게 된다.
시스템 상에서 이뤄지는 Kernel 단위의 연산들은 File I/O, Device I/O, 프로세스 생성 등이 있다.
Kernel Mode의 프로세스는 Instruction에 대해서 모든 권한을 갖고 있으며, 대표적으로는 운영체제가 이에 해당된다. 즉, 운영체제는 I/O 장치 제어 등 시스템 상에서 처리해야 하는 모든 Instruction을 하드웨어에게 요구할 수 있다.
User Mode의 프로세스는 대체적으로 사용자에 의해 구동된 어플리케이션이며, Instruction에 대해 범용적인 권한을 갖고는 있지만 Kernel Mode 만큼의 권한을 갖지는 못한다.

2. 시스템 콜

따라서 User Mode의 프로세스가 자식 프로세스를 만들고 싶다거나, R/W 작업을 수행하고 싶다거나, 파일을 열고 닫는 등의 작업을 수행하고 싶다면, 해당 Mode로는 하드웨어 단에서 거절되기 때문에 적절한 조치가 필요하다. 해당 작업들은 Kernel Mode의 프로세스에서만 가능하기 때문에, 대체적으로 운영체제에게 해당 작업을 요청하여 서비스를 제공 받게 된다. 이를 실행 모드 전환 (Execution Mode Switch)라 한다.
Kernel Mode에게만 제공되는 Instruction들을 이용하기 위해 운영체제는 해당 서비스들을 요청할 수 있도록 통로를 제공하는데, 이들이 곧 시스템 콜이 된다. User Mode의 프로세스가 시스템 콜을 호출하게 되면, User Mode의 프로세스가 요청한 대로 운영체제가 수행한 뒤 User Mode로 복귀하는 식으로 실행 모드 전환이 이뤄진다. 이와 같은 시스템 콜에는 open, write, shm, fork 등이 있다.
이전 항목에서 Context Switch시스템 콜에 의한 것이라고 했었는데, 이를 User ModeKernel Mode로 표현하면 위 그림과 같다는 것을 짐작할 수 있다.

3) Trap & Interrupt

TrapInterrupt는 이벤트 처리 기법이라는 공통점이 있지만, 이벤트 발생 요인과 처리 방법이 다르다. Trap은 동기적으로 이벤트를 처리하는 기법이며, Interrupt는 비동기적으로 이벤트를 처리하는 기법임을 명심해야 한다.

1. Trap

Trap은 주로 시스템 콜을 처리하는데 이용된다. 즉, Interrupt와는 달리 주로 현재 처리하고 있는 프로그램에 의해서 발생하게 된다. 이와 같이 발생한 이벤트는 Trap Handler에 의해 처리된다. Trap Handler에서는 Interrupt Handler와 비슷하게 Trap Service Routine이 존재하지만, Interrupt와 달리 동기적으로 이벤트를 처리하므로 현재 처리하고 있는 프로그램에 대한 Context를 저장할 필요도 없고 복원할 필요도 없다. 따라서 Trap이 발생하게 되어 Trap Handler가 특정 동작을 수행하고 나면, SP (Stack Pointer)PC (Program Counter)만을 이용하여 기존에 수행하던 동작으로 복귀할 수 있게 된다.

2. Interrupt

Interrupt는 주로 네트워크의 Packet 도착 혹은 I/O에 대한 이벤트를 처리하는데 이용된다. InterruptTrap과 달리 현재 처리하고 있는 프로그램에 의해 발생하는 것이 아니라 특정 하드웨어에 의해 발생하게 된다. 따라서 Interrupt는 하드웨어의 우선 순위에 따라 우선 순위를 가지게 되고, 하드웨어들이 동시에 Interrupt를 걸어도 적절히 처리가 가능하게 된다. 이와 같이 발생한 이벤트는 Interrupt Handler에 의해 처리된다. Interrupt Handler에서는 Interrupt Service Routine를 통해 이벤트를 처리하게 되는데, Interrupt를 처리한 뒤 복귀해야 하는 프로세스가 현재 프로세스가 아닐 수 있기 때문에 Interrupt Service Routine 진입 전에 반드시 Context에 대한 기록이 요구된다. Interrupt에 대한 처리를 마치면 저장된 Context를 복원하여 중단된 시점부터 다시 프로세스를 처리하게 된다.

3. 특징

Trap의 경우에는 Trap Service Routine 내에서 처리 도중에 Interrupt를 받을 수도 있지만, Interrupt의 경우에는 Interrupt Service Routine 내에서 처리 도중에 Inetrrupt를 받을 수 없게 되어 있다. 이는 InterruptDepth가 깊어짐에 따라 하나의 Interrupt가 끝나는데 긴 시간이 요구되는 구조가 될 수 있기 때문이다. 따라서 Interrupt를 처리할 때 다른 Interrupt들도 처리할 수 있도록 Interrupt Serivce Routine은 최대한 짧게 수행되도록 설계 되어 있다.
Trap은 프로세스의 Context를 저장하지 않아도 된다는 면에서 Interrupt보다 가볍지만 Trap에 대한 처리가 완료될 때까지 Block된다는 특징이 있다. InterruptTrap의 반대의 특징을 갖고 있다고 보면 된다.
만일 Interrupt가 동시에 발생하면 우선 순위에 따라 처리한다고 했는데, 동일한 우선 순위를 가진 Interrupt를 받게 되면 운영체제와 하드웨어에 의해 하나의 Interrupt를 처리하고 나머지 Interrupt는 저장해두거나 무시하게 된다.

4) 쓰레드?

1. 쓰레드와 프로세스

프로세스가 운영체제에 의한 스케줄링의 단위였다면, 실제로 이들의 처리 단위는 쓰레드가 된다. 모든 프로세스들은 Main Thread라는 적어도 하나의 쓰레드를 갖고 있고, 프로세스는 쓰레드 단위로 처리된다.
쓰레드가 기본적으로 프로세스가 처리되는 기본 단위라는 점이 잘 와닿지 않는다면, 1개의 쓰레드가 곧 1개의 실행 흐름이라고 이해해도 무방하다. 즉, 쓰레드는 프로세스를 구성하는 프로세스보다 작은 단위의 실행 흐름이다.
프로세스는 서로 다른 프로세스가 각각 다른 메모리 공간을 점유하고, 이들은 운영체제로부터 Protection Domain을 지원받음으로써 공간의 독립성을 유지하게 된다. 반면에 프로세스를 구성하는 쓰레드의 경우에는 각 쓰레드가 가진 메모리 공간이 Protection Domain을 지원받지 않기 때문에 각 쓰레드가 서로의 메모리 공간을 읽고 쓰는 등의 행위가 가능하다.
하나의 쓰레드로 구성된 하나의 프로세스는 운영체제에 의해 한 번의 제어를 받아 단일 흐름으로 작업을 처리하게 되지만, 이 프로세스를 여러 흐름으로 나누어 다수의 쓰레드를 두게 되면 사용자의 환경에 따라 병렬적으로 작업을 완료할 수 있다.
따라서 병렬성을 잘 보장하도록 프로세스 내에 쓰레드 처리를 하게 되면, Cooperative Process와 달리 값 비싼 IPC가 요구되지 않을 뿐더러, 값 비싼 Context Switch가 자주 요구되지 않을 수도 있다. 즉, 여러 프로세스가 협업하는 방식의 프로그램을 여러 쓰레드가 작업하도록 만듦으로써 프로세스보다 적은 비용으로 동일한 기능을 하게 만들 수 있다. 단, 프로세스 내의 쓰레드가 동일한 메모리 공간을 공유하고 Protection Domain이 지원되지 않기 때문에 이에 대한 동기화에 신경 써야한다.

2. 프로세스 당 쓰레드의 수

동기화 이전에 적절한 병렬성을 보장 받기 위해선 얼만큼의 쓰레드를 두는지도 중요하다는 것을 알 수 있는데, 실제로 얼만큼의 쓰레드를 두는 것이 바람직한 것일까? 몇 문단 위에서 사용자의 환경에 따라 병렬적으로 작업을 수행할 수 있다고 했는데, 이는 머신이 처리할 수 있는 논리 코어에 의존적이다. 예를 들어 8코어 16쓰레드의 CPU를 사용한다고 하면, 한 번에 16개의 쓰레드를 처리할 수 있다. (물론 Kernel에서 쓰레딩을 지원해야 이와 같은 기능이 지원되는 것인데 아래의 User-Level 쓰레드와 Kernel-Level 쓰레드에서 이에 대해 다룬다.)
여기서 CPU의 8코어 16쓰레드의 16쓰레드는 프로세스가 처리하는 쓰레드와 별개이다. CPU 스펙의 8코어 16쓰레드에서의 16 쓰레드가 곧 논리 코어로 작동한다.
언급된대로 단순히 논리 코어 개수에 맞게 쓰레드를 생성하면 간단하게 해결되는 것 같지만 실제로는 그렇지 않다. 컴퓨터의 동작에는 CPU에만 의존하는 것이 아니라 메모리, 디스크 등 다양한 하드웨어에 의존하게 된다. 만약 서버 작업에서 DB를 참조하여 디스크 내의 데이터를 찾아내는 식의 디바이스 타임을 많이 요구하는 작업이 다수 있다면, 해당 작업에 대해서는 CPU 연산을 요구하지 않으므로 해당 CPU는 다른 쓰레드를 처리할 수 있게 된다. 만일 정확히 논리 코어만큼의 쓰레드만 존재한다면, 각 쓰레드를 점유하고 있는 논리 코어는 디바이스 타임만큼 유휴 상태로 있게 된다. 즉, 디바이스 타임을 고려하여 쓰레드를 생성해야 한다.
프로그램 내에 처리해야 하는 작업들이 디바이스 타임을 요구하지 않는다면, 논리 코어의 수만큼 쓰레드를 두는 것이 적합하다. 반면에 프로그램 내에 처리해야 하는 작업들이 디바이스 타임을 요구한다면, 디바이스 타임에 비례하여 쓰레드를 두는 것이 적합하다. 예를 들어 프로그램 내에서 14\frac {1}{4}디바이스 타임을 요구하지 않는 작업이고 34\frac {3}{4}디바이스 타임을 요구하는 작업과 같은 식이라면, 논리 코어의 3배만큼의 쓰레드를 두는 것이 적합하다.
물론 프로세스 간의 Context Switch 보다 쓰레드 간의 Thread Switch가 더 가볍다고는 하지만, 처리할 수 있는 논리 코어 수보다 쓰레드의 수가 더 많으면 쓰레드를 처리하는 시간보다 Thread Switch에 더 많은 시간을 사용하면서 CPU 처리량은 낮아지는 모습을 볼 수 있다. 즉, 쓰레드 수가 많을수록 CPU의 활용량이 높아지긴 하나 이것이 곧 처리량이 높아지는 것이 아님을 명심해야 한다.
Thread SwitchContext Switch 보다 더 가벼운 이유는 동일한 프로세스 내의 쓰레드들은 Code Segment, Data Segment 및 프로세스 내에서 열어둔 파일 등에 대해서 공유하기 때문이다. 따라서 각 쓰레드의 Stack에 대해서만 교체하면 되므로 상대적으로 Context Switch 보다 가볍다고 볼 수 있다. 이 때 각 쓰레드는 서로 실행할 Instruction이 다르기 때문에 별도의 PC (Program Counter)를 갖고 있다.

3. 쓰레드 실행에 필요한 자료구조

생성된 쓰레드들 중 어떤 것을 실행할지에 대해 구분할 필요가 있으므로, 쓰레드 ID가 필요하다.
쓰레드는 프로세스의 여러 메모리 영역을 공유하지만, 각 쓰레드의 Stack은 분리되어 있다.
쓰레드마다 각기 다른 실행흐름을 갖기 때문에 각 쓰레드는 별도의 PC가 필요하다.
마찬가지로 별도의 PC를 갖고 있기 때문에 각 쓰레드마다 연산은 달라질 수 있다. 이에 따른 별도의 Register Set이 필요하다.
각 쓰레드가 사용하는 Register Set의 값들은 Context Switch 혹은 Thread Switch에 따라 그 값이 저장되었다가 복원되었다를 반복하게 되는데, 이 때문에 동일한 Physical Register Set를 사용하더라도 쓰레드마다 서로 다른 Register Set을 쓰는 것처럼 보이게 되는 것이다. 그렇다면 Physical Register Set은 얼만큼 존재하는 것일까? 실제로 프로세서들은 코드 단에서 사용할 수 있는 Physical Register Set보다 더 많은 Physical Register Set들을 갖고 있다. 이들은 코어 단위로 존재하기 때문에 서로 다른 코어를 점유하고 있는 쓰레드의 경우, Physical Register Set 마저도 별도로 점유하게 되는 것을 의미한다.

5) User-Level & Kernel-Level

1. 특징

쓰레드에는 User-Level 쓰레드와 Kernel-Level 쓰레드와 같이 2가지 종류로 나뉜다. 사용자들이 대체적으로 주로 사용하는 쓰레드는 User-Level 쓰레드이며, 별도로 속성에 대한 설정을 하지 않은 채로 쓰레드를 생성하게 되면 User-Level 쓰레드를 이용하게 된다. 이는 쓰레드를 지원하는 주체에 따라서 나뉘게 된다.
이는 CPU 실행 모드인 User ModeKernel Mode와는 별개라는 점을 유의하자.
User-Level 쓰레드의 경우에는 Kernel 위에서 지원되는 쓰레드이며, 일반적으로 User-Level의 라이브러리를 통해 구현된다. 따라서 라이브러리를 이용하여 쓰레드를 생성하게 되고, 이렇게 생성된 쓰레드는 동일한 메모리 영역을 공유한 채로 생성된다.
반면에 Kernel-Level 쓰레드의 경우에는 운영체제에서 쓰레딩을 지원하는 경우 이용할 수 있다. Kernel-Level 쓰레드는 이름에서도 알 수 있듯이 Kernel 내에서 사용할 쓰레드를 의미하며, 주로 스케줄링 등을 관리하기 위해 사용된다.

2. 동작 방식

두 종류의 쓰레드는 용도가 서로 다르기 때문에 각각의 입장에서 장점과 단점이 존재한다. User-Level 쓰레드는 동일한 메모리 영역에서 생성되고 관리되기 때문에 상대적으로 Kernel-Level 쓰레드보다 속도가 빠르다. 하지만 운영체제에서 쓰레딩을 지원하지 않아 Kernel-Level 쓰레드를 두는 것이 불가능하다면, KernelUser-Level의 쓰레드를 하나의 프로세스로 인식하기 때문에 User-Level 쓰레드들 중 하나에서 시스템 콜과 같은 Trap이 발생했을 때 나머지 쓰레드들 역시 Block된다는 단점이 있다.
운영체제에서 쓰레딩을 지원한다면 Kernel-Level 쓰레드를 이용할 수 있게 되고, 해당 쓰레드가 스케줄링에 관여되는 만큼 User-Level 쓰레드의 시스템 콜 호출에 따른 Block 상태의 단점을 보완할 수 있다. User-Level 쓰레드가 시스템 콜을 호출하여 Block이 발생하더라도 Kernel 내에서는 다른 Kernel-Level 쓰레드를 실행함으로써 다른 User-Level 쓰레드를 맡으면서 전체적으로는 Block이 발생하지 않게 할 수 있다. 또한 Kernel-Level 쓰레드는 스케줄링에 직접적으로 관여된다고 했으므로, 프로세싱에 이용될 여러 코어들이 있다면 각 Kernel-Level 쓰레드를 코어들에게 할당되면서 유휴 코어가 없도록 할 수 있다. 다만, User-Level 쓰레드에 비해 생성과 관리가 느리다는 단점이 있다.
Running 상태의 프로세스들이 보유하고 있는 각 User-Level 쓰레드들은 스케줄링을 위해 Kernel-Level 쓰레드를 점유하고자 한다. 즉, 운영체제에서는 Kernel-Level 쓰레드가 스케줄링을 위한 하나의 프로세스이면서 동시에 하나의 처리 단위이기 때문에, Kernel-Level 쓰레드를 어떻게 구성하느냐가 성능과 직결될 수 있다. 이와 같은 User-Level 쓰레드와 Kernel-Level 쓰레드의 구성을 Model이라고 한다.
위 내용을 통해 알 수 있듯이, 두 종류의 쓰레드는 택일로써 존재하는 것이 아니라 운영체제가 쓰레딩을 지원한다면 두 종류의 쓰레드가 서로 맞물리며 동작하는 것을 알 수 있다. 동일한 프로세스 내에 존재하는 여러 User-Level 쓰레드들은 Kernel-Level 쓰레드들에 Mapping되어 동작한다. 여러 User-Level 쓰레드들이 하나의 Kernel-Level 쓰레드에 Mapping 될 수도 있고, 여러 Kernel-Level 쓰레드에 Mapping이 될 수도 있다. 이는 운영체제의 Model에 따라 Mapping이 달라질 수 있다. Model에 대해선 아래에서 다룰 것이다.

3. 참고

Kernel 내부에서 사용할 쓰레드를 두겠다는 것은 기존에는 Interrupt를 받지 않고 처리만 하던 KernelTrap에 따른 Block을 만들지 않기 위해 Interrupt를 받는 것도 허용하겠다는 얘기가 된다. 이에 따른 동기화가 요구되므로 User-Level보다 복잡한 구조를 갖는다. Kernel-Level 쓰레드는 스케줄링을 위해 작업의 원자성을 고려하여 Interrupt를 받을 수 있는 특정 구간을 둬야하고, 이러한 구간을 Preemption Point라 한다. Preemption Point를 많이두면 즉각적으로 Interrupt에 반응할 수 있겠지만 그만큼 확인하는 과정에서 시간과 자원을 요구받게 되고, 반대로 듬성듬성 두면 즉각적인 Interrupt의 반응 안 되지만 작업에 대한 방해를 상대적으로 덜 받게 된다. 따라서 이와 같은 Preemption Point는 구현하는 사람의 관점에 따라 달라질 수 있는 예술의 영역이라 볼 수 있다.

6) Model

ModelUser-Level 쓰레드와 Kernel-Level 쓰레드의 Mapping 관계를 의미한다.

1. Many-to-One

Many-to-One의 경우 여러 User-Level 쓰레드가 하나의 Kernel-Level 쓰레드로 Mapping 되는 Model을 의미한다. 주로 운영체제가 쓰레딩을 지원하지 못하는 시스템에서 사용된다. 해당 Model은 한 번에 하나의 Kernel-Level 쓰레드만 Kernel에 접근할 수 있기 때문에, 시스템 콜을 호출하려는 User-Level 쓰레드가 Kernel-Level 쓰레드에 Mapping 되면 나머지 User-Level 쓰레드들은 Block 되므로 진정한 Concurrency는 지원하지 못한다. Kernel의 입장에서는 Mapping된 여러 User-Level 쓰레드들을 하나의 프로세스로 취급하기 때문에 멀티 프로세싱 환경이더라도 여러 프로세스의 동시 처리는 불가능하다.

2. One-to-One

One-to-One은 사용하고 있는 User-Level 쓰레드들을 그대로 Kernel-Level 쓰레드에 Mapping 하는 Model을 의미한다. 해당 Model을 이용하면 Many-to-One에서 문제가 되었던 User-Level 쓰레드들이 Block 되는 현상을 해결할 수 있다. 각 User-Level 쓰레드들이 Kernel-Level 쓰레드로 Mapping 됨에 따라 Kernel 입장에서는 각 User-Level 쓰레드를 별개의 프로세스로 취급하기 때문에 시스템 콜 호출에도 Block 되지 않고 동시적으로 처리할 수 있게 되는 것이다. 따라서 One-to-One은 멀티 프로세싱 환경의 이점을 챙길 수 있다는 장점이 있지만, 그 이면에는 User-Level 쓰레드의 수 만큼 Kernel-Level 쓰레드를 두어야 한다는 단점이 있다. Kernel-Level 쓰레드도 한정된 자원이기 때문에 무작정 생성해둔다고 모두 이용할 수 있는 것은 아니므로, 그 개수에 대한 고려가 동반된 Model이 필요하다.

3. Many-to-Many

Many-to-Many는 사용하고 있는 여러 User-Level 쓰레드들을 Kernel에 존재하는 여러 Kernel-Level 쓰레드로 Mapping 하는 Model을 의미한다. 일반적으로 Many-to-ManyKernel-Level 쓰레드는 User-Level 쓰레드와 동일하거나 적은 수 만큼 생성되어 적절히 스케줄링되므로 One-to-One과 같이 쓰레드 개수에 대해 고민할 필요가 없다. 또한 User-Level 쓰레드에서 시스템 콜을 호출한다고 해도 나머지 User-Level 쓰레드들은 Block되지 않으므로 Many-to-One의 문제에 대해서도 고민할 필요가 없다. 따라서 해당 Model을 이용하면 Many-to-OneUser-Level 쓰레드에 대한 Block 문제와 One-to-One의 한정된 자원 문제를 모두 해결할 수 있다. 이와 같은 Model은 프로세스 당 사용할 수 있는 Kernel-Level 쓰레드에 대해 최대 개수를 따로 정해둠으로써 운용된다.

7) 운영체제의 변화와 이슈

쓰레드에 대한 개념이 정립되기 이전의 운영체제는 프로세스 기반으로 동작했다. 하지만 쓰레드에 대한 개념이 정립되면서 기존의 프로세스와 관련된 시스템 콜에 대한 Semantics를 재고할 필요성이 생겼다. 그리고 시스템 콜 뿐만 아니라 쓰레드의 종료에 대해서도 여러 관점이 동반되었다. 또한 쓰레드를 효율적으로 사용하기 위한 방법이라든가, 멀티 쓰레딩을 위해 각 쓰레드간 통신하는 방법 등 현재 운영체제는 여러 부분들에 대해 의미를 부여하면서 발전해왔다. 운영체제의 변화들은 여러 운영체제의 방향성에 따라 각각 다르게 발전해왔기 때문에, 어떤 부분들을 고민하게 되었는지 정도를 짚어볼 것이다.

1. 시스템 콜

여러 시스템 콜 중에서도 특히 fork에 대한 고민이 주요하다. fork의 경우에는 단일 쓰레드 상에서 호출 시에는 기존 fork와 크게 다를 것 없다. 하지만 멀티 쓰레딩 환경에서 fork가 호출된 경우, 모든 쓰레드들을 복사하여 새로운 프로세스를 만들 것인지 fork를 요청한 쓰레드만 복사하여 새로운 프로세스를 만들 것인지에 대한 고민이 수반된다.
위와 같이 fork에 대한 두 방법의 고민이 수반되는 이유는 exec 함수 때문이다. exec의 경우 현재 프로세스를 새로운 프로세스로 교체하면서 처리되기 때문에, fork를 통해 모든 쓰레드를 복사하여 프로세스를 생성한 경우에 exec을 호출하면 모든 쓰레드들이 교체된다. 따라서 어차피 교체될 쓰레드들에 대한 복사는 불필요하므로 fork를 하고 exec을 수행하는 경우에는 fork를 요청한 쓰레드만이 복사되어 프로세스를 생성하는 것이 바람직하다. 반대로 exec을 수행하지 않는 경우라면 모든 쓰레드의 복사가 필요할 수도 있다. 이와 같은 문제를 해결하기 위해 Linux 상에서는 2가지 버전의 fork를 만들어 각각의 경우를 처리할 수 있도록 해결하였다.

2. Cancellation

Cancellation이라고 함은 쓰레드의 종료이긴 하나 외부로부터 쓰레드의 작업이 중지된 경우를 의미한다. 이는 구동 중인 프로세스의 종료를 의미하는 것은 아니다. 멀티 쓰레딩 환경에서 Cancellation의 고민이라 함은 하나의 쓰레드에서 중지 명령을 내렸을 때, 다른 쓰레드의 작업을 모두 중지 시킬 때 나타난다.
하나의 쓰레드를 중지 했을 때 모든 쓰레드가 종료되는 대표적인 예로는 웹 브라우저에서 이미지를 읽어오는 과정에서 사용자가 그 작업을 중지시키는 경우가 된다. 해당 상황에서는 이미지를 읽어오는 모든 쓰레드들이 중지되어야 할 것이다. 이 때, 이미지를 읽어오는 쓰레드 외에도 해당 웹 브라우저에서 작업 중인 다른 쓰레드들이 있다고 가정해보자. 이미지를 읽어오는 작업을 중지했다고 해서, 관련 쓰레드들을 모두 종료하는 것에 아무런 문제가 없는지가 고민의 포인트이다.
해당 상황에서는 자원에 대한 문제가 발생할 수 있다. 만일 이미지를 읽어오는 쓰레드들에게 할당된 어떤 자원을 관련 쓰레드외에 다른 쓰레드들이 이용하고 있는 상황이라면, 해당 쓰레드들을 모두 종료하는 행위가 종료와 함께 쓰레드 내의 모든 자원 반환을 야기하므로 문제가 될 수 있다. 이미지를 읽어오는 쓰레드 외의 나머지 쓰레드들은 이미 반환된 자원에 대해서 참조를 일으킬 수 있다는 것이다.

3. Thread Pool

쓰레드의 잦은 생성과 소멸이 반복되는 상황에서 쓰레드의 생성은 실제로 쓰레드를 동작하는 시간보다 긴 시간이 소요되는 경우가 많다. 그리고 쓰레드의 생성 자체는 시스템 상의 자원을 요구하기 때문에, 시스템의 동작을 보장할 수 있도록 최대 쓰레드 개수에 대한 제한 역시 필요하다.
위 2가지에 대한 해결 방안으로 Thread Pool이 제시되었다. Thread Pool을 둠으로써 정해진 수만큼의 쓰레드들을 Pool에 미리 할당해두고 이용하게 된다. 따라서 새로운 쓰레드가 필요하다면 Pool에서 가져오고, 쓰레드에 대한 작업이 끝나면 바로 소멸 시키는 것이 아니라 다시 Pool에 넣는 식으로 운용하게 된다.
Thread Pool의 동작 덕분에 제한된 수의 쓰레드를 두면서 시스템 상의 부하를 줄일 수 있을 뿐 아니라, 쓰레드 생성에 대해 소요되는 시간에 대해 득을 볼 수 있다. Thread Pool에 얼만큼의 쓰레드를 둘지는 시스템 혹은 메모리 혹은 수행할 작업의 수 등을 통해 추정치로 결정한다.

4. IPC

멀티 프로세싱 환경에서는 프로세스 간의 통신이 필요했던 것처럼, 멀티 쓰레딩 환경에서도 쓰레드 간의 통신이 필요할 수 있다. 멀티 프로세싱의 경우에는 공유 메모리 기법 혹은 메세지 교환 기법 등 다양한 방식의 IPC가 이용되었는데, 멀티 쓰레딩에서는 쓰레드 간의 통신을 어떻게 해결할 수 있었을까?
동일한 프로세스 내의 쓰레드 간의 통신에 대해서는 공유 메모리 기법을 주로 이용했는데, 이는 각 쓰레드들간 공유되는 메모리 영역이 있어서 메세지 교환 기법에 비해 훨씬 효율적이기 때문이다. 따라서 멀티 프로세싱에서 활용하는 메세지 교환 기법IPC는 자연스럽게 최소화 되었고, 멀티 쓰레딩에서의 IPC는 멀티 프로세싱에 비해 더 좋은 성능을 보여왔다. 다만 이와 같이 공유 메모리 기법을 이용하는 경우에는 공유되는 자원에 대한 동기화가 요구되는데, 이는 Kernel의 몫이 아니라 사용자의 몫이다.
동기화의 어려움 때문에 약간의 오버헤드를 감수하고 시그널, 파이프, 메세지 큐, 소켓 등의 메세지 교환 기법을 이용하는 방법도 있지만, 이에 대해서는 추가적인 디자인 이슈가 요구된다. 예를 들어 시그널을 보냈을 때, 여러 쓰레드들 중 어떤 쓰레드가 받을 것인지에 대한 고민이 동반된다. (쓰레드를 특정하여 보낼 수 있으면 좋겠지만, 메세지 교환 기법IPC는 모두 프로세스를 특정하는 방식으로 구현되어 있다.)
만일 다른 프로세스 내의 쓰레드와 통신을 해야하는 경우가 있다면, 이는 멀티 프로세싱의 IPC와 비슷한 성능을 보이게 된다. 이러한 통신이 발생하는 경우가 아예 없지는 않지만, 빈번하게 발생한다면 멀티 쓰레딩의 장점을 살릴 수 있도록 프로그램의 설계를 다시 한 번 살펴보는 것이 좋다.

3. Synchronization

Philosophers를 풀기 위해 식사하는 철학자 문제에 대한 소개도 마쳤고, 여기서 나오는 대략적인 개념들도 살펴보았다. 결국에는 동기화를 위한 모든 개념들에 불과한데, (식사하는 철학자 문제에서 주어진 코드들이 의사 코드이기도 했고) 정확하게 왜 동기화가 필요한지 이해하기 힘들 수 있다. 이에 대해서 설명하기 위해 간단히 용어 몇 개를 정리하면서 그 내용들을 알아보자.

1) Data Race

동기화라 함은 프로세스 내에서 사용되는 데이터의 일관성 (Data Consistency)를 보장하는 행위이다. 데이터의 일관성이 필요한 이유는 해당 데이터가 여러 프로세스 혹은 쓰레드에 의해 공유되고 이를 조작하려는 행위가 있기 때문이다. 주어진 상황처럼 데이터가 경쟁 상태로 존재하는 것을Data Race라고 부른다. 프로세스 간 공유된 데이터가 동기화 되지 않으면 Data Race 때문에 데이터의 일관성이 유지되지 않는지 확인해보자.
/* ** Shared Data Balance */ Balance = 100; /* ** This is A Process (Balance is Shared) */ Balance += 200; /* ** This is B Process (Balance is Shared) */ Balance += 300; /* ** Where to Branch? */ if (isBalanceEqual(600)) return (CONSISTENT); else return (INCONSISTENT);
C
복사
Balance를 조정하는 프로세스는 AABB가 있다. 만일 Balance를 조정하는 구문이 주어진 코드처럼 프로세스 별로 나뉘어 있는 것이 아니라 한 프로세스 내에서 순차적으로 주어져 있다면, 크게 문제가 되지 않는 것은 자명하다. Balance가 일관성이 없다는 것을 보이기 위해서는 Context Switch를 고려해야 한다.
단순히 주어진 코드를 보았을 때는 Context Switch를 고려한다 하더라도 각 프로세스가 갖고 있는 한 줄의 코드는 별 문제가 없어 보인다. 프로세스 AA에서 먼저 Balance를 조정한 후 Context Switch가 일어나서 프로세스 BB를 처리하든, 반대로 프로세스 BB에서 먼저 Balance를 조정한 후 Context Switch가 일어나서 프로세스 AA가 처리되든 그 결과는 600으로 동일한 것처럼 보이기 때문이다. 이는 Context Switch의 발생을 코드 한 줄 단위로 보았기 때문이다. 우리가 알고 있는 코드 한 줄은 실제로 여러 Instruction으로 구성되어 있기 때문에, 코드 한 줄은 결코 Atomic하지 않다.
Atomic? 원자성을 의미하는 Atomic이라는 성질은 원자라는 문자 그대로 기능적으로 분할할 수 없는 성질을 의미한다. 따라서 원자성 조작 (Atomic Operation)이라 함은 Atomic 성질을 보장하기 위한 의도적인 조작을 의미한다. 프로그램 상에서 Atomic하여 기능적으로 분할할 수 없다는 것의 판단 기준은 Interruptible이다. 원자성이 보장된 코드들은 Interrupt를 받지 않는다. InstructionAtomic하기 때문에, 이를 수행 중에는 Interrupt가 발생하지 않는다. 반면에 코드 한 줄은 여러 Instruction으로 구성되기 때문에 Atomic하지 않다. 따라서 코드 한 줄을 수행하다가 Interrupt가 발생할 수 있다. Context SwitchDispatcherInterrupt에 의해 발생하므로, 코드 한 줄 수행 중에도 Context Switch가 발생할 수 있음을 알 수 있다.
/* ** This is A Process */ Register1 = Balance; Register1 = Register1 + 200; Balance = Register1; /* ** This is B Process */ Register2 = Balance; Register2 = Register2 + 300; Balance = Register2;
C
복사
Context Switch는 운영체제의 Dispatcher 호출에 따른 Interrupt에 의해 발생하는데, InstructionAtomic 하기 때문에 Instruction 도중에는 Interrupt가 발생하지 않으므로 Context SwitchInstruction 단위로 발생한다는 것을 알 수 있다. 따라서 기존의 Balance에 대한 코드가 위 코드 블럭과 같이 치환되어 처리된다고 했을 때, 프로세스 AA 혹은 BB의 어떤 Instruction 사이에도 Context Switch가 발생할 수 있다는 것이다. 위 Instruction들을 기반으로 Context Switch가 발생했을 때를 가정해보자.
/* ** Ti : Time Quantum i ** ** T0 : Process A / Register1 = Balance / [Register1 = 100] ** ** T1 : Process A / Register1 = Register1 + 200 / [Register1 = 300] ** ** T2 : Process B / Register2 = Balance / [Register2 = 100] ** ** T3 : Process B / Register2 = Register2 + 300 / [Register2 = 400] ** ** T4 : Process A / Balance = Register1 / [Balance = 300] ** ** T5 : Process B / Balance = Register2 / [Balance = 400] */
C
복사
주어진 코드 블럭에서 보이는 대로 스케줄링 되었을 때, 프로세스 AABalance300이고 프로세스 BBBalance400이 되어 데이터의 일관성에 문제가 생긴 것을 확인할 수 있다. 이와 같은 데이터를 동기화하기 위해 고안된 것이 Critical Section이다.

2) Critical Section

/* ** Entry Section ** Critical Section ** ** Exit Section ** Remainder Section */
C
복사
Critical Section이라 함은 여러 프로세스 혹은 쓰레드들이 공유하는 데이터들이 있을 때, 이를 접근하는 코드 영역을 의미한다. 이전 항목에서 보았듯, Critical Section에 대해서는 하나의 프로세스 혹은 쓰레드가 진입했을 때는 다른 프로세스 혹은 쓰레드가 진입해서는 안 된다. Critical Section에 대한 의사 코드는 위와 같다. Critical Section을 이용하여 예시에서 들었던 Balance와 문제에 대해서 동기화를 성공적으로 제공하기 위해선 아래 제시된 3가지 조건을 모두 만족할 수 있어야 한다. 이들 중에서도 특히 Mutual ExclusionProgress는 필수적이다.

1. Mutual Exclusion

하나의 프로세스 혹은 쓰레드가 Critical Section에 진입해있다면, 다른 프로세스들은 Critical Section에 진입할 수 없어야 한다.

2. Progress

Critical Section이 어떤 프로세스에게도 점유되어 있지 않고 Critical Section에 진입하려는 프로세스가 존재한다면, 그 중 한 프로세스는 Critical Section에 진입할 수 있어야 한다.

3. Bounded Waiting

어떤 프로세스가 Critical Section에 진입하고자 할 때, 해당 프로세스가 무한히 기다리지 않도록 대기 시간에 적절한 제한이 필요하다.

3) Synchronization

1. 두 프로세스를 위한 알고리즘

/* ** Shared Variables ** int turn; ** turn = 0; ** turn == 0 이라면, 프로세스 A가 Critical Section에 진입 ** turn == 1 이라면, 프로세스 B가 Critical Section에 진입 */ /* ** 프로세스 A */ while (turn != 0) ; Critical Section turn = 1; Remainder Section /* ** 프로세스 B */ while (turn != 1) ; Critical Section turn = 0; Remainder Section
C
복사
두 프로세스 간 동기화를 위해 위와 같이 turn 변수를 이용한 경우에는 Mutual Exclusion이라는 조건은 만족할 수 있지만, 나머지 두 조건을 만족하진 않는다. 프로세스 AA, 프로세스 AA, 프로세스 AA 와 같은 순서로 스케줄링 되는 경우에는 두 번째 프로세스 AA에서 turn 값이 0이 될 일이 없어 Progress가 되지 않는다.

2. 개선된 알고리즘

/* ** Shared Variables ** bool flag[2]; ** flag[0] = flag[1] = false; ** flag[0] == true 라면, 프로세스 A가 Critical Section에 진입 ** flag[1] == true 라면, 프로세스 B가 Critical Section에 진입 */ /* ** 프로세스 A */ flag[0] = true; while (flag[1]) ; Critical Section flag[0] = false; Remainter Section /* ** 프로세스 B */ flag[1] = true; while (flag[0]) ; Critical Section flag[1] = false; Remainder Section
C
복사
기존에 turn을 이용했던 방식을 개선하여 각 프로세스가 이용할 수 있는 flag 배열을 두었다. 위 예시는 이전 예시와 구조가 비슷하기 때문에 Mutual Exclusion을 만족하지만, 여전히 나머지 두 조건을 만족하지 않는다. 해당 예시에서는 이전 예시의 반례인 동일한 프로세스의 연속적인 스케줄링에는 문제가 없지만, 프로세스 AABB가 동시에 flagtrue로 바꾸게 되면 서로 while에서 정체되어 어떤 프로세스도 Critical Section에 진입하지 못하여 Progress가 되지 않는다.

3. Peterson Solution

/* ** Shared Variables ** int turn; ** bool flag[2]; ** turn = 0; ** flag[0] = flag[1] = false; ** turn == 1 이고 flag[1] == true 라면, 프로세스 A가 대기 ** turn == 0 이고 flag[0] == true 라면, 프로세스 B가 대기 */ /* ** 프로세스 A */ flag[0] = true; turn = 1; while (flag[1] && turn == 1) ; Critical Section flag[0] = false; Remainder Section /* ** 프로세스 B */ flag[1] = true; turn = 0; while (flag[0] && turn == 0) ; Critical Section flag[1] = false; Remainder Section
C
복사
Peterson Solution은 기존 두 방법에서 제시한 turnflag 배열을 모두 이용한 방법이다. 우선 이전 방법들과 마찬가지로 Mutual Exclusion은 만족한다. 또한 동일한 프로세스가 연속적으로 스케줄링 되더라도 flag 배열 덕분에 해당 부분에 대해서는 Progress에 문제가 없다. 이전 방안에서 문제가 되었던 서로 다른 프로세스가 동시에 flagtrue로 만드는 부분에 대해서도, 두 프로세스가 공유하는 turn이라는 변수 덕분에 turn 값을 0 또는 1 둘 중 하나의 값으로만 유지하여 while에서 정체되지 않도록 할 수 있다. 따라서 Progress를 만족시킬 수 있다. Progress를 만족하므로 Bounded Waiting은 적절히 제어할 수 있다.
/* ** 프로세스 A */ do { flag[0] = true; turn = 1; while (flag[1] == ture && turn == 1) ; Critical Section flag[0] = false; Remainder Section } while (1); /* ** 프로세스 B */ do { flag[1] = true; turn = 2; while (flag[2] == true && turn == 2) ; Critical Section flag[1] = false; Remainder Section } while (1); /* ** 프로세스 C */ do { flag[2] = true; turn = 0; while (flag[0] == true && turn == 0) ; Critical Section flag[2] = false; Remainder Section } while (1);
C
복사
Peterson Solution동기화를 위한 세 가지 조건을 모두 만족시킴에도 확장성에 있어서 한계점이 존재한다. 위 코드에 기재된 것처럼 3개 이상의 프로세스가 존재한다고 했을 때 Peterson Solution은 정상적으로 동작하지 않는 것을 확인할 수 있다.
위 코드에 대해선 대표적으로 turn 값 만으로 반례를 찾을 수 있다. turn 값에는 0 혹은 1 외에도 다른 값을 가질 수 있는데 비해, turn 값에 대한 고려 자체는 하나의 값으로 이뤄지므로 2개 이상의 프로세스가 Critical Section에 접근할 수 있게 된다. 따라서 Mutual Exclusion을 보장할 수 없다.
만일 Peterson Solution에서 요구되는 자료들을 수정하여 여러 프로세스에 대해 동작하는 것처럼 만든다고 하여도, 2개의 프로세스 간의 동기화가 아닌 그 이상의 프로세스에 대해서 완벽히 동작하는 것을 증명한다는 것은 굉장히 어려운 일이다. 따라서 동기화를 위해 Peterson Solution과 같이 코드 상의 해결 방안 외에 다른 갈래의 해결책이 필요하다.

4. Instruction Solution

Peterson Solution 이후에 제시된 동기화 방법 중 하나는 Critical SectionAtomic Operation으로 두어 Critical Section을 수행할 때는 Interrupt를 받지 않도록 만드는 것이었다. 이와 같은 해결책은 확장성 측면에서 Interrupt라는 Kernel 단위의 작업을 User 단위의 프로세스에서 제어하는 행위가 바람직하지 않다는 문제점이 있었다. 예를 들어 프로세스 내에 Critical Section으로 지정한 영역이 방대하다면 이는 곧 프로세스들의 대기 시간의 증가로 연결되어 스케줄링에 문제가 생긴다. 또한 Kernel-Level 쓰레드 도입에 따른 멀티 쓰레딩 환경에서 각 코어마다 Atomic Operation을 수행하면 Critical Section에 대한 동시 접근을 막을 방법이 없으므로 동기화를 보장하지 못하는 문제가 생긴다.
/* ** Acquire LOCK ** Critical Section ** ** Release LOCK ** Remainder Section */
C
복사
결과적으로 동기화를 위한 해결 방안은 Atomic을 보장한다는 것인데, 이전과 같은 Atomic 보장을 위한 직접적인 Interrupt 조작보다는 조금 더 원초적인 방법이 제시되었다. Critical Section 진입에 대한 알고리즘을 이전 방법들처럼 소프트웨어 상에서 해결하려면 복잡해지지만, 하드웨어 상에서 해결할 경우 비교적 간단하게 처리할 수 있다는 것에 착안하여 동기화를 위한 Instruction Solution이 제시되었다. 위 의사 코드에서 AcquireRelease에 해당하는 작업을 Instruction으로 두어 말 그대로 Atomic 하게 만든 것이다.
Critical Section에 진입하기 위한 권한을 획득하는 행위 (Acquire)LOCK, 반대로 Critical Section에서 나갈 때 권한을 넘기는 행위 (Release)UNLOCK이라 한다.
동기화를 위한 AtomicInstruction은 크게 2종류로, Test-and-SetSwap으로 분류된다. 각 Instruction의 알고리즘과 해결 방안은 아래와 같다. 이들을 잘 살펴보면, LOCK을 잡는 과정에서는 Context Switch가 발생하지 않으나 LOCK을 잡고 난 후에 한 프로세스가 Critical Section을 처리할 때는 Context Switch가 발생할 수 있다. 하지만 Context Switch 된 다른 프로세스는 LOCK을 갖고 있지 않기 때문에 Critical Section에 진입하지 못한 채로 Busy Waiting을 하게 된다. 즉, Instruction Solution이 훌륭하게 Mutual ExclusionProgress에 대한 확장성을 보장하지만, Bounded Waiting까지 해결해주지는 못 한다는 것이다.
Test-and-Set
Swap
Instruction Solution의 한계점은 어떻게 극복할 수 있을까? Bounded Waiting의 경우 동기화 문제에 따라 차이가 있을 수 있기 때문에 이들을 Instruction으로 처리하는 것은 분명 어려움이 있다. 그렇다면 이와 같은 해결을 사용자에게 맡겨야 하는데, 일반적인 사용자에게 이에 대한 해결을 기대하기에도 어려움이 있다. 따라서 동기화에 대해 보다 Primitive한 해결 방법이 요구된다. 많은 사람들이 알고 있는 mutexsemaphore 역시 시스템에서 제공되는 Primitive 중 하나이다.
물론 의도적으로 Bounded Waiting에 대해서 Busy Waiting을 허용하는 동기화 방법도 존재한다. mutex 혹은 semaphore와 같은 Primitive에 대해선 LOCK을 잡지 못한 프로세스는 Sleep 상태로 만든 뒤에 Context Switch를 하여 다른 프로세스를 처리하도록 두는데 반해, spinlock과 같은 PrimitiveSleep 상태로 만들어 Context Switch를 하는 것이 아니라 Busy Waiting을 하며 LOCK을 꾸준히 잡으려 한다. spinlock과 같은 방법들은 Context Switch가 일어나지 않는 만큼 연산에 득을 볼 수 있지만, 이와 같은 성능을 보장하기 위해선 Critical Section이 아주 짧아야 한다. (즉, Busy Waiting이 무조건 나쁜 것은 아니고 상황마다 다를 수 있다. spinlock의 경우엔 Busy Waiting이 아주 짧다는 근거를 통해 Bounded Waiting 조건이 만족된다.)

4. Synchronization Primitive & Deadlock

mutexsemaphore의 사용법은 아래 External Functions<pthread.h><semaphore.h>에 대해 정리한 링크가 있으므로 이를 참고하면 된다. 여기서는 mutexsemaphore와 같은 Primitive를 이해할 수 있는 개념만 다룬다.

1) Synchronization Primitive

우선 Primitive의 정의에 대해서 알아보자. Synchronization Primitive를 의미하는 Primitive는 동기화를 위한 소프트웨어 메커니즘을 의미하며, 주로 운영체제 단위에서 제공되는 서비스이다. Primitive를 이용하여 프로세스 혹은 쓰레드에 대한 동기화를 지원하는 것이 목적이며, 대체적으로 Instruction Solution에서 나왔던 것처럼 Atomic Operation을 포함한 Memory Barriers, Context Switch 등과 관련된 낮은 레벨의 메커니즘을 이용하여 만들어졌다.
mutex, event, condional variables, semaphore 등이 Primitive에 해당된다. 그리고 글에서 설명된 Critical Section 자체는 코드 실행을 위한 경로에 불과하고 동기화의 대상이기 때문에 Primitive를 의미하지 않는다. 결론적으로 이전에 제시된 동기화를 위한 해결 방법들 대신에 mutex, semaphore와 같이 제시된 Primitve를 이용하여 Critical Section을 보호하면 된다.
monitor 기법은 조금 더 높은 레벨의 동기화 도구이지만, 상황에 따라 Primitive로 취급되기도 한다. monitor의 대표적인 사례로는 JavasynchronizedDBtransaction 등이 있다. 그리고 영역을 의미하는 Critical Section가 아닌, 동기화를 위한 Primitive로써 Critical Section이라는 것도 존재한다.
/* ** Busy Waiting */ while (Until Acquire LOCK) ; Critical Section Release LOCK; Remainder Section
C
복사
위에서 명시된 것을 포함한 대부분의 Primitive들은 LOCK을 취득하지 못한 프로세스 혹은 쓰레드에 대하여 대체적으로 무작정 Busy Waiting을 하는 것이 아니라 Sleep 상태로 만들어 Sleep Queue에 보관한다. 이에 따라 Context Switch가 발생하면서 다른 프로세스 혹은 쓰레드를 처리하게 되므로 Busy Waiting을 통해 낭비되는 CPU 자원을 효율적으로 사용할 수 있게 만든다.
물론 Busy Waiting이 무조건 나쁜 것은 아니다. 아주 짧은 시간만 Busy Waiting을 하는 것이 보장되는 Critical Section 이라면 Context Switch를 하는 것보다는 Busy Waiting이 더 효율적일 수 있다. 해당 동작을 수행해주는 spinlock과 같은 Primitive도 있다.
이 때 Sleep 상태가 되는 것은 프로세스 혹은 쓰레드의 상태를 의미하는데, 이 때 Primitive가 사용하는 Sleep Queue는 스케줄러의 Sleep Queue와 별개라는 점을 유의해야 한다. 동기화를 위해 Sleep 상태가 된 프로세스 혹은 쓰레드를 스케줄링을 위한 프로세스들과 엮어버리면 관리가 급격히 복잡해지는 문제 때문에 스케줄링과 동기화는 서로 관여하지 않는 쪽으로 설계되었다.
그렇다면 LOCK을 취득하지 못하여 PrimitiveSleep Queue에 있는 프로세스 혹은 쓰레드들은 언제 깨어날 수 있을까? LOCK을 취득했던 프로세스 혹은 쓰레드가 LOCK을 해제하면서 PrimitiveSleep Queue에 있던 모든 작업들을 모두 깨워버림으로써 스케줄링 될 수 있도록 한다. 특정 작업을 하나를 골라 꺠우지 않고 Sleep Queue의 모든 작업을 깨우는 이유는 다음과 같다. 예를 들어 LOCK을 취득했던 프로세스가 직접 하나의 작업을 골라 깨우게 되면, 대상이 되는 작업이 오래 기다렸다 하더라도 Low Priority일 수도 있는 상황에 대해 유연한 처리가 되지 않기 때문이다. 이는 스케줄러가 처리할 수 있는 상황이므로 스케줄러의 책임으로 두어 적절히 스케줄링이 되도록 만든다.

2) Mutex

mutex라 함은 Mutual Exclusion의 약어로 mut + ex를 합친 말이다. mutex의 범위 자체는 프로세스 내로 한정되어 쓰레드를 대상으로 사용된다. 이 때 쓰레드들은 동일 프로세스 내의 쓰레드일 수 있고, Cooperative Process와 같이 다른 프로세스의 쓰레드 일 수 있다.
mutex에서 LOCK을 취득하는 행위를 lock, LOCK을 해제하는 행위를 unlock이라고 한다. mutex도 구현에 따라 천차만별이고 다양한 종류들이 있지만, 기본적으로 mutex는 쓰레드가 LOCK을 취득했을 때 쓰레드에 귀속되는 Locking 메커니즘에 근거하여 동작한다. 이에 따라 오직 LOCK을 가지고 있는 쓰레드만이 LOCK을 해제할 수 있다.
mutex에 대해 예시를 통해 이해할 수 있다. 식당 내에 화장실이 하나만 있으며, 화장실을 이용하기 위해선 열쇠가 반드시 필요하다고 해보자. 여기서 화장실 내의 작업들이 Critical Section이고, 화장실의 열쇠가 LOCK이며, 화장실을 이용하려는 사람이 쓰레드라고 볼 수 있다. 화장실을 이용하고 싶은 사람들은 열쇠가 있어야 이용할 수 있으므로, 화장실 열쇠가 쓰이고 있다면 열쇠를 얻을 때까지 기다려야 한다.

3) Semaphore

semaphore의 범위 자체는 시스템에 걸쳐 있기 때문에 파일 시스템 상의 파일로써 존재한다. 따라서 프로세스 혹은 쓰레드를 대상으로도 사용될 수 있다. semaphore는 크게 Binary SemaphoreCouting Semaphore로 나뉘며 이는 LOCK의 수가 단일인지 여럿인지에 따라 나뉜다. Binary SemaphoreLOCK의 수가 단일이므로 mutex처럼 사용할 수 있다.
mutex처럼 이용할 수 있다는 것이 mutex와 동일하다는 의미는 아니다.
semaphore에서 LOCK을 취득하는 행위를 wait, LOCK을 해제하는 행위를 signal이라 한다. mutexLocking 메커니즘에 의해 동작했다면, semaphoreSignaling 메커니즘에 근거하여 동작한다. 이는 LOCK을 취득했을 때 프로세스 혹은 쓰레드에 귀속되어 동작하는 방식이 아니다. 즉, LOCK 자체를 일종의 공유되는 자원으로써 사용하여, LOCK을 취득하지 않은 프로세스 혹은 쓰레드도 LOCK을 해제시킬 수 있다.
Signaling 메커니즘에서의 흔히 waitP, signalV라고 한다. PLOCK의 수를 감소시키는 decrement 연산이되고, VLOCK의 수를 증가시키는 increment 연산이다. PV 자체는 Instruction Solution에 기반하지만, 이를 호출하여 동작시키는 부분은 시스템 콜로써 이뤄진다.
semaphore 역시 예시를 통해 이해할 수 있다. 식당 내에 화장실이 정해진 수 만큼 존재하며, 화장실을 이용할 때는 별도의 열쇠는 필요 없지만 얼만큼의 화장실이 비어있는지 확인할 수 있는 패널이 있다고 해보자. 사람들이 화장실을 이용하려 해서 화장실을 점유했다면 패널의 값은 줄어들 것이고, 화장실을 다 이용하고 나온다면 패널의 값은 다시 늘어날 것이다. 여기서 화장실 내의 작업들이 Critical Section이 되고, 화장실의 점유 여부가 LOCK이며, 화장실을 이용하려는 사람이 프로세스 혹은 쓰레드가 된다. 화장실을 이용하고 싶은 사람들은 화장실이 비어있는지 패널을 통해 확인할 수 있고, 패널을 확인했을 때 화장실을 이용할 수 없는 상황이라면 화장실이 비워질 때까지 기다려야 한다.
예시에서 화장실이 하나라면 Binary Semaphore, 2개 이상이라면 Counting Semaphore로 볼 수 있다.

1. Binary Semaphore

do { /* ** P 연산 */ while (test_and_set(&LOCK)) ; Critical Section /* ** V 연산 */ LOCK = 0; Remainder Section } while (1);
C
복사
이전 항목에서 제시되었던 Instruction SolutionTest-and-Set을 통해 Binary Semaphore를 구현할 수 있다. Binary Semaphore의 경우에는 LOCK을 공유 자원으로 보되, 그 개수가 1개이므로 P에 대해선 1 (true)가 되고 V에 대해선 0 (false)가 되는 식으로 동작하게 된다. LOCK을 개수로 취급하면 PV 연산에 대한 값이 각각 01로 증감처럼 다룰 수 있겠지만, 현재 설명하고 있는 Binary SemaphoreTest-and-Set을 기반으로 동작하는 것을 전제하고 있으므로 LOCK을 자원의 수가 아닌 Critical Section 진입을 위한 대기 유무로 취급하기 때문에 PV 연산에 대한 값이 각각 1, 0으로 다룬다.
비록 mutex가 내부적으로 동작하는 메커니즘이 semaphore와 달라 LOCK을 이용하는 개념에 차이가 있기는 하나, mutex 역시 위의 Binary Semaphore처럼 동작한다.

2. Couting Semaphore

wait_operation() { P(&LOCK1); --C; if (C < 0) { V(&LOCK1); P(&LOCK2); } else V(&LOCK1); } signal_operation() { P(&LOCK1); ++C; if (C <= 0) V(&LOCK2); V(&LOCK1); } do { wait_operation(); Critical Section signal_operation(); Remainder Section } while (1);
C
복사
Counting Semaphore는 2개의 Binary Semaphore를 이용하여 구현할 수 있다. Critical Section 진입을 위한 Binary Semaphore 1개와 자원의 수를 동기화 하기 위한 Binary Semaphore 1개로 구성된다. 여기서 자원의 수는 C로 표현되었다. 그리고 Binary Semaphore에서의 P 연산V 연산은 각각 PV로 표현했고, 두 Binary Semaphore에서 사용하는 LOCKLOCK1LOCK2로 구분지어 표현했다.
Counting SemaphoreAtmoic한 것처럼 동작하지만, 실제로 Atomic한 것은 내부의 PV이므로 이들을 제외한 구문들에서 얼마든지 Interrupt가 발생할 수 있다.

3. 주의할 점

Counting Semaphore에서 주어진 코드의 wait_operation을 잘 살펴보면 ifelse 구문 모두 V(&LOCK1)을 수행함에도 불구하고 각각 V(&LOCK1)을 기재한 것을 볼 수 있다. 통합하지 않고 각각 기재한 이유는 LOCK을 조작하는 순서가 굉장히 중요하기 때문이다. 이와 같은 순서를 지키지 않으면 Deadlock이 발생할 수 있다. 결과적으로 PV가 각각 나뉘어 있기 때문에 잘못 사용하지 않도록 굉장히 주의해야 한다. PV에 대한 잘못된 사용은 Deadlock 문제 뿐만 아니라 동기화 자체에 문제를 야기할 수도 있다.
P→ Critical Section → P와 같이 LOCK을 풀어주는 V가 없으면, Critical Section 진입 후 나오는 것이 불가능하여 다른 프로세스에서 Critical Section 진입이 막히는 Deadlock이 발생할 수 있다.
V→ Critical Section → P와 같이 Critical Section 이전에 LOCK을 거는 행위가 생략되어 있으면, 여러 프로세스가 동시에 Critical Section에 진입 할 수 있게 되어 Mutual Exclusion 보장되지 않는다.
코드는 사람이 짜는 것이기에 얼마든지 PV에 대한 실수 가능성이 존재한다. 이에 따라 위에서 언급했던 것과 같이 monitor 기법처럼 더 높은 차원의 동기화 방법을 언어 단위에서 제공하기도 한다.

4) Deadlock

교착 상태 (Deadlock)은 2개 이상의 프로세스들이 LOCK을 얻기 위해 계속해서 기다리고 있는 상황을 의미한다. semaphore를 이용하여 위 그림과 같은 Deadlock 발생의 예시를 한 번 알아보자.
/* ** This is Process A */ do { wait(&LOCK1); wait(&LOCK2); ... Critical Section; ... signal(&LCOK1); signal(&LOCK2); ... Remainder Section ... } while (1); /* ** This is Process B */ do { wait(&LOCK2); wait(&LOCK1); ... Critical Section ... signal(&LOCK2); signal(&LOCK1); ... Remainder Section ... } while (1);
C
복사
작성된 코드를 살펴보면, 두 프로세스가 각 LOCK을 잡는 순서가 달라 충돌이 발생하는 것을 볼 수 있다. 운이 좋다면 Deadlock이 발생하지 않을 수 있지만, 스케줄링 순서 및 Context Switch에 따라 얼마든지 Deadlock이 발생할 수 있다. Deadlock 발생은 잘못된 wait, signal의 이용 등 LOCK을 잡는 순서에 의존적이기 때문에, Deadlock이 발생하는 상황에 대해 수학적인 검증이 가능하다. 검증 자체는 LOCK을 잡는 순서가 Partial Order를 만족하는지 확인하는 것으로 이뤄진다. 따라서 프로그래머들에게는 동기화를 위해 LOCK을 사용하는 행위가 Partial Order를 충분히 만족하는지 확인하는 습관이 요구되며, 이를 위한 LOCK의 순서에 대해 사전에 정의하는 행위가 요구된다.
예를 들어, A→B→C 순서로 LOCK을 잡아야 한다고 정의해보자. 어떤 프로세스에서는 A→C의 순서로 LOCK을 잡았을 때, 이는 Partial Order를 만족하므로 Deadlock에 걸리지 않는다. 하지만 C→A의 순서로 LOCK을 잡는 프로세스가 있다면, 이는 Partial Order에 위배됨에 따라 Deadlock을 일으키는 요인이 된다.
Partial Order?
그렇다면 Deadlock을 해결할 수 있는 방법은 무엇이 있을까? Deadlock 해결을 위한 방법은 크게 예방 (Prevention), 회피 (Avoidance), 탐지 및 회복 (Detection and Recovery)으로 나뉜다. 이들에 대해서 알아보자.

1. 예방 (Prevention) → Deadlock을 일절 허용하지 않음

예방Deadlock이 발생하는 조건들과 관련되어 있다. Deadlock상호 배제 (Mutual Exclusion), 점유 대기 (Hold and Wait), 비선점 (Non-Preemption), 순환 대기 (Circular Wait)이 모두 만족되어야 발생한다. 예방이라는 행위는 위 4가지 조건들 중 하나를 명시적으로 위반하여 이뤄진다. 우선 각 조건들이 무엇을 의미하는지 확인하고 이를 어떻게 위반하여 예방이 이뤄지는지 알아보자.
Mutual Exclusion
조건 : 한 번의 하나의 작업에서만 LOCK을 이용할 수 있다. 사용 중인 LOCK에 대해 접근하기 위해선 LOCK이 해제되어야만 한다.
위반 : 한 번에 여러 작업이 LOCK을 이용할 수 있도록 만든다. 단, 동기화에 문제가 생길 수 있다.
Hold and Wait
조건 : 적어도 하나의 LOCK을 보유한 채로 다른 작업에서 보유하고 있는 LOCK을 취득하기 위해 대기하고 있다.
위반 : 작업 진행에 필요한 LOCK들을 한 번에 얻을 수 있을 때까지 대기 후에 취득하도록 만든다.
Non-Preemption
조건 : 다른 작업이 보유하고 있는 LOCK을 강제로 탈취할 수 없다.
위반 : 다른 작업이 보유하고 있는 LOCK을 취득하려 할 때는 현재 보유하고 있는 LOCK을 반환한 후 대기하도록 만든다. 단, 다른 작업이 보유하고 있는 LOCK을 강제 취득할 수 없다는 조건은 여전히 유지된다.
Circular Wait
조건 : LOCK을 얻기 위한 작업들이 순환 형태로 대기하고 있다. 예를 들어 작업들이 P0,P1,P2,...,PnP_{0}, P_{1}, P_{2}, ... , P_{n}과 같이 있을 때, P0P_{0}P1P_{1}LOCK을, P1P_{1}P2P_{2}LOCK을, ..., PnP_{n}P0P_{0}LOCK을 요구하는 상태가 Circular Wait이다. Hold and Wait 조건이 만족이 되어야 Circular Wait이 발생할 수 있다.
위반 : LOCK에 고유 번호를 할당한 뒤, LOCK의 번호대로 요구될 수 있도록 만든다.
Deadlock예방한다는 것은 굉장히 좋은 일이지만, 이와 같은 작업들은 컴퓨팅 자원을 많이 소모하기 때문에 시스템 상에 많은 부하를 줄 수 있다는 단점이 있다. 따라서 현재 대부분의 시스템에서는 이를 이용하지 않는다. 예방의 일부 단점들은 회피를 통해 해결될 수 있다.

2. 회피 (Avoidance) → Deadlock을 일절 허용하지 않음

회피Deadlock에 빠질 가능성을 사전에 확인한 뒤, Deadlock에 빠지지 않는 안전 순서 (Safe Sequence)를 찾아내어 안전 상태 (Safe State)를 고수하는 행위이다. 예방에서 야기되는 처리량의 감소는 회피에서 LOCK들의 추가적인 정보를 통해서 보완될 수 있으며, 이 때 Allocation, Need, Available과 같은 LOCK에 대한 정보들이 요구된다. 이와 같은 정보들을 이용하는 회피의 다양한 알고리즘이 존재하지만, 그 중에서도 가장 대표적인 알고리즘은 은행원 알고리즘 (Banker's Algorithm)이다.
은행원 알고리즘Dijkstra가 만든 알고리즘이다.
Safe State & Safe Sequence? 시스템이 안전 (Safe)하다는 의미는 어떤 순서로 작업들이 LOCK을 요청하여도 Deadlock을 만들지 않고 차례로 LOCK들을 할당할 수 있는 상태를 의미한다. 이를 Safe State라 한다. 이 때 Safe State를 보장할 수 있는 안전한 LOCK의 할당 순서를 곧 Safe Sequence라 한다. Safe State라면 Deadlock이 발생하지 않은 것이다. Deadlock이 발생한 시스템은 Unsafe State이지만, Unsafe State에 있다고 해서 반드시 Deadlock이 발생하는 것은 아님을 명심해야 한다.
은행원 알고리즘은 각 작업이 요구하는 여러 LOCK들의 최대 수 (Max)를 선언함으로써 동작한다. 그리고 LOCK에 대한 할당 상태의 확인을 통해 Circular Wait이 발생하는지 확인함으로써 Deadlock 발생 여부를 미리 알 수 있고, 이에 따라 Deadlock이 발생하지 않는 Safe Sequence를 보장할 수 있다. 이에 따라 LOCK의 할당이 이뤄지더라도 Safe State에 있을 수 있도록 한다. 은행원 알고리즘이 이용되는 상황은 다음 예시를 통해 이해할 수 있다.
은행원 알고리즘이 어떻게 동작하는지는 공룡 책 등에서 직접 찾아보는 것을 권한다.
시스템에서 이용할 수 있는 최대 LOCK의 수는 12개이고 현재 각 작업들에게 할당된 모든 LOCK은 9개일 때, 해당 시점을 t0t_{0}라 해보자. t0t_{0}에서 시스템은 Safe State인지 판별하기 위해선 Safe Sequence를 찾을 수 있어야 한다. <T1,T0,T2><T_{1}, T_{0}, T_{2}>와 같은 순서로 작업을 처리했을 때는 문제 없이 작업에서 요구하는 LOCK들을 분배하여 처리할 수 있으므로 이는 Safe Sequence가 된다.
T1T_{1}이 요구하는 추가 LOCK42=24 - 2 = 2이고, 가용할 수 있는 자원은 최대 LOCK 12개에서 현재 할당된 모든 LOCK인 9개를 뺀 3이다. 즉, T1T_{1}의 작업을 끝낼 수 있는 것이다. T1T_{1}의 작업을 끝내고 나면 시스템에서는 5개의 LOCK을 이용할 수 있는 상태가 되고, 이는 T0T_{0}의 모자란 LOCK을 채우기에 충분하다. T0T_{0}를 끝낸 후에는 총 10개의 LOCK을 가용할 수 있으므로 T2T_{2} 역시 문제가 되지 않는다.
위와 같은 예시에서 주의해야 하는 것이 바로 상태 전이 (State Transition)이다. 시스템은 Safe State에 있다가도 얼마든지 작업 진행에 따라 Unsafe State로 바뀔 수 있다. t0t_{0}에서의 Safe Sequence가 존재했었지만, 다음 시점인 t1t_{1}에서의 LOCK 요구의 변경에 따라 얼마든지 Unsafe State가 될 수 있다는 것이다.
t1t_{1}에서 작업 T2T_{2}가 추가적으로 LOCK을 하나 더 요구하여 이를 할당해줬다고 해보자. 가용할 수 있는 LOCK의 수는 최대 LOCK 12개에서 현재 할당된 모든 LOCK인 10개를 뺀 2이다. 이에 따라 T1T_{1}은 추가적으로 2개의 LOCK을 요구하고 있으므로 T1T_{1}을 끝낼 수 있고, 시스템 상에 유지되는 LOCK은 총 4개이다. 따라서 T0T_{0}, T2T_{2} 그 어느 것도 작업을 진행할 수 없는 상황이 되어 Unsafe State가 된다. 이와 같은 상황은 T2T_{2}에게 LOCK을 즉시 할당함으로써 벌어진 일이다. 해당 상황을 미리 파악하여 T2T_{2}는 대기하게 하고, 다른 작업에게 먼저 LOCK을 할당한 후에 반환된 LOCKT2T_{2}가 이용하도록 했다면 Deadlock이 발생하지 않았을 것이다.
따라서 은행원 알고리즘과 같은 회피들은 작업들이 LOCK을 요구했을 때 즉시 할당이 가능한지 대기를 해야하는지도 판별함으로써 Safe State를 유지하게 된다.
LOCK의 즉시 할당이 가능할 때는 Safe State에서 Safe State가 될 때만 해당된다.
은행원 알고리즘과 같은 회피예방의 단점을 일부 보완했다고는 하나, 몇가지 제한 사항 및 단점이이 따른다. 미리 알아야 하는 정보들이 많고, 이들을 얻어내기 위한 오버헤드가 큰 편이라 현재 대부분의 시스템에서는 이를 이용하지 않는다.
1.
할당할 수 있는 LOCK의 수를 사전에 파악할 수 있어야 하며, 그 수가 일정해야 한다
2.
LOCK을 이용하는 작업 수들도 일정해야 한다.
3.
Unsafe State를 방지하기 위해 Safe Sequence를 지켜야 하므로, LOCK의 이용도가 낮다.

3. 탐지 및 회복 (Detection and Recovery) → Deadlock을 허용함

별도의 예방이나 회피를 사용하지 않은 경우에는 Deadlock이 발생할 수 있기 때문에, 해당 상황에서는 Deadlock탐지하고 회복하는 방식으로 문제를 해결하게 된다. 탐지회복은 단점이 꽤나 극명한 편이어서 현재 대부분의 시스템에서는 이를 이용하지 않는다.
탐지
탐지회피에서 사용했던 은행원 알고리즘과 유사한 방식으로 LOCK에 대한 할당 상태를 파악하여 Deadlock이 발생했는지를 판별하게 된다. 따라서 회피에서 은행원 알고리즘Allocation, Need, Available 등의 정보를 이용했다면, 탐지에서는 Allocation, Request, Available 등의 정보를 이용한다. 두 방법의 다른 점이라 하면 NeedRequest에 있는 것을 볼 수 있다. 회피에서 Need는 현재 상태에서 LOCK을 취득하려 하지 않아도 최종적으로 작업 자체를 끝내기 위해 필요한 LOCK의 양을 의미하는데 반해, Request는 현태 상태에서 필요한 만큼의 LOCK을 요청한 상태를 의미한다.
은행원 알고리즘에서 사용하는 자료구조는 동일하지만, 위에서 제시된 부분을 포함하여 알고리즘 상에 조금 차이가 있다. 탐지에서 사용하는 알고리즘은 공룡 책 등에서 직접 찾아보는 것을 권한다.
탐지를 수행하기 위한 알고리즘에서는 Resource-Allocation GraphWait-For Graph를 사용할 수 있다. Resource-Allocation Graph의 경우 LOCK에 대해 소유되고 있는 상황을 표현한 그래프라면, Wait-For GraphLOCK을 제외하고 단순하게 작업과 작업 사이 대기 상황만을 표현한 그래프이다. 따라서 Resource-Allocation GraphLOCK의 할당 이전에 Deadlock 발생 가능 여부를 파악하여 LOCK의 할당 여부를 결정 짓는 반면, Wait-For GraphLOCK을 할당해준 후에 Deadlock이 발생했는지 확인하게 된다. 두 그래프의 Deadlock 유무 판별 기준은 그래프 내의 Cycle 유무인데, 두 그래프에는 차이가 있다.
Resource-Allocation GraphCycle이 존재하지 않으면 Deadlock이 없는 것이지만, Cycle이 존재한다고 해서 Deadlock이 무조건 있는 것은 아니다. 따라서 해당 그래프에서는 Deadlock의 유무 판별을 위해 그래프 내의 EdgeAssignment-EdgeRequest-Edge라는 LOCK의 할당과 요청에 대한 Edge로 구분지어 추가적으로 판별을 하게 된다. 이와 같은 추가적인 판별이 요구되는 이유는 Resource-Allocation Graph에서 각 작업이 요구하는 LOCK이 한 번에 여러 개일 수 있기 때문이다.
Assignment-EdgeLOCK에서 작업으로 할당되는 Edge를 말하고, Request-Edge는 작업에서 LOCK으로 요청되는 Edge를 말한다.
유형 별 판별
Wait-For Graph에는 LOCK에 대한 정보들을 포함하지 않는 간단한 그래프이다. 따라서 Assignment-EdgeRequest-Edge에 대한 정보를 포함할 수 없으므로 오로지 Cycle 존재만으로 Deadlock 발생 유무를 판별해야 한다. 이런 이유 때문에 Wait-For Graph는 작업들 사이에 Cycle이 존재할 때 Deadlock이 있다고 판단한다. 이와 같이 단순히 Cycle의 존재만으로 Deadlock 판별이 가능한 이유는 Wait-For Graph에서 각 작업이 요구하는 LOCK이 한 번에 오로지 하나이기 때문이다.
Wait-For GraphEdgeAssignment-EdgeRequest-Edge가 아닌 Claim-Edge이다.
탐지Cylcle을 확인하는데에서 O(n2)O(n^2)의 연산이 요구되는 상당히 컴퓨팅 자원을 많이 소모하는 작업이다.
회복
회복Deadlock에 빠진 작업들을 중단시키는 방법과 LOCK을 선점할 수 있도록 Preemption을 지원하는 방법 2가지로 나뉜다.
Deadlock에 빠진 작업들을 중단시키는 방법은 Deadlock에 빠진 모든 작업들을 한 번에 중단하거나 작업을 하나씩 중단시키는 방법이이 있다. 전자의 경우에는 연산 중이던 작업들의 중단으로 올바르게 처리되어야 하는 결과 값이 폐기될 수도 있는 위험이 있다. 후자의 경우에는 작업을 하나 중단시킬 때마다 Deadlock이 해결되었는지 탐지를 매 번 수행해야하므로 꽤나 큰 컴퓨팅 자원을 소모하는 편이다.
Preemption을 허용하는 방법은 작업에 할당된 LOCK을 탈취한 뒤, Deadlock이 해결될 때까지 해당 LOCK을 다른 작업들에게 할당하는 방식이다. 탈취하려는 대상에 대해서는 다음과 같은 사항들이 고려되어야 한다.
1.
Selection of Victim (희생 작업 선택)
→ 최소의 피해만 발생하는 작업을 선택한다.
2.
Rollback (되돌리기)
LOCK을 탈취한 작업을 문제 없던 시점으로 되돌릴 수 있어야 한다.
3.
Starvation (기아 상태)
→ 한 작업이 계속해서 탈취하여 다른 작업에서 기아 상태가 되는 문제가 없어야 한다.

4. 무시 (Ignorance) → Deadlock이 없다고 가정

무시는 말 그대로 Deadlock무시하고 넘기는 행위를 뜻하는 것이 아니라, Deadlock 자체가 발생하지 않는다고 가정하는 행위이다. Deadlock 자체가 발생하지 않는다는 가정은 곧 Deadlock 발생이 정상적인 동작이 아니라고 판단하는 것을 의미하며, Deadlock 해결을 위한 최후의 수단으로써 이용된다. 무시에 해당하는 알고리즘은 타조 알고리즘 (Ostrich Algorithm)이 있는데, 이는 Deadlock이 발생했을 때 시스템을 재시작하는 알고리즘이다.
Deadlock이 자주 발생하는 상황에서는 Deadlock을 다른 방법으로 해결해야 한다. 빈번한 Deadlock 발생에서는 Ostrich Algorithm을 이용하는 것은 바람직하지 않다. Ostrich Algorithm은 동시성을 제공하기 위한 프로그램에서 10년에 한 번처럼 어쩌다가 우연히 Deadlock이 발생하는 경우, 이를 해결하는 것보다 시스템을 재시작을 하는 것이 더 효율적일 때 이용하는 것이다.
무시는 현재 많은 운영체제들과 많은 프로그래머들이 이용하는 방법이다. 이에 따라 프로그램을 작성하는 사용자가 Deadlock을 발생하지 않도록 주의하는 것이 굉장히 중요하다. 따라서 프로그래머들은 늘 LOCK을 얻는 순서를 잘 준수했는지 확인하는 습관이 필요하다.

5. External Functions

PhilosophersMandatoryBonus 부분을 구현하는데 있어서 허용된 함수들은 아래와 같다.
memset
printf
malloc
free
write
fork
waitpid
usleep
gettimeofday
kill
pthread_create
pthread_detach
pthread_join
pthread_mutex_init
pthread_mutex_destroy
pthread_mutex_lock
pthread_mutex_unlock
sem_open
sem_close
sem_post
sem_unlink
malloc, free, write는 소개를 생략한다.
memset은 첫 번째 링크에서, printf는 두 번째 링크에서 확인하자.
forkwaitpid에 대해서는 pipex에서 다루었으므로 세 번째 링크에서 확인하자.
pthread는 네 번째 링크에서, semaphore는 다섯 번째 링크에서 확인하자.
여기서는 usleep, gettimeofday, kill 함수에 대해서 알아 볼 것이다.

1) usleep

1. 의존성

#include <unistd.h>
C
복사

2. 함수 원형

int usleep(useconds_t);
C
복사

3. 함수 설명

인자로 받는 useconds_tMac OS X 상에서 __darwin_usecond_t로 타입 정의 되어 있다. 이는 <_types.h>__uint32_t로 타입 정의 되어 있으며, microseconds를 의미한다. 즉, 프로세스를 얼만큼 재울지 microseconds 단위로 입력을 받는다. 예전 버전의 BSD 계열에서는 반환 타입이 void 였지만, POSIX에 따라 반환 타입이 int로 수정 되었다. 이는 정상적인 함수 수행이 되었다면 0을 반환하고, 그렇지 않다면 -1을 반환한다.
비슷한 함수로는 sleep이라는 것이 있는데 sleep의 입력 인자는 seconds 단위이므로, usleep은 조금 더 정교한 단위로 프로세스를 재우는 것이 가능하다.
sleep의 경우에는 입력 받는 인자가 unsigned int이므로 소수점에 대한 이용이 어려워 seconds 단위로만 이용할 수 있다.
프로세스를 재운다는 의미에 대해서 이해하기 위해선 프로세스가 가질 수 있는 상태에 대해 알아야 한다. 프로세스들은 New, Ready, Sleep, Running, Terminated의 상태를 가질 수 있으며, 이들은 각각의 Queue를 통해 관리된다. 프로세스가 생성되었을 때는 New, 종료되었을 때는 Terminated의 상태가 된다. 프로세스가 스케줄링될 준비가 되면 Ready 상태가 되며, 이들은 스케줄러의 Dispatcher에 의해 Running 상태가 된다. 프로세스가 잠든다는 의미는 Sleep 상태가 된다는 것이며, 이들은 Context Switch 발생 대상에서 자동으로 제외된다. Sleep 상태의 프로세스가 깨어나면 바로 Running 상태가 되는 것이 아니라 Ready 상태가 되며, Dispatcher에 의해 다시 Running 상태의 Queue에 추가되어 스케줄링 된다.

4. 예시

#include <stdio.h> #include <unistd.h> int main(void) { int i; i = 5; while (i--) { printf("%d seconds left\n", i + 1); if (usleep(1000000) == -1) return (1); } return (0); }
C
복사

2) gettimeofday

1. 의존성

#include <sys/time.h>
C
복사

2. 함수 원형

int gettimeofday(struct timeval * __restrict, void * __restrict);
C
복사

3. 함수 설명

gettimeofday 함수는 Unix Time을 얻음으로써 현재 시간을 구하고자 할 때 주로 이용된다. gettimeofdaysettimeofday와 쌍으로 많이 이용되며, 이를 이용하기 위해선 timevaltimezone 구조체가 요구된다. 이 때 timezone이라는 구조체는 내부에 정의된 매크로 값으로 시간대 지역을 구분할 수 있는데, 세계 여러 국가에 따라 시행되는 서머 타임은 간단한 알고리즘에 의해 지정할 수 없고 정치적인 결정에 영향을 많이 받으므로 timezone 구조체는 obsolete되었다. 그러므로 timezone에 대해서는 NULL 값을 이용하는 것이 적극 권장됨에 따라 두 함수가 이용하는 인자는 주로 timeval이라는 구조체가 된다.
Unix Time은 주로 POSIX Time 혹은 Epoch Time이라고도 많이 불리며, 이는 1970-01-01 00:00:00 을 기준으로 흘러간 seconds를 의미한다. time_t라는 unsigned long 타입을 반환하는 time 함수를 통해 seconds를 얻을 수 있는데, 이는 정교한 값이 아니기 때문에 일반적으로는 time 함수 대신에 timeval이라는 구조체를 이용하는 함수를 사용한다. 이와 같은 함수들로는 gettimeofdaysettimeofday가 있다. 특히 gettimeofday 함수의 역할은 time 함수와 유사하기 때문에, time 함수 대신에 gettimeofday 함수가 많이 사용된다.
_STRUCT_TIMEVAL { __darwin_time_t tv_sec; /* seconds */ __darwin_suseconds_t tv_usec; /* and microseconds */ }; struct timezone { int tz_minuteswest; /* minutes west of Greenwich */ int tz_dsttime; /* type of dst correction */ };
C
복사
Mac OS X에서 timevaltimezone 구조체는 위와 같이 정의되어 있다. gettimeofday를 이용할 때는 timeval 구조체의 포인터를 넘김으로써 Unix Time에 대해 microseconds 단위까지 기록하게 된다. Unix Time에 대한 기록이 성공하면 0을 반환하고, 그렇지 않으면 -1을 반환한다.
__darwin_time_t는 내부적으로 long으로 타입 정의되어 있고, __darwin_suseconds_t는 내부적으로 __int32_t로 타입 정의되어 있다.

4. 예시

#include <stdio.h> #include <sys/time.h> #include <time.h> int main(void) { const char *wday[] = {"일", "월", "화", "수", "목", "금", "토"}; struct timeval unix; struct tm *date; if (gettimeofday(&unix, NULL) == -1) return (1); printf("Unix Time: %ld\t%d\n", unix.tv_sec, unix.tv_usec); date = localtime(&(unix.tv_sec)); if (!date) return (1); printf("Date Time: %d년 %d월 %d일 %s요일 %02d시 %02d분 %02d초 %s\n", date->tm_year + 1900, date->tm_mon + 1, date->tm_mday, wday[date->tm_wday], date->tm_hour, date->tm_min, date->tm_sec, date->tm_zone); printf("%d days passed from Jan 1st\n", date->tm_yday); return (0); }
C
복사
<time.h> 내에 있는 localtime이라는 함수와 tm 구조체를 이용하면 Unix Time을 쉽게 Date Time으로 변환할 수 있다. localtime 함수를 보면 포인터를 반환하기 때문에 해당 포인터를 해제를 해야하는 것 아닌가 하는 의문이 들 수 있지만, 해당 포인터는 localtime 함수 내에 존재하는 정적 변수 혹은 런 타임 시스템에 의해 관리되는 전역 변수에 대한 포인터이므로 해제할 필요도 없고 해제를 해서도 안 된다. 단, localtime 함수의 반환 값은 내부 동작에서 오류가 생길 시 NULL을 반환하므로 이에 대한 검증은 요구된다. Unix Time은 서부 유럽 표준시를 기준으로 함에도 위 그림과 같이 지역과 시간이 잘 나오는 이유는 /etc/localtime이라는 파일을 통해 사용자 환경을 얻음으로써 지역과 이에 따른 Unix Time 기준을 적절히 설정하여 동작하기 때문이다.

3) kill

1. 의존성

#include <signal.h>
C
복사

2. 함수 원형

int kill(pid_t pid, int sig);
C
복사

3. 함수 설명

kill 함수는 이름과는 달리 단순히 시그널을 보내주는 함수에 불과하다. 그럼에도 이름이 kill로 붙은 이유는 시그널을 보냄으로써 프로세스를 죽이는데 흔히 사용되어왔기 때문이다.
시그널에 따른 동작은 정의하기 나름이지만, 대부분의 기본 동작이 프로세스의 종료와 관련이 있다.
pipex에서도 forkwait, waitpid 함수를 다루면서 시그널을 간략하게 이용했었고, 시그널의 종류와 기본 동작 및 사용자 정의에 따른 동작 등을 간단히 소개했었다. 당시 예시에서 시그널을 보낼 때는 터미널 상에서 사용자의 키 입력을 이용하거나, 터미널 상의 kill 명령어를 이용했었다. 하지만 2가지 방법은 모두 사용자의 입력에 달려있기 때문에 프로그램 상에서 시그널을 처리하기에는 다소 부적합하다. 이 때 이용할 수 있는 것이 kill 함수이다.
kill 함수는 특정 프로세스에 시그널을 보내주는 kill 명령어의 역할과 일치한다.
시그널을 보내고자 하는 프로세스의 IDpid로 주고, sig에는 보내고자 하는 시그널을 할당하여 호출하면 된다. 특정 프로세스를 대상으로 하는 일반적인 사용법과 달리, kill 함수를 적절히 이용하면 그룹에게 시그널을 보내는 것도 가능하다.
pid0으로 주면 현재 구동 중인 프로세스가 속한 그룹의 모든 프로세스에게 시그널을 보내게 된다.
pid-1로 주면 pid1init 프로세스를 제외하고, 모든 프로세스에게 시그널을 보내게 된다.
pid-1보다 작다면 -pid에 해당하는 그룹의 모든 프로세스에게 시그널을 보내게 된다.
sig로 이용할 수 있는 값은 시스템 마다 다를 수 있으므로 사전에 잘 확인하는 것이 중요하며, 그 값이 1부터 시작하더라도 sig 값으로 0을 사용할 수 있다. sig 값이 0인 경우에는 실제로 시그널을 보내지는 않지만, pid로 입력한 프로세스 혹은 그룹에 대해 존재 유무를 확인할 수 있고 그들에게 시그널을 보낼 수 있는지도 확인할 수 있다. 이는 kill 함수의 반환 값을 통해 그 결과를 알 수 있다. kill 함수는 성공적인 수행이 되었다면 0이 반환되고, 그렇지 않다면 -1을 반환하게 된다.
위 경우에서 pid에 해당하는 프로세스 혹은 그룹이 없다면 ESRCH, 프로세스 혹은 그룹이 존재는 하지만 시그널을 보내는 것이 허용되어 있지 않다면 EPERM 오류를 내게 된다.

4. 예시

#include <stdio.h> #include <stdlib.h> #include <signal.h> #include <unistd.h> void child_signal(int sig) { if (sig == SIGTERM) { printf("Child: I got SIGTERM\n"); exit(0); } else { printf("Child: I got other signal\n"); exit(1); } } void parent_signal(int sig) { pid_t ret; if (sig != SIGCHLD) exit(1); ret = waitpid(-1, NULL, WNOHANG); printf("Parent: Child successfully terminated\n"); exit(0); } int main(void) { int i; pid_t pid; pid = fork(); if (pid == -1) return (1); else if (!pid) { signal(SIGTERM, child_signal); while (1) ; } else { signal(SIGCHLD, parent_signal); i = 5; while (i--) { printf("Parent: Signal will be sent in %d seconds\n", i + 1); usleep(1000 * 1000); } if (kill(pid, SIGTERM) == -1) return (1); while (1) ; } return (0); }
C
복사
위의 코드에서는 SIGTERM자식 프로세스에게 보냈고, 자식 프로세스SIGTERM을 받았을 때 child_signal을 수행하도록 했다. child_signal 이후에는 자식 프로세스가 종료되어 자식 프로세스의 상태 변화가 발생하므로, 커널은 SIGCHLD부모 프로세스에게 보내면서 parent_signal을 수행하게 된다. 이와 같이 시그널에 따른 동작 정의는 signal 함수를 통해 이뤄지며, SIGSTOP, SIGKILL에 대해서는 동작 정의가 불가능하다는 것에 주의해야 한다.

6. Approach

1) Error Handling

대체적으로 usleep, kill, gettimeofday와 같은 함수에 대해선 Error에 대한 검증 및 처리를 해주지 않은 경우를 많이 보았다. 언급한 함수들 역시 원하는 작업을 수행하지 못하였을 경우엔 Error를 반환하기 때문에 이를 적절히 처리하도록 만들어야 한다.
또한 pthread_create, pthread_detach, pthread_join에 대해서는 Error에 대한 검증 및 처리를 잘 해두었지만, pthread_mutex_init, pthread_mutex_destroy, pthread_mutex_lock, pthread_mutex_unlock에 대해선 그렇지 않은 경우도 많이 보았다. pthread의 모든 함수들은 Error를 반환하도록 되어 있다. 물론 정의된 속성 값 중에 Robust인지 아닌지가 영향을 많이 끼치겠지만, 이는 구체적인 Error에 대한 동작이 다를 뿐이고 Error를 내고 안 내고의 문제는 아니다. 따라서 pthread 함수들에 대해서도 Error를 적절히 처리하도록 만들어야 한다.
다만 이번 프로젝트에 대해선 exit, pthread_exit, pthread_cancel, pthread_kill 및 종료 시 자원 정리를 위한 Handler 등록에 대한 함수들의 이용이 불가능하므로 완벽한 처리가 불가능할 수는 있다. 따라서 종료 흐름에 있는 pthread에 대한 Destroy, Unlock과 같은 행위에 대해선 Error 처리를 무시해도 무방하다. 하지만 그 외의 pthread 함수들에 대해서는 반드시 Error Handling을 해야하고, 혹여나 이를 풀어내는 과정에서 Deadlock이 걱정된다면 이는 Architecture를 통해 어느 정도 해결할 수 있다.
쓰레드를 생성한 프로세스에서는 mutexpthread_mutex_lock을 해두어 기다리게 만들고, 나머지 작업용 쓰레드에서는 Error 발생 시 해당 mutexpthread_mutex_unlock하도록 만들어 종료 흐름을 타도록 만드는 것이다. 이에 따라 pthread 함수들의 Error Handling도 가능하고, 기존에 생성되었던 쓰레드들 역시 문제 없이 종료될 수 있음을 알 수 있다.
forksemaphore를 이용했을 때도 mutex를 이용했을 때와 동일한 Architecture로 종료 흐름에 있는 semaphore에 대한 작업 외에 모든 semaphore의 작업에 대해서 Error Handling을 할 수 있다. 다만 fork를 이용하는 Bonus에서는 kill 함수가 허용되므로, 종료 흐름을 타고 있는 부모 프로세스에서 kill 함수를 통해 자식 프로세스를 종료할 수 있도록 만드는 것이 바람직하다.

2) Scheduling

철학자들에게 식사를 할 수 있도록 만드는 행위는 컴퓨팅 자원 중 특히 논리 코어의 수에 의존적이다. 따라서 이론상 죽지 않아야 하는 ./philo 1000 410 200 200과 같은 작업들은 많은 Context Switch 때문에 야금 야금 딜레이가 누적되면서 어쩔 수 없이 죽는 것을 확인할 수 있다. 이에 따라 테스트 케이스를 검증하는 과정에서 이론상 죽지 않는 케이스와 실제로 죽지 않는 케이스를 구분 지을 필요가 있다. 실제로 죽지 않는 케이스는 머신이라는 조건이 고려되어야 한다는 것이다.
다만 이를 평가에서 악용하여 평가지에 기재된 케이스들 마저도 Context Switch 때문에 딜레이가 쌓여 철학자가 죽는 것이라고 디펜스를 하는 행위는 옳지 않다. 평가를 위한 클러스터 환경은 평가지에 기재된 테스트 케이스를 수용하기에 넉넉한 논리 코어가 존재하고 있기 때문에 평가지에 기재된 테스트 케이스에 대해서는 딜레이가 쌓여 죽는 행위가 발생하지 않도록 만들어야 한다.
만일 평가지에 기재된 항목에 대해서도 철학자가 죽어버린다면, 이는 프로세스 혹은 쓰레드의 Scheduling을 전혀 고려하지 않았기 때문일 가능성이 높다. usleep 이라는 함수를 이용하여 철학자가 밥을 먹는 시간을 만족시키기 위해 한 번에 그 값을 기재하고, 철학자가 자야하는 시간을 만족시키기 위해 한 번에 그 값을 기재하는 행위는 철학자가 죽을 수 밖에 없는 상황에 놓이게 한다.
기본적으로 usleep을 통해서 인자로 받은 시간 만큼 프로세스 혹은 쓰레드를 Sleep 상태로 만들고 나면, 이를 깨우는 것은 최소한 인자 만큼의 시간이 지난 뒤일 뿐이고 정확히 인자 만큼의 시간이 지난 후에 깨우는 것이 아니다. 심지어 Sleep 상태에서 깨어나더라도 깨어난 프로세스 혹은 쓰레드는 곧 바로 Running 상태가 되는 것이 아니다. Sleep 상태에서 깨어난 프로세스 혹은 쓰레드는 Ready Queue에 들어가서 Ready 상태로 KernelDispatcher에 의해 처리되도록 기다린 후, DispatcherReady Queue를 수거해야만 비로소 Running 상태로 들어가기 때문에 인자로 받은 시간 만큼을 usleep을 넣는 행위는 꽤나 큰 딜레이를 누적시키게 만든다. 주어진 그림을 살펴보면, ./philo 4 410 200 200과 같이 죽어서는 안 되는 케이스 임에도 약 50초 경과 후에 철학자가 죽는 것을 볼 수 있다.
철학자가 죽는 시간은 상황마다 다를 수 있지만, 딜레이가 위처럼 쌓인다면 언젠가 죽는다.
이와 같은 상황은 usleep으로 수행하려는 시간을 EPSILON과 같은 상대적으로 작은 시간을 반복하는 식으로 극복할 수 있다. 예를 들어서 2000ms 만큼 자야한다면, 1ms만큼 재우는 행위를 2000번 반복해가면서 원하는 시간만큼을 잤는지 확인하는 식으로 반복하여 만족시킬 수 있다. 1ms와 같은 단위를 EPSILON이라고 정의할 수 있고, 이보다 더 작은 값을 사용하면 성능은 낮아지겠지만 조금은 더 정확한 시간 판단이 가능해진다. 따라서 위 그림과 같이 ./philo 4 410 200 200을 수행해보면 이전과는 달리 실제로 죽지 않는 것을 볼 수 있다.
즉, 여유로운 논리 코어가 보장되었을 때는 적어도 평가지에 기재된 항목들에 대해선 철학자들이 죽는 결과가 나타나서는 안 된다. 자신의 논리 코어보다 작거나 같은 수의 철학자가 존재할 때에 원하는 결과를 얻지 못한다면, 이에 대해서는 충분히 보정이 가능하니 Context Switch를 언급하여 디펜스를 하는 것은 최대한 지양하도록 하자.

3) Compiling Option

메모리에 대한 검사는 누수 확인을 위한 leaks 명령어 말고도 Buffer Overflow등을 확인하기 위한 Compiling Option으로 fsanitize라는 것이 있다. 이 중에서도 fsanitize=address 옵션을 기재한 채로 컴파일을 수행하게 되면, fork 함수와 같은 프로세스 관련 함수들에게 꽤나 큰 시간 딜레이를 야기하게 된다. 실제로 fsanitize 옵션을 이용한 채로 fork 이전과 이후로 gettimeofday를 호출하여 차이를 확인해보면, 두 gettimeofday 사이에 fork 밖에 없었음에도 무려 20ms ~ 30ms의 딜레이가 발생하는 것을 확인할 수 있다. 철학자들이 죽지 않기 위해선 딜레이를 최소화 할 필요가 있는데, fsanitize 옵션 기재는 프로젝트 완수에 치명적이라는 것을 알 수 있다. 물론 제출 전에는 fsanitize와 같은 디버깅 옵션을 지우게 되지만, 디버깅 옵션을 기재한 채로 여러 테스트 케이스를 검증하는 과정에서 fsanitize의 딜레이를 모른다면 꽤나 혼란스러울 수 있다. 따라서 메모리에 대한 검사를 마쳤다면 해당 옵션을 지운 뒤에 테스트 케이스를 검증하는 것을 권장한다.

7. Reference

고려대학교 COSE341 운영체제 by 유혁 교수님