[운영체제 ] 6주차 정리본

6주차 운영체제 필기

 

우선 순위 inversion (우선순위 역전 )

우선 순위가 낮은 순위를 가진 자원이 lock을 가져서 우선순위가 높은 순위를 가진 자원이 실행하지 못하는 문제

C가 우선 실행을 한다, 실행중에 wait를 호출하여 sem-a를 획득하여 크리티컬 섹션문제 해결

그러다가 높은 우선순위의 b가 들어와 b가 실행

그러다가 또 a가 들어와 a가 실행

이 상태에서 wait를 호출하여 sem-a를 요청 하지만 이미 c에 의해서 획득이 되어잇기 떄문에 a는 기다려야 되서 block이 실행된다.

결국 프로세서 c는 실행하지 못하기 때문에 a도 sem-a 때문에 실행하지 못하는 상황을

우선순위 역전 현상ㅇ을 말한다.

è  우선순위 계승으로 이 현상 해결

우선순위가 낮은 프로세스가 우선순위가 높은 프로세스를 계승하여 우선순위를 높여준다.

A가 wait를 호출하면 sem-a는 c 가 갖고있기 때문에 c의 우선순위를 a의 우선순위(1)로 높인다.

 

 

-Monitor

프로그래밍 언어에서 제공해주는 문법

Monitor에 관한 슈더코드

monitor monitor_name

{

// shared variable declaration

procedure P1 (…) { // 함수들을 선언, 함수들은 여러 개의 프로세서가 동시에 이함수들을 호출하더라고 한번에 하나씩 호출된다.

…

}

procedure P2 (…) {

…

}

initialization code (…) {

} //초기화해주는 작업

}

 

하지만 모니터는 프로세서간 실행순서를 컨트롤 할 수 없다.

 

Condition 변수

Condition 변수에 대해서 wait를 호출하게 되면 그 프로세서는 무조건 suspend되서 큐에 들어가게 된다.

Condition 변수에 대해서 시그널을 호출하게 되면 Condition 변수에 대해서 wait() 를 호출했던 모든 프로세서 중 하나를 wake up 시켜서 다시 원래 작업을 실행 할 수 있게 한다.

주의 : Condition 변수의 wait와 시그널은 세마포어의 wait 시그널과는 아무관련없다

 모니터가 존재

모니터 안에있는 프로시드를 호출하기 위하여 프로세서는 큐에 들어가게 된다.

그 다음 각 모니터 안에 존재하는 컨디션 변수는 또 다른 별도의 큐를 유지하고 있다.

이 큐내에 wait 와 시그널 호출

컨디션 변수에 대해 제약적인 조건 존재

P1도 f1을 호출 p2도 동시에 호출하게 되면 둘 중하나는 큐에 들어가있어야한다.

P2가 컨디션변수에있는 큐에서 나오게 되면 동시에 p1과 p2가 f1함수를 같이 액세스하는 경우가 발생할 수 있다.

è  크리티컬 섹션문제 발생

P가 시그널을 호출해, ,자기자신을 q에 집어넣는다.

그래서 Q가 컨디션변수에 나와서 q가 끝날때까지 기다린다.

wait(mutex); // 한 프로세서만 들어갈 수 있도록 호출

…

body of F;

…

if (next_count > 0) //다른 프로세서가 컨디션 변수에 대해서 기다리고 있으면

signal(next) // 그놈을 시그널을 호출해서 부른다.

else

signal(mutex); // 끝날때 시그널 호출

x,wait ->

x_count++; // x의 웨이터를 호출한 놈의 개수 알려준다 -> 증가시킨다.

if (next_count > 0) // 누군가가 시그널을 부른 다음에 기다리고 있는 프로세서가 있다.

signal(next); // 그 프로세서가 있으면 시그널을 불러 그 프로세서를 실행한다.

else

signal(mutex); // 프로세서가 x.wait를 하고 나머지 다른 프로세서가 f에 들어올 proceed가 없을 경우 반드시 mutex를 시그널 해줘야 한다.

wait(x_sem);

x_count--;

 

x.signal ->

 if (x_count > 0) { // 컨디션 변수에 대해서 누군가가 기다리고있으면

next_count++;

signal(x_sem); // 컨디션 변수에서 wait하고 있는 프로세서를 꺠우게 되어

wait(next); // 나 자신은 next 세마포어를 대상으로 기다리고 있어야 한다.

next_count--; //

}

 

또다른 방법은  p가 시그널호출,q가 시그널이아니라 레디큐에다가 집어넣는다.p가 끝나게 되면 q가 실행된다.

 

 

monitor ResourceAllocator

{

boolean busy;

condition x;

void acquire(int time) { // acquire 호출

if (busy) // 현재 누군가가 사용하고있으면 사용끝날때까지 기다리고 있는다.

x.wait(time);

busy = TRUE; // 누군가 사용하고 있지않으면 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();

}

 

 

 

총3개의 세마포어를 가지고 문제해결

1.    Mutax

버퍼라는 놈은 프로듀서하고컨슈머가 동시에액세스할수있어서 크리티컬섹션이다. 그래서 둘중에 하나만 들어갈수잇겠끔해서 뮤텍스를 사용

바이너리 세마포어

 

-Producer - Consumer

프로듀서는 엠티가 하나라도있으면 진행가능

하나라도 없으면 기다리고 있어야돼

버퍼가 비어있다고 확인이 되면 버퍼에 대한 독점권을 가져야 한다.

컨슈머가 사용하지 못하게끔 웨이트 뮤텍스를 호출

데이터를 집어넣고 다음에는 다른놓ㅁ이 버퍼 액세스가능하도록 시그널 호출

혹시라도 버퍼가 완전히 비어있어서 ㄷ기다리고있는 컨슈머가 있다면 컨슈머를 깨워줘야한다

è  시그널 풀 호출

컨슈머의 경우도 비슷

비어있으면 기다리고잇어야한다.-> 풀을 대상으로 웨이트

초기화 값이 0이기 대문에 프로듀스가 데이터를 집어넣고 있지않으면 기다리고 잇어야한다

프로듀스가 하나라도 데이터를 집어넣으면 시그널 풀을 호출해 웨이트 풀을 꺠워줘야한다.

0 -> 1(웨이트임패티->시그널 풀)

마찬가지로 버퍼로부터 데이터 입력을끝낸다음 버퍼가 가득차서 혹시라도 기다리고있는 프로듀스가 있다면 이를 꺠워줘야하기떄문에 시그널 앰피티를 호출새서 프로듀스의 웨이트 임패티를 깨워줘야 한다.

 

이렇게 위치를바꾸게 될경우-> 데드락 발생

 

-두번째 문제는 Readers-Writer 문제

공유데이터가 존재, 여러 개의 프로세서가 동시에 이를 액세스

리더스는 데이터를 읽어들이기만한 것, 업데이트안해

라이터는 리드와 라이터 둘다해

여러 개의 멀티풀 리더가 있고 싱글라이더가 있을 때 이를 어떻게 보호할 것인지가 중요하다.

라이터가 데이터를 액세스하고있으면 리더는 절대로 액세스 불가

반대의 경우도 마찬가지

리더만 존재할 때는 업데이트없이 데이터를 읽어들이기만하기 때문에 여러 개의 리더 액세스 가능

뮤텍스를 이용해서 데이터에 대한 액세스 권한을 가지게 된다.

뮤텍스는 리드 카운터를 액세스하기 위해 사용된다.

즉 리드 카운트는 리드가 데이터를 리드할때마다 하나씩 증가

프로세서가 공유데이터를 리드하기 위해서는 리드 카운트를 증가시켜야 한다.

리드 프로세서가 동시에 리드카운트를 액세스할려고(동시에 리드할려고 할떄) 할 때 뮤텍스를 이용하여 리드 칸우터를 보호

rw뮤텍스는 라이터가 있을경우에는 리더들이 데이터를 액세스 불가하도록 보호해준다.

라이터는 데이터를 액세스 할 때 웨이터를 호출

액세스가 끝나면 rw 뮤텍스를 이용해서 시그널 호출

è  rw뮤텍스이용해서 라이터가 데이터액세스하도있을 동안 리더가 데이터를 액세스불가하도록만들어준다

리더는 데이터를 리드 하기 전에 리드 카운트를 하나씩 증가시키고 리드가끝나면 리드 카운트를 하나씩 감소한다.

è  이는 크리티컬 섹션문제가 될수있어 리드카운트를 액세스하기전에 웨이트 뮤택스를 이용해 독점권 가진다.

리드카운트가 1일 경우에는 더 이상 라이터프로세서가 업데이트 할수없도록 막아줘야 한다.

리듵카운트가 1일 때 rw뮤텍스에 대해서 웨이트 호출

뮤텍스에대해서 시그널 호출-,다른 프로세서가 리드 카운터를 증가할 수 있게ㅔ끔

두번쩨 리드 프로세서가 진입하게 될경우 웨이트와 리드카운트 증가는 동일

이미 rw뮤텍스는 락이걸러져있어 rw뮤텍스에 대해 웨이트 호출해줄 필요없다

데이터를 읽게된후 웨이트를 걸고 리드카운트를 감소

리드카운트가 0일경우(더 이상 데이터를 읽는프로세서가 없다.)

= 라이터 프로세서가 데이터를 액세스할수잇게끔 만들어줘야한다.

따라서 리드캉운트가0일경우에 rw뮤텍스에 대해 시그널 호출해서 라이터 프로세서가 데이터를 액세스할경우 이르 시작하기 위해 뮤택스에 대한 시그널을 호출

 

리더프로세서는 동시에 데이터 리더 가능하도록, 리드 프로세서가 있을경우에는 라이터프로세서가 동작하지 못하게 한다, 반대의 경우도 동일 하다.

예제에서 시그널 뮤텍스와 웨이트 뮤택스를 뺴버리더라도 코드가 정상적으로 동작은 하지만 리더가 처음부터끝까지 독점해서 사용하기 때문에 리더가 병렬적으로 데이터읽어들이는 동작 불가

리더하나가 데이터를 읽고있으면 다른 리더들은 웨이트 뮤텍스에서 웨이팅하게 되서 병렬적으로 데이터 읽어들일수없어 효율이 떨어진다.

 

-다이닝 필라스포 문제

의자에 철학자가 앉아있고 젓가락도 사람수대로 5개만 존재, 식사를 할려면 자신의 오른쪽에있는 젓가락을 가지고 와 서 밥먹게된다. 근데 5명인데 젓가락이 10개가아니라 5개라 못먹느 사람 발생

è  이문제를 어떻게 해결할래

단순히 자신의 젓가락에 대해 웨이트를 호출하여 식사하고 자신의 옆에있는 젓가락에 시그널을 호출하면 -> 데드락 발생

자신의 왼편은 이미 락이 되어있는 경우 발생

 자신의 젓가락이 릴리즈가 될때까지 기다리는 데드락 발생

이문제를 모니터를 이용해 해결

철학자의 상태는 팅킹,헝그리,이팅상태로 나눠져있다.

self라는 컨디션변수 사용

픽업 호출한 후 식사하고 풋다운을 호출

픽업을 호출하게 되면 자신의 상태를 헝그리로 바꾼다.

테스트를 호출하여 이팅으로 바ㄱ꿔져있지않으면 자신에 관련된 컨디션변수에서 웨이팅 호출

테스트 코드 – 자신의 오른편에있는 철학자의 상태가 뭐냐, 자신의 왼쪽에있는철학자의 상태를 체크.

즉 젓가락을 얘가 사용할 수있으면 자신의 상태를 이팅으로바꾼다.

자기자신에 대한 시그널 호출,

 

반대로 풋다운이라는 메소드는

자신의 식사가끝나기 때문에 상태를 팅킹으로 바꾼다.

자신의 오른편에있는 프로세서 대상으로 테스터를 수행

이 기법의 문제점은 데드락은 발생하지 않지만 스타베이션 문제 발생

즉 어떤 찰힉지기 픽업을 할 지 알 수 없다.