Concurrency-Contrl Problem
동시성 제어 문제들
Bounded-Buffer 문제
Producer-Consumer 문제
Readers-Writers 문제
Dining-Philosopher 문제
Bouded-Buffer Problem
P와 Q는 중간에 공유된 Buffer (shared data) 를통해 주고받는다
n개의 버퍼가 있다. 버퍼의사이즈는 n , 각각의 버퍼에 한개의 아이템보유할 수 있다.
producer 는 버퍼를 가득채우는게 목표, consumer는 producer가 버퍼를 쓸 수 있게 비워주는게 목표
Shared Data Structures
int n;
semaphore mutex = 1; -> binary 세마포어
semaphore empty = n;
semaphore full = 0mutex 세마포어 - buffer pool에 엑세스할 때 상호배제해라 , mutex = 1
버퍼 공간에 접근하는 동안 다른 프로세스가 접근하지 못하게 상호 배제를 제공
mutex = 1 초기화, mutex = 0 : 접근 불가능, mutex = 1 : 접근 가능함
empty : 비어있는 버퍼의 개수를 의미하는 세마포어
empty = 0 : 버퍼가 가득찼다는 의미
empty = n : 버퍼가 비어있다는 의미
full : 차있는 버퍼의 개수를 의미하는 세마포어
full = 0 : 버퍼가 비어있다는 의미
full = n : 버퍼가 가득찼다는 의미
counting semaphores - empty, full
empty 버퍼, full 버퍼를 카운팅하기 위해서 사용
empty 는 n으로 초기화하고 점점 감소 --
full 은 0으로 초기화 하고 점점 증가 ++
puducer
while (true) {
/* produce an item in next_produced */
wait(empty); // 소비자가 empty 될때까지 기다리자
wait(mutex); // mutex를 가질때까지 기다리자
// critical section
/* add next_produced to the buffer */
signal(mutex) // mutex 반납
signal(full); // consumer에게 가져가라고 알려줌
}empty의 lock은 여러 생산자 프로세스가 가질 수 있음
그러나 mutex lock은 이진 세마포어이기 때문에 버퍼에 접근할 수 있는 프로세스는 단 하나 뿐임.
empty = 0 : 버퍼가 가득찼다는 의미이므로 생산자 프로세스는 대기해야 한다.
Consumer
while (true) {
wait(full); // consumer가 signal 줄때만 깨어남
wait(mutex);
// critical section
/* remove an item from buffer to next_consumed */
signal(mutex);
signal(empty);
/* consume the item in next_consumed */full lock을 가질수 있는 프로세스는 여러개이다.
그러나 mutex lock은 이진 세마포어이기 때문에 버퍼에 접근할 수 있는 프로세스는 단 하나 뿐이다.
full = 0 : 버퍼가 비어있다는 의미이므로 소비자 프로세스는 대기한다.
양쪽 대칭구조가 잘 맞아야함 , wait(empty)와 wait(mutex) 순서 바껴있거나, signal(mutex) signal(empty) 순서 바껴있거나하면 꼬인다.
The Readers-Writers Problem
자기 프로세스들이 concurrently 하게 돌면서 어떤 프로세스는 읽기만한다, 어떤 프로세스들은 읽고 쓰고 한다
concurrent process들이 database 엑세스할때
select from 만 열심히하는 프로세스 : reader
update 하는 프로세스들 : writer
두개 이상의 reader 들이 동시에 shared data 에 접근한다면-> 문제 안생김
데이터 무결성을 해치는일은 안함
writer 가 다른 writer하고 같이 shared data에 접근하면 , reader와 writer가 같이 엑세스하면 -> 데이터 무결성 깨짐
Readers-Writers Problem 유형
우선순위 관련
first readers-writers problem:
Reader 프로세스가 임계 영역에서 데이터를 읽는 상태에서 Writer 프로세스가 대기하고 있다고 해서 Reader 프로세스가 대기해야할 필요는 없다.
-> reader 들이 너무많아서 writer 가 접근못한다. starvation 발생한다.
공유된 데이터를 reader들과, writer 들이 대기중이면 같은 우선순위로 공평하게 기회를줘서 lock 획득한놈이 엑세스 하도록 해야함
second readers-writers problem:
writer 가 엑세스하려고 기다리면 , 새 reader 들은 진입하지 못한다.
-> write 한다고 reader 들이 접근하지 못한다. starvation 발생한다
-> 둘 다 starvation이 발생할 수 있다.
first readers-writers ploblem 해결법
semaphore rw_mutex = 1; // 1 초기화 binary semaphore
// critical section 보호
semaphore mutex = 1; // 1 초기화 binary semaphore
// critical section 보호
int read_count = 0; // 현재의 read 갯수가 0이되면 write 접근할 수있다. mutex : read_count를 갱신할때 다른 Reader 프로세스의 접근을 막기 위한 상호 배제에 사용되는 lock
rw_mutex : 다른 writer의 접근을 막기 위한 상호 배제에 사용됨
Reader 프로세스와 Writer 프로세스가 둘다 참조한다.
read_count : 현재 몇 개의 Reader 프로세스들이 객체를 읽고 있는지 알려줌
read_count = 0 : 공유 자원을 읽고 있는 Reader 프로세스들이 없으므로 Writer 프로세스가 진입해도 된다는 의미
rw_mutex를 reader와 writer 공유해서 쓰고
mutex를 read_count가 update될때 mutual exclusion 보장하는데 쓴다
read_count는 얼마나 많은 프로세스를 읽고 있는지 체크, read count가 0이되면 writer 접근할수있다.
writer process
while(true)
wait(rw_mutex); // rw_mutex획득하면 진입
/* writing is perforemd */
signal(rw_mutex); // 끝나고나서 시그널 줘라
}reader process
while(true){
---
wait(mutex); // 다른 Reader 프로세스들과 lock을 얻기 위해 경쟁
read_count++; //reader가 들어가기전에 count++
// 만약 현재 읽을려고 하는 Reader 프로세스가 첫번째라면
// rw_mutex의 lock을 얻는다. 그러면 다른 Writer 프로세스는
// 대기해야 한다.
if (read_count ==1) // count가 1이면 wait
wait(rw_mutex);
signal(mutex);
--- (critical section)
/* reading is performed */
---
wait(mutex);
read_count--; //읽고나서 count --
if (read_count == 0) //raed_count가 0이면 signal
signal(rw_mutex); // writer의 rw_mutex 깨움
// reader 도 여기서 깨움
signal(mutex);
--- (critical section)
}Writer 프로세스가 임계 영역에서 작업중이면 n개의 Reader 프로세스는 대기중
n개의 Reader중에서 1개의 Reader 프로세스는 rw_mutex의 큐에 있습니다.
1개의 Reader 프로세는 제일 첫번째로 읽을려고 하는 Reader 프로세스입니다.
n개의 Reader중에서 n-1개의 Reader 프로세스는 mutex의 큐에 있습니다.
Writer 프로세스가 signal(rw_mutex)를 실행하는 경우
대기중인 Reader 프로세스들 또는 단일 대기중인 Writer 프로세스가 실행을 재개한다.
누구를 선택할 것인지는 스케줄러에 달려 있다.
writer 한명은 critical section에 들어갈 수 있는데, n개의 reader들은 기다려야한다.
한명의 reader가 rw_mutex 쥐고있으면 이거 제외한 n-1개의 reader들은 mutex에서 대기하고 있다.
signal(rw_mutex)를 해줘야 그때 resume 시킬 수 있는데 스케줄러가 reader , writer 공평하게 준다. => first 해결방법
writer 에게 먼저 기회를 준다 => second 해결방법
The Reader-Writer Locks
read 모드냐 write 모드냐 실행해준다.
여러개의 프로세들은 읽기 모드에서 Reader-Writer lock을 얻을 수 있다.
그러나 오직 하나의 프로세스만이 Writer 프로세스들을 위해 요구되는 배타적인 접근으로서 쓰기에 대한 lock을 얻을 수 있다.
여러개의 프로세스가 read모드에서 reader-writer lock을 획득하면 여러개가 진입할 수 있고, righting lock을 획득하면 한개만 진입하게 한다.
-> exclusive access가 writers에서 보장됨
리더프로세스와 라이터프로세스가 서로 공유되어있는 동기화 문제를 품
Bounded Buffer Problem
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
#define true 1
#define BUFFER_SIZE 5 // 버퍼사이즈 5
int buffer[BUFFER_SIZE]; // producer, consumer 공유하는 버퍼
pthread_mutex_t mutex; // mutex
sem_t empty, full; // empty, full 세마포어
int in = 0, out = 0; // in, out
int main(int argc, char *argv[]) {
int i, numOfProducers = 1, numOfConsumers = 1;
// producer 1개, consumer 1개
pthread_t tid;
pthread_mutex_init(&mutex, NULL); // mutex초기화
sem_init(&empty, 0, BUFFER_SIZE); // empty 버퍼사이즈 5 초기화
sem_init(&full, 0, 0); // full 0초기화
srand(time(0));
// Create the producers
for (i = 0; i < numOfProducers; i++) // number 1 만큼 생성
pthread_create(&tid, NULL, producer, NULL);
// Create the consumers
for (i = 0; i < numOfConsumers; i++) // 1개의 컨슈머 생성
pthread_create(&tid, NULL, consumer, NULL);
sleep(10);
return 0;
}void *producer(void *param) {
int item;
while (true) {
usleep((1 + rand() % 5) * 100000);
item = 1000 + rand() % 1000;
insert_item(item); // critical section
//item 을 버퍼에 넣자
}
}
void *consumer(void *param) {
int item;
while (true) {
usleep((1 + rand() % 5) * 100000);
remove_item(&item); // critical section
}
}void insert_item(int item) {
// remove와 티키타가
sem_wait(&empty); // semaphore 획득
pthread_mutex_lock(&mutex); // mutex 락 획득
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE; // in을 증가시켜준다
printf("Producer: inserted $%d\n", item);
pthread_mutex_unlock(&mutex); // 나오때 free
sem_post(&full); // signal(full)
}
void remove_item(int *item) {
sem_wait(&full);
pthread_mutex_lock(&mutex);
*item = buffer[out];
out = (out + 1) % BUFFER_SIZE; // out을 증가시켜준다.
printf("Consumer: removed $%d\n", *item);
pthread_mutex_unlock(&mutex);
sem_post(&empty);
}버퍼가 한개일때, n개일때 producer가 한개일때, 여러개일때, consumer 한개일때, 여러개일때 등.. 동기화문제 생기지 않음
=> semaphore을 이용한 기본적인 concurency control
