# 2023q1 Homework3 (fibdrv)
contributed by < [p96114175](https://github.com/p96114175/fibdrv) >
> [題目](https://hackmd.io/@sysprog/linux2023-quiz3)
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
$ lscpu
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 24
On-line CPU(s) list: 0-23
每核心執行緒數： 1
每通訊端核心數： 16
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 151
Model name: 12th Gen Intel(R) Core(TM) i9-12900F
製程： 2
CPU MHz： 2400.000
CPU max MHz: 5100.0000
CPU min MHz: 800.0000
BogoMIPS: 4838.40
虛擬： VT-x
L1d 快取： 384 KiB
L1i 快取： 256 KiB
L2 快取： 10 MiB
```
## 開發紀錄
在執行 `make check` 遇到以下問題
```
$ make check
Git hooks are installed successfully.
cc -o client client.c
make -C /lib/modules/5.15.0-69-generic/build M=/media/huaxin/D磁碟區/NUKU/fibdrv modules
make[1]: 進入目錄「/usr/src/linux-headers-5.15.0-69-generic」
CC [M] /media/huaxin/D磁碟區/NUKU/fibdrv/fibdrv.o
/media/huaxin/D磁碟區/NUKU/fibdrv/fibdrv.c: In function ‘fib_sequence’:
/media/huaxin/D磁碟區/NUKU/fibdrv/fibdrv.c:30:5: warning: ISO C90 forbids variable length array ‘f’ [-Wvla]
30 | long long f[k + 2];
| ^~~~
MODPOST /media/huaxin/D磁碟區/NUKU/fibdrv/Module.symvers
CC [M] /media/huaxin/D磁碟區/NUKU/fibdrv/fibdrv.mod.o
LD [M] /media/huaxin/D磁碟區/NUKU/fibdrv/fibdrv.ko
BTF [M] /media/huaxin/D磁碟區/NUKU/fibdrv/fibdrv.ko
Skipping BTF generation for /media/huaxin/D磁碟區/NUKU/fibdrv/fibdrv.ko due to unavailability of vmlinux
make[1]: 離開目錄「/usr/src/linux-headers-5.15.0-69-generic」
make unload
make[1]: 進入目錄「/media/huaxin/D磁碟區/NUKU/fibdrv」
sudo rmmod fibdrv || true >/dev/null
rmmod: ERROR: Module fibdrv is not currently loaded
make[1]: 離開目錄「/media/huaxin/D磁碟區/NUKU/fibdrv」
make load
make[1]: 進入目錄「/media/huaxin/D磁碟區/NUKU/fibdrv」
sudo insmod fibdrv.ko
make[1]: 離開目錄「/media/huaxin/D磁碟區/NUKU/fibdrv」
sudo ./client > out
make unload
make[1]: 進入目錄「/media/huaxin/D磁碟區/NUKU/fibdrv」
sudo rmmod fibdrv || true >/dev/null
make[1]: 離開目錄「/media/huaxin/D磁碟區/NUKU/fibdrv」
```
我們可以關閉 Secure Boot，該部分參考至 [willwillhi1](https://hackmd.io/@willwillhi/linux2023q1-fibdrv)
```
$ sudo mokutil --disable-validation
```
後續我再次執行
```
$ make check
make -C /lib/modules/5.15.0-69-generic/build M=/media/huaxin/D磁碟區/NUKU/fibdrv modules
make[1]: 進入目錄「/usr/src/linux-headers-5.15.0-69-generic」
make[1]: 離開目錄「/usr/src/linux-headers-5.15.0-69-generic」
make unload
make[1]: 進入目錄「/media/huaxin/D磁碟區/NUKU/fibdrv」
sudo rmmod fibdrv || true >/dev/null
rmmod: ERROR: Module fibdrv is not currently loaded
make[1]: 離開目錄「/media/huaxin/D磁碟區/NUKU/fibdrv」
make load
make[1]: 進入目錄「/media/huaxin/D磁碟區/NUKU/fibdrv」
sudo insmod fibdrv.ko
make[1]: 離開目錄「/media/huaxin/D磁碟區/NUKU/fibdrv」
sudo ./client > out
make unload
make[1]: 進入目錄「/media/huaxin/D磁碟區/NUKU/fibdrv」
sudo rmmod fibdrv || true >/dev/null
make[1]: 離開目錄「/media/huaxin/D磁碟區/NUKU/fibdrv」
Passed [-]
f(93) fail
input: 7540113804746346429
expected: 12200160415121876738
```
## 限定 CPU 給特定的程式使用
```
$ sudo nano /etc/default/grub
```
將 `GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=1"` 加入
## fast-doubling 加速 Fibonacci 運算
### 原先 fib 的寫法
```c
static long long fib_sequence(long long k)
{
/* FIXME: C99 variable-length array (VLA) is not allowed in Linux kernel. */
long long f[k + 2];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= k; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f[k];
}
```
參考了 [Matrix Difference Equation for Fibonacci Sequence](https://chunminchang.github.io/blog/post/matrix-difference-equation-for-fibonacci-sequence) 和 [Calculating Fibonacci Numbers by Fast Doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 如何進行加速運算，下方為參考公式
\begin{align*}
F_{2n+1}&=F^2_{n+1} + F^2_n \\
F_{2n}&=F_{n}\cdot(F_{n+1}+F_{n-1}) \\
&=F_{n}\cdot(F_{n+1}+(F_{n+1}-F_{n}) \\
&=F_{n}\cdot(2\cdot F_{n+1}-F_{n}) \\
\end{align*}
### Fast Doubling - recursive version
改良結果如下
```c
static long long fib_doubling(long long n)
{
if(n <= 2) return n ? 1 : 0;
long long k = n >> 1;
long long a = fib_doubling(k);
long long b = fib_doubling(k+1);
if (n % 2) return a*a+b*b;
return a * ((b<<1) - a);
}
```
### Fast Doubling - iterative version
改良結果如下
```c
static long long fib_interative(long long n)
{
uint8_t bits = 0;
for (uint64_t i = n ; i ; ++bits, i >>= 1);
long long a = 0; // F(0) = 0
long long b = 1; // F(1) = 1
for (uint64_t mask = 1 << (bits - 1) ; mask ; mask >>= 1) {
long long c = a * (2 * b - a); // F(2k) = F(k) * [ 2 * F(k+1) – F(k) ]
long long d = a * a + b * b; // F(2k+1) = F(k)^2 + F(k+1)^2
if (mask & n) { // n_j is odd: k = (n_j-1)/2 => n_j = 2k + 1
a = d; // F(n_j) = F(2k + 1)
b = c + d; // F(n_j + 1) = F(2k + 2) = F(2k) + F(2k + 1)
} else { // n_j is even: k = n_j/2 => n_j = 2k
a = c; // F(n_j) = F(2k)
b = d; // F(n_j + 1) = F(2k + 1)
}
}
return a;
}
```
### Fast Doubling with clz
首先，可以使用 clz / ctz 指令來計算 n 的二進制表示中最高位之前 0 的個數，再透過 `64 - __builtin_clzll(n)` 得到 n 的最高位數
在 Fibonacci 數列的計算過程中，我們需要從最高位開始遍歷 n 的二進制表示，因此需要先得到最高位需要的位數，然後用它來初始化 mask 變量：
```c
static long long fib_with_clz(long long n)
{
long long a = 0;
long long b = 1;
for (uint64_t mask = 1ull << 64 - __builtin_clzll(n) ; mask ; mask >>= 1) {
long long c = a * (2 * b - a);
long long d = a * a + b * b;
if (mask & n) {
a = d;
b = c + d;
} else {
a = c;
b = d;
}
}
return a;
}
```
## 核心模式的時間測量
在[教材](https://hackmd.io/@sysprog/linux2022-fibdrv#%E6%A0%B8%E5%BF%83%E6%A8%A1%E5%BC%8F%E7%9A%84%E6%99%82%E9%96%93%E6%B8%AC%E9%87%8F)中提到，一個新的機制是跳脫 `jiffies` 而將計時機制建立在一個新的資料結構 `ktime_t` 上面。這個結構體的定義會隨架構有所不同。
教材也提供了[ktime 相關的 API](https://www.kernel.org/doc/html/latest/core-api/timekeeping.html) 讓我們可以來測量時間。並參考教材範例，更改我的 `fibdrv.c`
透過 fib_time_proxy() 函數來計算 Fibonacci 數列函數 fib_doubling() 的運行時間，並在 fib_read() 中調用此函數來返回計算出的 Fibonacci 數，同時在 fib_write() 中返回上次呼叫 fib_read() 的運行時間。
```c
static ktime_t kt;
static long long fib_time_proxy(long long k)
{
kt = ktime_get();
long long result = fib_interative_clz(k);
kt = ktime_sub(ktime_get(), kt);
return result;
}
static ssize_t fib_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
return (ssize_t) fib_time_proxy(*offset);
}
static ssize_t fib_write(struct file *file,
const char *buf,
size_t size,
loff_t *offset)
{
return ktime_to_ns(kt);
}
```
在 [C語言：使用clock_gettime計算程式碼的時間需求](https://starforcefield.wordpress.com/2012/08/06/c%E8%AA%9E%E8%A8%80%EF%BC%9A%E4%BD%BF%E7%94%A8clock_gettime%E8%A8%88%E7%AE%97%E7%A8%8B%E5%BC%8F%E7%A2%BC%E7%9A%84%E6%99%82%E9%96%93%E9%9C%80%E6%B1%82/)中有提到
> 一般來說，C語言的標準程式庫裡面提供的time或clock兩個函數就可以滿足大部分的計時需求了。但在某些場合下可能會需要更精確的計時函數，例如說，比較兩個跑超快函數的時間消耗差異，或者是比較兩個時間消耗差異不大的函數。如果真有這個需求，而且你使用GNU/Linux，那就必須請到clock_gettime函式了。
首先，設定函式庫在 `test.c`
```
#include <time.h>
```
`time.h` 已經定義出 `timespec`
* tv_sec 表示為秒(s)
* tv_nsec 表示為奈秒(ns)
```c
struct timespec {
time_t tv_sec; /* seconds */
long tv_nsec; /* nanoseconds */
};
```
`time.h` 也涵蓋了 `clock_gettime` 函式的原型，在[clock_gettime(3) - Linux man page](https://linux.die.net/man/3/clock_gettime)有提到
> The clk_id argument is the identifier of the particular clock on which to act. A clock may be system-wide and hence visible for all processes, or per-process if it measures time only within a single process.
* 第二個參數則是放存時間的 `struct timespec`
```
int clock_gettime(clockid_t clk_id, struct timespec *tp);
```
我們再設計一個函式用於存取當前時間
```c
static inline long long get_ns()
{
struct timespec t;
clock_gettime(CLOCK_REALTIME, &t);
return t.tv_nsec + t.tv_sec;
}
```
以下為設計結果，
```c
int main()
{
long long sz, start, real_time, k_time;
char buf[1];
char write_buf[] = "testing writing";
int offset = 90;
int fd = open(FIB_DEV, O_RDWR);
if (fd < 0) {
perror("Failed to open character device");
exit(1);
}
write(fd, write_buf, strlen(write_buf));
for (int i = 0; i <= offset; i++) {
lseek(fd, i, SEEK_SET);
start = get_ns();
sz = read(fd, buf, 1);
real_time = get_ns() - start;
k_time = write(fd, write_buf, strlen(write_buf));
printf("%d %lld %lld %lld\n",i, real_time, k_time, real_time-k_time);
}
close(fd);
return 0;
}
```
在該圖可以發現，依照花費的時間由小到大，如下
1. fib sequence
2. iterative
3. recursive
4. iterative clz
### 接著可以進行以下設定排除干擾效能分析的因素
抑制 `address space layout randomization (ASLR)`
```
sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
```
撰寫` perfomance.sh`，並執行
```
for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
do
echo performance > ${i}
done
```
便可以得到下面的結果
可以從上下圖比較發現，在我們排除干擾效能分析的因素後，依據花費時間少到多，依序為
1. iterative
2. iterative_clz
3. fib_sequence
4. recursive
我們可以發現 `iterative` 加上 `clz` 後並無明顯減少運算時間，此外，`recursive` 比原先的做法 `fib_sequence` 還需耗費更多時間進行計算。
## 學習指出針對大數運算的加速運算和縮減記憶體操作成本的舉措，紀錄你的認知和疑惑
### _bn
針對大數運算，宣告以下結構體
* `number` 為一個指標指向著儲存的數值，其型別為 `unsigned int*`
* `size` 表示該數的記憶體大小
* `sign` 表示該數的正或負
```c
/* number[size - 1] = msb, number[0] = lsb */
typedef struct _bn {
unsigned int *number;
unsigned int size;
int sign;
} bn;
```
### bn_to_string
* 首先計算出 `len`，其中 `(8 * sizeof(int) * src.size)` 在計算 `src` 結構體中 `number` 的總 `Byte` 數目，再來使用 `/3` 將 `number` 轉換成十進制 `string` 所需要的 `characters` 數目，`2 + src.sign` 的 2 是為了預留 `\0` 的空間，`src.sign` 則是考慮到，若為負數，在轉換成 `string` 時，需要加上一個負號。
* 定義一個 `char` 型指標 s ，使用 `kmalloc` 分配記憶體空間，其中 `kmalloc` 函數是一個在 `kernel` 模塊中使用的動態內存分配函數
* 使用 `memset` 將 s 指標所指向的記憶體空間的前 `len-1` 個 byte 都填為 '0'
```c
/*
* output bn to decimal string
* Note: the returned string should be freed with kfree()
*/
char *bn_to_string(bn src)
{
// log10(x) = log2(x) / log2(10) ~= log2(x) / 3.322
size_t len = (8 * sizeof(int) * src.size) / 3 + 2 + src.sign;
char *s = kmalloc(len, GFP_KERNEL);
char *p = s;
memset(s, '0', len - 1);
s[len - 1] = '\0';
for (int i = src.size - 1; i >= 0; i--) {
for (unsigned int d = 1U << 31; d; d >>= 1) {
/* binary -> decimal string */
int carry = !!(d & src.number[i]);
for (int j = len - 2; j >= 0; j--) {
s[j] += s[j] - '0' + carry; // double it
carry = (s[j] > '9');
if (carry)
s[j] -= 10;
}
}
}
// skip leading zero
while (p[0] == '0' && p[1] != '\0') {
p++;
}
if (src.sign)
*(--p) = '-';
memmove(s, p, strlen(p) + 1);
return s;
}
```
## 研讀 `Linux 效能分析的提示` ，在自己的電腦上運作GNU/Linux，並做好必要的設定和準備工作，從中理解為何不要在虛擬機器上進行實驗。
根據 [查看行程的 CPU affinity](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-c)
### 若想要查看指定行程的處理器親和性，可使用 `taskset` 加上 `-p` 參數再加上該行程的 PID（process ID）：
```
$ taskset -p PID
```
於是我開啟了一個 `chrome` 的分頁，透過以下方式獲得 process 的 PID
```
$ pidof chrome
```
然後得到以下結果，由高到低列出，換句話說就是最近到最舊
```
8638 8602 8504 8503 8487 8480 8466 8465 8442 8438 8437 8420
```
接著我使用了最近的 PID `8638` ，並執行以下指令
```
$ taskset -p 8638
```
得到以下輸出，就是 `8638` 的`處理器親和性`
接著我們加上 `-c` 參數，讓 taskset 直接輸出 `CPU 核的列表`：
```
$ taskset -cp 8638
```
得到以下輸出
### 將行程固定在特定的 CPU 中執行
在教材中有提到，可使用以下兩個方法完成，兩種方式效果一致
第一種，COREMASK 就是指定的十六進位 core mask，PID 則為行程的 ID。
```
$ taskset -p COREMASK PID
```
第二種，使用 `-c` 參數以 CPU 的核心列表來指定
```
$ taskset -cp CORELIST PID
```
後來我選用了第二個方法來實現，我將行程的PID `8638` 固定在第一個和第三個 CPU 核，以下為我的輸入
```
$ taskset -cp 1,3 8638
```
輸出為：
### 限定 CPU 給特定的程式使用
流程可分為
* 第一步，讓特定的 CPU 核在開機時就被保留下來。
下方為教材提到的範例，讓在開機時，第0個和第1個 `CPU` 保留下來
```
isolcpus=0,1
```
* 第二步，使用 `taskset` 命令將這兩個 CPU 核指定給要執行的程式使用即可。
### 排除干擾效能分析的因素
該部分主要以環境設定為主，將可能對效能產生影響的因素盡可能避免掉，分別為
* 抑制 address space layout randomization (ASLR)
* 設定 scaling_governor 為 performance。
* 針對 Intel 處理器，關閉 turbo mode
* 關閉 [SMT](https://en.wikipedia.org/wiki/Simultaneous_multithreading) (Intel 稱它為 [Hyper-Threading](https://en.wikipedia.org/wiki/Hyper-threading))
## 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？
**DEFINE_MUTEX**
在`fibdrv.c` 這一文件中，我觀察到
```c
static DEFINE_MUTEX(fib_mutex);
```
使用 `DEFINE_MUTEX` 可用於定義出我們的 mutex
**mutex_trylock**
從字面上可以理解該字樣是常是獲取 lock ，於是我觀看教材 [POSIX Threads](https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fposix-threads) 裡面提到
> If `pthread_mutex_trylock()` returns `EBUSY`, the lock is already locked. Otherwise, the calling thread becomes the owner of this lock.
接著再觀察 `fibdrv.c` 這一文件中這樣撰寫
```c
static int fib_open(struct inode *inode, struct file *file)
{
if (!mutex_trylock(&fib_mutex)) {
printk(KERN_ALERT "fibdrv is in use");
return -EBUSY;
}
return 0;
}
```
我們可以清楚的知道，當返回 `EBUSY` 時意味著，你的 lock 仍然被鎖著，你的 thread 並未取得 lock ，相反的，你的 thread 便會獲得 lock 並成為 lock 的擁有者。
**mutex_init**
在 [mutex_init](https://archive.kernel.org/oldlinux/htmldocs/kernel-locking/API-mutex-init.html) 有提到
> Initialize the mutex to unlocked state.
> It is not allowed to initialize an already locked mutex.
那接著再觀察 `fibdrv.c` 這一文件中，可知道正在對 mutex 進行初始化到未鎖狀態
```c
static int __init init_fib_dev(void)
{
int rc = 0;
mutex_init(&fib_mutex);
```
**mutex_unlock**
在 [mutex_unlock](https://archive.kernel.org/oldlinux/htmldocs/kernel-locking/API-mutex-unlock.html) 有提到
> Unlock a mutex that has been locked by this task previously.
> This function must not be used in interrupt context. Unlocking of a not locked mutex is not allowed.
接著再觀察 fibdrv.c 這一文件中這樣撰寫
```c
static int fib_release(struct inode *inode, struct file *file)
{
mutex_unlock(&fib_mutex);
return 0;
}
```
它將 `mutex_unlock` 應用在 `fib_release` 這一函式中，目的是在費伯納西釋放時，將 mutex 進行解鎖
**mutex_destroy**
在 fibdrv.c 這一文件中，該處使用了 `mutex_destroy`
```c
static void __exit exit_fib_dev(void)
{
mutex_destroy(&fib_mutex);
device_destroy(fib_class, fib_dev);
class_destroy(fib_class);
cdev_del(fib_cdev);
unregister_chrdev_region(fib_dev, 1);
}
```
從字樣中可判斷出，這是在離開 fib 時所調用的函式，裡頭使用了 `mutex_destroy` 目的在於將 mutex 進行釋放
## 撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。
#### 參考資料
[POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads)
搭配閱讀〈[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)〉
我會做個實驗組和對照組，分別為有用到 mutex 和沒有使用到 mutex 的
### 有用到 mutex(並未註解掉原先程式有用到 mutex 的部分)
我參考了 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 設計一個名為 `thread.c` 的檔案並使用兩個執行序去執行我的函數 `Run_fibonacci`
```c
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <sys/types.h>
#include <pthread.h>
#include <unistd.h>
#define NUM_THREADS 2
#define FIB_DEV "/dev/fibonacci"
void Run_fibonacci()
{
long long sz;
char buf[128];
char write_buf[] = "testing writing";
int offset = 92;
int fd = open(FIB_DEV, O_RDWR);
if (fd < 0) {
perror("Failed to open character device");
exit(1);
}
write(fd, write_buf, strlen(write_buf));
for (int i = 0; i <= offset; i++) {
lseek(fd, i, SEEK_SET);
sz = read(fd, buf, 1);
printf("reading from " FIB_DEV " at ofset %d, returned the sequence ""%lld.\n", i, sz);
}
close(fd);
}
int main() {
pthread_t threads[NUM_THREADS];
int i;
int result_code;
//create all threads one by one
for (i = 0; i < NUM_THREADS; i++) {
printf("IN MAIN: Creating thread %d.\n", i);
result_code = pthread_create(&threads[i], NULL, (void *(*)(void *))Run_fibonacci, NULL);
assert(!result_code);
}
printf("IN MAIN: All threads are created.\n");
//wait for each thread to complete
for (i = 0; i < NUM_THREADS; i++) {
result_code = pthread_join(threads[i], NULL);
assert(!result_code);
printf("IN MAIN: Thread %d has ended.\n", i);
}
printf("MAIN program has ended.\n");
return 0;
}
```
在我執行 `fib_thread.sh` 後
```
make
sudo rmmod fibdrv
sudo insmod fibdrv.ko
gcc thread.c -pthread -o thread
sudo ./thread > fib_mutex.txt
```
在 `fib_mutex.txt` 得到以下結果
```
IN MAIN: Creating thread 0.
IN MAIN: Creating thread 1.
reading from /dev/fibonacci at ofset 0, returned the sequence 0.
reading from /dev/fibonacci at ofset 1, returned the sequence 1.
reading from /dev/fibonacci at ofset 2, returned the sequence 1.
reading from /dev/fibonacci at ofset 3, returned the sequence 2.
reading from /dev/fibonacci at ofset 4, returned the sequence 3.
reading from /dev/fibonacci at ofset 5, returned the sequence 5.
reading from /dev/fibonacci at ofset 6, returned the sequence 8.
reading from /dev/fibonacci at ofset 7, returned the sequence 13.
reading from /dev/fibonacci at ofset 8, returned the sequence 21.
reading from /dev/fibonacci at ofset 9, returned the sequence 34.
reading from /dev/fibonacci at ofset 10, returned the sequence 55.
reading from /dev/fibonacci at ofset 11, returned the sequence 89.
reading from /dev/fibonacci at ofset 12, returned the sequence 144.
reading from /dev/fibonacci at ofset 13, returned the sequence 233.
reading from /dev/fibonacci at ofset 14, returned the sequence 377.
reading from /dev/fibonacci at ofset 15, returned the sequence 610.
reading from /dev/fibonacci at ofset 16, returned the sequence 987.
reading from /dev/fibonacci at ofset 17, returned the sequence 1597.
reading from /dev/fibonacci at ofset 18, returned the sequence 2584.
reading from /dev/fibonacci at ofset 19, returned the sequence 4181.
reading from /dev/fibonacci at ofset 20, returned the sequence 6765.
reading from /dev/fibonacci at ofset 21, returned the sequence 10946.
reading from /dev/fibonacci at ofset 22, returned the sequence 17711.
IN MAIN: All threads are created.
reading from /dev/fibonacci at ofset 23, returned the sequence 28657.
reading from /dev/fibonacci at ofset 24, returned the sequence 46368.
reading from /dev/fibonacci at ofset 25, returned the sequence 75025.
reading from /dev/fibonacci at ofset 26, returned the sequence 121393.
reading from /dev/fibonacci at ofset 27, returned the sequence 196418.
reading from /dev/fibonacci at ofset 28, returned the sequence 317811.
reading from /dev/fibonacci at ofset 29, returned the sequence 514229.
reading from /dev/fibonacci at ofset 30, returned the sequence 832040.
reading from /dev/fibonacci at ofset 31, returned the sequence 1346269.
reading from /dev/fibonacci at ofset 32, returned the sequence 2178309.
reading from /dev/fibonacci at ofset 33, returned the sequence 3524578.
reading from /dev/fibonacci at ofset 34, returned the sequence 5702887.
reading from /dev/fibonacci at ofset 35, returned the sequence 9227465.
reading from /dev/fibonacci at ofset 36, returned the sequence 14930352.
reading from /dev/fibonacci at ofset 37, returned the sequence 24157817.
reading from /dev/fibonacci at ofset 38, returned the sequence 39088169.
reading from /dev/fibonacci at ofset 39, returned the sequence 63245986.
reading from /dev/fibonacci at ofset 40, returned the sequence 102334155.
reading from /dev/fibonacci at ofset 41, returned the sequence 165580141.
reading from /dev/fibonacci at ofset 42, returned the sequence 267914296.
reading from /dev/fibonacci at ofset 43, returned the sequence 433494437.
reading from /dev/fibonacci at ofset 44, returned the sequence 701408733.
reading from /dev/fibonacci at ofset 45, returned the sequence 1134903170.
reading from /dev/fibonacci at ofset 46, returned the sequence 1836311903.
reading from /dev/fibonacci at ofset 47, returned the sequence 2971215073.
reading from /dev/fibonacci at ofset 48, returned the sequence 4807526976.
reading from /dev/fibonacci at ofset 49, returned the sequence 7778742049.
reading from /dev/fibonacci at ofset 50, returned the sequence 12586269025.
reading from /dev/fibonacci at ofset 51, returned the sequence 20365011074.
reading from /dev/fibonacci at ofset 52, returned the sequence 32951280099.
reading from /dev/fibonacci at ofset 53, returned the sequence 53316291173.
reading from /dev/fibonacci at ofset 54, returned the sequence 86267571272.
reading from /dev/fibonacci at ofset 55, returned the sequence 139583862445.
reading from /dev/fibonacci at ofset 56, returned the sequence 225851433717.
reading from /dev/fibonacci at ofset 57, returned the sequence 365435296162.
reading from /dev/fibonacci at ofset 58, returned the sequence 591286729879.
reading from /dev/fibonacci at ofset 59, returned the sequence 956722026041.
reading from /dev/fibonacci at ofset 60, returned the sequence 1548008755920.
reading from /dev/fibonacci at ofset 61, returned the sequence 2504730781961.
reading from /dev/fibonacci at ofset 62, returned the sequence 4052739537881.
reading from /dev/fibonacci at ofset 63, returned the sequence 6557470319842.
reading from /dev/fibonacci at ofset 64, returned the sequence 10610209857723.
reading from /dev/fibonacci at ofset 65, returned the sequence 17167680177565.
reading from /dev/fibonacci at ofset 66, returned the sequence 27777890035288.
reading from /dev/fibonacci at ofset 67, returned the sequence 44945570212853.
reading from /dev/fibonacci at ofset 68, returned the sequence 72723460248141.
reading from /dev/fibonacci at ofset 69, returned the sequence 117669030460994.
reading from /dev/fibonacci at ofset 70, returned the sequence 190392490709135.
reading from /dev/fibonacci at ofset 71, returned the sequence 308061521170129.
reading from /dev/fibonacci at ofset 72, returned the sequence 498454011879264.
reading from /dev/fibonacci at ofset 73, returned the sequence 806515533049393.
reading from /dev/fibonacci at ofset 74, returned the sequence 1304969544928657.
reading from /dev/fibonacci at ofset 75, returned the sequence 2111485077978050.
reading from /dev/fibonacci at ofset 76, returned the sequence 3416454622906707.
reading from /dev/fibonacci at ofset 77, returned the sequence 5527939700884757.
reading from /dev/fibonacci at ofset 78, returned the sequence 8944394323791464.
reading from /dev/fibonacci at ofset 79, returned the sequence 14472334024676221.
reading from /dev/fibonacci at ofset 80, returned the sequence 23416728348467685.
reading from /dev/fibonacci at ofset 81, returned the sequence 37889062373143906.
reading from /dev/fibonacci at ofset 82, returned the sequence 61305790721611591.
reading from /dev/fibonacci at ofset 83, returned the sequence 99194853094755497.
reading from /dev/fibonacci at ofset 84, returned the sequence 160500643816367088.
reading from /dev/fibonacci at ofset 85, returned the sequence 259695496911122585.
reading from /dev/fibonacci at ofset 86, returned the sequence 420196140727489673.
reading from /dev/fibonacci at ofset 87, returned the sequence 679891637638612258.
reading from /dev/fibonacci at ofset 88, returned the sequence 1100087778366101931.
reading from /dev/fibonacci at ofset 89, returned the sequence 1779979416004714189.
reading from /dev/fibonacci at ofset 90, returned the sequence 2880067194370816120.
reading from /dev/fibonacci at ofset 91, returned the sequence 4660046610375530309.
reading from /dev/fibonacci at ofset 92, returned the sequence 7540113804746346429.
dev/fibonacci at ofset 41, returned the sequence 165580141.
reading from /dev/fibonacci at ofset 42, returned the sequence 267914296.
reading from /dev/fibonacci at ofset 43, returned the sequence 433494437.
reading from /dev/fibonacci at ofset 44, returned the sequence 701408733.
reading from /dev/fibonacci at ofset 45, returned the sequence 1134903170.
reading from /dev/fibonacci at ofset 46, returned the sequence 1836311903.
reading from /dev/fibonacci at ofset 47, returned the sequence 2971215073.
reading from /dev/fibonacci at ofset 48, returned the sequence 4807526976.
reading from /dev/fibonacci at ofset 49, returned the sequence 7778742049.
reading from /dev/fibonacci at ofset 50, returned the sequence 12586269025.
reading from /dev/fibonacci at ofset 51, returned the sequence 20365011074.
reading from /dev/fibonacci at ofset 52, returned the sequence 32951280099.
reading from /dev/fibonacci at ofset 53, returned the sequence 53316291173.
reading from /dev/fibonacci at ofset 54, returned the sequence 86267571272.
reading from /dev/fibonacci at ofset 55, returned the sequence 139583862445.
reading from /dev/fibonacci at ofset 56, ret
```
### 未用到 mutex(註解掉原先程式有用到 mutex 的部分)
我已將 `fibdrv.c` 有關 `mutex` 的關鍵字註解掉
```c
#include <linux/cdev.h>
#include <linux/device.h>
#include <linux/fs.h>
#include <linux/init.h>
#include <linux/kdev_t.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/mutex.h>
MODULE_LICENSE("Dual MIT/GPL");
MODULE_AUTHOR("National Cheng Kung University, Taiwan");
MODULE_DESCRIPTION("Fibonacci engine driver");
MODULE_VERSION("0.1");
#define DEV_FIBONACCI_NAME "fibonacci"
/* MAX_LENGTH is set to 92 because
* ssize_t can't fit the number > 92
*/
#define MAX_LENGTH 92
static dev_t fib_dev = 0;
static struct cdev *fib_cdev;
static struct class *fib_class;
// static DEFINE_MUTEX(fib_mutex);
static long long fib_sequence(long long k)
{
/* FIXME: C99 variable-length array (VLA) is not allowed in Linux kernel. */
long long f[k + 2];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= k; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f[k];
}
static long long fib_doubling(long long n)
{
if(n <= 2) return n ? 1 : 0;
long long k = n >> 1;
long long a = fib_doubling(k);
long long b = fib_doubling(k+1);
if (n % 2) return a*a+b*b;
return a * ((b<<1) - a);
}
static long long fib_interative(long long n)
{
uint8_t bits = 0;
for (uint64_t i = n ; i ; ++bits, i >>= 1);
long long a = 0; // F(0) = 0
long long b = 1; // F(1) = 1
for (uint64_t mask = 1 << (bits - 1) ; mask ; mask >>= 1) {
long long c = a * (2 * b - a); // F(2k) = F(k) * [ 2 * F(k+1) – F(k) ]
long long d = a * a + b * b; // F(2k+1) = F(k)^2 + F(k+1)^2
if (mask & n) { // n_j is odd: k = (n_j-1)/2 => n_j = 2k + 1
a = d; // F(n_j) = F(2k + 1)
b = c + d; // F(n_j + 1) = F(2k + 2) = F(2k) + F(2k + 1)
} else { // n_j is even: k = n_j/2 => n_j = 2k
a = c; // F(n_j) = F(2k)
b = d; // F(n_j + 1) = F(2k + 1)
}
}
return a;
}
static int fib_open(struct inode *inode, struct file *file)
{
// if (!mutex_trylock(&fib_mutex)) {
// printk(KERN_ALERT "fibdrv is in use");
// return -EBUSY;
// }
return 0;
}
static int fib_release(struct inode *inode, struct file *file)
{
// mutex_unlock(&fib_mutex);
return 0;
}
/* calculate the fibonacci number at given offset */
static ssize_t fib_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
return (ssize_t) fib_sequence(*offset);
}
/* write operation is skipped */
static ssize_t fib_write(struct file *file,
const char *buf,
size_t size,
loff_t *offset)
{
return 1;
}
static loff_t fib_device_lseek(struct file *file, loff_t offset, int orig)
{
loff_t new_pos = 0;
switch (orig) {
case 0: /* SEEK_SET: */
new_pos = offset;
break;
case 1: /* SEEK_CUR: */
new_pos = file->f_pos + offset;
break;
case 2: /* SEEK_END: */
new_pos = MAX_LENGTH - offset;
break;
}
if (new_pos > MAX_LENGTH)
new_pos = MAX_LENGTH; // max case
if (new_pos < 0)
new_pos = 0; // min case
file->f_pos = new_pos; // This is what we'll use now
return new_pos;
}
const struct file_operations fib_fops = {
.owner = THIS_MODULE,
.read = fib_read,
.write = fib_write,
.open = fib_open,
.release = fib_release,
.llseek = fib_device_lseek,
};
static int __init init_fib_dev(void)
{
int rc = 0;
// mutex_init(&fib_mutex);
// Let's register the device
// This will dynamically allocate the major number
rc = alloc_chrdev_region(&fib_dev, 0, 1, DEV_FIBONACCI_NAME);
if (rc < 0) {
printk(KERN_ALERT
"Failed to register the fibonacci char device. rc = %i",
rc);
return rc;
}
fib_cdev = cdev_alloc();
if (fib_cdev == NULL) {
printk(KERN_ALERT "Failed to alloc cdev");
rc = -1;
goto failed_cdev;
}
fib_cdev->ops = &fib_fops;
rc = cdev_add(fib_cdev, fib_dev, 1);
if (rc < 0) {
printk(KERN_ALERT "Failed to add cdev");
rc = -2;
goto failed_cdev;
}
fib_class = class_create(THIS_MODULE, DEV_FIBONACCI_NAME);
if (!fib_class) {
printk(KERN_ALERT "Failed to create device class");
rc = -3;
goto failed_class_create;
}
if (!device_create(fib_class, NULL, fib_dev, NULL, DEV_FIBONACCI_NAME)) {
printk(KERN_ALERT "Failed to create device");
rc = -4;
goto failed_device_create;
}
return rc;
failed_device_create:
class_destroy(fib_class);
failed_class_create:
cdev_del(fib_cdev);
failed_cdev:
unregister_chrdev_region(fib_dev, 1);
return rc;
}
static void __exit exit_fib_dev(void)
{
// mutex_destroy(&fib_mutex);
device_destroy(fib_class, fib_dev);
class_destroy(fib_class);
cdev_del(fib_cdev);
unregister_chrdev_region(fib_dev, 1);
}
module_init(init_fib_dev);
module_exit(exit_fib_dev);
```
執行 `fib_thread.sh`
```
make
sudo rmmod fibdrv
sudo insmod fibdrv.ko
gcc thread.c -pthread -o thread
sudo ./thread > fib_without_mutex.txt
```
在 `fib_without_mutex.txt` 得到以下結果
```
IN MAIN: Creating thread 0.
IN MAIN: Creating thread 1.
reading from /dev/fibonacci at ofset 0, returned the sequence 0.
reading from /dev/fibonacci at ofset 1, returned the sequence 1.
reading from /dev/fibonacci at ofset 2, returned the sequence 1.
reading from /dev/fibonacci at ofset 3, returned the sequence 2.
reading from /dev/fibonacci at ofset 4, returned the sequence 3.
reading from /dev/fibonacci at ofset 5, returned the sequence 5.
reading from /dev/fibonacci at ofset 6, returned the sequence 8.
reading from /dev/fibonacci at ofset 7, returned the sequence 13.
reading from /dev/fibonacci at ofset 8, returned the sequence 21.
reading from /dev/fibonacci at ofset 9, returned the sequence 34.
reading from /dev/fibonacci at ofset 10, returned the sequence 55.
reading from /dev/fibonacci at ofset 11, returned the sequence 89.
reading from /dev/fibonacci at ofset 12, returned the sequence 144.
reading from /dev/fibonacci at ofset 13, returned the sequence 233.
reading from /dev/fibonacci at ofset 14, returned the sequence 377.
reading from /dev/fibonacci at ofset 15, returned the sequence 610.
reading from /dev/fibonacci at ofset 16, returned the sequence 987.
reading from /dev/fibonacci at ofset 17, returned the sequence 1597.
reading from /dev/fibonacci at ofset 18, returned the sequence 2584.
reading from /dev/fibonacci at ofset 19, returned the sequence 4181.
reading from /dev/fibonacci at ofset 20, returned the sequence 6765.
IN MAIN: All threads are created.
reading from /dev/fibonacci at ofset 21, returned the sequence 10946.
reading from /dev/fibonacci at ofset 22, returned the sequence 17711.
reading from /dev/fibonacci at ofset 23, returned the sequence 28657.
reading from /dev/fibonacci at ofset 24, returned the sequence 46368.
reading from /dev/fibonacci at ofset 25, returned the sequence 75025.
reading from /dev/fibonacci at ofset 26, returned the sequence 121393.
reading from /dev/fibonacci at ofset 27, returned the sequence 196418.
reading from /dev/fibonacci at ofset 28, returned the sequence 317811.
reading from /dev/fibonacci at ofset 29, returned the sequence 514229.
reading from /dev/fibonacci at ofset 30, returned the sequence 832040.
reading from /dev/fibonacci at ofset 31, returned the sequence 1346269.
reading from /dev/fibonacci at ofset 32, returned the sequence 2178309.
reading from /dev/fibonacci at ofset 33, returned the sequence 3524578.
reading from /dev/fibonacci at ofset 34, returned the sequence 5702887.
reading from /dev/fibonacci at ofset 35, returned the sequence 9227465.
reading from /dev/fibonacci at ofset 36, returned the sequence 14930352.
reading from /dev/fibonacci at ofset 37, returned the sequence 24157817.
reading from /dev/fibonacci at ofset 0, returned the sequence 0.
reading from /dev/fibonacci at ofset 1, returned the sequence 1.
reading from /dev/fibonacci at ofset 2, returned the sequence 1.
reading from /dev/fibonacci at ofset 3, returned the sequence 2.
reading from /dev/fibonacci at ofset 4, returned the sequence 3.
reading from /dev/fibonacci at ofset 5, returned the sequence 5.
reading from /dev/fibonacci at ofset 38, returned the sequence 39088169.
reading from /dev/fibonacci at ofset 6, returned the sequence 8.
reading from /dev/fibonacci at ofset 39, returned the sequence 63245986.
reading from /dev/fibonacci at ofset 7, returned the sequence 13.
reading from /dev/fibonacci at ofset 40, returned the sequence 102334155.
reading from /dev/fibonacci at ofset 8, returned the sequence 21.
reading from /dev/fibonacci at ofset 41, returned the sequence 165580141.
reading from /dev/fibonacci at ofset 9, returned the sequence 34.
reading from /dev/fibonacci at ofset 42, returned the sequence 267914296.
reading from /dev/fibonacci at ofset 10, returned the sequence 55.
reading from /dev/fibonacci at ofset 43, returned the sequence 433494437.
reading from /dev/fibonacci at ofset 11, returned the sequence 89.
reading from /dev/fibonacci at ofset 44, returned the sequence 701408733.
reading from /dev/fibonacci at ofset 12, returned the sequence 144.
reading from /dev/fibonacci at ofset 45, returned the sequence 1134903170.
reading from /dev/fibonacci at ofset 46, returned the sequence 1836311903.
reading from /dev/fibonacci at ofset 47, returned the sequence 2971215073.
reading from /dev/fibonacci at ofset 48, returned the sequence 4807526976.
reading from /dev/fibonacci at ofset 13, returned the sequence 233.
reading from /dev/fibonacci at ofset 49, returned the sequence 7778742049.
reading from /dev/fibonacci at ofset 50, returned the sequence 12586269025.
reading from /dev/fibonacci at ofset 14, returned the sequence 377.
reading from /dev/fibonacci at ofset 51, returned the sequence 20365011074.
reading from /dev/fibonacci at ofset 15, returned the sequence 610.
reading from /dev/fibonacci at ofset 52, returned the sequence 32951280099.
reading from /dev/fibonacci at ofset 16, returned the sequence 987.
reading from /dev/fibonacci at ofset 53, returned the sequence 53316291173.
reading from /dev/fibonacci at ofset 17, returned the sequence 1597.
reading from /dev/fibonacci at ofset 54, returned the sequence 86267571272.
reading from /dev/fibonacci at ofset 55, returned the sequence 139583862445.
reading from /dev/fibonacci at ofset 56, returned the sequence 225851433717.
reading from /dev/fibonacci at ofset 57, returned the sequence 365435296162.
reading from /dev/fibonacci at ofset 18, returned the sequence 2584.
reading from /dev/fibonacci at ofset 58, returned the sequence 591286729879.
reading from /dev/fibonacci at ofset 19, returned the sequence 4181.
reading from /dev/fibonacci at ofset 59, returned the sequence 956722026041.
reading from /dev/fibonacci at ofset 20, returned the sequence 6765.
reading from /dev/fibonacci at ofset 60, returned the sequence 1548008755920.
reading from /dev/fibonacci at ofset 21, returned the sequence 10946.
reading from /dev/fibonacci at ofset 61, returned the sequence 2504730781961.
reading from /dev/fibonacci at ofset 22, returned the sequence 17711.
reading from /dev/fibonacci at ofset 62, returned the sequence 4052739537881.
reading from /dev/fibonacci at ofset 23, returned the sequence 28657.
reading from /dev/fibonacci at ofset 63, returned the sequence 6557470319842.
reading from /dev/fibonacci at ofset 64, returned the sequence 10610209857723.
reading from /dev/fibonacci at ofset 65, returned the sequence 17167680177565.
reading from /dev/fibonacci at ofset 66, returned the sequence 27777890035288.
reading from /dev/fibonacci at ofset 24, returned the sequence 46368.
reading from /dev/fibonacci at ofset 67, returned the sequence 44945570212853.
reading from /dev/fibonacci at ofset 25, returned the sequence 75025.
reading from /dev/fibonacci at ofset 68, returned the sequence 72723460248141.
reading from /dev/fibonacci at ofset 26, returned the sequence 121393.
reading from /dev/fibonacci at ofset 69, returned the sequence 117669030460994.
reading from /dev/fibonacci at ofset 27, returned the sequence 196418.
reading from /dev/fibonacci at ofset 70, returned the sequence 190392490709135.
reading from /dev/fibonacci at ofset 28, returned the sequence 317811.
reading from /dev/fibonacci at ofset 71, returned the sequence 308061521170129.
reading from /dev/fibonacci at ofset 29, returned the sequence 514229.
reading from /dev/fibonacci at ofset 72, returned the sequence 498454011879264.
reading from /dev/fibonacci at ofset 73, returned the sequence 806515533049393.
reading from /dev/fibonacci at ofset 74, returned the sequence 1304969544928657.
reading from /dev/fibonacci at ofset 75, returned the sequence 2111485077978050.
reading from /dev/fibonacci at ofset 30, returned the sequence 832040.
reading from /dev/fibonacci at ofset 76, returned the sequence 3416454622906707.
reading from /dev/fibonacci at ofset 31, returned the sequence 1346269.
reading from /dev/fibonacci at ofset 77, returned the sequence 5527939700884757.
reading from /dev/fibonacci at ofset 32, returned the sequence 2178309.
reading from /dev/fibonacci at ofset 78, returned the sequence 8944394323791464.
reading from /dev/fibonacci at ofset 33, returned the sequence 3524578.
reading from /dev/fibonacci at ofset 34, returned the sequence 5702887.
reading from /dev/fibonacci at ofset 35, returned the sequence 9227465.
reading from /dev/fibonacci at ofset 36, returned the sequence 14930352.
reading from /dev/fibonacci at ofset 79, returned the sequence 14472334024676221.
reading from /dev/fibonacci at ofset 80, returned the sequence 23416728348467685.
reading from /dev/fibonacci at ofset 81, returned the sequence 37889062373143906.
reading from /dev/fibonacci at ofset 37, returned the sequence 24157817.
reading from /dev/fibonacci at ofset 82, returned the sequence 61305790721611591.
reading from /dev/fibonacci at ofset 38, returned the sequence 39088169.
reading from /dev/fibonacci at ofset 83, returned the sequence 99194853094755497.
reading from /dev/fibonacci at ofset 39, returned the sequence 63245986.
reading from /dev/fibonacci at ofset 84, returned the sequence 160500643816367088.
reading from /dev/fibonacci at ofset 40, returned the sequence 102334155.
reading from /dev/fibonacci at ofset 85, returned the sequence 259695496911122585.
reading from /dev/fibonacci at ofset 86, returned the sequence 420196140727489673.
reading from /dev/fibonacci at ofset 87, returned the sequence 679891637638612258.
reading from /dev/fibonacci at ofset 41, returned the sequence 165580141.
reading from /dev/fibonacci at ofset 42, returned the sequence 267914296.
reading from /dev/fibonacci at ofset 43, returned the sequence 433494437.
reading from /dev/fibonacci at ofset 44, returned the sequence 701408733.
reading from /dev/fibonacci at ofset 88, returned the sequence 1100087778366101931.
reading from /dev/fibonacci at ofset 45, returned the sequence 1134903170.
reading from /dev/fibonacci at ofset 89, returned the sequence 1779979416004714189.
reading from /dev/fibonacci at ofset 46, returned the sequence 1836311903.
reading from /dev/fibonacci at ofset 90, returned the sequence 2880067194370816120.
reading from /dev/fibonacci at ofset 47, returned the sequence 2971215073.
reading from /dev/fibonacci at ofset 91, returned the sequence 4660046610375530309.
reading from /dev/fibonacci at ofset 48, returned the sequence 4807526976.
reading from /dev/fibonacci at ofset 92, returned the sequence 7540113804746346429.
reading from /dev/fibonacci at ofset 49, returned the sequence 7778742049.
reading from /dev/fibonacci at ofset 50, returned the sequence 12586269025.
reading from /dev/fibonacci at ofset 51, returned the sequence 20365011074.
reading from /dev/fibonacci at ofset 52, returned the sequence 32951280099.
reading from /dev/fibonacci at ofset 53, returned the sequence 53316291173.
reading from /dev/fibonacci at ofset 54, returned the sequence 86267571272.
reading from /dev/fibonacci at ofset 55, returned the sequence 139583862445.
reading from /dev/fibonacci at ofset 56, returned the sequence 225851433717.
reading from /dev/fibonacci at ofset 57, returned the sequence 365435296162.
reading from /dev/fibonacci at ofset 58, returned the sequence 591286729879.
reading from /dev/fibonacci at ofset 59, returned the sequence 956722026041.
reading from /dev/fibonacci at ofset 60, returned the sequence 1548008755920.
reading from /dev/fibonacci at ofset 61, returned the sequence 2504730781961.
reading from /dev/fibonacci at ofset 62, returned the sequence 4052739537881.
reading from /dev/fibonacci at ofset 63, returned the sequence 6557470319842.
reading from /dev/fibonacci at ofset 64, returned the sequence 10610209857723.
reading from /dev/fibonacci at ofset 65, returned the sequence 17167680177565.
reading from /dev/fibonacci at ofset 66, returned the sequence 27777890035288.
reading from /dev/fibonacci at ofset 67, returned the sequence 44945570212853.
reading from /dev/fibonacci at ofset 68, returned the sequence 72723460248141.
reading from /dev/fibonacci at ofset 69, returned the sequence 117669030460994.
reading from /dev/fibonacci at ofset 70, returned the sequence 190392490709135.
reading from /dev/fibonacci at ofset 71, returned the sequence 308061521170129.
reading from /dev/fibonacci at ofset 72, returned the sequence 498454011879264.
reading from /dev/fibonacci at ofset 73, returned the sequence 806515533049393.
reading from /dev/fibonacci at ofset 74, returned the sequence 1304969544928657.
reading from /dev/fibonacci at ofset 75, returned the sequence 2111485077978050.
IN MAIN: Thread 0 has ended.
reading from /dev/fibonacci at ofset 76, returned the sequence 3416454622906707.
reading from /dev/fibonacci at ofset 77, returned the sequence 5527939700884757.
reading from /dev/fibonacci at ofset 78, returned the sequence 8944394323791464.
reading from /dev/fibonacci at ofset 79, returned the sequence 14472334024676221.
reading from /dev/fibonacci at ofset 80, returned the sequence 23416728348467685.
reading from /dev/fibonacci at ofset 81, returned the sequence 37889062373143906.
reading from /dev/fibonacci at ofset 82, returned the sequence 61305790721611591.
reading from /dev/fibonacci at ofset 83, returned the sequence 99194853094755497.
reading from /dev/fibonacci at ofset 84, returned the sequence 160500643816367088.
reading from /dev/fibonacci at ofset 85, returned the sequence 259695496911122585.
reading from /dev/fibonacci at ofset 86, returned the sequence 420196140727489673.
reading from /dev/fibonacci at ofset 87, returned the sequence 679891637638612258.
reading from /dev/fibonacci at ofset 88, returned the sequence 1100087778366101931.
reading from /dev/fibonacci at ofset 89, returned the sequence 1779979416004714189.
reading from /dev/fibonacci at ofset 90, returned the sequence 2880067194370816120.
reading from /dev/fibonacci at ofset 91, returned the sequence 4660046610375530309.
reading from /dev/fibonacci at ofset 92, returned the sequence 7540113804746346429.
IN MAIN: Thread 1 has ended.
MAIN program has ended.
```
我們可以在有 `mutex` 和 `without_mutex` 的實驗裡發現，一旦沒有 `mutex` 的控制，在寫入檔案時會發生 race condition ， 寫入順序會變成亂序，
## 自我檢查清單
- [x] 研讀上述 Linux 效能分析的提示 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 → 從中也該理解為何不希望在虛擬機器中進行實驗;
- [x] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
- [ ] 複習 C 語言 [數值系統](https://hackmd.io/@sysprog/c-numerics) 和 [bitwise operation](https://hackmd.io/@sysprog/c-bitwise)，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
- [ ] 學習指出針對大數運算的加速運算和縮減記憶體操作成本的舉措，紀錄你的認知和疑惑
- [x] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 的程式碼來確認。 → 搭配閱讀〈[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)〉
Sign in with Wallet
Connect another wallet