# 2020q2 Homework3 (fibdrv)
contributed by < `eecheng87` >
###### tags: `linux2020`
## 修改 Fibonacci 演算法
原本提供的版本是最直覺的演算法，複雜度為 $O(N)$
```cpp
unsigned long long easy_fib(int n)
{
unsigned long long series[92];
series[0] = 0;
series[1] = 1;
for (int i = 2; i < n + 1; i++) {
series[i] = series[i - 1] + series[i - 2];
}
return series[n];
}
```
接著尋找更快的演算法，藉由作業説明的提示，開始著手以 Fast Doubling 手法實做 fibonacci 。
由作業說明提供的公式和 pesudo code 實做
$$
\begin{align}
&F(2n) = 2F(n)\times F(n+1) - F(n)^2 \\
&F(2n+1) = F(n)^2 + F(n+1)^2
\end{align}
$$
```cpp
unsigned long long double_fib(int n)
{
unsigned long long a = 0, b = 1, t1, t2;
for (int i = 31; i >= 0; i--) {
t1 = a * (b * 2 - a);
t2 = b * b + a * a;
a = t1;
b = t2;
if ((n & (1 << i)) > 0) {
t1 = a + b;
a = b;
b = t1;
}
}
return a;
}
```
這個演算法理論上複雜度 $O(log{N})$，但時實際的速度卻不如預期，在 n 很小的時候速度會比原版本的還慢很多。原因不外乎就是 Fast doubling 每次都會從位元最高位開始找，在本範例即 bit 31 開始。改善的想法很簡單，我們要避免在 n 很小的時候，迴圈計數引數 `i` 仍從 31 開始。 `clz` 函數就是我們要找的，它能算出左起第一個 1 之前 0 的個數，接著再用 `31` 減掉該數字就能知道要從哪個 bit 開始做 fast doubling。
```cpp
int i = clz ? 31 - __builtin_clz(n) : 31;
```
新增的部份是先判斷是否採用 `clz` 來優化原本的演算法，從而給定不同的起始位元數 `i`。
既然函式已做好，那麼馬上開始檢驗不同 n 值的對應的運算時間分佈
```cpp
for (int i = 2; i < 93; i++) {
clock_gettime(CLOCK_REALTIME, &t1);
(void) easy_fib(i);
clock_gettime(CLOCK_REALTIME, &t2);
printf("%d ", i);
printf("%ld ", elapse(t1, t2));
clock_gettime(CLOCK_REALTIME, &t1);
(void) double_fib(i, false);
clock_gettime(CLOCK_REALTIME, &t2);
printf("%ld ", elapse(t1, t2));
clock_gettime(CLOCK_REALTIME, &t1);
(void) double_fib(i, true);
clock_gettime(CLOCK_REALTIME, &t2);
printf("%ld\n", elapse(t1, t2));
}
```
透過 gnuplot 製圖:
觀察：最初版本模擬出來的確符合 $O(N)$ 的複雜度，此外尚未優化的 fast doubling 在 n 太小時 (從圖中看大概是 70 以前) 效率是會比上一個版本還慢的。不過若添加 `clz` 提前檢查的話，可以得到很好的效率。
[實驗程式碼](https://github.com/eecheng87/fibdrv/tree/master/experiment)
:::warning
TODO: 參照 [A Fairly Fast Fibonacci Function](http://www.oranlooney.com/post/fibonacci/)，我們可透過 vector 一類的資料結構 (這也是 quiz4 命題的考量) 充當 cache，只要空間控制得當 (太小沒效果，太大反而會變慢)，可達到加速。參考的 JavaScript 實作:
```javascript
var fib = (function(cache){
return cache = cache || {}, function(n){
if (cache[n]) return cache[n];
else return cache[n] = n == 0 ? 0 : n < 0 ? -fib(-n)
: n <= 2 ? 1 : fib(n-2) + fib(n-1);
};
})();
```
:notes: jserv
:::
## 增加 fibonacci 計算範圍
原本透過 `sudo ./client` 可以觀察到輸出到 92 後開始怪怪的，但還是維持正數 ( 這是 `MAX_LENGTH` 設定在 92 下起的保護作用 )。若把值設大就可以明顯觀察到 overflow 的發生。
```
Reading from /dev/fibonacci at offset 92, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 93, returned the sequence -6246583658587674878.
Reading from /dev/fibonacci at offset 94, returned the sequence 1293530146158671551.
Reading from /dev/fibonacci at offset 95, returned the sequence -4953053512429003327.
```
### 檢查機制
當我們什麼都還沒做，直接對剛 fork 下來的專案執行 `make check` ，如同預期出現綠色 pass 字樣，另外也有指出第 92 項錯誤。先來檢查 `Makefile` 裡面的 `check` 到底做了什麼
```shell
check: all
$(MAKE) unload
$(MAKE) load
sudo ./client > out
$(MAKE) unload
@diff -u out scripts/expected.txt && $(call pass)
@scripts/verify.py
```
首先為了避免已經掛載其他模組，所以得先 `unload`，其實對應的就是 `rmmod` 指令。再來把模組裝上 (`insmod`)。接著執行 `client.c`，但是把輸出導向 `out`，效果類似寫檔案。
接著的下一行就是比較透過 `fibdrv.c` 得到的費氏數列和預期答案 ( expected.txt ) 是否相同。事實上我認為沒有加這行的必要，第一個原因是 `expected.txt` 裡面的答案是錯的，超過 92 項以後都是一樣的數字。所以用這個檔案無法來檢查正確性。第二個原因是，其實下一行的 `verify.py` 就是在幫我們檢查 driver 的正確性。
把 `verify.py` 拿出來看看裡面在做什麼
```python
for i in range(2, 101):
expect.append(expect[i - 1] + expect[i - 2])
```
`python` 有一個非常棒的特性是整數並沒有上限，完全不用考慮 overflow 的問題。所以可以很輕鬆的直接把 101 項以前的答案紀錄在 `expect` 中。
```python
with open('out', 'r') as f:
tmp = f.readline()
while (tmp):
result.append(tmp)
tmp = f.readline()
f.close()
for r in result:
if (r.find('Reading') != -1):
..
```
接著把透過我們實做的 `fib_sequence` 得到的數列存到 `dics` 中 ( 當然要用 `split` 對字串做處理，才能只拿到數字 )。
```python
for i in dics:
fib = i[1]
if (expect[i[0]] != fib):
..
```
最後一個步驟就是檢查 `expect` ( 正確答案 ) 和 `dics` 中的數列是否吻合，只要一有不一樣的，就馬上輸出預期的答案和離開 `verify.py`。
### 增加運算範圍
原本作業說明提供的方法是透過 `struct bigN` 來存共 128 位元的資料。但是這個方法其實比較麻煩 (跨高低位的乘法需要考慮的事情很多，同時也會再次面對空間不夠的問題)，且擴充性不好 (需要更多位呢? 總不能一直增加 struct 的成員吧)。於是我選擇用字元來表示數字，並且做出字元運算。
事實上，M H Rasel 已實做 [Big integer](http://billor.chsh.chc.edu.tw/IT/C/BigInteger.htm)，我就直接拿來用。以下簡單摘要幾個 operation 如何實做。
首先定義一個新的型態作為運算的物件，當然若只是要用來 fast doubling 其實可以拿掉 `signbit`。因為是在負數減法才需要用到的 bit。
```cpp
typedef struct {
char digits[MAXDIGITS]; /* represent the number */
int signbit; /* 1 if positive, -1 if negative */
int lastdigit; /* index of high-order digit */
} bignum;
```
<br>
以下是加法的實做：
```cpp
int add_bignum(bignum *a, bignum *b, bignum *c)
{
..
if (a->lastdigit < b->lastdigit)
return add_bignum(b, a, c);
int k = c->lastdigit = a->lastdigit + 1;
c->digits[k--] = '\0';
carry = 0;
n_carry = 0;
for (i = b->lastdigit - 1, j = a->lastdigit - 1; i >= 0; i--, j--) {
carry = b->digits[i] - '0' + a->digits[j] - '0' + carry;
c->digits[k--] = (carry % 10) + '0';
carry = carry / 10;
if (carry)
n_carry++;
}
for (; j >= 0; j--) {
carry = a->digits[j] - '0' + carry;
c->digits[k--] = (carry % 10) + '0';
carry = carry / 10;
if (carry)
n_carry++;
}
if (carry)
c->digits[k] = carry + '0';
else {
char string[MAXDIGITS];
strlcpy(string, &c->digits[1], MAXDIGITS);
strlcpy(c->digits, string, MAXDIGITS);
c->lastdigit = c->lastdigit - k - 1;
}
return n_carry;
}
```
省略的部份是判斷是否遇到加負數的情況。若是，則呼叫成 subtract 的形式。接著加法是選定大者為被除數，兩者從尾端開始加。最後判斷是否進位，若進位則需要把 `c->digit[k]` 補上應有的數字。反之，則把結果往前移，填滿預留的空格。
<br>
以下是減法的實做：
```cpp
int subtract_bignum(bignum *a, bignum *b, bignum *c)
{
..
int k = c->lastdigit = MAX(a->lastdigit, b->lastdigit);
n_borrow = 0;
c->digits[k--] = '\0';
for (i = a->lastdigit - 1, j = b->lastdigit - 1; j >= 0; i--, j--) {
temp = a->digits[i] - '0' - (b->digits[j] - '0' + op);
if (temp < 0) {
temp += 10;
op = 1;
n_borrow++;
} else
op = 0;
c->digits[k--] = temp + '0';
}
while (op) {
temp = a->digits[i--] - op - '0';
if (temp < 0) {
temp += 10;
op = 1;
n_borrow++;
} else
op = 0;
c->digits[k--] = temp + '0';
}
for (; i >= 0; i--)
c->digits[k--] = a->digits[i];
for (i = 0; !(c->digits[i] - '0'); i++)
;
c->lastdigit = c->lastdigit - i;
..
}
```
同樣省略前面在判斷**非**正數減正數的情況。首先第一個迴圈負責相減，直到減數最高位被減完，接著只要把被減數多出的位數補上即可。
以下是乘法的實做：
```cpp
void multiply_bignum(bignum *a, bignum *b, bignum *c)
{
register long int i, j, k = 0;
short int num1[MAXDIGITS], num2[MAXDIGITS], of = 0, res[MAXDIGITS] = {0};
for (i = 0, j = a->lastdigit - 1; i < a->lastdigit; i++, j--)
num1[i] = a->digits[j] - 48;
for (i = 0, j = b->lastdigit - 1; i < b->lastdigit; j--, i++)
num2[i] = b->digits[j] - 48;
res[0] = 0;
for (j = 0; j < b->lastdigit; j++) {
for (i = 0, k = j; i < a->lastdigit || of; k++, i++) {
if (i < a->lastdigit)
res[k] += num1[i] * num2[j] + of;
else
res[k] += of;
of = res[k] / 10;
res[k] = res[k] % 10;
}
}
for (i = k - 1, j = 0; i >= 0; i--, j++)
c->digits[j] = res[i] + 48;
c->digits[j] = '\0';
c->lastdigit = k;
c->signbit = a->signbit * b->signbit;
}
```
相較字元相加減，字元並沒有提供**乘法**，所以不得已得先把數字擷取出來，分別存放到 `num1`和`num2`。接著迭代這兩個陣列把乘法結果放到 `res`，最後在填到 `c` 的 `digit` 中。
以上，fast doubling 所需要的運算都已經完成了，接著馬上開始建構 fast doubling。事實上，我們已經在第一個步驟中實做 fast doubling，儘管是用 `int` 的運算來做，但是我們只要把運算元換成對應的字元運算函數，也能達到一樣的效果。
```cpp
bignum a, b;
bignum big_two;
int_to_bignum(0, &a);
int_to_bignum(1, &b);
int_to_bignum(2, &big_two);
for (int i = 31 - __builtin_clz(k); i >= 0; i--) {
bignum t1, t2;
bignum tmp1, tmp2;
multiply_bignum(&b, &big_two, &tmp1);
(void) subtract_bignum(&tmp1, &a, &tmp2);
multiply_bignum(&a, &tmp2, &t1);
multiply_bignum(&a, &a, &tmp1);
multiply_bignum(&b, &b, &tmp2);
(void) add_bignum(&tmp1, &tmp2, &t2);
copy(&a, &t1);
copy(&b, &t2);
if ((k & (1 << i)) > 0) {
(void) add_bignum(&a, &b, &t1);
copy(&a, &b);
copy(&b, &t1);
}
}
return a;
```
可對照 `double_fib` 的 [pesudo code](https://hackmd.io/1UeUSEGCQOKQ1thdlKVd7A?both#%E4%BF%AE%E6%94%B9-fibonacci-%E6%BC%94%E7%AE%97%E6%B3%95) 不難發現兩者根本一樣。
:::warning
上述實作的問題在於，從十進位運算去思考，就會忽略尚可改善效能之處，運算過程如果全是二進位，就可運用 bitwise 去改善，最終再考慮到轉回十進位即可。參照 [bignum](https://github.com/sysprog21/bignum)
:notes: jserv
:::
### client 端如何取得結果
原本的實做是直接在 `fib_read` 中直接回傳 `fib_sequence` ，這是剛好回傳的東西是可以轉形成 `ssize_t` 所以才能這樣寫。但是如今我們使用了自己的型態 `bignum` ，所以無法直接強行轉型成 `ssize_t`。
```cpp
char kbuf[MAXDIGITS] = {0};
bignum res = fib_sequence(*offset);
snprintf(kbuf, MAXDIGITS, "%s", res.digits);
copy_to_user(buf, kbuf, MAXDIGITS);
return 0;
```
不過我們發現 `fib_read` 有傳一個 `buf` 進來，所以我們可以透過這個參數，從 user 端取得答案。這裡需要注意的是在 kernel 與 user space 間無法隨心所欲的交換資料，所以我們要透過 [copy_to_user](https://www.fsl.cs.sunysb.edu/kernel-api/re256.html) 來完成。
### 測試結果
```
Reading from /dev/fibonacci at offset 92, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 93, returned the sequence 12200160415121876738.
Reading from /dev/fibonacci at offset 94, returned the sequence 19740274219868223167.
Reading from /dev/fibonacci at offset 95, returned the sequence 31940434634990099905.
Reading from /dev/fibonacci at offset 96, returned the sequence 51680708854858323072.
Reading from /dev/fibonacci at offset 97, returned the sequence 83621143489848422977.
Reading from /dev/fibonacci at offset 98, returned the sequence 135301852344706746049.
Reading from /dev/fibonacci at offset 99, returned the sequence 218922995834555169026.
Reading from /dev/fibonacci at offset 100, returned the sequence 354224848179261915075.
```
可查閱[預期答案](http://www.protocol5.com/Fibonacci)對照，發現正確。
## 測量 user space 和 kernel space 的傳遞時間
利用前面完成的 `fib_sequence`(增加計算範圍+ fast doubling)。在 kernel 中稍微修改程式，這次 read 的回傳值改成回傳 `fib_sequence` 的運算時間 ( 在 kernel space )，同時我們也計算在 user space 呼叫 `read` 前後的時間差距，因而得到在 kernel 運算的時間和在 user space 運算的時間。接著，把兩者相減得到傳遞時間 ( user -> kernel + kernel -> user )。
kernel
```cpp
static ssize_t fib_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
ktime_t k1, k2;
k1 = ktime_get();
bignum res = fib_sequence(*offset);
k2 = ktime_sub(ktime_get(), k1);
return (long long)ktime_to_ns(k2);
}
```
client
```cpp
for (int i = 0; i <= offset; i++) {
lseek(fd, i, SEEK_SET);
clock_gettime(CLOCK_REALTIME, &t1);
sz = read(fd, buf, MAXDIGITS);
clock_gettime(CLOCK_REALTIME, &t2);
printf("%d ",i);
// this is transporting time between kernel and user space
printf("%lld ",elapse(t1,t2) - sz);
// this is executing time in user space
printf("%ld ", elapse(t1, t2));
// this is executing time in kernel
printf("%lld \n",sz);
}
```
接著用 gnuplot 畫圖
傳遞的時間不會因為 n 的大小而改變
## 自我檢查清單
### 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
已於第一部份- 修改 fibonacci 演算法 - 中討論。
### 複習 C 語言 數值系統 和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
### lsmod 的輸出結果有一欄名為 Used by，這是 “each module’s use count and a list of referring modules”，但如何實作出來呢？模組間的相依性和實際使用次數 (reference counting) 在 Linux 核心如何追蹤呢？
[lsmod](https://man.linuxde.net/lsmod) 可以列出目前系統中的模組有哪些，而下 lsmod 這個命令時就是在執行一支程式。比起找出 lsmod 的原始馬來研究它到底如何辦到追蹤模組的引用狀況，我發現一個更好的工具 [strace](https://medium.com/fcamels-notes/%E4%BD%BF%E7%94%A8-strace-%E4%BA%86%E8%A7%A3%E7%A8%8B%E5%BC%8F%E8%AE%80%E5%8F%96%E8%B3%87%E6%96%99%E7%9A%84%E4%BE%86%E6%BA%90-aaa17ee2df2b)，它能夠逐行印出呼叫的 system call。如此一來，我們更能知道程式是透過什麼手段拿到資料。
```shell
$ strace lsmod
```
會得到一堆輸出，擷取重點：
```shell
write(1, "Module Size Us"..., 38Module Size Used by
) = 38
openat(AT_FDCWD, "/sys/module/fibdrv/refcnt", O_RDONLY|O_CLOEXEC) = 3
read(3, "0\n", 31) = 2
read(3, "", 29) = 0
close(3) = 0
```
看起來 lsmod 會到 `sys/module` 底下去拿資料，而 used by 這格欄位的值，看來和檔案 `refcnt` 相當有關係。接著直接找出這個檔案，觀察裡面是什麼。
```shell
$ cat refcnt
0
```
沒錯，得到的是一個數字，而這個數字剛好是 used by 的次數。
接著我們思考的是，什麼時候會讓 `refcnt` 的值變動？應該是 load 和 unload 時，所以開始找相對應的呼叫。
首先，我們要找尋的目標是紀錄 reference counting 的變數，根據 [module.c](https://github.com/torvalds/linux/blob/cc12071ff39060fc2e47c58b43e249fe0d0061ee/kernel/module.c) 中許多模組的初始化或刪除，都牽涉到一個 struct mod 型態的變數。於是我們開始找起這個變數的定義：
[/linux/module.h](https://github.com/torvalds/linux/blob/14cd0bd04907df79b36a31e55f18768172230987/include/linux/module.h)
```cpp=360
struct module {
enum module_state state;
/* Member of list of modules */
struct list_head list;
...
```
我們在 module.h 底下找到 module 的定義，接著往下繼續找，在 510 行找到了 `refcnt`。
```cpp=510
/* Destruction function. */
void (*exit)(void);
atomic_t refcnt;
#endif
```
再透過這個線索，找到 [module.c](https://github.com/torvalds/linux/blob/master/kernel/module.c) 底下的 system call: delete_module ，發現它會呼叫 try_stop_module
```cpp=1019
/* Stop the machine so refcounts can't move and disable module. */
ret = try_stop_module(mod, flags, &forced);
if (ret != 0)
goto out;
```
加上註解的提示，這個函數肯定和 `refcnt` 的維護有關。於是繼續往下找，發現 try_stop_module 會再呼叫 try_release_module_ref
```cpp
/* Try to release refcount of module, 0 means success. */
static int try_release_module_ref(struct module *mod)
{
int ret;
/* Try to decrement refcnt which we set at loading */
ret = atomic_sub_return(MODULE_REF_BASE, &mod->refcnt);
BUG_ON(ret < 0);
if (ret)
/* Someone can put this right now, recover with checking */
ret = atomic_add_unless(&mod->refcnt, MODULE_REF_BASE, 0);
return ret;
}
```
我們找到 try_release_module_ref 後，馬上發現裡面的 `atomic_sub_return(MODULE_REF_BASE, &mod->refcnt);` 就是我們在找的目標，它正在維護 `refcnt`。當 unload 時代表少一個人用，所以要減一。
:::warning
TODO: 從 module 間的相依性去考慮 reference count 的作用，不要只看 load/unload
:notes: jserv
:::
### 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題
mutex_lock 是為了保證 critical section 所需要用的手段，顧名思義，在 lock 間的程式碼即 critical section ，在此區段永遠只有一個人能進來。若你像我只用過 pthread 的話，那 mutex_trylock, mutex_unlock 對應的就是 pthread_mutex_lock 和 pthread_mutex_unlock。
那什麼情境下需要 lock？以下附上一個我曾經寫過的片段程式碼：
```cpp
pthread_mutex_lock(&mutex);
if(head!=NULL)
{
// (A)
// queue is not empty
queue *tmpq = head;
strcpy(query_str,tmpq->element);
send_fd = tmpq->fd;
head = head->next;
free(tmpq);
*(thread_state+offset) = 1;
}
pthread_mutex_unlock(&mutex);
```
以上功能是要把 list 的頭刪掉，若今天沒有鎖起來，同時有兩條 thread 進 if statement，倘若不幸的是 list 只剩一個 node，那麼這樣程式就會錯掉。
簡單寫一個 client 端程式，目的讓多執行緒同時 read 檔案（記得要把 `exit` 註解掉，否則無法觀察）
```cpp
void *task(void* in){
long long sz;
// u128_t sz;
char buf[MAXDIGITS];
char write_buf[] = "testing writing";
int offset = 100; /* TODO: try test something bigger than the limit */
int fd = open(FIB_DEV, O_RDWR);
if (fd < 0) {
perror("Failed to open character device");
// exit(1);
}
for (int i = 0; i <= offset; i++) {
lseek(fd, i, SEEK_SET);
sz = read(fd, buf, MAXDIGITS);
printf("Reading from " FIB_DEV
" at offset %d, returned the sequence "
"%s.\n",
i, buf);
}
}
int main(){
pthread_t t[5];
for(int i = 0; i < 5; i++)
pthread_create(&t[i], NULL, task, NULL);
for(int i = 0; i < 5; i++)
pthread_join(t[i], NULL);
return 0;
}
```
在 `fibdrv.c` 中要改的是：
```cpp
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;
}
```
比較註解掉和沒註解掉的差異（ 保留註解表示有上鎖 )
Ps: Makefile 也要修改
```=27
client: client.c
$(CC) -o $@ $^ -lpthread
```
以下是有上鎖的輸出：
```
Failed to open character device: Device or resource busy
Reading from /dev/fibonacci at offset 0, returned the sequence 0.
Failed to open character device: Device or resource busy
Failed to open character device: Device or resource busy
Reading from /dev/fibonacci at offset 1, returned the sequence 1.
Reading from /dev/fibonacci at offset 0, returned the sequence .
Reading from /dev/fibonacci at offset 1, returned the sequence .
Failed to open character device: Device or resource busy
Reading from /dev/fibonacci at offset 2, returned the sequence .
..
Reading from /dev/fibonacci at offset 10, returned the sequence 55.
Reading from /dev/fibonacci at offset 11, returned the sequence 89.
Reading from /dev/fibonacci at offset 12, returned the sequence 144.
Reading from /dev/fibonacci at offset 13, returned the sequence 233.
```
以下是沒上鎖的輸出：
```
Reading from /dev/fibonacci at offset 99, returned the sequence 218922995834555169026.
Reading from /dev/fibonacci at offset 75, returned the sequence 2111485077978050.
Reading from /dev/fibonacci at offset 100, returned the sequence 354224848179261915075.
Reading from /dev/fibonacci at offset 76, returned the sequence 3416454622906707.
Reading from /dev/fibonacci at offset 77, returned the sequence 5527939700884757.
Reading from /dev/fibonacci at offset 78, returned the sequence 8944394323791464.
Reading from /dev/fibonacci at offset 79, returned the sequence 14472334024676221.
Reading from /dev/fibonacci at offset 80, returned the sequence 23416728348467685.
Reading from /dev/fibonacci at offset 81, returned the sequence 37889062373143906.
Reading from /dev/fibonacci at offset 82, returned the sequence 61305790721611591.
Reading from /dev/fibonacci at offset 83, returned the sequence 99194853094755497.
Reading from /dev/fibonacci at offset 84, returned the sequence 160500643816367088.
Reading from /dev/fibonacci at offset 85, returned the sequence 259695496911122585.
Reading from /dev/fibonacci at offset 86, returned the sequence 420196140727489673.
Reading from /dev/fibonacci at offset 87, returned the sequence 679891637638612258.
Reading from /dev/fibonacci at offset 88, returned the sequence 1100087778366101931.
Reading from /dev/fibonacci at offset 89, returned the sequence 1779979416004714189.
Reading from /dev/fibonacci at offset 90, returned the sequence 2880067194370816120.
Reading from /dev/fibonacci at offset 91, returned the sequence 4660046610375530309.
Reading from /dev/fibonacci at offset 92, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 93, returned the sequence 12200160415121876738.
Reading from /dev/fibonacci at offset 94, returned the sequence 19740274219868223167.
Reading from /dev/fibonacci at offset 95, returned the sequence 31940434634990099905.
Reading from /dev/fibonacci at offset 96, returned the sequence 51680708854858323072.
Reading from /dev/fibonacci at offset 97, returned the sequence 83621143489848422977.
Reading from /dev/fibonacci at offset 98, returned the sequence 135301852344706746049.
Reading from /dev/fibonacci at offset 99, returned the sequence 218922995834555169026.
Reading from /dev/fibonacci at offset 100, returned the sequence 354224848179261915075.
```
令人訝異的是，反而沒上鎖的表現在某些地方竟然比較好。可以觀察到**上鎖版本**的輸出會因為有上鎖，所以不讓你讀，自然沒辦法算費氏數列，因此看到 `Reading from /dev/fibonacci at offset 1, returned the sequence .` 的輸出。反之，**沒上鎖版本**仍允許同時多個執行緒去開檔案，因此每條 thread 都能算出數字出來。此外也可以觀察到有上鎖版本輸出的次序有由小到大，反之則沒有。
但是話說回來，為什麼沒上鎖也能算出正確的值。我想是因為開檔案**讀**而非**寫**，並不會造成競爭或互斥等現象，所以多個人同時讀也不會造成程式錯誤。
:::warning
由此也不難發現，lock 也該依據適用場域去調整，例如 [Readers–writer lock](https://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock) 針對單一寫入者、多個讀取者的情境去特化同步處理機制。
:notes: jserv
:::
## Reference
* [VFS](http://sp1.wikidot.com/linuxvfs)
* [bigN](https://stackoverflow.com/questions/25095741/how-can-i-multiply-64-bit-operands-and-get-128-bit-result-portably)
Sign in with Wallet
Connect another wallet