티스토리 뷰
6-4. Hardware Support for Synchronization
- Peterson's solution과 같은 sw기반 해결책은 올바른 작동을 보장하지 못한다.
- 다음 Hardware명령어는 임계구역(Critical Section)문제를 해결해주며 Atomic(원자성)을 보장한다.
- Test-And-Set instruction -> spinlock 잘돌아가도록! : 상호배제만 구현 (Mutual Exclusion)
typedef struct __lock_t {
int flag;
} lock_t;
void init(lock_t *lock) {
// 0 은 락이 획득 가능한 상태를 표시, 1 은 락을 획득했음을 표시
lock−>flag = 0;
}
void lock(lock_t *lock) {
while (TestAndSet(&lock−>flag, 1) == 1)
; // lock 만들어, busy-waiting = spinlock
}
void unlock(lock_t *lock) {
lock−>flag = 0;
}- Compare-And-Swap instruction : Critical-Section 문제 해결: Mutual Exclusion, Progress, Bounded Waiting, perforamnce
void lock(lock_t *lock) {
while (CompareAndSwap(&lock−>flag, 0, 1) == 1)
; // lock 만들어
}
6.5 Higher-level SW tools: SpinLock
Spinlock
lock 확보이유: 공유변수가 있기 때문
Q. spinlock이 single보다 multi-processor에 더 적합한 이유는?
A. spinlock을 벗어나게 하는 조건은 다른 process를 실행하여서 context switch가 일어나지 않아서 오버헤드가 적어지는 것이 더 유리하기 때문에 single보다는 multi-processor시스템이 더 유리하다.
- Critical Section에 진입 불가능 시 진입 가능할 때까지 루프를 돌면서 재시도하는 방식으로 구현된 lock.
- No Context switch
- busy waiting(무한루프, acquire())과 CPU 소모 해결 방법.
- yield() [무조건 양보!]: 가장 간단한 접근법, lock 사용중일 때 CPU시간 포기 후 다른 스레드 먼저 실행되도록 양 -> 무한히 양보만 하면 unlock때문에 starvation문제
- Using Queues: Sleepng [spin 대신 잠자기!]: (wait)큐를 사용해 thread를 sleep track에 넣어주는 방식.
//해결책
park() //thread를 sleep상태로 만들어준다.
unpark(threadID) //threadID에 맞는 thread를 깨운다.
guard() // flag(공유변수) 동작에 대한 mutual exclusion 확보(상호배제보장, 즉 스핀락으로부터 보호)
▶몇가지 중요한 질문:
○ guard가 필요한 이유: 공유변수(flag) 동작에 대한 mutual exclusion확보
○ guard는 왜 spinlock으로 확보하는가 : spinlock시간이 굉장히 짧아서
○ park()하고 나서 guard를 해제하면? : sleep하고 guard를 0해봤자 계속 1로 오버헤드 커짐.
○ park() 직전에 lock이 해제되면?: guard를 가진 park()이기 때문에 lock못해! 그래서 영원히 잠드는 마비가 됨
→ 문제점: Wakeup/waiting race (깨우기/대기 경쟁)
→ 해결: Solaris운영체제에서 setpark()라는 새로운 syscall 도입.
setpark(): 현재 스레드가 park()하기 직전임을 알리는 system call. 만약 현재 thread의 park()직전에 다 른 thread에서 unpark()가 수행되면 interrupt가 발생해서 현재 thread를 바로 return하는 방식 으로 문제 해결.
- Futex: Linux가 제공하는 park(), unpark()와 비슷한 방법
futex_wait(address, expected) //park()와 비슷하고 setpark() 섞인기능. 만약 address가 expected와 다르면 현재 thread 즉시 return
futex_wake //unpark()와 비슷, thread를 깨우는 기능
v = *mutex; // v를 사용하는 이유: 불필요한 futex_wait 호출 제거, spinlock 제거
if (v >= 0) continue; // v가 0보다 크다는 것은 대기 중인 스레드가 0개 이상이고 lock 해제를 의미
6-6. Lock-based Concurrent Data Structures
- lock을 추가할 때 thread-safe하게!!
- single lock 추가: thread가 늘어날 때 마다 소요시간이 훅훅 늘어나고 있음 (상황악화) → no scalability! 느려져..
→ 해결: 결국 여러 thread들이 빠르고 각 작업들이 병렬적으로 처리되어 전체완료시간이 늘어나지 않는 Perfect scaling을 구현하는 것이 목표!
[ Sloppy counter ]
병렬적처리가 핵심
: local counter의 증가,
독자적 local counter(확장성),
local value의 주기적인 global counter로의 변환 (local count then reset to 0) : small S: 성능↓ 정확 , big S: 성능↑, 부정확값
ex) 4 logical counters,1 global counter
- Concurrent Linked List
6-7.(동기화를 위한) Condition Variables
- 부모가 spinlock을 통해 자식스레드의 완료를 기다리면 어마어마한 CPU Time의 낭비가 일어난다.
- 이러한 CPU낭비 줄이기 위해 Condition variable(조건변수, 일종의 큐) 사용.
① Wait: 기다리는 함수 , lock 해제
- mutex, 즉 lock을 매개변수로 갖는다.
- lock을 해제하여 대기중인 스레드에 시그널을 보내 깨운다[signal](다른 스레드가 lock을 획득하게 해주고) 원래 lock을 갖고 있던 스레드는 sleep상태로 전환한다.
- wait() 리턴전에 반드시 lock 재확보 - 경쟁조건 방지 [즉, signal보내기 전에 반드시 lock을 획득하자]
② Signal: 기다리는 함수를 깨우는 함수
- single 스레드를 깨운다.
◎ CASE #1: 부모가 자식스레드만들고 스스로 진행되도록한다.(자식 스레드 끝나길 기다려)
▶ parent: thr_join() 호출, wait child
→ child: thr_exit()호출, wake parent
→ parent: wait()에서 깨어나, return to thr_join()
◎ CASE #2: 부모가 자식스레드만들고 context switch되도록한다. (바로 자식스레드가 실행)
▶ child: thr_exit()호출, wake parent
→ parent: thr_join호출, return to main 이미 다되어있네? 그러니까 대기없이 바로 return
- thr_join에서 왜 mutex lock을 확보하는가? : 공유변수 done 즉 공유변수 값이 있기 때문
<공유변수 done의 중요성>
void thr_exit() {
done = 1;
Pthread_cond_signal(&c);
}
void thr_join() {
if (done == 0)
Pthread_cond_wait(&c);
}
- 만약 child가 즉각 동작한다면? : 부모스레드는 절대 일어나지 않을 것이다. 깨워줄 자식이 없다.
→ 실제론 왜 즉각 동작안하냐? : child가 먼저 실행하는 경우 때문에(race condition), 조건을 안보고 wait하면 깨워줄 함수가 없다.
- Producer/Consumer (Bounded Buffer) problem
: producer(put data) → buffer(공유자원) → consumer(get data)
: buffer가 shared resource이기 때문에 race condition발생할 수 있다. → 제대로 동작안한다.
(원래는 T1이 가져가야하는데 데이터가 없네,,,? 문제발생!)
깨운 스레드가 반드시 실행된다고 보장할 수 없다: mesa semantic, 이거와 반대인 반드시 실행되는게 hoare samentic
while문으로 한번더 체크하는대 얘도 딱히 해결해주지 않는다.
소비자 생산자 구분없이 깨우는게 가장 큰 문제
깨워야하는 스레드만 깨우도록 한다.
: 버퍼크기는 크게, 조건변수는 2개로 만들어 producer는 consumer만 깨우고, consumer는 producer만 깨우도록 하게 해줘야 모두가 sleep인 문제가 발생하지 않는다
(공유변수 총 3개. 버퍼,empty,fill)
[ producer-> buffer fill이면 sleep / consumer -> buffer empty이면 sleep ]
- Covering Conditions (조건변수 사용시 주의점)
: 메모리를 할당(allocate()) 받으려는 스레드가 여러 개일 때 어떤 스레드를 깨워야할까?
-> 해결법: signal()말고 broadcast()를 사용해 깨운다. broadcast()는 sleep상태의 모든 스레드를 깨우는 함수다.
6-8 Higher-level SW tools: Semaphore
Semaphore 완전중요
- lock과 조건변수로 모두 사용가능
- Mutex lock, counting lock, condition variable로 활용 가능한 객체
- Semaphore S는 정수변수로, wait()와 post()로 접근 가능, 원자성 가진다.
#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1); // 세마포어 변수 s를 1로 초기화int sem_wait(sem_t *s) {
decrement the value of semaphore s by one; // 세마포어 값 1 감소
if(value of semaphore s is negative)
wait; // 세마포어가 음수면 대기
}
int sem_post(sem_t *s) {
increment the value of semaphore s by one; // 세마포어 값 1 증가
if (there are one or more threads waiting)
wake one; // 하나 이상의 쓰레드가 대기중이면, 그 중 하나 깨우기
}
- Counting semaphore: 사용할 때 wait() - 카운트 감소, 음수면 대기(사용할 수 있는 자원이 없기 때문), 사용안할 때 post() - 카운트 증가, 다른스레드 wake
- Binary Semaphore(락): 초기 x=1
S가 0과 1로만 이루어짐, 2개의 프로세스에 한해 동작,
0이면 모든 자원이 사용 중,
종종 Mutual Exclusion 보장하기 위해 사용,
모든 자원이 사용 중일 때, 이후 자원을 사용하려는 프로세스는 semaphore 값이 0보다 커질 때까지 blocking 된다.
- 조건변수로서의 semaphore(condition variable): 어떤 조건이 참될때까지 기다려.
- 생산자/소비자(유한버퍼) 문제: 생산자가 full이거나 소비자가 empty면 문제, semaphore가 해
-> 해법1: 상호배제의추가(잘못된방법)
sem_t empty;
sem_t full;
sem_t mutex;
void *producer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&mutex); // p0 라인 (추가됨)
sem_wait(&empty); // p1 라인
put(i); // p2 라인
sem_post(&full); // p3 라인
sem_post(&mutex); // p4 라인 (추가됨)
}
}
void *consumer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&mutex); // c0 라인 (추가됨)
sem_wait(&full); // c1 라인
int tmp = get(); // c2 라인
sem_post(&empty); // c3 라인
sem_post(&mutex); // c4 라인 (추가됨)
printf("%d\n", tmp);
}
}
int main(int argc , char *argv[]) {
// ...
sem_init(&empty, 0, MAX); // MAX 버퍼는 비어 있는 상태로 시작
sem_init(&full, 0, 0); // ... 그리고 0이 가득 참
sem_init(&mutex, 0, 1); // 락이기 때문에 mutex=1 (추가됨)
// ...
}
-> 최종해법: lock의 범위 scope 줄여
sem_t empty;
sem_t full;
sem_t mutex;
void *producer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&empty); // p1 라인
sem_wait(&mutex); // p1.5 라인 (여기로 mutex 이동) <-
put(i); // p2 라인
sem_post(&mutex); // p2.5 라인 (... 그리고 여기) <-
sem_post(&full); // p3 라인
}
}
void *consumer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&full); // c1 라인
sem_wait(&mutex); // c1.5 라인 (여기로 mutex 이동) <-
int tmp = get(); // c2 라인
sem_post(&mutex); // c2.5 라인 (... 그리고 여기) <-
sem_post(&empty); // c3 라인
printf("%d\n", tmp);
}
}
int main(int argc , char *argv[]) {
// ...
sem_init(&empty, 0, MAX); // MAX 버퍼는 비어 있는 상태로 시작
sem_init(&full, 0, 0); // ... 그리고 0이 가득 참
sem_init(&mutex, 0, 1); // 락이기 때문에 mutex=1 (추가됨)
// ...
}
- Reader-wrriter 락 : 삽입 연산이 없다는 보장만 된다면, 다수의 검색 작업을 동시에 수행할 수 있다.
6-9. Higher-level SW tools: Monitors
Monitor
- Semaphore는 타이밍 에러가 많이 발생한다.(User Hazards)
- wait과 signal의 순서를 반대로 구현하였을 경우 : Mutual Exclusion 보장 X
signal(mutex);
...
/* critical section */
...
wait(mutex);
- signal을 wait으로 대체하였을 경우 : Bounded Waiting 보장 X
wait(mutex);
...
/* critical */
...
wait(mutex);
- 이러한 문제를 Monitor타입을 이용해 해결할 수 있다. [Mutual exclusion 보장, Bounded Waiting 보장]
- Monitor는 주요한 high-level 동기화 구조이다.
- Abstract Data Type: 추상화된 데이터 타입
- 한번에 하나의 프로세스만이 모니터와 활성화된다.
- Condition Variables: x.wait(), x.signal() → x.wait()이 변수로 없으면 x.signal도 의미 없다.
// Condition Variables in Monitor
condition x, y;
x.wait();
x.signal();'운영체제' 카테고리의 다른 글
| 13. File System (0) | 2024.06.20 |
|---|---|
| 12. I/O Device (0) | 2024.06.19 |
| 9. Main Memory (1) | 2024.06.14 |
| 8. Deadlocks - Concurrency problems (1) | 2024.06.14 |
| 2. OS Service (0) | 2024.04.26 |