この記事では、オペレーティングシステムにおける「読者-書士問題」について説明し、これをマルチスレッド環境で実装する方法を示します。また、具体的なコード例を通じて、どのようにして読者と書士の操作を同期させるかを説明します。
読者・書士問題とは
読者・書士問題は、データベースや共有リソースへのアクセス制御において頻繁に議論されるテーマです。この問題では、複数のスレッドがリソースに対して読み取りまたは書き込みを行う際の競合を防ぐ必要があります。以下の条件を満たすことが要求されます：
- 複数の読者は同時にリソースを読むことができる。
- 読者と書士は同時にリソースを利用できない。
- 複数の書士は同時にリソースを変更できない。
実装の概要
読者優先と書士優先の両方を実現するために、信号量（semaphore）を使用してスレッド間の同期を管理します。以下にそれぞれのケースでの実装例を示します。
書士優先の実装
書士優先の場合、新しい書士が到着した際に他の読者や書士がブロックされる仕組みを提供します。
/*
* 書士優先
*/
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
sem_t accessControl, writerLock, readerGate;
int activeReaders = 0, waitingWriters = 0;
struct task {
int id;
int delay;
int duration;
};
void* readTask(void* arg) {
struct task* param = (struct task*)arg;
sleep(param->delay);
sem_wait(&readerGate);
sem_wait(&accessControl);
activeReaders++;
if (activeReaders == 1) sem_wait(&writerLock);
sem_post(&accessControl);
sem_post(&readerGate);
printf("Reader %d: Reading starts\n", param->id);
sleep(param->duration);
printf("Reader %d: Reading ends\n", param->id);
sem_wait(&accessControl);
activeReaders--;
if (activeReaders == 0) sem_post(&writerLock);
sem_post(&accessControl);
free(param);
pthread_exit(NULL);
}
void* writeTask(void* arg) {
struct task* param = (struct task*)arg;
sleep(param->delay);
sem_wait(&writerLock);
waitingWriters++;
if (waitingWriters == 1) sem_wait(&accessControl);
sem_post(&writerLock);
printf("Writer %d: Writing starts\n", param->id);
sleep(param->duration);
printf("Writer %d: Writing ends\n", param->id);
sem_wait(&writerLock);
waitingWriters--;
if (waitingWriters == 0) sem_post(&accessControl);
sem_post(&writerLock);
free(param);
pthread_exit(NULL);
}
int main() {
pthread_t thread;
sem_init(&accessControl, 0, 1);
sem_init(&writerLock, 0, 1);
sem_init(&readerGate, 0, 1);
while (!feof(stdin)) {
int id, delay, duration;
char type;
scanf("%d %c %d %d", &id, &type, &delay, &duration);
struct task* t = malloc(sizeof(struct task));
t->id = id;
t->delay = delay;
t->duration = duration;
if (type == 'R') pthread_create(&thread, NULL, readTask, t);
else if (type == 'W') pthread_create(&thread, NULL, writeTask, t);
}
sem_destroy(&accessControl);
sem_destroy(&writerLock);
sem_destroy(&readerGate);
return 0;
}
読者優先の実装
読者優先では、新しい読者が到着しても既存の読者が完了するまで待つ必要はありません。
/*
* 読者優先
*/
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
sem_t writeBlock, readerSync;
int currentReaders = 0;
struct task {
int id;
int delay;
int duration;
};
void* readTask(void* arg) {
struct task* param = (struct task*)arg;
sleep(param->delay);
sem_wait(&readerSync);
currentReaders++;
if (currentReaders == 1) sem_wait(&writeBlock);
sem_post(&readerSync);
printf("Reader %d: Reading starts\n", param->id);
sleep(param->duration);
printf("Reader %d: Reading ends\n", param->id);
sem_wait(&readerSync);
currentReaders--;
if (currentReaders == 0) sem_post(&writeBlock);
sem_post(&readerSync);
free(param);
pthread_exit(NULL);
}
void* writeTask(void* arg) {
struct task* param = (struct task*)arg;
sleep(param->delay);
sem_wait(&writeBlock);
printf("Writer %d: Writing starts\n", param->id);
sleep(param->duration);
printf("Writer %d: Writing ends\n", param->id);
sem_post(&writeBlock);
free(param);
pthread_exit(NULL);
}
int main() {
pthread_t thread;
sem_init(&writeBlock, 0, 1);
sem_init(&readerSync, 0, 1);
while (!feof(stdin)) {
int id, delay, duration;
char type;
scanf("%d %c %d %d", &id, &type, &delay, &duration);
struct task* t = malloc(sizeof(struct task));
t->id = id;
t->delay = delay;
t->duration = duration;
if (type == 'R') pthread_create(&thread, NULL, readTask, t);
else if (type == 'W') pthread_create(&thread, NULL, writeTask, t);
}
sem_destroy(&writeBlock);
sem_destroy(&readerSync);
return 0;
}
テストデータ
以下の入力データを用いてプログラムをテストできます。
1 R 3 5 2 W 4 5 3 R 5 2 4 R 6 5 5 W 7 3