머신 명령어(Machine Instruction)

각각의 프로세서들이 0과 1로 이루어진 머신 명령어를 실행

어셈블리 언어(Assembly Language)

인간이 읽을 수 있으며, 머신 명령어와 1:1 매칭

고급 언어

대부분의 명령들이 여러 머신 명령어로 변환됨

동기화

3.4.1 섹션에서 bounded buffer를 이용해 프로세스(생산자, 소비자)끼리 메모리를 공유하지만, 동시에 공유메모리에 접근해서 쓸 경우 데이터 불일치 문제 발생 (레이스 컨디션)

프로세스 간의 Process synchronization과 coordination으로 해결해야 한다.

크리티컬 섹션(Critical Section)

공유메모리를 수정하는 코드로, 동시에 두개 이상의 프로세스가 크리티컬 섹션을 실행하고 있으면 안된다.

크리티컬 섹션 문제(critical section problem)

프로세스들이 상호작용할 수 있게 하는 프로토콜을 디자인하는 것.

프로세스의 기본적인 구조

do {

	[entry section]

    	critical section

    [exit section]

    	remainder section

} while (TRUE);

크리티컬 섹션 문제의 해결조건 3가지

Mutual Exclusion

만약 프로세스 P~i~ 가 크리티컬 섹션을 실행중이면, 다른 프로세스가 해당 크리티컬 섹션에서 실행될 수 없다.

Progress

크리티컬 섹션에 진입한 프로세스가 없고, 몇몇 프로세스들이 실행하고자 한다면 어느 프로세스가 들어갈지 결정해준다.

Bounded waiting

크리티컬 섹션에 대한 request(요청)가 발생되고, grant(허용)되기 전에, 크리티컬 섹션에 대한 접근 대기 시간은 한정되어야 한다.

각 프로세스의 진행속도는 0이 아니라고 가정하지만, n개의 프로세스간의 상대적인 속도는 가정할 수 없다.

운영체제에서의 크리티컬 섹션 문제 해결방법

preemptive kernels vs nonpreemptive kernels

대부분 preemptive방식을 선호한다. 너무 길게 특정 커널 프로세스가 실행되지 않아 반응성이 좋고, 실제(real time) 프로그래밍에 적합하기 때문이다.

소프트웨어 기반 크리티컬 섹션 문제 해결 //바운딩 해결방법

Peterson’s Solution

LOAD/STORE 명령어가 atomic 하다고 가정해보자..

turn과 flag 변수를 공유한다.

//Program 1

do	{

	flag[i] = TRUE;

    turn = j;

    while (flag[j] == TRUE && turn == j);

    // [critical section]

    flag[i] = FALSE;

    // [remainder section]

} while (TRUE);

do	{

//Program 2

	flag[j] = TRUE;

    turn = i;

    while (flag[i] == TRUE && turn == i);

    // [critical section]

    flag[j] = FALSE;

    // [remainder section]

} while (TRUE);

Mutual exclusion을 만족한다.

P~i~ 가 크리티컬 섹션에 들어가기 위해서는 flag[j] == False 또는 turn == i
P~i~ 와 P~j~ 가 동시에 크리티컬 섹션을 실행하기 위해서는 flag[i] == flag[j] == TRUE
turn은 i나 j 중 하나이므로 P~i~ 와 P~j~ 는 while문을 동시에 실행할 수 없다.

Progress & Bounded waiting을 만족한다.

만약 P~j~ 가 크리티컬 섹션에 들어갈 준비가 안 되었다면, flag[j] == FALSE, 즉 P~i~가 크리티컬 섹션에 들어갈 수 있다.
만약 P~j~ 가 flag[j]를 TRUE로 설정하고, 또한 while 루프를 실행중이면
- 1) turn == i일 경우, P~i~가 크리티컬 섹션에 들어간다.
- 2) turn == j일 경우, P~j~가 크리티컬 섹션에 들어간다.
크리티컬 섹션을 빠져나오면,
- 1) flag[i]를 FALSE로 설정해서 P~j~가 크리티컬 섹션에 들어간다.
- 2) flag[j]를 FALSE로 설정해서 P~i~가 크리티컬 섹션에 들어간다.
첫 실행이 다 끝나고 다음 루프에서는
- 만약 P~i~가 flag[i]를 TRUE로 설정하면, turn을 j로 설정해야 한다.
- 만약 P~j~가 flag[j]를 TRUE로 설정하면, turn을 i로 설정해야 한다.
그러므로 최대 P~j~가 한번 실행된 후 P~i~가 실행될 것이므로 Bounded Waiting 만족

하드웨어 기반 크리티컬 섹션 문제 해결

하드웨어 싱크로(Synchronization Hardware) - Lock 사용

niprocessor - 인터럽트를 비활성화한다.

현재 실행중인 코드는 간섭을 받지 않는다.

보통 멀티프로세서 시스템에서는 매우비효율적이므로 거의 실현 불가능하기 때문에(이것을 사용하는 운영체제는 확장성이 떨어진다, 시계같은 경우 매번 인터럽트를 발생한다.)(인터럽트 비활성화 시 모든 프로세스에게 메세지를 전달해야 하므로 비효율적), 이를 위한 하드웨어 명령어를 따로 지원한다.

Atomic : 인터럽트 불가능한 명령어

ex) TestAndSet() 명령어, Swap() 명령어

***TestAndSet()

booleanTestAndSet(boolean*target) {

	boolean rv = *target;

    *target = TRUE;

    return rv;

}

do {

	while (TestAndSet(&lock)) ; //lock의 초기값은 FALSE

    // critical section

    lock = FALSE;

    // remainder section

} while (TRUE);

=> Bounded Waiting을 만족하지 못한다.

Swap

void  Swap(bllean*a, boolean*b) {

	boolean temp = *a;

    *a = b;

    *b = temp;

}

do {

	key = TRUE;

    while (key == TRUE)

    Swap(&lock, &key);

    // critical section

    lock = FALSE;

    // remainder section

} while (TRUE);

=> Bounded Waiting을 만족하지 못한다.

do {

	waiting[i] = TRUE;

    key = TRUE;

    while (waiting[i] && key)

    	key = TestAndSet(&lock);

    waiting[i] = FALSE;

    // critical section

    j = (i+1) % n;

    while ((j != i) && !waiting[j])

    	j = (j+1) % n;

    if (j == i)

    	lock = FALSE;

    else

    	waiting[j] = FALSE;

    // remainder section

} while (TRUE);

Mutex Lock(Mutual exclusion Lock)

운영체제 상에서만 지원하는 Lock을 프로그래머가 사용할 수 있도록 만든 도구로, aquire과 release는 atomic하게 동작한다.

acquire() {

	while (!available)

    ; /* busy wait */

    available = false;;

}

release() {

	available = true;

}

do	{

	// [Aquire lock]

    //	[critical section]

    // [Release lock]

    //	[remainder section]

} while (TRUE);

단점: mutex lock은 spinlock 이라고도 불리는데, busy waiting 상태로 계속 while문을 실행하기 때문에 효율이 떨어진다.

장점: 프로세스가 wait 상태일때 콘텍스트 스위치가 필요없다.

가끔 멀티프로세서 환경에서 프로세서의 한 스레드가 spin할 동안 다른 스레드는 크리티컬 섹션을 진행할 때 쓰인다.

세마포어(Semaphore)

세마포어 S는 wait과 signal 함수로만 접근이 가능하다.

wait(S) {

	while S <= 0;

    S--;

}

signal(S) {

	S++;

}

세마포어의 종류

바이너리 세마포어(0, 1)
카운팅 세마포어(0 ~ n)

세마포어의 사용

do {

	// [wait(mutex)]

    // [critical section]

    // [signal(mutex)]

    // [remainder section]

} while (TRUE);

//P1 process

	S~1~;

    signal(sync)

//P2 process

	wait(sync)

    S~2~;

세마포어 적용

typedef struct {

	int value;

    struct process *list;

} semaphore;

wait(semaphore *S) {

	S->value--;

    if (S->value < 0){

    	add this process to S->list;

        block();

    }

}

signal(semaphore *S) {

	S->value++;

    if(S->value <= 0) {

    	remove a process P from S->list;

        wakeup(P)

    }

}

Busy waiting

프로세스가 크리티컬 섹션을 실행중일 때, 접근하려는 다른 모든 프로세스는 entry code에서 루프를 돈다.

Blocking & Wake-up

프로세스가 wait()을 하고 세마포어가 negative인지 체크하면 프로세스가 block상태가 된다.

(waiting queue에 들어간다.)

프로세스는 다른 프로세스가 signal() 을 실행해서 되살려야된다.

bounded waiting을 만족시키려면 FIFO 큐 방식 구현

싱글코어 프로세서: 인터럽트를 이용해서 wait과 signal 구현

멀티코어 프로세서: 인터럽트는 항상 비활성화되어 있어야 하고(다른 프로세서의 프로세스들끼리 독자적인 방법으로 상호작용할 확률이 있기 때문에), 이는 심각한 성능 저하를 일으킬 수 있다. 그래서 SMP 시스템은 대체 lock 테크닉(compare_and_swap이나 spinlock과 같은 명령셋)을 제공해주어야 한다.

완전히 busy waiting을 떨쳐내지는 못했지만, busy waiting을 어플리케이션에서 커널 단으로 옮기고, wait과 signal 명령의 크리티컬 섹션으로 제한해놨고, 이 섹션들은 짧다. 그러므로, 크리티컬 섹션은 거의 점유되지 않고, busy waiting은 가끔 짧게 일어난다.

(중요한 섹션이 길거나(분 또는 심지어 시간) 거의 항상 점유될 수 있는 애플리케이션 프로그램에는 전혀 다른 상황이 존재한다. 그러한 경우, 바쁜 기다림은 매우 비효율적이다.)??

세마포어 문제

데드락, starvation, Priority Inversion 문제

데드락

//P~0~

wait(S);

wait(Q);

...

signal(S);

signal(Q);

//P~1~

wait(Q);

wait(S);

...

signal(Q);

sitnal(S);

굶주림(Starvation)

무한(Indefinite) 블로킹(blocking)

세마포어 큐에서 영원히 제거되지 않을 수 있다.

LIFO 순서로 프로세스를 큐에서 제거하게 되면 발생하는 문제

*** Priority Inversion 문제

획득: Lock = wait

해제: Unlock = signal

27p 29p 그림

Priority Inheritance Protocol (우선 순위 계승)

특정 프로세스가 우선 순위가 높은 프로세스에서 요구하는 자원을 가지고 있을 때, 프로세스의 우선 순위를 자원을 요구하는 프로세스의 우선순위로 높여주는 기법

Classic Problems

Bounded Buffer Problem

N개의 버퍼와 각각의 버퍼가 오직 하나의 아이템만 획득 가능

세마포어

mutex
- 버퍼 풀(buffer pool)에 접근하기 위한 Mutual exclusion
- 1으로 초기화
full
- 가득찬 버퍼의 개수를 센다.
- 0으로 초기화
empty
- 비어있는 버퍼의 개수를 센다.
- N으로 초기화

do   {

	// produce an itmein

    nextpwait(empty);

    wait(mutex);

    // add nextpto buffer

    signal(mutex)

    signal(full);

} while (TRUE)

wait(mutex)가 먼저 나오고 wait(empty)나 wait(full)을 부르게 될 경우 deadlock

Readers-Writers Problem

여러 명의 사용자가 동시에 읽을 수 있고, 한 사용자만 쓸 수 있게 할 때

readcount
- 얼마나 많은 프로세스가 데이터를 읽고있는지
mutex
- readcount가 업데이트되었을 때 mutual exclusion을 보장한다.
wrt(rw_mutex)
- writer에서 mutual exclusion semaphore과 같은 기능들
- 1로 초기화된다.

writer:

do   {

	wait(wrt);

    // writing is performed

    signal(wrt);

} while (TRUE);

reader:

do   {

	wait(mutex);

    readcount++;

    if (readcount== 1)

    	wait(wrt);

    signal(mutex);

    // reading is performed

    wait(mutex);

    readcount--;

    if (readcount== 0)

    	signal(wrt);

    signal(mutex);

} while (TRUE);

Dining-Philosophers Problem

do   {

	wait(chopstick[i]);

    wait(chopstick[(i+1)%5]);

    // eat

    signal(chopstick[i]);

    signal(chopstick[(i+1)%5]);

    // think

} while (TRUE);

데드락 발생 가능

해결법

최대 4명의 철학자만 식사를 하도록 한다.
2 개의 젓가락이 모두 존재할 때만 젓가락을 획득하도록 한다.
비대칭(asymmetric) 해결법을 쓴다. 홀수 자리의 철학자는 왼쪽-오른쪽 순으로, 짝수 자리의 철학자는 오른쪽-왼쪽 순으로 젓가락을 획득한다.

Monitor

세마포어를 잘못 사용하거나 빠뜨리면 찾기 어려운 타이밍 오류를 발생시킨다.

고수준의 데이터 타입으로, 프로세스 동기화를 위해 편리하고 효과적인 매커니즘을 제공한다.

프로그래머가 정의한 명령 셋을 present

Presents a set of programmer-defined operations that are provided mutual exclusion within the monitor

모니터 구현 (uses Condition value to control the thread or process)

monitor monitor_name

{

	//shared variable declaration

    procedure P1 (...) {

    	...

    }

    procedure P2 (...) {

    	...

    }

    initialization code (...) {

    }

}

조건(Condition) 변수들

x.wait()
- A process that invokes the operation is suspended
x.signal()
- Resumes one of the process that has been wait()

monitor ResourceAllocator

{

	boolean busy;

    condition x;

    void aquire(int time) {

    	if(busy)

        	x.wait(time);

        busy = TRUE;

    }

    void release() {

    	busy = FALSE;

    	x.signal();

    }

    initialization code(){

    	busy = FALSE;

    }

}

process A:

ResourceAllocator aPrinter;

int main(void) {

	...

    aPrinter.acquire(100);

    //print out something

    aPrinter.release();

}

process B:

ResourceAllocator aPrinter;

int main(void) {

	...

    aPrinter.acquire(200);

    //print out something

    aPrinter.release();

}

데드락(Deadlock)

각각의 blocking 상태의 프로세스들이 리소스를 가진 상태로 서로에게 자원을 요청할 때

a set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set

시스템 모델

리소스 타입 R~i~(CPU 사이클, 메모리 공간, I/O 장치)
각각의 리소스 타입(R~i~는 W~i~ 인스턴스를 가짐)
각각의 프로세스는 리소스를 다음과같이 utilize함
- Request
- Use
- Release

데드락 조건(conditions)

네 개의 조건이 동시에 만족되면 데드락 발생 가능성이 있다.

Mutual Exclusion
- 동시에 하나의 프로세스만 자원을 사용할 수 있고, 요청하는 다른 프로세스는 기다려야 한다.
- -> 적어도 하나의 자원이 공유불가능한 모드로 사용되고 있어야 한다.
Hold and Wait
- 적어도 하나의 리소스를 홀딩중인 프로세스가 다른 프로세스에 의해 홀딩된 추가로 필요한 자원을 획득하기 위해 기다린다.
No Preemption
- 리소스는 홀딩되고 있는 프로세스가 직접 릴리즈해야만 된다.
Circular Wait
- 리소스 요청(Wait)이 꼬리를 물며 원형을 이루게 될 때 발생한다.
- 하나의 리소스에 하나의 인스턴스: 데드락 100%
- 하나의 리소스에 여러개의 인스턴스: 데드락 발생 가능성 있음

리소스 할당 그래프

verticles V와 edge E의 집합

P = {P~0~, P~1~, …, P~n~}: 시스템에 존재하는 모든 프로세스

R = {R~0~, R~1~, …, R~m~}: 시스템에 존재하는 모든 리소스 타입

E = {P~1~->R~2~, …}: 엣지

데드락 방지(prevention)

적어도 조건 중 하나를 충족하지 않음을 보인다,

Mutual Exclusion
- 공유 자원에는 필요가 없다. 공유불가능한 리소스를 홀드해야 한다.
- 보통 우리는 mutual exclusion을 거부해서 데드락을 방지할 수 없다. 왜냐면 몇몇 리소스들은 intrinsically 공유불가능하기 때문이다.
Hold and Wait
- 프로세스가 자원을 요청할 때, 다른 리소스를 홀드하지 않고 있다는 것을 보장해야 한다.
- 프로세스가 시작되기 전 모든 리소스를 할당하고 요청하거나, 프로세스가 리소스를 가지고 있지 않음을 필요로 한다.
- 낮은 리소스 최적화 + starvation 가능성
No Preemption
- 보유한 리소스가 있는 상태에서 다른 리소스를 요청하면 모든 리소스를 drop하고 모든 리소스를 한번에 받을 수 있을 때 다시 시작한다,
Circular Wait
- 모든 리소스 유형의 전체 순서를 지정하며 각 프로세스가 증가하는 열거 순서에 따라 리소스를 요청하도록 요구
- 프로세스가 현재 보유하고 있는 인스턴스 유형이 R~i~인 경우, 프로세스는 F(R~j~) > F(R~i~)인 경우에만 R~j~ 리소스 유형의 인스턴스를 요청할 수 있다.

데드락 회피(avoidance)

시스템이 추가적인 priori 정보를 가지고 있다고 한다
- 현재 가능한 리소스들
- 각각의 프로세스에 할당된 리소스들
- 각각의 프로세스에 대해 요청될 또는 릴리즈될 정보

데드락 진입 후 복구 Wait

모든 리소스 유형의 전체 순서를 지정하며 각 프로세스가 증가하는 열거 순서에 따라 리소스를 요청하도록 요구
프로세스가 현재 보유하고 있는 인스턴스 유형이 R~i~인 경우, 프로세스는 F(R~j~) > F(R~i~)인 경우에만 R~j~ 리소스 유형의 인스턴스를 요청할 수 있다.

데드락 회피(avoidance)

시스템이 추가적인 priori 정보를 가지고 있다고 한다
- 현재 가능한 리소스들
- 각각의 프로세스에 할당된 리소스들
- 각각의 프로세스에 대해 요청될 또는 릴리즈될 정보

심플하고 가장 유용한 모델은 각각의 프로세스들이 필요할 수 있는 각각의 타입에 대한 최대 리소스 갯수를 정의하는것을 필요로 한다.

이를 통해서 circular wait을 원초적으로 차단하는것이 이 알고리즘의 목적이다.

Safe State

프로세스가 자원을 요청하면, 자원을 준 후에도 Safe State를 유지하는지 시스템이 판별

모든 프로세스의 시퀀스 {P~0~, P~1~, P~2~, …, P~n~}가 존재하고 그러한 각각의 P~i~에 대하여, P~i~가 요청할 수 있는 자원들이 “현재 가능한 자원 + 모든 P~j~에 홀드된 자원”에 대해 j<i를 만족해야 한다.

만약 P~i~가 필요한 자원이 현재 불가능하다면, P~i~가 모든 P~j~가 끝날 때까지 기다린다.
P~j~가 끝나면, P~i~가 필요한 자원을 얻어 실행하고, 자원을 반환 후 종료한다.
P~i~가 종료되면, P~i+1~이 반복한다.

safe state: 데드락이 없다.

unsafe state: 데드락 가능성이 있음.

리소스 유틸라이제이션 감소

데드락 회피 알고리즘 (Deadlock Avoidance Algorithm)

자원 타입의 싱글 인스턴스
- resource-allocation 그래프를 사용
자원 타입의 여러 인스턴스
- banker 알고리즘을 사용한다

Resource-Allocation 그래프 Scheme

Claim edge P~i~ -> R~j~ 는 P~i~ 프로세스가 R~j~ 리소스를 요청할 수 있다는것을 ‘-‘으로 표현한다.

Claim edge는 프로세스가 자원을 요청하면 request edge로 바뀐다.

Request edge는 자원이 프로세스에 할당되면 assignment edge로 바뀐다.

// request(P~i~->R~j~) -> assignment(R~i~->P~j~) 때 사이클이 만들어지지 않아야 유효하다.

리소스가 프로세스에 의해 release 됨 -> claim edge

리소스는 시스템에서 선행되어야 한다.

Banker’s 알고리즘

sch_bankers

리소스 타입이 다중 인스턴스를 가지는 시스템

데이타 구조

n: 프로세스의 갯수
m: 리소스 타입의 갯수
Available: 길이가 m인 벡터
- if Available[j] = k, R~j~ = available
Max
- if Max[i,j] = k, P~i~ request R~j~ * k instance
Allocation
- if Allocation[i,j] = k, P~i~ is using R~j~ * k instance
Need
- if Need[i,j] = k, P~i~ need R~j~ * k instance

Need = Max - Allocation

Safety algorithm in banker’s algorithm

Work = Available, Finish[i] = false로 초기값 설정
Finish[i] == false && Need~i~ <= Work 인 i를 찾음
Work = Work + Allocation~i~ , Finish[i] = true , goto step 2
만약 모든 Finish가 true면 Safe State

Resource request algorithm in banker’s algorithm

만약 Request가 need보다 크면 오류 발생
만약 Request가 Available보다 크면 wait 상태
Available = Available - Request

Allocation = Allocation + Request

Need = Need - Request

만약 safe하면 할당, unsafe하면 P~i~를 멈추고, 할당 상태를 복원한다.

데드락 탐지(detection)

탐지 알고리즘

시스템이 데드락에 빠지는것을 허용

하나의 타입에 싱글 인스턴스: (wait-for 그래프 사용)

sch_waitfor

여러 타입에 여러 인스턴스: (banker 알고리즘 변형)

sch_deadlockdetect1

sch_deadlockdetect2

scheme 복구

Resource allocation algorithm in deadlock detection

Available: 길이가 m인 벡터
- if Available[j] = k, R~j~ = available
Allocation
- if Allocation[i,j] = k, P~i~ is using R~j~ * k instance
Need
- if Need[i,j] = k, P~i~ need R~j~ * k instance

Safety algorithm in deadlock detection

Work = Available, 만약 Allocation이 0이 아니면 Finish[i] = false로 초기값 설정 그 반대라면 Finish[i] = true
Finish[i] == false && Request~i~ <= Work 인 i를 찾음 (없으면 step 4)
Work = Work + Allocation~i~ , Finish[i] = true , goto step 2
만약 모든 Finish가 true면 Safe State

어떤 Finish[i]가 false이면 P~i~는 데드락 상태

데드락 무시

데드락 무시 후 데드락이 시스템에 발생지 않는것처럼 가장한다. 대부분의 운영체제에서 씀

데드락 진입 후 복구

Recovery scheme

모든 데드락 프로세스를 중지

또는 하나의 프로세스를 한번에 하나씩 데드락 사이클이 없어질때까지 중지

리소스 preemption

희생자 선택 (리소스를 가지고 있는 프로세스) 후 리소스를 전부 할당 해제

다른 프로그램이 리소스를 전부 썼다면 할당 해제 전으로 롤백

starvation 가능성이 존재.

cost factor에 롤백횟수를 집어넣어 starvation을 방지해 주는 해결책이 있다.

Categories

Recent Posts

Categories ▼

운영체제2

머신 명령어(Machine Instruction)

어셈블리 언어(Assembly Language)

고급 언어

동기화

크리티컬 섹션(Critical Section)

크리티컬 섹션 문제(critical section problem)

프로세스의 기본적인 구조

크리티컬 섹션 문제의 해결조건 3가지

운영체제에서의 크리티컬 섹션 문제 해결방법

소프트웨어 기반 크리티컬 섹션 문제 해결 //바운딩 해결방법

Peterson’s Solution

하드웨어 기반 크리티컬 섹션 문제 해결

하드웨어 싱크로(Synchronization Hardware) - Lock 사용

Mutex Lock(Mutual exclusion Lock)

세마포어(Semaphore)

Priority Inheritance Protocol (우선 순위 계승)

Classic Problems

Bounded Buffer Problem

Readers-Writers Problem

Dining-Philosophers Problem

Monitor

데드락(Deadlock)

데드락 조건(conditions)

데드락 방지(prevention)

데드락 회피(avoidance)

데드락 진입 후 복구 Wait

데드락 회피(avoidance)

Safe State

데드락 회피 알고리즘 (Deadlock Avoidance Algorithm)

Resource-Allocation 그래프 Scheme

Banker’s 알고리즘

Safety algorithm in banker’s algorithm

Resource request algorithm in banker’s algorithm

데드락 탐지(detection)

탐지 알고리즘

Resource allocation algorithm in deadlock detection

Safety algorithm in deadlock detection

데드락 무시

데드락 진입 후 복구

Recovery scheme

리소스 preemption

Categories ▼