논리적인 주소 공간(코드,데이터 영역)을 공유하거나, 공유 데이터를 가질 때
공유 데이터에 concurrent하게 접근하면 데이터 불일성(data inconsistency)가 발생할 수 있다.
데이터 일관성을 유지하기 위해 프로세스의 실행을 제어할 필요가 있다.
생산자-소비자 문제에서 발생할 수 있는 데이터 불일치
producer
while(true){
while(count== BUFFER_SIZE)
; /* do nothing */
buffer[in] = next_item;
in = (in+1) % BUFFER_SIZE;
count++;
}
consumer
while(true){
while(count== 0)
; /* do nothing */
next_item = buffer[out];
out = (out+1) % BUFFER_SIZE;
count--;
}
위 코드가 개별적으로는 올바를지라도, concurrent하게 실행하면 올바르게 동작하지 않는다. 공유 데이터 counter를 수정하는 코드에서 문제가 발생할 수 있다.
counter의 값을 변경하는 counter++
, counter--
명령어가 병행하게 실행한다고 가정해보자
counter++
register1 = counter
register1 = register1 + 1
counter = register1
counter--
register2 = counter
register2 = register1 - 1
counter = register2
counter++
, counter--
를 기계어로 보면 위와 같이 볼 수 있다.
register1, register2가 동일한 레지스터이더라도, 레지스터의 내용은 문맥 교환시 메모리에 보관되었다가 적재된다.
counter의 값을 변경하는 counter++
, counter--
명령어들은 아래와 같이 임의적인 순서로 인터리빙 방식으로 수행된다.
[Producer] register1 = counter // register1 = 5
[Producer] register1 = register1 + 1 // register1 = 6
[Consumer] register2 = counter // register2 = 5
[Consumer] register2 = register2 - 1 // register2 = 4
[Producer] counter = register1 // counter = 6
[Consumer] counter = register2 // counter = 4
정상적으로 counter = 5가 되어야 하지만, 위의 결과는 4이다.
이러한 데이터 불일치가 발생한 것은 두 개의 프로세스가 동시에 공유 변수 counter를 조작하도록 허용했기 때문이다.
따라서 프로세스가 공유 데이터에 접근하는 순서를 제어해야 한다.
동시에 여러 개의 프로세스가 공유 데이터를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 순서에 의존하는 상황
데이터 불일치를 막으려면 Race Condition
을 방지해야 한다. 특정 시점에 오직 하나의 프로세스만이 공유 데이터를 조작하도록 해야 한다.
package process_synchronization;
public class RaceCondition {
static int count = 0;
public static void main(String[] args) throws InterruptedException {
Thread thread1 = new Thread(new MyRunnable());
Thread thread2 = new Thread(new MyRunnable());
thread1.start();
thread2.start();
thread1.join();
thread2.join();
System.out.println(count); // 13415
}
static void increment() {
count++;
}
}
class MyRunnable implements Runnable {
@Override
public void run() {
for (int i = 0; i < 10000; i++) {
RaceCondition.increment();
}
}
}
프로세스들이 협력할 때 사용할 수 있는 동기화 프로토콜를 설계하는 것
Mutual Exclusion(상호 배제): 한 프로세스가 임계 구역에서 실행되고 있다면, 다른 프로세스들은 임계 구역에 진입할 수 없어야 한다.
Progress(진행): 임계 영역에서 실행되는 프로세스가 없고, 임계 영역에 진입하려는 프로세스가 있을 때 진입하려는 프로세스는 진입할 수 있어야 한다. -> deadlock 방지
Bounded Waiting(한정된 대기): 진입 허가 요청 대기 시간이 한정적이여야 한다. -> starvation 방지
CSP를 해결하기 위해서 위 세가지 조건을 만족해야 한다.
do {
flag[i] = true;
turn = j;
while(flag[j] && turn ==j); // entry section
// critical section
flag[i] = false; // exit section
// remainder section
} while(true);
turn
, boolean flag[2]
)를 사용하여 해결한다.load
, store
와 같은 기본적인 기계어를 수행하는 방식 때문에 올바르게 실행된다고 보장하지 않는다.#include "stdio.h"
#include "pthread.h"
int sum = 0;
int turn;
int flag[2];
void *producer(void *param);
void *consumer(void *param);
int main() {
pthread_t tid1, tid2;
pthread_create(&tid1, NULL, producer, NULL);
pthread_create(&tid2, NULL, consumer, NULL);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
printf("sum = %d\n", sum); // 19997
}
void *producer(void *param) {
for (int k = 0; k < 10000; k++) {
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1);
sum++;
flag[0] = false;
}
pthread_exit(0);
}
void *consumer(void *param) {
for (int k = 0; k < 10000; k++) {
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0);
sum++;
flag[1] = false;
}
pthread_exit(0);
}
피터슨 알고리즘에서 보았듯이 entry section에서 인터럽트가 발생하면 race condition이 발생할 수 있다. 단일 프로세서 환경에서는 인터럽트를 허용하지 않게하여 CSP를 해결할 수 있지만, 멀티 프로세서 환경에 적용할 수 없기 때문에, 하드웨어의 도움이 필요해진다.
현대 컴퓨터는 워드(word) 내용을 검사하고 변경하거나, 두 워드의 내용을 원자적으로 교환할 수 있는, 즉 인터럽트 되지 않는 하나의 단위로써, atomic한 명령어를 제공한다.
atomic value는 내부에서 atomic 명령어를 사용하여 value에 대한 race condition을 막는다
boolean test_and_set(boolean *target){
boolean rv = *target;
*target = true;
return rv;
}
위 블록을 하나의 하드웨어 명령어(atomic한 명령어로 지정, 실행 도중에 문맥교환X) 제공한다.
false로 초기화되는 전역 변수 lock을 사용한다.
do{
while(test_and_set(&lock)); // entry section
// critical section
lock = false; // exit section
} while(true);
atomic한 명령어를 제공하여 mutual exclusion 제공
bounded waiting은 제공하지 않는다.
int compare_and_swap(int *value, int expected, int new_value){
int temp = *value;
if(*value==expected)
*value = new_value;
return temp;
}
위 블록을 하나의 하드웨어 명령어(atomic한 명령어로 지정, 실행 도중에 문맥교환X) 제공한다.
0으로 초기화되는 전역 변수 lock을 사용한다,
while(true){
while(compare_and_swap(&lock,0,1)!=0); // entry section
// critical section
lock = 0;
}
atomic한 명령어를 제공하여 mutual exclusion 제공
bounded waiting은 제공하지 않는다.
package process_synchronization;
import java.util.concurrent.atomic.AtomicBoolean;
import static process_synchronization.PetersonAlgorithmWithAtomicValue.*;
public class PetersonAlgorithmWithAtomicValue {
static final int NUMBER = 10000;
static int count;
static int turn;
static AtomicBoolean[] flags; // atomic value
static {
count = 0;
turn = 0;
flags = new AtomicBoolean[2];
for (int i = 0; i < flags.length; i++) {
flags[i] = new AtomicBoolean();
}
}
public static void main(String[] args) throws InterruptedException {
Thread t1 = new Thread(new Runnable1());
Thread t2 = new Thread(new Runnable2());
t1.start();
t2.start();
t1.join();
t2.join();
System.out.println(count);
}
static void increment() {
count++;
}
}
class Runnable1 implements Runnable {
@Override
public void run() {
flags[0].set(true);
turn = 1;
while (flags[1].get() && turn == 1) { // entry section
}
for (int i = 0; i < NUMBER; i++) { // critical section
increment();
}
flags[0].set(false); // exit section
}
}
class Runnable2 implements Runnable {
@Override
public void run() {
flags[1].set(true);
turn = 0;
while (flags[0].get() && turn == 0) { // entry section
}
for (int i = 0; i < NUMBER; i++) { // critical section
increment();
}
flags[1].set(false); // exit section
}
}
while(true){
// acquire lock
// critical section
// release lock
// remainder section
}
Lock
을 획득해야 한다.Lock
을 반환해야 한다.acquire(){
while(!available); // busy wait
available = false;
}
release(){
available = true;
}
mutext lock 연산에는 acquire()
, release()
두가지가 있고, 두가지 연산 모두 atomic하게 실행되어야 한다.
available
이라는 불린 변수를 사용한다
#include "stdio.h"
#include "pthread.h"
int sum = 0; // shared data
pthread_mutex_t mutex;
void *counter(void *param);
int main() {
pthread_t tid1, tid2;
pthread_mutex_init(&mutex, NULL);
pthread_create(&tid1, NULL, counter, NULL);
pthread_create(&tid2, NULL, counter, NULL);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
printf("sum = %d\n", sum);
}
void *counter(void *param) {
for (int k = 0; k < 10000; k++) {
pthread_mutex_lock(&mutex); // entry section
sum++; // critical section
pthread_mutex_unlock(&mutex); // exit section
}
}
Busy waiting
- 락을 획득하기 위해 CPU 코어를 점유하면서 반복문을 계속 실행하는 것을 말한다.
- CPU 싸이클을 낭비한다.
Spinlock
- Busy waiting하는 뮤텍스 락을 말한다.
- 멀티코어 환경에서는 스핀락은 CPU 코어을 점유하면서 락을 대기하기 때문에 컨텍스트 스위치 오버헤드가 생기지 않는다.
wait(S){
while(S<=0){
sleep();
}
S--;
}
signal(S){
S++;
if(S>0({
wakeup();
}
}
wait()
,signal()
연산을 사용하여 S 값을 변경한다.wait()
: 세마포어 S를 감소signal()
: 세마포어 S를 증가wait()
,signal()
연산은 atomic 하게 수행되어야 한다.
- 임계 영역이 짧은 시간안에 수행될 경우, 컨텍스트 스위치 오버헤드가 커진다.
- Progress, Bounded waiting을 보장하지 않는다
- 순서가 정확하지 않으면 timing error가 발생하고 코드가 복잡할수록 에러를 찾기 쉽지 않다.
#include "stdio.h"
#include "pthread.h"
#include "semaphore.h"
int sum = 0;
sem_t sem;
void *counter(void *param);
int main() {
pthread_t tid1, tid2;
sem_init(&sem, 0, 1);
pthread_create(&tid1, NULL, counter, NULL);
pthread_create(&tid2, NULL, counter, NULL);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
printf("sum = %d\n", sum);
}
void *counter(void *param) {
for (int k = 0; k < 10000; k++) {
sem_wait(&sem);
sum++;
sem_post(&sem);
}
}
condition
변수를 사용하여 부가적인 동기화를 작성할 수 있다.condition
변수는 wait()
,signal()
을 제공한다.signal()
은 정확히 하나의 waiting 프로세스를 재개한다.Monitor-lock
이라는 모니터와 유사한 동기화 기법을 제공한다. (synchronized
, wait()
, notify()
등등 )
synchronized
- 임계 영역에 해당하는 코드 블록을 선언하는 키워드
- 해당 코드 블록에는 모니터락 객체 인스턴스을 획득해야 진입 가능
- 모니터락을 가진 객체 인스턴스를 지정할 수 있음
- 메서드에 선언하면 메서드 코드 블록 전체가 임계영역으로 지정됨
- 이 때, 모니터락을 가진 객체 인스턴스는 this 객체 인스턴스이다(모니터 락을 가진 객체 인스턴스는 해당 메서드를 가진 클래스의 인스턴스이다.)
wait()
,notifiy()
- java.lang.Object 클래스에 선언됨
- 쓰레드가 어떤 객체의
wait()
메서드를 호출하면
- 해당 객체의 모니터락을 획득하기 위해 대기 상태로 진입
- 쓰레드가 어떤 객체의
notify()
메서드를 호출하면
- 해당 객체 모니터에 대기중인 쓰레드 하나를 깨움
notify()
대신에notifyAll()
을 호출하면
- 해당 객체 모니터에 대기중인 쓰레드 전부를 깨움
package process_synchronization;
public class MonitorEx {
static final int MAX = 10000;
public static void main(String[] args) throws InterruptedException {
syncEx1(); // 메서드 전체에 synchronized(클래스 자체가 모니터락 소유)-> 50000
syncEx2(); // 메서드 내부에서 synchronized -> 50000
syncEx3(); // 쓰레드마다 다른 모니터락 객체 인스턴스 설정 -> 49998
syncEx4(); // 쓰레드마다 같은 모니터락 객체 인스턴스 설정 -> 50000
}
static void syncEx1() throws InterruptedException {
Thread[] threads = new Thread[5];
for (int i = 0; i < threads.length; i++) {
threads[i] = new Thread(() -> {
for (int j = 0; j < MAX; j++) {
Monitor.increment1();
}
});
threads[i].start();
}
for (int i = 0; i < threads.length; i++) {
threads[i].join();
}
System.out.println("[Ex1] count = " + Monitor.count);
}
static void syncEx2() throws InterruptedException {
Monitor.count = 0;
Thread[] threads = new Thread[5];
for (int i = 0; i < threads.length; i++) {
threads[i] = new Thread(() -> {
for (int j = 0; j < MAX; j++) {
Monitor.increment2();
}
});
threads[i].start();
}
for (int i = 0; i < threads.length; i++) {
threads[i].join();
}
System.out.println("[Ex2] count = " + Monitor.count);
}
private static void syncEx3() throws InterruptedException {
Monitor.count = 0;
Thread[] threads = new Thread[5];
for (int i = 0; i < threads.length; i++) {
Monitor monitor = new Monitor();
threads[i] = new Thread(() -> {
for (int j = 0; j < MAX; j++) {
monitor.increment3();
}
});
threads[i].start();
}
for (int i = 0; i < threads.length; i++) {
threads[i].join();
}
System.out.println("[Ex3] count = " + Monitor.count);
}
static void syncEx4() throws InterruptedException {
Monitor.count = 0;
Monitor monitor = new Monitor();
Thread[] threads = new Thread[5];
for (int i = 0; i < threads.length; i++) {
threads[i] = new Thread(() -> {
for (int j = 0; j < MAX; j++) {
monitor.increment3();
}
});
threads[i].start();
}
for (int i = 0; i < threads.length; i++) {
threads[i].join();
}
System.out.println("[Ex4] count = " + Monitor.count);
}
}
class Monitor {
static int count = 0;
static Object object = new Object();
synchronized public static void increment1() {
count++;
}
static void increment2() {
synchronized (object) {
count++;
}
}
public void increment3() {
synchronized (this) {
count++;
}
}
}
프로듀서-컨슈머에서 동시에 버퍼에 접근할 경우, Race Condition이 발생할 수 있다.
producer
while(true){
wait(empty);
wait(mutex);
// critical section
signal(mutex);
signal(full);
}
consumer
while(true){
wait(full);
wait(mutex);
// critical section
signal(mutex);
signal(empty);
}
semaphore mutex = 1;
mutex = CS mutexsemaphore empty = n;
n=버퍼 개수semaphore full = 0;
# include "stdio.h"
# include "stdlib.h"
# include "unistd.h"
# include "pthread.h"
# include "semaphore.h"
#define BUFFER_SIZE 5
#define NUMBER_OF_PRODUCERS 1
#define NUMBER_OF_CONSUMERS 1
void *produce(void *param);
void *consume(void *param);
void insert_item(int item);
void remove_item(int *item);
int buffer[BUFFER_SIZE];
pthread_mutex_t mutex;
sem_t empty, full;
int in = 0, out = 0;
int main() {
pthread_t tid;
pthread_mutex_init(&mutex, NULL);
sem_init(&empty, 0, BUFFER_SIZE);
sem_init(&full, 0, 0);
for (int i = 0; i < NUMBER_OF_PRODUCERS; i++) {
pthread_create(&tid, NULL, produce, NULL);
}
for (int i = 0; i < NUMBER_OF_CONSUMERS; i++) {
pthread_create(&tid, NULL, consume, NULL);
}
sleep(10);
return 0;
}
void *produce(void *param) {
int item;
while (true) {
usleep((1 + rand() % 5) * 10000);
item = 1000 + rand() % 1000;
insert_item(item); // critical section
}
}
void *consume(void *param) {
int item;
while (true) {
usleep((1 + rand() % 5) * 10000);
remove_item(&item); // critical section
}
}
void insert_item(int item) {
sem_wait(&empty);
pthread_mutex_lock(&mutex);
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
printf("[PRODUCER] inserted $%d\n", item);
pthread_mutex_unlock(&mutex);
sem_post(&full);
}
void remove_item(int *item) {
sem_wait(&full);
pthread_mutex_lock(&mutex);
*item = buffer[out];
out = (out + 1) % BUFFER_SIZE;
printf("[CONSUMER] removed $%d\n", *item);
pthread_mutex_unlock(&mutex);
sem_post(&empty);
}
package process_synchronization;
public class BoundedBufferSolution {
public static void main(String[] args) {
Buffer buffer = new Buffer(1);
Thread[] producers = new Thread[1];
Thread[] consumers = new Thread[1];
for (int i = 0; i < producers.length; i++) {
producers[i] = new Thread(() -> {
while (true) {
try {
Thread.sleep((long) (Math.random() * 500));
int item = ((int) (1 + Math.random() * 9)) * 10000;
buffer.produce(item);
} catch (InterruptedException e) {
}
}
});
producers[i].start();
}
for (int i = 0; i < consumers.length; i++) {
consumers[i] = new Thread(() -> {
while (true) {
try {
Thread.sleep((long) (Math.random() * 500));
buffer.consume();
} catch (InterruptedException e) {
}
}
});
consumers[i].start();
}
}
}
class Buffer {
private int[] buffer;
private int cnt;
private int in;
private int out;
public Buffer(int bufferSize) {
this.buffer = new int[bufferSize];
this.cnt = this.in = this.out = 0;
}
synchronized public void produce(int item) {
while (this.cnt == buffer.length) {
try {
wait();
} catch (InterruptedException e) {
}
}
buffer[in] = item;
in = (in + 1) % buffer.length;
cnt++;
System.out.printf("[Producer] item = %d\n", item);
notify();
}
synchronized public int consume() {
while (this.cnt == 0) {
try {
wait();
} catch (InterruptedException e) {
}
}
int item = buffer[out];
out = (out - 1) % buffer.length;
cnt--;
System.out.printf("[Consumer] item = %d\n", item);
notify();
return item;
}
}
데이터베이스에 같은 여러개의 프로세스가 동시에 접근한다고 했을 때, 프로세스는 읽는 작업만 수행하는 프로세스(readers), 읽고 쓰는 작업을 수행하는 프로세스(writers)로 나눌 수 있다.
readers-writers 문제는 아래 2개의 우선순위 상황을 기반으로 발생할 수 있다.
이 포스트에서는 1번 우선순위 상황에 대하여 발생하는 문제를 해결하는 방법을 알아볼 것이다.
writer
while(true){
wait(rw_mutex);
// writing opereation
signal(rw_mutex);
}
reader
while(true){
wait(mutex);
read_count++;
if(read_count==1)
wait(rw_mutex);
signal(mutex)
// reading operation
wait(mutex);
read_count--;
if(read_count==0)
wait(rw_mutex);
signal(mutex)
}
int read_count = 0
= reader 카운트 변수sempahore rw_mutex = 1
= reader,writer 공유sempahore mutex = 1
= read_count를 위한 mutexpublic class Database {
private int readCnt = 0;
private boolean writeMode = false;
public void read() {
acquireReadLock();
// read operation
releaseReadLock();
}
public void write() {
acquireWriteLock();
// write operation
releaseWriteLock();
}
synchronized private void acquireWriteLock() {
while (readCnt > 0 || writeMode) {
try {
wait();
} catch (InterruptedException e) {
}
}
writeMode = true;
}
synchronized private void releaseWriteLock() {
writeMode = false;
notifyAll();
}
synchronized private void releaseReadLock() {
readCnt--;
if (readCnt == 0) {
notify();
}
}
synchronized private void acquireReadLock() {
while (writeMode) {
try {
wait();
} catch (InterruptedException e) {
}
}
readCnt++;
}
}
while(true){
wait(chopstick[i]);
wait(chopstick[(i+1)%5]);
// eat
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);
// think
}
semaphore chopstick[5]
위 두가지 솔루션 모두 데드락은 해결할 수 있으나, starvation을 해결하는 것은 보장하지 않는다.
hungry
, eating
, thinking
세가지 상태로 구분한다eating
상태가 아니면 철학자는 먹는다DiningPhilosopher
이라는 모니터에서 mutual exclusion을 보장하는 연산을 제공한다pickup
연산을 수행한다putdown
연산을 수행한다c구현
# include "stdio.h"
# include "stdlib.h"
# include "unistd.h"
# include "pthread.h"
#define NUM_OF_PHILS 5
enum {
THINKING, HUNGRY, EATING
} state[NUM_OF_PHILS];
pthread_mutex_t mutex_lock;
pthread_cond_t cond_vars[NUM_OF_PHILS];
void init();
int leftOf(int i);
int rightOf(int i);
void *philosopher(void *param);
void think(int id);
void eat(int id);
void test(int id);
void pickup(int id);
void putdown(int id);
int main() {
pthread_t tid;
init();
for (int i = 0; i < NUM_OF_PHILS; i++)
pthread_create(&tid, NULL, philosopher, (void *) &i);
for (int i = 0; i < NUM_OF_PHILS; i++)
pthread_join(tid, NULL);
return 0;
}
void init() {
for (int i = 0; i < NUM_OF_PHILS; i++) {
state[i] = THINKING;
pthread_cond_init(&cond_vars[i], NULL);
}
pthread_mutex_init(&mutex_lock, NULL);
srand(time(0));
}
int leftOf(int i) {
return (i + NUM_OF_PHILS - 1) % NUM_OF_PHILS;
}
int rightOf(int i) {
return (i + 1) % NUM_OF_PHILS;
}
void *philosopher(void *param) {
int id = *((int *) param);
while (true) {
think(id);
pickup(id);
eat(id);
putdown(id);
}
}
void think(int id) {
printf("%d is thinking\n", id);
usleep((1 + rand() % 50) * 10000);
};
void eat(int id) {
printf("%d is eating\n", id);
usleep((1 + rand() % 50) * 10000);
};
void test(int id) {
if (state[id] == HUNGRY && state[leftOf(id)] != EATING && state[rightOf(id)] != EATING) {
state[id] = EATING;
pthread_cond_signal(&cond_vars[id]);
}
};
void pickup(int id) {
pthread_mutex_lock(&mutex_lock);
state[id] = HUNGRY;
test(id);
while (state[id] != EATING) {
pthread_cond_wait(&cond_vars[id], &mutex_lock);
}
pthread_mutex_unlock(&mutex_lock);
};
void putdown(int id) {
pthread_mutex_lock(&mutex_lock);
state[id] = THINKING;
test(leftOf(id));
test(rightOf(id));
pthread_mutex_unlock(&mutex_lock);
};
java 구현
package process_synchronization;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import static process_synchronization.State.*;
enum State {
THINKING, EATING, HUNGRY;
}
public class DiningPhilosopher {
static final int numOfPhils = 5;
public static void main(String[] args) {
Philosopher[] philosophers = new Philosopher[numOfPhils];
DiningPhilosopherMonitor monitor = new DiningPhilosopherMonitor(numOfPhils);
for (int id = 0; id < numOfPhils; id++) {
new Thread(new Philosopher(id, monitor)).start();
}
}
}
class Philosopher implements Runnable {
private int id;
private DiningPhilosopherMonitor monitor;
public Philosopher(int id, DiningPhilosopherMonitor monitor) {
this.id = id;
this.monitor = monitor;
}
@Override
public void run() {
while (true) {
think();
monitor.pickup(this.id);
eat();
monitor.putdown(this.id);
}
}
private void eat() {
System.out.printf("[%d] Eating\n", this.id);
try {
Thread.sleep((long) (Math.random() * 500));
} catch (InterruptedException e) {
}
}
private void think() {
System.out.printf("[%d] Thinking\n", this.id);
try {
Thread.sleep((long) (Math.random() * 50));
} catch (InterruptedException e) {
}
}
}
class DiningPhilosopherMonitor {
private int numOfPhills;
private State[] states;
private Condition[] self;
private Lock lock;
public DiningPhilosopherMonitor(int numOfPhills) {
this.numOfPhills = numOfPhills;
this.states = new State[numOfPhills];
this.self = new Condition[numOfPhills];
this.lock = new ReentrantLock();
for (int i = 0; i < states.length; i++) {
states[i] = THINKING;
self[i] = lock.newCondition();
}
}
private int leftOf(int id) {
return (id + this.numOfPhills - 1) % this.numOfPhills;
}
private int rightOf(int id) {
return (id + +1) % this.numOfPhills;
}
public void pickup(int id) {
lock.lock();
try {
states[id] = HUNGRY;
test(id);
while (states[id] != EATING) {
self[id].await();
}
} catch (InterruptedException e) {
} finally {
lock.unlock();
}
}
public void putdown(int id) {
lock.lock();
try {
states[id] = THINKING;
test(leftOf(id));
test(rightOf(id));
} finally {
lock.unlock();
}
}
private void test(int id) {
if (states[id] == HUNGRY && states[leftOf(id)] != EATING && states[rightOf(id)] != EATING) {
states[id] = EATING;
self[id].signal();
}
}
}
두 개 이상의 프로세스가 자원을 소유한채로 무한히 대기하는 상황
높은 우선순위를 가진 프로세스가 낮은 우선순위 프로세스가 자원을 해제하기를 기다리는 상황
해결 방안 = 더 높은 우선순위 프로세스가 필요로 하는 자원을 접근하는 모든 프로세스들은 문제가 된 자원의 사용이 끝날 때까지 더 높은 우선순위를 상속받도록 하고, 자원 사용이 긑나면 원래 우선순위로 되돌아간다
mutex_lock()
을 호출해야하고, 나오기 전에 mutext_unlock()
을 호출해야 한다.단일 처리기 | 다중 처리기 |
---|---|
커널 선점을 불가능하게 한다 | 스핀락을 획득한다 |
커널 선점을 가능하게 한다 | 스핀락을 방출한다 |
스핀락과 커널 선점 불가능 및 가능은 오직 락이 짧은 시간 동안만 유지될 때 사용된다. 락이 오랜 시간동안 유지되어야 한다면 세마포을 사용하는 것이 적절하다