5장 - 병행프로세스와 동기화

CHO·2022년 12월 26일

OS(운영체제)

목록 보기

12/18

병행프로세스
상호배제
상호배제를 위한 소프트웨어 기법들
성공적인 기법들, n 프로세스 간의 상호배제를 위한 sw기법

상호배제를 위한 하드웨어 기법
-인터럽트 금지를 사용한 기법, 하드웨어 명령어를 사용한 기법
세마포어, 생산자-소비자 문제, Eventcount와 Sequencer를 사용한 기법
모니터

5장은 "프로세스 관리"에 있어서 중요하다

-키워드 정리-
병행(concurrent)
: 메모리에 여러개의 프로세스가 같이 존재한다
: 같이 존재하고있다,메모리에 다수의 프로세스가 같이 존재한다는 것!!!!

병렬
: 다중처리 시스템의 경우 여러개의 프로세스가 동시에 '실행'된다
: 처리할 수 있는 cpu가 여러개 있다는 의미

비동기적(Asynchronous)
: 프로세스들이 어떤 상태에 있는지, 어떤 자원을 가지고 있는지, 어디까지 실행됐는지 등에 대해 전혀 모른 채 서로 독립적인 환경에서 실행되고 있음을 말한다

5.1 병행프로세스(Concurrent Processes)

예시1) 산골마을 다리 한명씩 건넌다
누가 언제 다리를 건널거냐 : 서로 모르니까 비동기적 관계
산골마을 사람들 : 병행프로세스(함께 공존)
병렬은 절대 안돼!!

프로세스의 공유변수 count에 대한 조작 도중 다른 프로세스에게도 count에 대한 조작이 허용되면 부정확한 결과 값을 초래하게 될 것이다. 단일처리 시스템의 경우 "정확한 결과값"을 위해서는 A의 count에 대한 조작 도중 CPU가 B로 넘겨지더라도 B의 count에 대한 조작은 허용되어서는 안되겠다.

5.2 상호배제(Mutual Exclusion)

디폴트: 여러개의 프로세스가 메모리에 접근 시도하려고 할 때의 상태

프로세스들이 공유 데이터에 대해 서로 접근을 시도하는 경쟁상태(Race Condition)
:상호배제를 하려는 조치 중에 잘못하면 기아상태(starvation), 데드락(deadlock) 상태에 빠진다

임계영역(Critical Section) = 코드부분!
: 두 개 이상의 프로세스가 동시에 사용할 수 없는 자원이다.(임계자원_critical source = count)에 대해 접근하고 실행하는 프로그램 내의 코드 부분을 의미한다

"critical section"에 대한 프로세싱은 mutual exclusion을 해줘야한다!!!!!
가장 중요한문장임
임계영역에 대한 프로세스들은 상호배제를 해줘야한다.
이게 뭔소리인가?

여러개의 프로세스가 메모리에 접근하려고 할 때 임계영역이 있는데, 임계영역은 두 개 이상의 프로세스가 들어갈 수 없다. 하나씩 들어갈 수 있개 상호배제를 꼬옥 해줘야한다.

상호배제(Mutual Exclusion)
: 한번에 하나의 프로세스만이 임계영역에 들어가 임계영역을 실행해야 한다는 것을 의미한다!!!!!

1프로세스 1임계영역!!! 이 원칙 지켜줘! 즉, 임계영역은 상호배제를 해줘서 하나의 프로세스만이 들어가 실행될 수 있게 해줘야한다는 의미

상호배제를 실현하기 위한 필요조건(원칙!!)
: 임계영역에 있지 않는 프로세스가 다른 프로세스의 임계영역 진입 막아서는 안된다
: 비어있는 임계영역은 바로 진입 허용시켜야한다
: 특정프로세스 진입시도가 계속 무산되어 기아현상 겪게 해서는 안 된다. 즉, 진입시도를 최대한 들어줄 것

상호배제를 실현하기 위해서는?
: 임계영역을 진입할 때(enter primitive)와 나올 때(exit primitive) 꼭 해야할 일들을 어떻게 잘 구현하느냐??가 성공여부를 가른다!
: 운영체제가 다양한 경우, 구체적인 모든 내역을 파악해 알아서 상호배제를 해주기는 어렵다. 하여 운영체제는 사용자의 상호배제 구현을 지원하기 위한 도구를 제공한다.
ex) 세마포어, 모니터

5.3 상호배제를 위한 소프트웨어 기법들

: 소프트웨어 기법들은 병행 프로세스들에게 상호배제를 책임지도록 한다
: 운영체제의 지원없이 프로세스들 간에 자신의 프로그램에서 임계영역 앞뒤로 적절한 코딩을 해준다. 이를통해 상호배제를 해결한다
: 프로그램들을 이해하기 위해서는 "parbegin/parend" 구조를 알아야 한다.
: 시스템이 여러개면 병렬적으로 실행해도 좋고 아무거나 실행해도 좋다는 구조

프로세스 둘 사이의 문제를 해결하기 위한 시도들...

몇 가지 미완성 시도들...
병행프로세스 간의 실행속도와 임계영역에 들어가고자하는 횟수의 차이는 얼마든 날 수 있다

두 프로세스 사이의 상호배제를 위한 첫 번째 시도

p0
: while문은 고유의 코드 실행(독립적이라 작성 x)
: 부분 실행 전에 while(turn 어쩌구) 문장 존재 = enter primitive / 셔구 := 1; 이건 exit primitive가 나옴

: cpu뺏기면 exit 문장 실행함

문장 결과 : p0문장 임계양역 부분이 실행되면 cpu p1에 못 들어가게 설정 / p1에 임계영역부분 cpu 실행되면 p0에는 못 들어가게 문장을 설정해둔 것이다
결과 : 문제점이 있어서 좋은 코드가 아님. 이유는, p0만이 시작을 끊을 수 있기 때문에 상호배제 원칙을 위배한다.(임계영역에 있지 않는 프로세스가 다른 프로세스의 임계영역 진입 막아서는 안된다라는 원칙 + 진입횟수 제한두면 안된다라는 원칙 위배)

Begin : p0, p1은 cpu받는대로 알아서 실행해도 좋다는 의미

<두 프로세스 사이의 방호배제를 위한 두번째 시도...>

문장 해석
: 둘 다 임계영역에 들어가버려서 상호배제 원칙 위배된다
: flag 두 개를 사용하면 정상적으로 진행되면 첫 번째와 달리 임계영역의 최초 진입에 대한 제한이 없어졌다. 상대적으로 많은 횟수의 진입이나 상대 프로세스가 먼저 종료되어도 진입이 가능하다.

<세번째 시도>
-flag를 true로 만드는 작업을 while문 앞으로 가져감.
: 두 프로세스 모두 임계영역에 들어갈 수 없어짐...ㅠ

0
0
0
0

5.3.2 성공적인 기법들
1. Dekker의 알고리즘
: flag와 turn 변수를 적절히 사용해 두 프로세스 사이의 상호배제를 제대로 구현
: 이해하기 어렵고 증명하기 까다롭다

Peterson의 알고리즘
: 전역변수 flag[0]와 flag[1]은 초기값이 false이며, turn은 0또는 1의 값을 갖는다. 그런 상황에서 p0의 프로그램을 봤는데, p1은 p0에서 0은 1로 1은 0으로 바꾸면 되기 때문에 생략했다

1번, 2번 둘 다 primitive를 적절하게 넣어서 sw적으로 해결하려는 시도였다

5.3.3 프로세스 간의 상호배제를 위한 소프트웨어 기법들
: n개의 프로세스들이 들어갈 때 생길 수 있는 문제들을 해결하기 위한 기법(상호배제 기법)들을 알아보자

1)베이커리알고리즘 - 람포트 알고리즘(lamport)
: 임계영역 진입 시도하는 프로세스들에게 순번표 부여해서 순서 기다려서 기아 방지함

여러개 프로세스가 들어갈 수 있는 여러개 enter문장 실행 뒤 임계영역 실행, 이후 number인 end프리미티브 실행함
: 상호배제가 요구되는 n개의 프로세스의 임의의 프로세스 i를 위한 프로그램을 짠다.
: 모든 number과 choosing 값은 0과 false로 초기화한다.
: 임계영역의 진입을 원하는 프로세스 i는 먼저 number값이 주어지는데, 다른 프로세스들이 이미 받은 값보다 더 큰 값을 받게 된다

: for문 안에서 첫번째 while문은 번호 값을 받는 중인 프로세스가 있다면 그 값을 비교해야한다. 그래서 기다린다. 두번째 while문에서 자신의 값이 가장 작을 때 임계영역의 진입이 허가된다

: 임계영역을 벗어난 뒤에는 자신의 값을 0으로 바꿔, 차례를 기다리는 다른 프로세스들에게 임계영역의 기회를 준다. 번호값에 의해 차례가 정해진다. 따라서 특정 프로세스의 무한대기를 걱정하지 않아도 된다.

: 들어가기 전에 자신의 차례값을 받는다. 그게 차별점임

5.4 상호배제를 위한 하드웨어 기법들

5.4.1 인터럽트 금지를 사용한 기법
: 단일처리시스템의 단점 - 다중처리기 시스템에서 사용하기 힘들고, 임계영역의 처리 동안 모든 종류의 인터럽트를 금지시켜 시스템의 효율적인 운영을 방해한다

5.4.2 하드웨어 명령어를 사용한 기법
: 아예 하드웨어를 이용해보자~ 의미에서 나온 기법
: 기계명령어를 사용해 원자적으로 실행된다.

: 장점 - 다중처리시스템에서 쉽게 사용가능, 한 프로그램 내에서 서로 다른 변수를 사용해 여러개의 임계영역도???? 지원할 수 있다
: 단점 - 바쁜 대기(busy wait)을 발생시킬 수 있다, 임계영역 실행 중 높은 우선순위를 가지는 프로세스에게 cpu를 뺏길 경우 교착상태???가 발생한다

0
0
0

5.5 세마포어

: 변수야,,,세마포어 변수,,, 몇 개의 특수 명령에서만 접근이 된다!
: 이진 세마포어, 정수 세마포어 등이 있다~
: p명령, v명령 등이 있다
: p명령 - s값이 0보다 크며 단순히 s를 -1 하는 작업인데, 그렇지 않으면 s값이 0보다 크게 되기를 기다린다 (큐에서 대기한당)
: v명령 - s가 0보다 크게 되기를 기다리는 프로세스가 있다면, 그둘 중 하나의 프로세스가 수행되고 만약에 그런 프로세스가 존재하지 않으면 단순한 s값을 +1 증가시키는 작업만 한다.

: 세마포어에 대한 명령들은 - 각각 분리되지 않게, 수행될 수 있게 구현해야한다, 그리고 같은 세마포어에 대해서는 동시에 실행될 수 없다. 1세마포어 1행동!!!

세마포어 어쩌구 사진

큐에서 대기 : 실제로 block을 시키고 스케줄러 동원해서 run 시킴. os 가 개입한다는 것 = block & wake up 방식으로 p,v 오퍼레이션 실행했다, cpu를 다른 프로세스에 줘서 유용하게 사용할 수 있게 한다

while문 : busywait 방식을 이용해 실행한다(cpu 부지런히 실행하면서 나감)

busywait
단점 : cpu 유용한 곳에 활용하지 못하고, 계속 매어있어 cpu 낭비된다
장점 : while문에 바로 진입할 수 있다?

block & wake up 방식??
: cpu 낭비 막을 수 있다
장점 : ready를 보내면 다시 경쟁을 해야한다?
단점 : 즉각적인 반응이 늦어진다

커널의 개입을 해야한다. os가 cpu타입을 사용한다...

세마포어를 이용한 상호배제

: 세마포어 변수 s가 1로 초기화되어있다. 최초로 시도하는 프로세스는 s를 0으로 바꾸고 임계영역에 진입하게 된다. 이후 진입을 시도하는 프로세스들은 대기상태가 된다.
: 임계영역을 빠져 나오는 프로세스에 의해 대기상태의 프로세스들 중 하나가 실행가능한 상태가 되어 임계영역으로 진입하게 된다. 대기상태의 프로세스들이 없으면 s를 +1해서 증가시킨다.
: p와 v 명령의 정의에 따라서 한 번에 하나의 프로세스만이 임꼐영역에 들어갈 수 있음을 알 수 있다

계수세마포어?
: 91쪽 참조하기

세마포어 동기화
: 동기화란 '서로를 의식하고 실행 보조를 맞춘다' 라는 의미
: p0는 p1이 데이터를 생성해주면 받아서 계속 실행하는 경우를 의미한다

알고리즘 따라가며 이해해야하는 양이 많다...

5.6 생산자-소비자 문제

: 버퍼가 있는디~~
: 생산자는 데이터를 만들어 버퍼를 채워나가고, 소비자는 버퍼에 있는 데이터를 꺼내 소비(비우는) 프로세스를 의미
: 버퍼는 곧 공유자원. 버퍼에 대한 접근(저장하고 꺼내는 일)은 상호배제 되어야한다
: 버퍼가 비어있을 때는 소비자가, 버퍼가 꽉 차면 생산자가 기다려야하는 동기화도 자연스럽게 포함되어있다. 버퍼의 크기는 저장공간이 하나인 것부터 무한개까지 설정이 가능하다.

만약 무한버퍼이면? (슬롯 갯수가 무한개면? - 93쪽에 글 써져있는데)
e를 사용하는 것을 모두 삭제하면 된다 즉 버퍼 사이즈를 책정하는 변수들을 모두 지우면 된다!

Eventcount와 Sequencer를 사용한 기법 - 참고

: 임계영역 진입 시도하는 프로세스들에게 순번 표를 부여한다
: 세마포어처럼 특별 명령들에 의해서만 접근이 가능한 정수형 변수들

ticket = 번호표 부여받는거
await = 내 차례가 될 때까지 기다리는거!

5.8 모니터

: 모니터 구조를 활용해 코딩 진행
: 공유 데이터들과 이들에 대한 임계영역을 관리하는 소프트웨어 구성체이다(시스템을 제공하는 것임)
: 프로세스들은 모니터의 프로시저??를 호출해 모니터 안으로 진입한 후, 원하는 공유 데이터에 대한 접근을 한다. 모니터 내의 변수들은 프로시저들을 통해서만 접근이 가능하다.
: 중요한 점은, 상호배제를 위해 모니터 진입을 한 프로세스로 제한한다.
1모니터 - 1 프로세스!!

모니터 구조는 어떤 놈들인거야?
: 프로시저의 호출로 진입이 가능하다
: 한 프로세스만이 들어갈 수 있고, 여러개가 올 경우를 대비해 대기 큐~존재
: 조건변수(condition variable)눈 cwait(대기표 받고 대기), csignal(대기 깨어나기)에 의해서만 접근 가능
: cwait(c)는 조건 c의 큐에 대기시키고, csignal(c)는 cwait(c)에 의해 대기되었던 프로세스를 재개시킨다. 자신은 신호자 대기 큐로 비켜난다

+)신호자대기큐 : csignal()에 의해 대기하고있던 프로세스를 실행시킬 때, csignal()을 호출한 프로세스는 신호자 대기 큐에서 대기했다가 모니터가 비면 모니터에 들어가 남은 작업을 수행한다