?
# Homework2
第一段程式碼補全,嘗試補全了其中的程式碼,聽過兩次 google meet 之後比較有感覺了。
## 實驗環境
```
```
補全的代碼
```c
#pragma once
#if USE_PTHREADS
#include <pthread.h>
#define cond_t pthread_cond_t
#define cond_init(c) pthread_cond_init(c, NULL)
#define COND_INITIALIZER PTHREAD_COND_INITIALIZER
#define cond_wait(c, m) pthread_cond_wait(c, m)
#define cond_signal(c, m) pthread_cond_signal(c)
#define cond_broadcast(c, m) pthread_cond_broadcast(c)
#else
#include <limits.h>
#include <stddef.h>
#include "atomic.h"
#include "futex.h"
#include "mutex.h"
#include "spinlock.h"
typedef struct {
atomic int seq;
} cond_t;
static inline void cond_init(cond_t *cond)
{
atomic_init(&cond->seq, 0);
}
static inline void cond_wait(cond_t *cond, mutex_t *mutex)
{
int seq = load(&cond->seq, relaxed);
mutex_unlock(mutex);
#define COND_SPINS 128
for (int i = 0; i < COND_SPINS; ++i) {
if (load(&cond->seq, relaxed) != seq) {
mutex_lock(mutex);
return;
}
spin_hint();
}
futex_wait(&cond->seq, seq);
mutex_lock(mutex);
fetch_or(&mutex->state, MUTEX_SLEEPING, relaxed);
}
static inline void cond_signal(cond_t *cond, mutex_t *mutex)
{
fetch_add(&cond->seq, 1, relaxed);
futex_wake(&cond->seq, 1);
}
static inline void cond_broadcast(cond_t *cond, mutex_t *mutex)
{
fetch_add(&cond->seq, 1, relaxed);
futex_requeue(&cond->seq, 1, &mutex->state);
}
#endif
mutex.h
#pragma once
#if USE_PTHREADS
#include <pthread.h>
#define mutex_t pthread_mutex_t
#define mutex_init(m) pthread_mutex_init(m, NULL)
#define MUTEX_INITIALIZER PTHREAD_MUTEX_INITIALIZER
#define mutex_trylock(m) (!pthread_mutex_trylock(m))
#define mutex_lock pthread_mutex_lock
#define mutex_unlock pthread_mutex_unlock
#else
#include <stdbool.h>
#include "atomic.h"
#include "futex.h"
#include "spinlock.h"
typedef struct {
atomic int state;
} mutex_t;
enum {
MUTEX_LOCKED = 1 << 0,
MUTEX_SLEEPING = 1 << 1,
};
#define MUTEX_INITIALIZER \
{ \
.state = 0 \
}
static inline void mutex_init(mutex_t *mutex)
{
atomic_init(&mutex->state, 0);
}
static bool mutex_trylock(mutex_t *mutex)
{
int state = load(&mutex->state, relaxed);
if (state & MUTEX_LOCKED)
return false;
state = fetch_or(&mutex->state, MUTEX_LOCKED, relaxed);
if (state & MUTEX_LOCKED)
return false;
thread_fence(&mutex->state, acquire);
return true;
}
static inline void mutex_lock(mutex_t *mutex)
{
#define MUTEX_SPINS 128
for (int i = 0; i < MUTEX_SPINS; ++i) {
if (mutex_trylock(mutex))
return;
spin_hint();
}
int state = exchange(&mutex->state, MUTEX_LOCKED | MUTEX_SLEEPING, relaxed);
while (state & MUTEX_LOCKED) {
futex_wait(&mutex->state, MUTEX_LOCKED | MUTEX_SLEEPING);
state = exchange(&mutex->state, MUTEX_LOCKED | MUTEX_SLEEPING, relaxed);
}
thread_fence(&mutex->state, acquire);
}
static inline void mutex_unlock(mutex_t *mutex)
{
int state = exchange(&mutex->state, 0, release);
if (state & MUTEX_SLEEPING)
futex_wake(&mutex->state, 1);
}
#endif
```
### 目前的理解
首先我觀察的是 main function 他的主要功能為
將每一個節點作為 p_theard ,並且將它作為 theard_func ,
接下來透過 futex wait & wake 來進行控制
然後我們來觀察結構:
```c
struct node {
struct clock *clock;
struct node *parent;
mutex_t mutex;
cond_t cond;
bool ready;
};
```
可以發現 node 的結構使他有以下功能,
clock 提供了他可以
```c
typedef struct {
atomic int state;
} mutex_t;
```
### WTF is Futex?
futex 使用 systemcall 來進行存取,