운영체제 3. 병행 프로세스, 상호배제

병행 프로세스

운영체제가 프로세스를 빠르게 전환하여 프로세서 시간을 나누어 마치 프로세스가 여러 개를 동시에 실행하는 것 처럼 보이게 함

독립프로세스, 협력 프로세스가 있음

 

독립 프로세스

단일처리시스템에서 수행하는 병행 프로세스

다른 프로세스 영향을 주고 받지 않으면서 독립 실행

초깃값에 따른 항상 동일한 결과

단일프로그래밍 - 프로세서를 사용중이던 프로세스 완료 후 다른 프로세스 사용

다중 프로그래밍 - 프로세서 하나를 여러 프로세스가 공유함

다중 처리 프로세서 2개 이상 사용하여 동시에 여러 개를 병렬 실행 이 포함

 

협력 프로세스

다른 프로세스와 상호작용하며 측정 기능을 수행하는 비동기적 프로세스

제한된 컴퓨터 자원의 효율성 증대를 목적

여러 작업을 동시에 수행

동일한 파일을 하나의 프로세스는 읽고 다른 프로세스가 쓰는 상황과 같이 출돌 발생 가능성

이런 충돌을 피하기 위한 상호작용 상태

서로 인식하지 못하는 경쟁관계

개체를 공유하는 단계에서 서로를 간접인식

프로세스끼리 통신하는 기본함수 사용

 

병행성

여러 프로세스를 이용하여 작업을 수행하는 것

신뢰도, 처리속도, 처리능력을 올림

 

병행프로세스 문제

공유자원 베타적 사용(한순간에 하나의 프로세스만 사용)문제

병행프로세스 간 협력, 동기화 문제

두 프로세스간 통신 문제

일정한 결과를 모장해야하는 문제

교착상태를 해결해야하는 문제

 

상호배제

병행 프로세스에서 프로세스 하나가 공유자원 사용 시 다른 프로세스들이 동일한 일을 할 수 없도록 하는 방법

읽기와 동시에 스기와 같은 느낌

동기화

공유자원을 동시에 사용하지 못하게 제어하는 방법

차례로 읽거나 쓰도록 함

순차적으로 자사용 가능한 자원을 공유하려 상호작용하느 프로세스 사이에서 나타남

동기화로 상호배제는 보장할 수 있으나 교착, 기아상태가 나타날 수 있음

 

임계자원

두 프로세스가 동시에 공유할 수 없는 자원

임계영역

임계자원에 접근하고 실행하는 프로그램 코드부분

다수의 프로세스가 접근 가능하나 어느 한 순간에는 한 프로세스만 접근 가능

 

상호배제 조건

두 프로세스는 동시에 공유자원 진입 불가

프로세스 수나 속도에 영향받지 않음

공유자원을 사용하는 프로세사만 다른 프로세스 차단 가능

프로세스 자원을 사용하기 위해 너무 오래 기다리면 안됨

 

임계영역의 조건

상호배제

어떤 프로세스가 임계영역에서 작업 중이면 다른 프로세스는 임계영역에 진입 불가

진행

임계 영역에 프로세스가없는 상태에서 어떤 프로세스가 들어갈 지 결정

한정 대기

임계영역을 무한히 기다리는 상황을 방지하기 위해 한번 임게영역에 들어갔던 프로세스는 다시 임계영역에 들어가는 것이 제한

 

생산자 소비자 문제

생상자 프로세스가 생사낳ㄴ 정보를 소비자 프로세스가 소비하는 형태

두 프로세스의 속토 차이 발생 시 문제가 생김

 

속도문제를 해결하기 위해 버퍼를 사용하여 해결하려 함

버퍼가 꽉차면 생산자는 생산 불가, 버퍼가 비면 소비자는 소비 불가

 

하지만 이 방식은 접근 순서에 따라 다른 결과가 나오는 문제가 있음

남는 데이터의 결과를 보장할 수 없음

즉 병행 프로세스들은 동기화가 필요함

 

데커 알고리즘

2개의 프로세스에만 사용 가능

두 프로세스가 통신을 위해 공유 메모리를 사용하여 충돌 없이 단일 자원을 공유할 수 있도록 허용

flag() false 진입의사 없음, true 진입의사 있음

turn 이 상대 프로세스 번호이면 상대가 사용중

특징

하드웨어 명령문이 필요없음

임계영역 밖에서 수행중인 프로세스가 다른 프로세스들의 임계영영진입을 막지 않음

임계영역에 들어가기 원하는 프로세스를 무한정 기달게 하지 않음

 

피터슨 알고리즘

데커랑 비슷하나 turn을 서로 양보함

turn을 가장 늦게 양보함 프로세스가 늦게 진입함

상호배제조건 만존 - 임계영역을 하나의 프로세스만 사용

진행조건 만족 - 임계영역에서 나올 시 flag를 false로 바꿈

 

다익스트라 알고리즘

N개의 프로세서 상호배제 문제를 해결

idle 프로세스가 임계영역 진입을 시도하지 않을 때

want-in 임계영역 진입 1단계

in-CS 임계영역 진입 2단계 임계영역 내일 때

 

TAS명령어

하드웨어로 돌아가는 명령어

공유 변수를 수정하는 동안 인터럽트 발생얼 억제하여 임계영역문제 간단해결

실행 효율이 떨어짐

메모리 영역의 값에 대한 검사와 수정을 원자적으로 수행 할 수 있는 하드웨어 명령어

원자적 연산 - 더 이상 쪼갤 수 없는 하나의 연산

알고리즘이 간단함

해당 주소의 값을 읽고 새 값으로 교체, 해당 메모리 위치의 이전 값을 반환함으로서 원자 연산 수행

 

boolean 변수 lock를 사용해 상호 배제

lock는 바쁜대기를 발생해 접근을 제한

 

mutex locks

처음 acquire()/은 임계영역을 보호하고, 다음은 release()를 통해 임계영역을 보호함

acquire(), release()에 대한 call은 원자적이어야함

바쁜대기를 요구함

 

세마포

다익스트라가 테스 문제를 해결하기 위해 제안

상호 배제 및 연산 순서도 제공

S 표준 단위 연산(임계영역에 들어갈 수 있는 프로세스 수)

P 임계영역에 진입하기 위한 연산 S를 감소시킴

V 임계영역에서 나와 다른 프로세스에게 자원 사용을 알리는 연산 S를 증가시킴 siginal에 의해 수행

무조건 wait 다음 siginal이라는 제약이 있음

 

이진 세마포

S가 0 또는 1이다

P, V 연산을 교대로 실행한다

 

계수 세마포

S가 N인 경우

S강 0이면 입장못함 0이상이면 임계영역 입장

입장 시S -1

이몌영역에서 나올 시 S +1

 

세바포 구현

바쁜대기를 없에기 위해

wait()가 실행되면 S를 큐에 넣어 블락시켜 바쁜대기를 없앰

 

두 프로세스가 동시에 세마포에서 wait, siginal을 연산할 수 없도록 하는 방법

단일프로세스

wait, siginal 수행 중 인터럽트 금지

다중프로세스

인터럽트 금지가 안됨, 바쁜대기 시기조절로 해결