# 2023 Homework2 (quiz1)
contributed by <RoyWFHuang>
## futex introduction
[futex](https://man7.org/linux/man-pages/man2/futex.2.html)(fast user-space locking), 用來減少 user space 使用競爭資源時, 對於 lock 的 kernel 系統呼叫.
:::success
舉例來說, 兩個 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 進行等待跟喚醒.
```c
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](https://elixir.bootlin.com/linux/v6.4.11/source/kernel/futex/waitwake.c#L632)
```c
int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val, ktime_t *abs_time, u32 bitset)
```
FUTEX_WAKE: 對應至 [futex_wake](https://elixir.bootlin.com/linux/v6.4.11/source/kernel/futex/waitwake.c#L143)
```c
int futex_wake(u32 __user *uaddr, unsigned int flags, int nr_wake, u32 bitset)
```
## futex 修改第一次作業
src code: [github](https://github.com/RoyWFHuang/linux2023_summer/tree/master/quiz1)
目標: 使用 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
```
:::warning
在競爭比較不激烈( thread nunber, element 數量較少)的狀況下, 符合預期.
但在許多 thread 共同競爭下, futex 似乎就沒有 pthread 效能來的好?
或許是如同 futex 使用上所說, 如果 thread 之間, 競爭的資源越不相關, 使用的成本則是會越低?
:::
## priority inheritance mutex
### PI in POSIX thread
首先先看 POSIX thread 提供的 API
[pthread_attr_set(get)schedpolicy(3)](https://man7.org/linux/man-pages/man3/pthread_attr_setschedpolicy.3.html):
```c
#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)](https://man7.org/linux/man-pages/man3/pthread_attr_setinheritsched.3.html)
```c
#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)](https://man7.org/linux/man-pages/man3/pthread_setschedparam.3.html)
```c
#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)](https://man7.org/linux/man-pages/man7/sched.7.html). 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](https://github.com/RoyWFHuang/linux2023_summer/commit/cdf92dce39b847c2211a65afe6a550e62431e875)
test reusult using pthread define.
```shell
$ 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 (未經改寫)
```shell
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](https://elixir.bootlin.com/linux/v6.4.12/source/include/uapi/linux/futex.h)
```c
#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)](https://man7.org/linux/man-pages/man2/futex.2.html) 文件中閱讀:
:::info
* 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 跑出來的結果
```shell
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](https://github.com/RoyWFHuang/linux2023_summer/commit/80bdf91986bfc3918e41d5962b8ad511651751b3)
```shell
$ 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)](https://man7.org/linux/man-pages/man2/futex.2.html)
[並行程式設計: 建立相容於 POSIX Thread 的實作](https://hackmd.io/@sysprog/concurrency-thread-package)
[Linux中的同步机制 -- Futex](https://ryan0988.pixnet.net/blog/post/181245363)
[蜗窝科技 - futex基础问答](http://www.wowotech.net/kernel_synchronization/futex.html)
[openeuler - linux--futex原理分析](https://www.openeuler.org/zh/blog/wangshuo/Linux_Futex_Principle_Analysis/Linux_Futex_Principle_Analysis.html)
Sign in with Wallet
Connect another wallet