세마포어 busy waiting - semapo-eo busy waiting

Scheduled maintenance: Thursday, December 22 from 3PM to 4PM PST

Home

Subjects

Expert solutions

Create

Log in

Sign up

Upgrade to remove ads

Only A$47.99/year

• Flashcards

• Learn

• Test

• Match

• Flashcards

• Learn

• Test

• Match

Terms in this set (41)

세마포

임계영역이 상호 배제로 수행되게 하는 방법
세마포는 병행 프로그래밍을 위해서 운영 체제에 의해서 제공되는 공유 변수

여러 프로세스 사이에서 공유된다
System-call, operating call등의 운영체제 도움 받음

세마포 s

정수 변수이거 수행할 수 있는 프로세스의 개수를 의미
1로 초기화

초기화한 다음에는 wait와 signal의 표준 원자 연간으로는 접근 가능

Wait와 signal의 고전적 정의

코드 설명

Wait와 signal 연산에 있는 s의 값의 변경은 분리할 수 없도록 실행되어 한다

Wait의 경우 s의 값을 검사하고, 수정하는 과정은 연속적(인터럽트 없이)으로 수행된다

사용법

세마포는 n개의 프로세스의 임계 영역 문제를 취급하는 데 사용

N개의 프로세스들은 공동 세마포 mutex(mutual exclusion)을 공유하며 1로 초기화

세마포에 의한 상호 배제 구현 코드

Critical section의 문제를 해결했다
운영체제로 spinlock이 옮겨감(사라지지는 않았다)
(여전히 cpu 낭비)

Repeat
Wait(mutex)
임계 영역

Signal(mutex)
잔류 영역
Until false

예) 두개의 병행 프로세스의 "동기화(synchronization)" 해결 방법

1.가정:p2의 문장 s2는 p1의 문장 s1이 실행된 다음에만 실행
2.초기 조건: 공동 세마포 synch = 0으로 초기화

P1코드
S1;
Signal(synch);

P2코드
Wait(synch);
S2;

세마포의 단점

바쁜 대기 (busy waiting)요구 - cpu시간 낭비 (spinlock)

바쁜 대기 해결 방법

1.Wait 상태에 있고 세마포가 양이 아닐때, busy waiting에 머물지 말고 자신을 block시킨다

2.Blocked된 프로세스는 세마포와 관련된 대기 큐에 들어가고, 프로세스의 상태는 대기 상태가 된다

3.cpu스케쥴러는 다른 프로세스를 실행시킬 수 있다

4. Block된 프로세스는 후에 다른 프로세스가 signal 명령을 실행하면 wakeup명령에 의해 다시 시작한다

수정된 세마포 정의

세마포를 record로 정의한다

Type semaphore = record
Value : integer;
L: lists of process;
End

세마포의 값이 음수이면, 그것의 크기(절대값)은 세마포를 기다리는 프로세스들이 수이다.

세마포 동작의 정의 코드 확인

Wait(s)
{
S.value = s.value -1;
If(s.value <0)
Then begin
Add this process to s.L;
Block;
End
}

Signal(s)
{
S.value = s.value +1;
If(s.value <=0)
Then begin
Remove a process p from s.L;
Wakeup(p);
End
}

교착상태

2개 이상의 프로세스가 절대 발생하지 않는 이벤트를 기다리고 있는 상태

해결방법

프로세스나 리소스에 우선 순위를 정하거나
자원 공유시에 DeadLock 안생긴다

식사하는 철학자 경위 교착상태 생기는 이유

젓가락은 공유 안됨

컴퓨터에서도 프린터나 메모리든지 리소스도 공유안한다

프로세스가 자원을 이용하는 순서

1.요청 - 요청이 즉시 허용되지 않으면, 대기 상태로 들어간다

2.사용

3.해제

교착 상태가 발생하기 위한 4가지 조건

1. 상호배제(mutual exclusion) - 자원들이 서로 다른 프로세스에 의해서 동시에 사용될 수 없다

2. 점유대기(hold and wait) - 프로세스가 이미 어떤 자원을 할당 받은 상태에서 다른 자원을 기다린다

3. 비선점(no preemption) - 프로세스가 어떤 자원의 사용을 끝낼 때까지 다른 프로세스가 그 자원을 뺏을 수 없다.

4. 순환대기(circular wait) - 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고있다.
즉 자원 할당 그래프에서 원형(cycle)을 그리는 상태

자원 할당 그래프

원은 프로세스를 의미
사각형은 자원을 의미

사각형에서 원으로 향하는 화살표 : 자원이 이미 할당
원에서 사각형으로의 화살표 : 자원 요청

교착 상태 발생 여부

1. 자원 할당 그래프에 주기가 존재하지 않으면 교착 상태 발생 않는다

2. 주기 존재하면
-각 자원 형태가 정확하게 하나의 지원만이 가지면 : 교착 상태 발생
- 각 자원의 형태에 여러 개의 자원들이 있으면: 주기는 교착 상태 발생의 필요 조건이지만 충분 조건은 아니다

예) 7-1, 7-2, 7-3

7-2만 교착 상태에 빠졌다

교착상태 처리 방법

1. 방지(prevention)- 4가지 원인 중 하나 이상을 제거하여 원천적으로 발생하지 않도록 하는 것
자원 사용의 비효율성이 있을 수 있다.

2. 회피(avoidance) - 교착 상태가 발생하지 않는 상태일 때만 자원을 할당하는 방법

3. 탐지와 회복(detection and recovery)-교착 상태가 발생하면 이를 감지하고 교착 상태를 해제하는 것
실행 중인 프로세스들 중의 특정 프로세스를 중지 시켜야 해서 결정이 쉽지 않다.

4. 무시 (ignore) - 교착 상태의 발생 여부를 무시

교착상태 처리방법중 방지의 4가지 방법중 점유와 대기 조건 배제

프로세스가 자원을 요청할 때마다 다른 자원들을 점유하지 안하도록 조장해야 한다.

프로토콜 1 : 실행되기 전에 모든 자원 함께 할당
프로토콜2: 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있다.( 자원을 더 요청하려면 할당된 모든 자원을 먼저 해제)

예) 테이프 드라이브에서 디스크 파일로 자료를 복사하고, 정렬한 다음에 프린터에 결과를 인쇄하는 프로세스 경우

프로토콜1:
모든 자원 요청: (프린터는 마지막 단계에서 필요하더라도 전체 실행시킨 동안 프린트 점유 - 비효율적)

프로토콜2:
.테이프 드라이브와 디스크 파일 먼저 요청
.테이프에서 디스크로 복사한 후
.테이프 드라이브와 디스크 파일 해제(반납)
.디스크 파인과 프린터 요청
.디스크에서 프린터로 인쇄 후 두 자원 해제
.프로세스 종료

점유와 대기 배제에서의 두 프로토콜의 단점

1. 많은 자원이 할당되어서 오랫동안 사용될지 않기 때문에 자원의 이용도가 낮다

2. 기아 상태가 존재 할 수 있다
자주 쓰이는 자원들을 여러 개 필요로 하는 프로세스는 끝없이 대기 해야 한다

교착상태 처리방법중 방지의 4가지 방법중 상호 배제 조건 배제

자원의 공유를 허용한다.
어떤 자원들은 공유가 불가능한 곳도 있다

교착상태 처리방법중 방지의 4가지 방법중 비선점 조건 배제

프로토콜1: 선점 당함
프로세스가 즉시 할당 받을 수 없는 다른 자원을 요청하면, 현재 점유하고 있는 모든 자원들은 선점된다
선점된 자원들은 대기 중인 프로세스를 위하여 자원들의 리스트에 추가
프로세스는 요청한 자원과 선점된 옛 자원들을 다시 확보해야 다시 시작할 수 있다

프로토콜: 선점 함
프린트 봐

비선점 조건 배제에서의 두 프로토콜의 단점

1. Cpu레지스터가 메모리 공간처럼 상태가 쉽게 기억되고 재사용돌 수 있는 자원들에만 적용된다

2. 일반적으로 프린터나 테이프 드라이브같이 자원들에는 적용할 수 없다.

교착상태 처리방법중 방지의 4가지 방법중 순환 대기 조건 배제

모든 자원 형태들을 전체 순서를 부여하며, 각 프로세스가 열거된 상태에서 오름차순으로 자원을 요청한다.

프로토콜1- 오름차순으로만 요청
프린트 봐

프로토콜2 - 자원을 요청할 때 그보다 우선순위 낮은 자원은 해제한다

모든 교착 상태 방지 방법의 단점

장치의 이용률이 저하되고, 시스템 처리율이 감소

교착상태 처리방법중 방지의 4가지 방법중 교착 상태 회피

교착 상태 회피 모형

.자원들을 요청하는 데 필요한 추가 정보를 미리 요구
.각 프로세스가 필요한 각 형태의 자원하다 최대급의 숫자를 선언하면
시스템이 교착 상태로 되지 않을 확실한 알고리즘을 만들 수 있다
.자원 할당 상태는 가용한 자원의 수, 할당된 자원을 수, 그리고 프로세스들이 최대 요구 수에 의해서 정의된다

Safe상태에서 unsafe상태로 들어가지 않도록 하는 것이

Avoidance 회피이다

안정상태(safe state)

시스템이 각각의 프로세스에게 특정한 순서대로 자원들을 할당하고 나서도 교착 상태에 빠지지 않았을 때 안정 상태라고 한다

Safe sequence

모든 Pi에 대해서 Pi가 요청한 자원들이 현재 사용 가능한 자원들과 j<i인 모든 Pj가 점유한 자원들로부터 만족될 수 있다면
프로세스들의 순서 <p1,p2,p3.......pn>은 safe sequence이다.

Safe sequence가 존재할 때 시스템이 안정 상태에 있다고 할 수 있다

안정상태는 교착 상태?

아니다

불안정 상태

교착 상태는 불안정 상태이다
불안정 상태라고해서 모두 교착 상태는 아니나, 교착 상태로 될 수 있다

마그네틱 테이프 드라이브 12 개 예를 이해하라

재밌어

교착 상태 회피를 이루기 위해서 무슨 알고리즘이 있나?

은행가 알고리즘

교착상태 처리방법중 교착 상태 탐지

.각 자원 형태라도 자원이 한 개씩 있는 경우- 대기 그래프를 사용

.자원 형태마다 여러 개의 자원이 있는 경우: 은행가 알고리즘 사용

1.각 자원 형태 마다 자원이 한 개씩 있는 경우

자원 할당 그래프의 변형인 대기 그래프를 사용

대기 그래프 - 자원 할당 그래프에서 자원 형태 노드와 관련 간선을 제거함으로써 구성된다

교착 상태는 대기 그래프에서 순환(circle)이 존재할 때 발생한다

2.자원 형태마다 여러 개의 자원이 있는 경우

Banker's 알고리즘과 유사한 기법이 있다

교착상태 처리방법중 교착 상태초부터 회복

1. 프로세스 중지
.교착 상태 프로세스 모두 중지

.교착 상태가 해결될 때까지 한 프로세스마다 중지

2. 자원 선점(os가 뺏어 옮): 프로세스로부터 자원을 선점해 이들을 교착 상태가 해결될 때까지 다른 프로세스에게 주어야 하며,
희생자 선택, 복귀 방법, 기아 상태의 문제들을 해결해야 한다.

1. 프로세스 중지

. 교착 상태 프로세스 모두 중지 : 확실하게 교착 상태 해결이지만 비용이 많이 든다(프로세스들이 오랫동안 연산했을 가능성있다)

.교착 상태가 해결될 때까지 한 프로세스마다 중지:
각 프로세스가 중지될 때마다 교착 상태 탐지 알고리즘 호출해야-> 부담이 크다

.프로세스 중지 원칙
프로세스의 우선 순위
지금까지 프로세스가 수행된 시간과 종료하는 데 필요한 시간
프로세스가 사용한 자원의 형태와 수
프로세스가 종료를 위해 더 필요한 자원의 수
종료하는 데 필요한 프로세스들의 수
프로세스가 대화식인지 일괄식인지 여부

2. 자원 선점

프로세스로부터 자원을 선점해 이들을 교착 상태가 해결될 때까지 다른 프로세스에게 주어야 한다

.해결해야만 사항

{ . 희생자 선택 - 어느 자원과 어느 프로세스들이 선점될 것인가 선택.
비용을 최소화 하기 위해 선점 순서 결정
비용 요인 (프로세스가 점유하고 있는 자원의 ㄸ0수,
교착 상태,
지금까지 실행하는 데 소요한 시간)
. 복귀- 프로세스를 중지시키고 재 시작하는 것이다.
프로세스를 단지 교착 상태에서 벗어날 정도로 복귀시킬 수
있다면 효과적이다
.기아상태 - 프로세스가 단지 작은 시간 동안만 희생자로 지정된다는
것을 확실하게 보장해야 함

대부분의 일상적인 해결 방법은 비용 요소로 복귀의 수를 포함시킨다
}

Other sets by this creator

google sign in for firebase database

5 terms

sgraphy

how to

2 terms

sgraphy

SingleView D:\xamarin_ios\all new\Hello\Hello

8 terms

sgraphy

ealbum에서 기본적으로 알아야 하는것들

3 terms

sgraphy

Other Quizlet sets

Section 1: Intro real estate

28 terms

hailey_hall174

AP Gov Midterm Exam Practice Questions Chapters 1-8

177 terms

bobannon11

CDFM Module 3, Area 2 Finance

197 terms

Kls2381

AllCards1020

165 terms

squire215