2023 Homework2 (quiz1)

contributed by <RoyWFHuang>

futex introduction

futex(fast user-space locking), 用來減少 user space 使用競爭資源時, 對於 lock 的 kernel 系統呼叫.

舉例來說, 兩個 process, 一個是網路程式, 另一個是檔案 io 操作.
P1: socket 使用 write 動作時候, 會對於 buffer 做一次的 lock.
P2: fd write 對於 disk block 進行 io, 此時也會對 kernel 呼叫一次 lock
但兩個 processes 資源是沒有衝突的, 所以 lock 就變成是多餘的 kernel lock.

而 futex 提供一個簡易的 atomic 操作(利用 mmaps 讓 user space 操作使用同一個資源), 進入 futex lock 跟 unlock 時, 確認共享的資源變動前後是否一致, 如果一致則沒有發生競爭, 避免進行 system call ( futex(2) ), 如果衝突了, 則呼叫 futex_wait/ futex_wake 進行等待跟喚醒.

long syscall(SYS_futex, uint32_t *uaddr, int futex_op, uint32_t val,
             const struct timespec *timeout,   /* or: uint32_t val2 */
             uint32_t *uaddr2, uint32_t val3);

futex_op :
FUTEX_WAIT: 對應至 futex_wait

int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val, ktime_t *abs_time, u32 bitset)

FUTEX_WAKE: 對應至 futex_wake

int futex_wake(u32 __user *uaddr, unsigned int flags, int nr_wake, u32 bitset)

futex 修改第一次作業

src code: github
目標: 使用 futex 包裝的 muthex.h 取代 POSIX thread.

target	replace by
pthread_mutex_init	mutex_init
pthread_mutex_destory	(removed)*
pthread_mutex_lock	mutex_lock
pthread_mutex_unlock	mutex_unlock
pthread_cond_init	cond_init
pthread_cond_destory	(removed)*
pthread_cond_signal	cond_signal

*pthread_mutex_destory/pthread_cond_destory remove: 因為 mutex/cond init 使用 atomic init 去設定 mutex state, 沒有使用到 POSIX thread system call, 所以不需要其他相對應的回收動作.

測試結果:

$ time ./test_qspthread -t -f2 -h2 -n100
0.00571 0.0282 0.0401

real	0m0.088s
user	0m0.029s
sys	0m0.047s

$ time ./test_qslinux -t -f2 -h2 -n100
0.00153 0.022 0.011

real	0m0.045s
user	0m0.024s
sys	0m0.012s

若使用程式內預設的

$ time ./test_qspthread -t
39 38.8 0.244

real	0m39.072s
user	0m38.788s
sys	0m0.257s

$ time ./test_qslinux -t
42.8 42.6 0.14

real	0m42.815s
user	0m42.634s
sys	0m0.153s

在競爭比較不激烈( thread nunber, element 數量較少)的狀況下, 符合預期.
但在許多 thread 共同競爭下, futex 似乎就沒有 pthread 效能來的好?

或許是如同 futex 使用上所說, 如果 thread 之間, 競爭的資源越不相關, 使用的成本則是會越低?

priority inheritance mutex

PI in POSIX thread

首先先看 POSIX thread 提供的 API

pthread_attr_set(get)schedpolicy(3):

#include <pthread.h>
int pthread_attr_setschedpolicy(pthread_attr_t *attr, int policy);
int pthread_attr_getschedpolicy(const pthread_attr_t *restrict attr, int *restrict policy);

• Desc: set the scheduling policy attribute of the thread attributes object referred to by attr to the value specified in policy.
  pthread_attr_setschedpolicy() to have effect when calling pthread_create(3), the caller must use pthread_attr_setinheritsched(3) to set the inherit-scheduler attribute of the attributes object attr to PTHREAD_EXPLICIT_SCHED.
• policy : SCHED_FIFO, SCHED_RR, and SCHED_OTHER

pthread_attr_setinheritsched(3)

#include <pthread.h>
int pthread_attr_setinheritsched(pthread_attr_t *attr, int inheritsched);
int pthread_attr_getinheritsched(const pthread_attr_t *restrict attr, int *restrict inheritsched);

• Desc: set/get inherit-scheduler attribute in thread attributes object
• inheritsched: PTHREAD_INHERIT_SCHED, PTHREAD_EXPLICIT_SCHED

pthread_setschedparam(3)

#include <pthread.h>
struct sched_param {
    int sched_priority;     /* Scheduling priority */
};  
    
int pthread_setschedparam(pthread_t thread, int policy, const struct sched_param *param);
int pthread_getschedparam(pthread_t thread, int *restrict policy, struct sched_param *restrict param);

• Desc: set/get scheduling policy and parameters of a thread
• sched_priority: cheduling priorities in each scheduling policy, see sched(7). Portable programs should use sched_get_priority_min(2) and sched_get_priority_max(2) to find the range of priorities supported for a particular policy.
  Linux allows the static priority range 1 to 99 for the SCHED_FIFO and SCHED_RR policies.

src_code

test reusult using pthread define.

$ gcc pi.c -o pi -lpthread -D_GNU_SOURCE -std=gnu11 -DUSE_PTHREADS
$ sudo ./pi
start low pri
start high pri
end of busy work in low pri
high pri inhro
high pri
mid pri
low pri

使用原本 linux 內的 futex (未經改寫)

start low pri
start high pri
mid pri
end of busy work in low pri
high pri
low pri    

很明顯的看出 mid priroity 提早在 high priority 之前跑完了.

PI in linux

futex with pi parameter

#define FUTEX_LOCK_PI		6
#define FUTEX_UNLOCK_PI		7
#define FUTEX_LOCK_PI2		13
    .....
#define FUTEX_LOCK_PI_PRIVATE	(FUTEX_LOCK_PI | FUTEX_PRIVATE_FLAG)
#define FUTEX_LOCK_PI2_PRIVATE	(FUTEX_LOCK_PI2 | FUTEX_PRIVATE_FLAG)
#define FUTEX_UNLOCK_PI_PRIVATE	(FUTEX_UNLOCK_PI | FUTEX_PRIVATE_FLAG)
    ....

其中

• FUTEX_LOCK_PI2 (since Linux 5.14)
• FUTEX_TRYLOCK_PI (since Linux 2.6.18)
  所以可以知道我們要用的 lock 是 pi2

另外從 fetex(2) 文件中閱讀:

• If the lock is not acquired, the futex word's value shall be 0.
• If the lock is acquired, the futex word's value shall be the thread ID (TID; see gettid(2)) of the owning thread.
• a user-space application can acquire an unacquired lock or release a lock using atomic instructions executed in user mode
• If a futex is already acquired (i.e., has a nonzero value), waiters must employ the FUTEX_LOCK_PI or FUTEX_LOCK_PI2

上述幾點得知, futex status 如果為 0, 則可以用 atomic instruction 去改變內容, 如果不為 0, 則使用 FUTEX_LOCK_PI or FUTEX_LOCK_PI2 去等待 release.

另外一點很重要: 必須使用 TID 不可以使用 pthread id 下面就是用 thread id 跑出來的結果

start low pri
start high pri
high pri inhro
high pri
mid pri
end of busy work in low pri
low pri

會連基本的正確性都有問題…

改用 tid 之後結果就跟 pthread 結果一致了 src code

$ sudo ./test_pilinux 
start low pri
start high pri
end of busy work in low pri
high pri inhro
high pri
mid pri
low pri

Ref

fetex(2)
並行程式設計: 建立相容於 POSIX Thread 的實作
Linux中的同步机制 – Futex
蜗窝科技 - futex基础问答
openeuler - linux–futex原理分析