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

5주차 운영체제 필기

백그라운드

가장 하위레벨: 머신 코드로 만들어지지

0,1를 이용해 코딩

è  이후 어셈블리 언어

 

 

Race condition  :

여러 개의 프로세서가 동시에 공유된 데이터에 액세스할 떄 실행순서가 어떻게 되는냐에 따라 값이 달라지는 현상(어떤 프로세서가 먼저 실행하느냐)

레이스 컨디션이 발생하는 코드에서 공유데이터를 액세스하는 코드가 존재한다.

이부분을 바로 크리티컬 섹션이라고 한다. Critical Section

여러 개의 프로세서가 공유된 데이터에 동시에 액세스하는 문제 (Critical section problem)

임의의 두 프로세서가 크리티컬 섹션에 들어가지 않게끔 해줘야한다. -> 크리티컬 섹션문제 해결

임의의 한순간에 한 프로세서만 크리티컬 섹션에 들어가게 한다.

데이터가 꺠지는 문제를 해결하는 방법론들을 설명할 것이다.

 

솔루션은 세가지 조건을 만족해야 한다 .-중요

첫번째는 mutual exclusion

임의의 한순간에 어떤 프로세서가 크리키컬 섹션에 들어가있으면 다른 프로세서는 절대 들어가지못한다 à 한순간에 하나의 프로세서만 크리티컬 섹션에 들어가 있는다.

Progress

크리티컬 섹션에 들어갈 준비가 되어있는 프로세서들만 대상으로

누가 그 크리티컬 섹션에 들어갈 것 결정하는 것

하지만 결정시에 무한정 기다리게끔해서는 안된다

Bounded Waiting

임의의 한프로세서가 크리티컬섹션에 들어갈준비가 되어있으면 그러면 일정시간이 지나면 반드시 크리티컬섹션에 들어가야한다.

무한정기다릴수없다.

프로세서간의 상대적인 속도를 가정해서는 안된다.

프로세서가 언제 contetxt switch가 일어날지는 가정할 수 없다.

Context switch는 언제든지 일어날 수 있다.

 

1.     피터순 솔루션 Peterson’s solution

두개의 프로세서만 대상으로 해결

Load(flag[j]=true &&turn ==j)와 store(flag[i]=true 이부분) 는 Atomic하게 수행!!

– 그 명령어가 수행할 때 context switch가 일어나지 않는다.(interrupt 발생하지 않는다)

변수)

turn-누가 크리티컬섹션에 들어갈것인가를 결정

flag-프로세서가 크리티컬섹션에 들어갈 준비가되어있으면 자기의 플래그변수를 true로

 설정

두가지변수에 의해 솔류션 동작

 

코드

// Pi 프로세스 코드

do {

flag[i] = TRUE;

turn = j; // pj 프로세서에게 우선권을 준다.

while (flag[j] = TRUE && turn == j); // pj도 크래티컬 섹션에 들어갈 준비가 되어있고 turn도 j이면 waiting 한다.

flag[i] = FALSE;  //critical section, 위의 코드에서 둘중 어떠한 조건도 만족하지 않으면 크리티컬 섹션으로 들어간다. 이게 끝나면 더 이상 크리티컬 섹션에 들어가지 않기 때문에 flag의 값을 false로 바꿔준다.

remainder section

} while (TRUE)

 

// Pj 프로세스 코드 (pi도 동일)

do {

flag[j] = TRUE;

turn = i;

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

flag[j] = FALSE;

 

critical section

remainder section

} while (TRUE)

이 솔루션이 크리티컬 섹션문제가 해결되느냐에 대한 증명

1.     Mutal exclusion

만족하지 않는다고 가정한다.  Pi, pj 둘다 크리티컬 섹션에 들어갈수가있다.

=(while문을 통과했다)

è  둘다 크리티컬섹션에 준비가 되어있기 때문에 flag 값 true

그럼 turn 값에의해 들어갈수있는지 결정

근데 turn이라는 값은 I 또는 j 둘중의 하나의 값만 가질 수 있다.

두 프로세서가 모두 크리티컬 섹션에 들어갈 수 있다는 것은 거짓

고로 만족한다.

다른예) 만약 pi는 크리티컬 섹션에 들어갈 준비되어있고 pj는 그렇지 않을 경우

Pj는 크리티컬섹션에 들어갈 준비안되어있기 때문에 당연히 flag는 false

고로 pi의 flag[j]가 false 값이라서 pi는 크리티컬 섹션에 들어갈 수 있다.

 

 

Bounded waiting

또다른예) 둘다 크리티컬 섹션에 들어갈 준비가 되어있을 때

Turn 값에의해서 pj가 크리티컥ㄹ 섹션에 들어왔다고 가정한다.

그 이후 다음 문장을 실행하게 되면 그때 cont4ext switch가 일어나면 pi가 크리티컬 섹션에 들어가게 된다.

하지만 bounded waiting은 언제 context switch 가 일어난다고 가정하면 안된다.

다른예제) pj가 크리티컬 섹션에 들어갔다. Pi는 들어갈준비하고있다.

pi프로세서가 크리티컬 섹션이 끝나서 flag j 값 false

여전히 cpu가 pj에 할당되어있어서 또 다시 크리티컬 섹션으로 들어간다고 가정한다.

Turn은 자기자신에의해 i로 바꾼다, 그래서 반드시 waiting해야한다. Pj의 경우

Pi의 경우 turn==j인경우 불만족하여 크리티컬 섹션에 들어간다.

 

Testandset () . swq()

è  크리티컬 섹션문제 해결하는 명령어

Testandset

Target 을 내부변수로 저장하고 true로 값을 바꾼후 반환한다.

Lock 이라는 변수를 false로 설정하여 testandset을 실행, target은 false로 설정되어있어서 rv= false가 된다.

Target을 true로 바꾼다 즉 lock이 true가 된다.

첫번째 실행하는 프로세서는 크리티컬 섹션으로 들어간다.

두번째 실행하는 프로세서는 while문 계속 돌아

 

하지만 여기서는 bounded waiting 을 만족하지 못한다.

 

Swap()

첫번째 프로세서는 크리티컬 섹션에 들어간다

또한 이방법도 바운디드 웨이팅 불만족

바운디드 웨이팅 만족하는 코드

프로세서가 4개가 있다고 가정 그중 2번이 먼저 들어간다고 가정

 

do {

waiting[i] = true; // 프로세서가 크리티컬 섹션에 들어갈 준비가 되어있으면 자신의 에이팅 변수를 TRUE로 바꿔준다. //p4가 들어간다고 하자 //p0가 들어간다고 하자

key = true;

while (waiting[i] && key) p2가 크리티컬 섹션에 들어간다.

key = test_and_set(&lock); 이후 TESTANDSET을 수행, 락의 최촛값은 FALSE

키 값은 고로 false가 되고 lock=true가 된다.

//이후 p4가 testandset을 실행한다고 하면 lock값은 true가 되어있기떄문에 key값도 true

P4는 계속 while문을 돈다. //p0도 동일한 과정으로 while 문 돈다.

waiting[i] = false;

/* critical section */

j = (i + 1) % n; // p2가 크리티컬 섹션을 빠져나왔다고가정 ,

// 자기자신이 2니깐 자기자신에 대해  연산,

while ((j != i) && !waiting[j]) // j가 크리티컬섹션에 들어갈준비가 되어있나 안되어있나를 본다. 둘다 true이기 때문에 그 다음 프로세서인 p3을 본다

j = (j + 1) % n; // (3+1) %5=4

if (j == i)

lock = false;

else

waiting[j] = false;

/* remainder section */

} while (true);

 

 

 

뮤텍스락

운체가 제공해주는 가장 간단한 솔루션

가장큰특징: busy waiting

Available이 true 면 넘어가 ,false 면 계속 while

acqure이라는 동작은 available를 활용해 동작

available이 거짓이면 계속 루프를 돌아

비지 웨이팅은 abailbabl값이 true가 될때까지 루프를 돌기 때문에 붙여짐

락을해제할 때 release()함수사용

비지웨이팅 단점 : cpu를 쓸데없이 소비

항상바쁜건아니다. 크리티컬 섹션이 아주짦다고 하면 별도의 context switch일어나지않다고해도 문제가 해결될수있다

 

Semaphore

크리티컬섹션을해결하기위한 실제솔루션

정수형 변수- S – 두개의 atomic한 오퍼레이션에 의해서만 액세스가능한 것이 세마포어

Wait와 signal이라는 오퍼레이션 이용

Wait () : 0이하일 경우 S감소,

Signal() : S 증가

동작들이 전부다 atomic하게 동작하는게 가장 큰 특징

Binary 와 countiong 세마포어 존재

Binary는 0과1만가짐-> Mutex lock, 클리티컬 섹션에드러가는 놈을 한놈만을 고정

Counting-총 n개의 프로세서가 크리티컬 섹선에 들어갈수있게 해준다.

Wait 와 signal 함수가 운영되는 과정, 역할 중요

그 다음장 매우 중요

크리티컬섹션과 process synchronization(프로세스간 실행순서를 제어할 때)  문제 해결할 때 세마포어 사용

크리티컬섹션에들어갈 때 wati라는 오퍼레이션수행

빠져나갈 때 signal함수 수행

è  하나의 프로세서만 들어갈수있게해준다

process synchronization(프로세스간 실행순서를 제어할 때) : 세마포어 사용

P1,p2 프로세서가 있고 p1실행후 p2프로세스가 바로 실행되어야할 때 세마포어 사용할 수 있다

초기값 : 0으로설정

P2는 wait()수행 p2가 먼저 실행된다해도 sync의 값이 0이기 때문에 0이하일경우에는 계속 while문을 돌고있어야한다. 그래서 계속 항상기다리고 있어야한다

S1을실행하고 signal함수를 이용해 sync값을 1로바꿔 p1 이 다 끝나야 p2가 실행되도록 한다.

 

 Semaphore의 구현 방법

1.      Busy waiting

Cpu를 반납하지 않고 계속 while문을 돌면서 S 값을 확인하는 것

비지웨이팅 단점 : cpu를 쓸데없이 소비

항상바쁜건아니다. 크리티컬 섹션이 아주짦다고 하면 별도의 context switch일어나지않다고해도 문제가 해결될수있다

 

2.      Block and wakeup

프로세스를 while문을 계속 돌게 하는게 아니라 그 프로세스를 waiting 큐에 집어넣는다, cpu를 다른 프로세스에게 할당하여 cpu  효율증가시킨다.

           Value : 세마포어의 값, list  : waiting 큐

Block : waiting 큐에 집어넣는 과정 세마포어의 값이 0이하이면 waiting 큐에 집어넣는 작업

Wake up : 세마포어 값이 0보다 크게 되면 리스트에있는 값들을 레디큐에 집어넣는 작업

signal(semaphore *S) {

 S->value++;

  if(S->value <= 0)

 

위 코드는 Block & wakeup 구조로 되어 있기 때문에 음수값을 가지는 value는 현재 waiting queue에서 대기 중인 프로세스의 수를 나타냅니다. 따라서 (S->value <= 0) 이면 현재 대기 중인 프로세스가 존재한다는 의미이며, 따라서 waiting queue에서 프로세서를 선택하여 wake up 시키게 됩니다

잘못사용하게되면 여러가지 문제 발생

S=1l고 q가 1일 때

 

P0가 s에 대해서 wait를 호출

S=0이된다. Context switch 일어난다.

P1프로세스가 q에 대해서 wait 호출 - > q가 0이 된다 . Context switch 일어난다.

P0에서 q에 대해서 호출하게 되면 이미 q는 0이기 떄문에 whlie문을 돈다.

P1에서 s에 대해서 호출하게 되면 이미 s는 0이기 때문에 p1프로세스가 s에대해서 wait해야 한다.

즉 p0는 p1이 q에 대해서 signal(q)하기 기다리고있고

P1은 p0이 s 에 대해서 signal(s)하기 기다리고 있다

그래서 둘다 멈춰야 하는 현상이 발생 à 이를 데드락이라고 한다.

 

스타베이션 : 우리가 세마포어를 잘못 구현했을 때 생길수있는 문제

큐를 관리할 때 큐에 프로세서를 넣고 빼는 과정을 LIFO을 쓰게되면

뒤에있는애들이 먼저빠져나올경우 그 앞에있는애들은 무작정 기다려야하는 문제 발생

그래서 FIFO로 구현해야 스타베이션 문제 해결가능