- 병행이란?
- 같이 존재하고 있다.
- 메모리에 다수의 프로세스가 같이 존재한다(멀티프로그래밍).
- 단일처리 시스템에서는 병행 프로세스 중 한 개만이 실제로 실행되지만 CPU의 처리 시간을 효과적으로 나눔으로써 겉으로는 병행 프로세스들이 동시에 처리되는 것처럼 보인다.
- 다중처리 시스템에서는 여러 개의 프로세스가 동시에 병렬로 실행될 수 있으므로 병행과 병렬은 다른 뜻
- 병행성은 처리기의 수와 상관없으나, 병렬처리가 성공하기 위해서는 기본적으로 병행성이 전제되어야 한다.
- 병행 프로세스들은 서로 간에 비동기적인데, 이는 프로세스들의 상태와 실행여부 등을 모른 채 실행되고 있다는 것을 의미.
1. 병행 프로세스
- 병행 프로세스들의 비동기적 실행은 서로 공유된 자원이 없는 한 아무 문제없이 독립적으로 진행되지만, 공유된 자원이 있을 경우 이 자원의 접근에는 위와 같이 일정한 룰을 따라야 한 것이다. 여기서 룰은 한 번에 한 프로세스만이 접근하도록 하고, 해당 자원에 대해 의도했던 실행을 완료하도록 보장 한다는 것
- 병행 프로세스들의 공유 데이터에 대한 접근이 제대로 처리되지 않았을 대 문제가 발생하므로 정확한 실행을 보장하기 위해서 특정 룰들을 지켜야 한다.
2. 상호배제
- 경쟁 상태 : 프로세스들이 공유 데이터에 대해 서로 접근을 시도하는 상황
- 경쟁 상태 때문에 상호배제, 교착 상태, 기아와 같은 문제가 발생.
- 임계자원 : 두 개 이상의 프로세스가 동시에 사용할 수 없는 자원
- 임계영역 : 임계 자원에 대해 접근하고 실행하는 프로그램 내의 코드 부분
- 상호 배제 : 한 번에 하나의 프로세스만이 임계영역에 들어가야 함
- 임계영역의 성공적인 실행을 위해
- 상호배제가 지켜져야 한다
- 임계영역에 있지 않는 프로세스가 다른 프로세스의 임계영역 진입을 막아서도 안된다.
- 비어 있는 임계영역에 대한 진입은 바로 허용한다.
- 특정 프로세스의 진입 시도가 계속 무산되어 기아를 겪지 않도록 해야 한다.
- 임계영역 진입 순서
- 임계영역에 들어가고자 하는 프로세스는 먼저 임계영역 내 다른 프로세스가 있는지를 확인한 후 있다면 기다리고, 없다면 들어가면서 자신이 나올 때까지 다른 프로세스가 들어오지 못하도록 해야 한다.
- 임계영역을 벗어날 때는 자신이 나오는 사실을 알려 다른 프로세스가 들어올 수 있도록 해야 한다.
- 운영체제가 다양하므로 구체적인 모든 내역을 파악하여 알아서 상호배제를 해주기가 어려우므로 공유 자원에 대한 상호배제의 의무는 일반적으로 그 내용을 잘 아는 프로그래머에게 주어진 대신, 운영체제는 사용자의 상호배제 구현을 지원하기 위한 구조로 모니터와 같은 프로그래밍 언어 수준의 도구를 제공하고 있다.
3. 상호배제를 위한 소프트웨어 기법들
- 운영체제의 지원 없이 프로세스들 간에 자신의 프로그램에서 임계영역 앞뒤로 적절한 코딩을 해줌으로써 상호배제를 해결하는 방식
- parbegin/parend 구조 : parbegin과 parend 사이에 존재하는 n개의 문장들이 동시에 수행될 수 있음을 의미, 단일처리기 시스템의 경우라면 각 문장의 수행 순서를 임의로 진행해도 좋다는 뜻, 다중처리기의 경우에는 각 문장을 병렬로 실행하겠다는 뜻으로 이 구조에서 n개의 문장들의 나열 순서는 아무 의미가 없다.
- 몇 가지 미완성 시도들
- 첫번째 시도 : P0가 시행되는 중간에 CPU를 빼앗기면 P1은 무한반복을 하게 된다. turn의 초기값이 0이므로 임계영역의 첫 번째 진입은 P0만 할 수 있다 → 임계영역이 비어있을 경우 진입을 원하는 프로세스를 방해해서는 안된다는 원칙에 위배. 임계영역의 진입이 turn값을 바꾸어줌으로써 가능하므로 P0과 P1은 정확하게 한 번씩 번갈아가며 진입이 가능하고 누구든 연속해서 두 번 이상 진입할 수 없다.
- 두번째 시도 : 상호배제가 지켜지지 않음 →P0에서 flag[0]이 true가 되기전에 CPU를 빼앗기는 경우
- 세번째 시도 : flag를 true로 만드는 작업을 while문 앞으로 옮긴다. 이의 문제점은 flag[0]를 true로 만든 다음 while문에서 맴돌다 P1에 넘겨주고 P1도 flag[1]을 true로 만든 후 while문에서 맴돌다 다시 P0로 왔을 때 두 프로세스 모두 임계영역에 들어갈 수 없게 되는 상황이 발생할 수 있다.
- 성공적인 기법들
- Dekker의 알고리즘 : flag와 turn 변수를 적절히 사용하여 프로세스 사이의 상호배제를 제대로 구현한 것
- Peterson의 알고리즘 : 전역변수 flag[0]과 flag[1]은 초기 값이 false이며, turn은 0 또는 1값을 갖는 상황에서 P0의 프로그램을 보였는데, P1은 P0에서 0은 1로 1은 0으로 바꾸면 된다.
- n프로세스 간의 상호배제를 위한 소프트웨어 기법들
- Bakery 알고리즘
- 상호배제가 요구되는 n개의 프로세스에서 임의의 프로세스 i를 위한 프로그램
- 모든 number값과 choosing 값은 0과 false로 초기화되어 있고, 임계영역의 진입을 원하는 프로세스 i는 먼저 number값이 주어지는데 다른 프로세스들이 이미 받은 값보다 더 큰 값을 받게 된다.
- for문 안에서 첫 번째 while문은 번호 값을 받는 중인 프로세스가 있다면 그 값도 비교해야 하기 때문에 기다리는 것이며, 두 번째 while문에서 자신의 값이 가장 작을 때 임계영역의 진입이 허가된다.
- 임계영역을 벗어난 후 자신의 값을 0으로 해줌으로써 차례를 기다리는 다른 프로세스들에게 임계영역의 진입 기회를 주게 되는데, 번호 값에 의해 차례가 정해지므로 특정 프로세스의 무한 대기는 걱정하지 않아도 된다.
** 소프트웨어 기법들의 단점 : 소프트웨어 기법들은 운영체제의 특별한 지원 없이, 프로세스 간 협력을 통해 상호배제를 실현하는 것이므로 실행 시의 부하가 크며, 실수로 인한 오류의 가능성도 높다. CPU 낭비(Busy wait, Spinlock)
4. 상호배제를 위한 하드웨어 기법들
- 인터럽트 금지를 사용한 기법
- 단일처리 시스템의 경우는 병행 프로세스들이 실제로는 CPU를 번갈하 사용하는 것이므로 한 프로세스가 임계영역에 실행 중일 때 CPU를 뺏기지 않도록 하면 간단하게 상호배제를 지켜줄 수 있을 것이다. 즉 인터럽트를 임계영역의 실행을 완료할 때까지 발생하지 않도록 하면 된다.
- 모든 종류의 인터럽트를 금지시켜 시스템의 효율적인 운영을 방해하기 쉽다.
- 인터럽트는 처리기 단위이므로 다중처리 시스템에서 다른 처리기에서 실행되는 프로세스로부터의 접근 가능성은 여전히 존재하기 때문에 사용하기 힘든 방법
- 메모리의 같은 위치에 대한 읽기와 쓰기, 또는 읽기와 검사와 같은 일을 한 명령어 사이클동안 처리해주는 명령어가 있다면, 이런 종류의 기계명령어는 다른 접근 요청이 차단된 가운데, 원자적으로 실행 동안 끊기지 않고(실행완료까지 보장) 완료될 수 있다.
- 하드웨어 명령어를 사용한 기법
- testandset과 exchange 명령어를 사용하면 실행 도중 끊김 없이 완료된다.
- testandset의 target은 true로 만들고 원래 target을 리턴
- 장점 : 다중 처리 시스템에서도 쉽게 사용가능, 한 프로그램 내에서 서로 다른 변수를 사용하여 여러 개의 임계영역도 지원 가능
- 단점 : 바쁜 대기(busy wait : while문을 계속 맴돌게 됨으로써 CPU의 낭비 초래) 발생가능, 임계영역 실행 중 높은 우선순위를 가지는 프로세스에게 CPU를 뺏길 경우 교착 상태 발생 가능
5. 세마포어
- 세 개의 특수한 명령들만 접근할 수 있게 허용되는 보호된 변수
- 더 높은 수준에서 상호배제 구현 가능
- 세마포어가 0 또는 1의 이진 값만을 가진다면 이진 세마포어, 음이 아닌 모든 정수가 될 수 있으면 계수 또는 정수 세마포어
- 세마포어를 위한 특수한 명령들은 비분리 명령들로서, 세마포어 값을 초기화하는 명령, P명령, V명령이 있다
- P명령 : wait, 또는 down이라는 이름을 사용하기도 함
- V명령 : signal 또는 up이라는 이름을 사용하기도 함
- P명령 : S값이 0보다 크면 단순히 S값을 1감소시키는 작업을 하지만, 그렇지 않으면 S값이 0보다 크게 되기를 기다린다
- V명령 : S가 0보다 크게 되기를 기다리는 프로세스가 있으면, 그들 중 하나의 프로세스가 준비 또는 실행상태로 만들고 만약 그러한 프로세스가 존재하지 않는다면 단순히 S의 값을 1만큼 증가시키는 작업만 한다.
- 세마포어에 대한 명령들은 각각 분리되지 않고 수행될 수 있도록 구현해야 하며, 같은 세마포어에 대해서는 동시에 실행될 수 없다.
- 세마포어를 이용한 상호 배제
- 세마포어 변수 S가 1로 초기화되어 있으므로 최초로 시도하는 프로세스는 S를 0으로 바꾸고 임계영역에 진입
- 그 후 진입을 시도하는 프로세스들은 대기상태가 된다.
- 임계영역을 빠져 나오는 프로세스에 의해 대기 상태의 프로세스들 중 하나가 실행 가능한 상태가 되어 임계 영역으로 진입하게 된다.
- 대기 상태의 프로세스들이 없으면 S를 1 증가 시킨다.
- P와 V 명령의 정의에 따라 한 번에 하나의 프로세스만이 임계영역에 들어갈 수 있다.
- 세마포어 동기화 : P0는 P1이 데이터를 생성하여 주면 받아 계속 실행하는 경우, 서로를 의식하고 실행의 보조를 맞추다.
6. 생산자-소비자 문제
- 생산자는 데이터를 만들어 버퍼에 저장하고(채워나가고), 소비자는 버퍼에 있는 데이터를 꺼내 소비하는(비우는) 프로세스
- 버퍼는 공유 자원이므로 버퍼에 대한 접근 즉, 저장하고 꺼내는 일들이 상호배제 되어야 함
- 버퍼가 비어 있을 대는 소비자가, 버퍼가 꽉 차있을 때는(더 이상 저장할 공간이 없으므로) 생산자가 기다려야 하는 동기화도 자연스럽게 포함되어 있다. 버퍼의 크기는 저장 공간이 하나인 것부터 무한개까지 설정 가능
- e=empty, f=full
- 무한 버퍼라면 e와 관련된 코드 삭제하면 됨
7. Eventcount와 Sequencer를 사용한 기법
- Eventcount와 Sequencer 역시 특별한 명령들에 의해서만 접근이 가능한 정수형 변수들이며 초기 값은 0으로 시작하고 그 값이 감소하지 않는다.
- ticket(s)명령은 비분리로 실행되며 sequencer변수인 s값을 반환해주고 ticket(s)명령이 실행될 때마다 s값은 1증가한다.
- Eventcount변수인 E에 대한 명령은 현재의 E값을 반환해주는 read(E), 1증가시키는 advance(E) 그리고 E가 v값보다 작으면 기다리도록 하는 await(E,v)명령들이 있는데, 이 세 명령은 비분리로 실행되지 않아도 좋다.
- 임계영역의 진입을 시도하는 프로세스들에게 순번 표를 부여함으로써 기다린 순서대로 처리되게 하여 기아방지
8. 모니터
- 공유 데이터들과 이들에 대한 임계영역들을 관리하는 소프트웨어 구성체
- 모니터는 프로그래밍 언어 수준에서 제공되는 모듈로서 공유 데이터를 위한 변수들과 초기화 루틴, 임게영역을 코딩한 프로시저들로 이루어진 일종의 함으로 이해
- 모니터 내의 변수들은 프로시저를 호출하여 모니터 안으로 진입한 후, 원하는 공유 데이터에 대한 접근을 하게 된다.
- 중요한 점은 언제나 모니터의 진입을 한 프로세스로 제한함으로써 즉, 한 번에 하나 이하의 프로세스만이 모니터 내에 있게 함으로써 상호배제를 자연스럽게 실현한다는 것이다.
- 모니터로의 진입은 프로시저의 호출로 가능하고, 한 프로세스만이 들어갈 수 있으므로 이미 한 프로세스가 들어가 있을 때를 대비해 대기 큐가 있다.
- 모니터에서는 조건변수를 선언하고, 조건의 대기를 위해 cwait()를, 대기에서 깨어나기 위해 csignal()을 제공한다. 조건변수는 모니터에서만 선언하고 사용하는 것으로 cwait()와 csignal()에 의해서만 접근된다.
- cwait(c)는 이 연산을 호출한 프로세스를 조건 c의 큐에 대기시키고 다른 프로세스의 모니터 진입을 가능하게 한다. csignal(c)는 cwait(c)에 의해 대기되었던 프로세스를 재개시키고, 자신은 신호자 대기 큐로 비켜준다. 만일 cwait(c)로 대기 중인 프로세스가 많다면 그 중에 하나를 고를 것이고, 없다면 단순히 다음 문의 실행을 계속하면 된다.
- 신호자 대기큐 : csignal()에 의해 대기하고 있던 프로세스를 실행시킬 때, csignal()을 호출한 프로세스는 신호자 대기 큐에서 대기하였다가 모니터가 비면 모니터에 들어가 남은 작업을 수행함
- 생산자는 데이터를 만든 후 append(x)를 호출하여 모니터의 진입을 요청한다. 내부에 이미 프로세스가 있다면 append 진입 큐에서 기다리게 될 것이며, 아닐 경우 append 프로시저 내의 if문을 실행하게 될 것이다.
- 버퍼가 차있다면 cwait(notfull)에 의해 notfull 조건 큐로 이동하게 될 것-모니터를 비우게 될 것-이며, 아닐 경우 데이터를 저장한 후 notempty조건 큐에서 기다리는 프로세스를 재개시켜 모니터로 진입하게 하고 자신은 신호자 대기 큐로 이동한다.
- 물론 notempty 조건 큐에 아무도 없다면 다음 명령으로 실행을 옯기는데 여기서는 더이상 실행할 것이 없으므로 append의 호출이 끝나고 모니터를 벗어나게 된다.
- 소비자도 비슷한 방법으로 진행
- 원형 버퍼를 활용한 예 : 스풀링
- 스풀러 프로세스(생산자) : 디스크와 같은 보조 기억장치에 빠른 속도로 출력을 하는 프로세스
- 디스풀러 프로세스(소비자) : 디스크에 임시로 출력된 내용을 실제로 프린터로 출력하는 프로세스
- 상대적으로 속도가 느린 프린터와 직접적으로 관련된 작업을 하는 디스플러 프로세스는 스풀러 프로세스에 비하여 처리 속도가 느리다. 이러한 두 프로세스 간의 속도 차이를 완화해주기 위해 원형 버퍼를 사용할 수 있다.
- 장점 : 실제 프린트 작업으로부터 빠르게 벗어날 수 있다.
-식사하는 철학자들
- 포크에 대한 상호배제를 위해 세마포어를 사용하고 오른쪽 포크를 집은 후 왼쪽 포크를 집는데, 모든 철학자들이 한번에 오른쪽을 집으면 교착상태에 빠진다.
- 철학자들이 동시에 양쪽 포크를 집고 하나라도 못집으면 내려놓게 만들면 교착상태는 빠지지 않지만 기아상태에 빠질 수 있다.
- 첫번째 예시에서 모니터를 이용해 구현하면 교착상태를 방지할 수 있다.
*상기 내용들은 OS? Oh YES! 책을 참고하여 작성하였습니다.
