* Shared Memory에서 발생하는 문제
- Concurrency : 하나의 공유 데이터에 동시 접근할 때 발생하는 문제
(데이터가 비일관적이다. data inconsistency)
> 이러한 문제를 해결하기 위해서 협동하는 process에서의 실행순서가 중요한 문제로 작용.
- Circular array로 구현시 저장공간을 100% 사용이 불가능하다.
> counter변수를 생성하여 process숫자를 관리한다.
- producer와 consumer가 동시에 동작을 한다면 실행순서에 따라 다른 결과가 나올 수 있다.
이런 경우를 race control이라고 한다. 또한 이로 인해 발생하는 문제를 critical section problem이라고한다.
* Critical Section problem
- 두 개의 프로세스가 공유되 있는 변수 또는 저장공간을 사용하는 도중에 생기는 문제(동시공유X)
> 프로토콜을 만들어 규약을 통해서 해결
- 이 규약은 process 실행 부분을 3가지로 나눠서 해결을 추구한다.
ⓐ entry section : 공유공간을 사용하고 있는지를 검사
ⓑ exit section : 자신이 공유 메모리 사용이 끝났음을 알림
ⓒ remainder section : 공유 메모리를 사용하지 않는 process부분
- 하드웨어, 소프트웨어적 해결이 가능하며, 다음을 만족해야한다.
ⓐ Mutual Exclusion : 서로 배타적
ⓑ Progress : 어떠한 프로세스도 크리티컬 section을 사용하지 않고, 대기자가 있다면 누군가는
critical section에 진입
ⓒ Bounded waiting : priority에 의해 양보하는 횟수가 정해져 있다.(starvation 방지)
* Critical section software solution
> Peterson's Algorithm
- 가정 : LOAD와 STORE에 대해서는 Atomic하다.
> turn에 대한 concurrency가 보장.
- 단 두개의 process만이 memory를 공유하고 있다.
- 두 개의 변수가 필요하다.
ⓐ turn : 현재 어떤 process가 들어갈 차래인지를 저장
ⓑ flag[2] : flag[i] : Pi가 들어갈 준비가 되었는지를 나타낸다.
* Critical section hardware solution
> Test & Set
- 특별한 단일의 HW명령어를 제공해준다.
- 이 명령어는 중간에 interrupt되지 않는 명령어 집합으로 구성된다.
- 일반적으로 test memory와 set value사이에는 시간차가 발생한다. 이를 critical section문제라고 정의했었다.
- 이를 해결하기 위해 test와 set을 하나로 묶어서 방지를 하게 된다.
boolean TestAndSet(boolean *target){ do{
boolean rv = *target; while(TestAndSet(&lock)); // wait
*target = TRUE; //critical section
return rv; lock = FALSE
} }while(TRUE);
> Test과정 : 일단 target값을 기억하고 target값을 TRUE로 변경. 이전 target값을 기억하는 이유는 다른 누군가가
사용하고 있는지 여부를 확인 하기 위해서이다. *target = TRUE과정은 아무도 memory를 점유하지
않고 있다면, 즉시 그 메모리에 대해 예약을 한후 return된 값(false)을 확인후 critical section 자리를
차지 하는 것이다.
※ 이렇게 돌아가는 과정은 swap하는 개념과 상통한다.
- 이러한 hardware solution인 test&set은 mutual exclusion과 progress를 만족한다. 하지만 bounded waiting을
만족하지 않아서 starvation이 예상된다.(busy waiting) > 이는 각각의 task에 대기표를 줌으로써 해결한다.
* Semaphore
- 위에서 자세히 다루지 않았지만 하드웨어적 해결법에서 bounded waiting을 만족시켜야 하기 때문에 별도의
작업이 필요하다. 이에 의해서 하드웨어적 해결법은 사용하기 힘들다.
- Semaphore는 S라는 integer variable을 사용하여 이를 간단하게 하려고 시도한 것이다.
또한, wait()과 signal()이라는 atomic operations을 사용한다.
wait(S){ // 들어갈때 signal(S){ // 나갈때
while S <= 0; S++;
S--; }
}
> 이 S(semaphore integer variable)는 2가지로 사용이 가능하다.
ⓐ Counting semaphore : S의 숫자가 재한되있지 않다.S가 0보다 크면 접근이 가능하다.
또한 이 숫자는 접근제한 횟수를 나타내기도 한다.
ⓑ Binary semaphore : 0과 1로 제한되어 각각의 상태는 사용가능과 불가능을 나타낸다.
이를 다른 말로 mutex locks라고도 한다.
- 단점 : 누군가 리소스 점유를 하지 않을때까지 지속적으로 while문을 돌아야 하기 때문에 CPU리소스
낭비가 생긴다. 이로인해 Busy-waiting상태가 된다.(이 상태를 spinlock이라고도 한다)
> 이 단점을 해결하기 위해서 semaphore 각각에 process list를 생산한다. 각 wait queue에서 wait()이 불릴 때,
다른 task들은 waiting상태로 변환한다. block()시킨다고도 함.
> 만일 리소스를 다 사용한 task가 밖으로 나갈때에는 다음위치에 있는 waiting queue의 semaphore를 깨운다.
wakeup(), process를 waiting queue에서 ready queue로 보낸다.
> typedef struct{
int value;
struct process * list; // semaphore의 waiting queue
} semaphore;
2개의system call, block(), wakeup()이 불린다.
implements
wait(semaphore *S){
S->value--;
if ( S->value < 0 ){ //만약 누군가 resource를 점유하고 있다면
add this process to S->list; // 내 꼬리로 붙어라 Enqueue
block(); // 그리고 waiting queue로 가서 자고 있어라
}
}
signal(semaphore *S){
S->value++;
if( S->value <= 0 ){ //만약 resource를 대기하는 process가 존재한다면,
remove a process P from S->list; // 일단 다음 프로세스를 dequeue시켜달라.
wakeup(P); // 그리고 그 프로세스를 ready queue로 보내라
}
}
> semaphore 의 waiting list는 PCB들의 리스트일 것이고 FIFO queue를 따를 것이다.
> 이때 또 2가지를 고려해봐야 한다.
* single processor vs SMP
- 하나의 프로세스만 존재하면 순차적으로 지속적으로 semaphore를 관리 해주면된다.
- 다음을 가정하자.
semaphore process list에서 P1이 P2보다 앞에 있다. 하지만 두 프로세스는 다른 프로세서에서 작동하고 있다.
하지만 P2의 우선순위는 1이고 P1의 우선순위는 9이다. P1은 다른 프로세스에게 우선순위가 밀려서 작동하지
CPU를 점유하지 못한다. 이에따라 우선순위가 높은 P2또한 계속 대기해야 한다.
이를 Priority inversion이라고 한다. 이를 해결하기 위해서 OS는 낮은 순위의 Process와 높은 순위의 Process가
같은 resource를 공유할때 높은 Process가 한 없이 기다려야 하는 것을 방지하기 위해서 priority-inheritance를
제공한다. 이는 낮은 우선순의의 프로세스를 잠시동안 우선순위를 높여서 우선 실행 해주는 것이다.
- 또 한가지 가정하자.
P1과 P2가 프로세서 위에서 동작하고 있는데, P1은 P2의 resource를 받아야하고, P2는 P1의 resource를 받아야
된다. 2프로세서는 서로가 작업이 끝나서 resource를 반납하기를 기다리는 deadlock에 걸리게 된다.
deadlock이란 2개이상의 process가 맞물려서 무한히 기다리는 상태를 말한다. 이때 OS가 중재를 통해서
deadlock을 해결한다.
- 위 2가지 경우 모두 starvation이 발생하는 것으로 OS가 관여해서 해결을 하는 것이다.