OS #6. 동기화(Synchronization) Part1

오늘은 동기화를 공부한 내용에 대해서 정리 해 보려고 한다.

프로세스 간 통신

프로세스는 시스템 내에서 독립적으로 실행 되기도 하고, 데이터를 주고받으며 협업하기도 한다. 프로세스가 다른 프로세스와 데이터를 주고받는 프로세스간 통신(IPC)에는 같은 컴퓨터 내에 있는 프로세스 뿐만 아니라 네트워크로 연결된 다른 컴퓨터에 있는 프로세스와의 통신도 포함된다. 프로세스간 통신에는 크게 세 가지가 있다.

프로세스 내부 데이터 통신

하나의 프로세스 내에 2개 이상의 스레드가 존재하는 경우의 통신이다. 프로세스 내부의 스레드는 전역 변수나 파일을 이용하여 데이터를 주고받는다.

• 전역 변수를 이용한 통신 : 전역 변수를 이용한 통신은 공동으로 관리하는 메모리를 사용하여 데이터를 주고 받는 것이다. 데이터를 보내는 쪽에서는 전역 변수나 파일에 값을 쓰고, 데이터를 받는 쪽에서는 전역 변수의 값을 읽는다.
• 파일을 이용한 통신 : 파일 입출력 코드는 크게 세 부분으로 구성되어 있다. 파일을 열고(open), 쓰기(write) 또는 읽기(read) 연산을 한 후, 파일을 닫는다.(close)

/* 파일 입출력 코드 */

#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>

int main()
{   
    int fd;
    char buf[5];
    
    fd=open("com.txt", 0_RDWR); /* init */
    
    write(fd, "Test", 5); /* 하드 디스크로 쓰기 */
    
    read(fd, buf, 5); /* 하드 디스크에서 읽기 */
    
    close(fd);
    
    exit(0);
}

프로세스 간 데이터 통신

같은 컴퓨터에 있는 여러 프로세스끼리 통신하는 경우로, 공용 파일 또는 운영체제가 제공하는 파이프를 사용하여 통신한다.

• 파이프를 이용한 통신 : 파이프는 운영체제가 제공하는 동기화 통신 방식으로, 파일 입출력과 같이 open() 함수로 기술자를 얻고 작업을 한 후 close() 함수로 마무리 한다. 파이프를 이용한 통신은 전역 변수를 이용한 통신과 마찬가지로 단방향 통신이다. 파이프로 양방향 통신을 하려면 파이프 2개를 이용해야 한다.

네트워크를 이용한 데이터 통신

여러 컴퓨터가 네트워크로 연결되어 있을 때도 통신이 가능한데, 이 경우 프로세스는 소켓을 이용하여 데이터를 주고받는다. 이처럼 소켓을 이용하는 프로세스 간 통신을 네트워킹이라고 한다. 다른 컴퓨터에 있는 함수를 호출하여 통신하는 원격 프로시져 호출도 여기에 해당된다. 

• 소켓을 이용한 통신 : 소켓을 매개로 한 쪽의 프로세스와 반대쪽의 프로세스를 연결하는 작업을 바인딩이라고 하는데, 시스템에 있는 프로세스가 소켓을 바인딩한 후 소켓에 쓰기 연산을 하면 데이터가 전송되고, 읽기 연산을 하면 데이터를 받게 된다. 소켓은 프로세스 동기화를 지원하므로 데이터를 받는 쪽의 프로세스가 바쁜 대기를 하지 않아도 된다. 소켓은 하나만 가지고도 양방향 통신이 가능하다.

통신은 데이터가 전송되는 방향에 따라 양방향 통신(ex. 소켓), 반양방향 통신(ex. 무전기), 단방향 통신(ex. 전역 변수와 파이프)으로 나눌 수가 있다. 만약 전역변수를 사용해서 양방향 통신을 하기 위해서는 전역변수를 2개 사용해야 한다.

전역 변수를 사용하는 통신 방식의 가장 큰 문제는 언제 데이터를 보낼지 데이터를 받는 쪽에서 모른다는 점이다. 그러므로 데이터를 받는 쪽에서는 반복적으로 전역 변수의 값을 점검하는 수 밖에 없다. 이렇게 반복문을 무한으로 실행하며 기다리는 것을 바쁜 대기(busy waiting)라고 한다. 시스템 차원에서 큰 자원 낭비인 바쁜 대기는 안 좋은 프로그램의 예시에 속한다. 이러한 바쁜 대기 문제를 해결하기 위해서 데이터가 도착했음을 알려주는 동기화(synchronization)를 사용한다. 

 

---

 

동기화

공유 데이터에 대한 동시 접근은 데이터의 일관성(consistency)을 해치는 결과를 낳을 수 있다. 여기서 말하는 공유 자원은 여러 프로세스가 동시에 이용하는 변수, 메모리, 파일 등을 말한다. 공유 데이터에 대해 여러 프로세스가 동시에 접근하여 변경을 시도하는 상황에서 데이터의 일관성이 보장되지 않는 경우를 경쟁 상태(race condition)라고 한다.

데이터 일관성을 유지하기 위해서 하나의 한 프로세스만 순차적으로 데이터에 접근할 수 있게 하는 기법이 필요하게 되었는데, 이 기법을 동기화라고 한다. 지금까지 배운 부분 중에서 동기화가 필요한 부분은 다음과 같다

• Thread Programming : Data section is shared
• Shared Memory : Multiple Process can access
• Kernel : Data structure shared

공유 자원 접근 순서에 따라서 실행 결과가 달라지는 구역을 임계 구역(critical section)이라고 한다. 한 번에 하나의 프로세스만이 이 임계 구역에 진입해야 문제가 생기지 않는다. 동기화 문제를 이 임계구역을 통해 해결하려고 많은 시도를 지금까지 해왔으며 임계 구역 해결 조건에는 다음과 같은 것들이 있다.

• 상호 배재(mutual execution) : 한 프로세스가 임계 구역에 들어가면 다른 모든 프로세스는 임계 구역에 들어갈 수 없다.
• 한정 대기(bounded waiting) : 어떤 프로세스든지 임계 구역에 들어갈 때까지 걸리는 시간에 limit가 있어야 한다.
• 진행의 융통성(progress flexibility) : 한 프로세스가 다른 프로세스의 진행을 방해해서는 안된다. 임계 구역에 진입하려는 프로세스들이 존재한다면 그 중에 한 프로세스는 임계 구역에 진입할 수 있어야 한다.

 

---

Peterson Solution

피터슨 알고리즘은 임계 구역 문제를 해결하기 위해 게리 피터슨이 제안하였다. 기존의 상호 배제 문제에서 공유변수로 2개의 flag를 사용했는데, 여기에 turn 이라는 공유변수를 하나 더 추가했다. 

프로세스 P0는 임계구역에 진입하기 전에 먼저 잠금을 한 후(flag[0] = true) turn을 1로 설정한다. 변수 turn은 두 프로세스가 동시에 임계구역에 못 들어가는 상황을 대비하기 위한 장치이다. 만약에 두 프로세스가 동시에 flag를 true로 설정했더라도 turn을 사용하여 다른 프로세스에 양보하게 된다. 이어서 while(flag[1] && turn == 1)문을 실행한다. 만약 프로세스 P1이 잠금을 설정하지 않았거나 잠금을 설정했더라도 곧바로 turn = 0으로 바꾸면 프로세스 P0은 임계 구역에 진입하여 작업을 마친 후 잠금을 해제하고 임계구역을 빠져나온다. 프로세스 P1도 같은 방식으로 임계구역에 진입한다.

피터슨 알고리즘은 임계구역 해결의 3가지 조건을 모두 만족하지만 2개의 프로세스만 사용 가능하다는 한계를 가지고 있다. 여러 프로세스가 하나의 임계구역을 사용하려면 공유 변수를 추가하고 코드를 변경해야 하는데 이러한 scalability 측면에서 한계를 가지고 있다. 그럼에도 불구하고 하드웨어의 도움 없이 임계 구역 해결을 할 수 있다는 점에서 의미가 있다.

 

---

 

세마포(Semaphore)

앞서 살펴본 임계 구역 해결 알고리즘은 바쁜 대기(busy waiting)를 사용하여 자원을 낭비하고 알고리즘도 너무 복잡하다. 이러한 단점을 해결하기 위해 에츠허르 다익스트라는 세마포라는 알고리즘을 제안했다. 세마포는 임계구역에 진입하기 전, 스위치를 사용 중으로 놓고 임계구역으로 들어간다. 이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠 때 까지 기다린다. 프로세스가 작업을 마치면 세마포는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다. 세마포는 다른 알고리즘과 다르게 임계구역이 잠겼는지 직접 점검하거나, 바쁜 대기를 하거나, 다른 프로세스에 동기화 메시지를 보낼 필요가 없다.

세마포는 두 가지의 원자적인 연산을 가지는 함수 변수이다. 첫 번째는 P()(또는 wait())이고 두 번째는 V()(또는 signal())이다. P()는 잠금을 수행하는 코드로 임계 구역에 들어가기 전에 수행되며, V()는 잠금 해제 및 동기화를 수행하는 코드로 임계 구역에서 나와서 수행하게 된다. P()와 V()는 서로 독립적으로, 그리고 서로 원자적으로 수행된다. 즉, 하나의 프로세스가 P()를 수행하여 세마포의 값을 수행하는 동안 다른 프로세스에서 P()나 V()를 수행해도 세마포의 값을 수정하지는 못한다.

세마포 구조체

세마포 wait(또는 P()) 함수 

세마포 signal(또는 V()) 함수

공유자원이 하나이고 두 개의 프로세스가 접근하는 상황을 설명해 보자. 공유자원은 하나이므로 초기 전역변수 RS = 1이다.

1. 먼저 도착한 프로세스 P0가 임계 구역에 진입을 한다. 현재 RS = 1 이므로 이 값을 1 감소시키고 임계 구역에 진입한다.
2. 나중에 도착한 프로세스 P1은 현재 RS = 0 이므로 P0가 임계 구역을 빠져나올 때 까지 세마포 큐에서 대기한다. 
3. P0은 임계 구역 안에서 작업을 수행한다. 
4. P0은 작업을 마친 후 V()를 실행하여 RS = 1 로 증가시키고 wake_up 신호를 P1에 보낸다.
5. wake_up 신호를 받은 P1가 작업을 시작한다. 

세마포의 종류에는 Counting SP와 Binary SP가 있다. Counting SP는 전역 변수를 정수형으로 나타내고 Binary SP는 전역 변수를 boolean 타입으로 나타내는 차이가 있다. 또한 세마포의 단점에는 다음과 같은 것들이 있다.

1. 데드락이 발생할 수 있는 가능성이 있다.
2. P와 V의 연산이 분리되어 있기 때문에 잘못 사용할 경우 대책이 없다. (ex. P -> CS -> P / V -> CS -> V)
3. High-Level 언어에서 동기화를 제공하는 방법이 필요하다.

데드락은 다음 포스팅에서 조금 더 깊게 다룰 예정이다. 2번과 3번 문제를 해결하기 위해 구현된 것이 모니터(Monitor)이다. 사람이 직접 동기화 작업을 하는 것은 너무 어렵고 복잡하며 실수할 가능성도 존재한다. 이를 위해 모니터는 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써 자원을 보호하고 프로세스 간 동기화를 시킨다. 결과적으로 모든 프로세스가 세마포 알고리즘을 따르게 되고 임계 구역 내에서만 작업이 안전하게 이루어 지도록 한다.

 

 

---

 

참고자료

1. 고려대학교 유혁 교수님 운영체제(COSE341) 수업 자료
2. <Operating System Concepts> 9th ed. by A. Silberschatz
3. <쉽게 배우는 운영체제> 조성호 저, 한빛아카데미