critical section lock = false;
remainder section
}
Lock-free と Wait-free を用いた同期
• Wait-free
な実装–
すべてのプロセスが、任意の有限ステップで終わる命令を、ほかのプロ セスの実行速度に無関係に実行できることが保証されていること– つまりクリティカルセクションにおいてtest_and_setやswapな どを用いたLockを行う実装は、Wait-freeではない
• Lock-free
な実装–
いくつかのプロセスが、任意の有限ステップで終わる命令を、ほかのプ ロセスの実行速度に無関係に実行できることが保証されていること– Lock-free
アルゴリズムでは、飢餓状態になるスレッドが発生してもよい– Wait-free
な実装ではLock-free
になっているが、その逆は真ではない2018/4/23 第3回 オペレーティングシステム 45
Compare and Swap
• Compare/Swap
命令•
対象のアドレスの値をある値と比較し、もしそれが同じなら新たな値 をそのアドレスに書き込み（以下のプログラムを参照）•
これを不可分（アトミック）に処理shared_obj *old_sop, *new_sop, *t_sop;
new_sop = malloc(…);
do {
old_sop = sop;
modify(new_sop, old_sop);
t_sop = CAS(sop, old_sop, new_sop);
shared_obj *old_sop, *new_sop, *t_sop;
new_sop = malloc(…);
do {
old_sop = sop;
modify(new_sop, old_sop);
t_sop = CAS(sop, old_sop, new_sop);
shared_obj *sop = malloc(…);
int CAS (int *target, int old, int new) { int temp = *target;
if (temp == old) *target = new;
return temp;
}
ABA 問題
• ABA
は略語ではない• ABA
はある変数の値• ABA
は、ある変数の値がA
からB
に変更され、再びA
に戻ること2018/4/23 第3回 オペレーティングシステム 47
shared_obj *old_sop, *new_sop, *t_sop;
new_sop = malloc(…);
do {
old_sop = sop;
modify(new_sop, old_sop);
t_sop = CAS(sop, old_sop, new_sop);
} while (t_sop != old_sop); /* modified by others */
free(old_sop);
new_sop = malloc(…);
do {
old_sop = sop;
modify(new_sop, old_sop);
t_sop = CAS(sop, old_sop, new_sop);
} while (t_sop != old_sop); /* modified by others */
shared_obj *old_sop, *new_sop, *t_sop;
new_sop = malloc(…);
do {
old_sop = sop;
modify(new_sop, old_sop);
t_sop = CAS(sop, old_sop, new_sop);
} while (t_sop != old_sop); /* some process has modified */
同じメモリ領域が割 り当てられている
ABA 問題
• 回避策
– “tag” ビットの導入
•
例：ある共有オブジェクトが常に32
バイトアラインさ れているとき、下位5
ビットは常に0
•
それをtag
として活用•
この場合のtag
ビットが扱える数は有限なので、ABA
問 題を完全には解決できていないRCU (Read-Copy Update)
• 方法
– RCU
参照側クリティカルセクションでは、共有メモリにはポインタ経由でアクセス
–
システムはそのポインタの使用状況をすべて追跡–
変更が加わるたびにコピーが作られ、それに対して変更を適用–
変更前のデータ構造の読み込みがすべて終了した段階で、ポインタを新たに作成したコピーに対するものに変更
2018/4/23 第3回 オペレーティングシステム 49
RCU (Read-Copy Update)
‒ rcu_read_lock()
‒ Readerが参照側クリティカルセクションに入る前
に呼び出し
‒ rcu_read_unlock()
‒ 参照側クリティカルセクションから抜けるときに 呼び出し
‒ synchronize_rcu() / call_rcu()
‒ Updaterコードの終わりとreclaimerコードの終わり をマーク
‒ すべての参照側クリティカルセクションの完了を まつ
‒ なお、後続のRCU参照側クリティカルセクション の終了を待つ必要なし
‒ rcu_assign_pointer()
‒ Updaterはこの関数を利用することで、RCUで保
護されたポインタに新たな値を代入
‒ rcu_dereference()
‒ Readerはこの関数を利用して、RCUで保護された
Updater
Reader
Reclaimer rcu_read_lock()
rcu_read_unlock() rcu_dereference()
rcu_assign()
synchronize_rcu() call_rcu()
updates into
“removal
”and "reclamation" phases
• 特徴
– Wait-free
な読み込みが可能– RCU
は、古い状態のデータ構造を一定期間そのまま残す必要があるため、大量のメモリを使用する可能性あり
2018/4/23 第3回 オペレーティングシステム 51
RCU (Read-Copy Update)
Transactional Memory
• Locking の問題点
–
メニーコア環境下で効率的に処理を行うことは困難• Compare_and_Swap の問題点
–
複数の変更がある場合、アルゴリズムが複雑化• Transactional Memory
–
一部のメモリ領域に対して、シリアライズされた「読み込 みー変更ー書き込み」という操作が可能– Lock-free
pthread_mutex_lock(pthread_mutex_t
*mutex)
• The mutex object referenced by mutex shall be locked by calling pthread_mutex_lock(). If the mutex is already locked, the calling thread shall block until the mutex becomes available. This operation shall return with the mutex object referenced by mutex in the locked state with the calling thread as its owner.
• If the mutex type is PTHREAD_MUTEX_NORMAL, deadlock detection shall not be provided.
Attempting to relock the mutex causes deadlock. If a thread attempts to unlock a mutex that it has not locked or a mutex which is unlocked, undefined behavior results.
• If the mutex type is PTHREAD_MUTEX_ERRORCHECK, then error checking shall be provided. If a thread attempts to relock a mutex that it has already locked, an error shall be returned. If a thread attempts to unlock a mutex that it has not locked or a mutex which is unlocked, an error shall be returned.
• If the mutex type is PTHREAD_MUTEX_RECURSIVE, then the mutex shall maintain the concept of a lock count. When a thread successfully acquires a mutex for the first time, the lock count shall be set to one. Every time a thread relocks this mutex, the lock count shall be incremented by one. Each time the thread unlocks the mutex, the lock count shall be decremented by one. When the lock count reaches zero, the mutex shall become available for other threads to acquire. If a thread attempts to unlock a mutex that it has not locked or a mutex which is unlocked, an error shall be returned.
• If the mutex type is PTHREAD_MUTEX_DEFAULT, attempting to recursively lock the mutex results in undefined behavior. Attempting to unlock the mutex if it was not locked by the calling thread results in undefined behavior. Attempting to unlock the mutex if it is not locked results in undefined behavior.
2018/4/23 第3回 オペレーティングシステム 53
pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex)
• The pthread_cond_wait() functions shall block on a condition variable. They shall be called with mutex locked by the calling thread or undefined behavior results.
• These functions atomically release mutex and cause the calling thread to block on the
condition variable cond; atomically here means "atomically with respect to access by another thread to the mutex and then the condition variable". That is, if another thread is able to
acquire the mutex after the about-to-block thread has released it, then a subsequent call to pthread_cond_broadcast() or pthread_cond_signal() in that thread shall behave as if it were issued after the about-to-block thread has blocked.
• Upon successful return, the mutex shall have been locked and shall be owned by the calling thread.
• The pthread_cond_signal() function shall unblock at least one of the threads that are blocked
pthread_cond_signal(pthread_cond_t *cond)
Pthread (1/2)
2018/4/23 第3回 オペレーティングシステム 55
• int pthread_create(pthread_t *thread, pthread_attr_t * attr, void * (*start_routine)(void *), void * arg);
• void pthread_exit(void *retval);
• int pthread_join(pthread_t th, void **thread_return);
• int pthread_detach(pthread_t th);
• pthread_t pthread_self(void);
• int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutex‐attr_t *mutexattr);
• int pthread_mutex_lock(pthread_mutex_t *mutex));
• int pthread_mutex_trylock(pthread_mutex_t *mutex);
• int pthread_mutex_unlock(pthread_mutex_t *mutex);
• int pthread_mutex_destroy(pthread_mutex_t *mutex);
• int pthread_cond_init(pthread_cond_t *cond, pthread_condattr_t *cond_attr);
• Int pthread_cond_signal(pthread_cond_t *cond);
• int pthread_cond_broadcast(pthread_cond_t *cond);
• Int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);
• int pthread_cond_timedwait(pthread_cond_t *cnd, pthread_mutex_t *mtx, const struct timespec *at);
• int pthread_cond_destroy(pthread_cond_t *cond);
• int pthread_barrier_init ( pthread_barrier_t * barri, const pthread_barrierattr_t * attr, unsigned int cnt );
• int pthread_barrier_destroy ( pthread_barrier_t * barrier );
• int pthread_barrier_wait ( pthread_barrier_t * barrier );
Pthread (2/2)
• ipthread_attr_init, pthread_attr_destroy, pthread_attr_setdetachstate, pthread_attr_getdetachstate, pthread_attr_setschedparam, pthread_attr_getschedparam, pthread_attr_setschedpolicy,
pthread_attr_getschedpolicy, pthread_attr_setinheritsched, pthread_attr_getinheritsched,
pthread_attr_setscope, pthread_attr_getscope pthread_attr_init, pthread_setschedparam,
pthread_getschedparam, pthread_equal
Bounded Buffer using pthread (1/3)
2018/4/23 第3回 オペレーティングシステム
#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>
#define N_ITEM 8
#define N_PRODUCER 4
#define N_CONSUMER 4
#define BSIZE 8
int buf[BSIZE];
int count;
int in, out;
int waiting;
pthread_mutex_t bbmutex;
pthread_cond_t bbcond;
pthread_barrier_t pbarrier;
void bbinit() {
pthread_mutex_init(&bbmutex, NULL);
pthread_cond_init(&bbcond, NULL);
in = out = waiting = 0;
}
main() {
int i, cc;
pthread_t pth[N_PRODUCER+N_CONSUMER];
void *retval;
pthread_barrier_init(&pbarrier, 0, N_PRODUCER+N_CONSUMER);
for (i = 0; i < N_PRODUCER; i++) {
cc = pthread_create(&pth[i], NULL, producer, 0);
if (cc != 0) { perror("main"); exit(-1); } }
for (i = 0; i < N_CONSUMER; i++) {
cc = pthread_create(&pth[i + N_PRODUCER], NULL, consumer, 0);
if (cc != 0) { perror("main"); exit(-1); } }
for (i = 0; i < (N_PRODUCER + N_CONSUMER); i++) { pthread_join(pth[i], &retval);
pthread_detach(pth[i]);
if (cc != 0) { perror("main"); exit(-1); } }
exit(0);
}
57
Bounded Buffer using pthread (2/3)
void *producer(void *arg) {
int ret = 0;
int i;
pthread_barrier_wait(&pbarrier);
for (i = 0; i < (N_CONSUMER*N_ITEM)/N_PRODUCER; i++) put(i);
pthread_exit(&ret);
return 0;
}
void *consumer(void *arg) {
int ret = 0;
int val;
int i;
pthread_barrier_wait(&pbarrier);
for (i = 0; i < N_ITEM; i++) { val = get(i);
}
pthread_exit(&ret);
return 0;