# 2018q1 Homework 3 ( List )
contributed by <`mrwenwei`>
* [作業說明](https://hackmd.io/s/HkxZbJzif)
---

## 生日悖論
* 如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式

在一間有 23 人的房間內，就會有超過 50% 的機率有兩人以上同一天生日，這是著名的生日悖論，若把2/29生日的人考慮進去(閏年)，其最直觀的機率算法為 $1-全部人都不同生日機率$：

$~~~~\begin{split}1-\dfrac{366}{366}·\dfrac{365}{366}·\dfrac{364}{366}·⋯·\dfrac{344}{366}&=1-0.49367698818054007\\&=0.5063230118194599\end{split}$

然而我們可以用一些數學方法來近似。
當 $x$ 趨近於 $0$ 時：

$~~~~e^x \approx1+x$

因此：

$~~~~e^{\dfrac{-n}{366}} \approx1-\dfrac{n}{366}$

令全部人都不同生日的機率為

$\begin{split}~~~~P(x)&=\dfrac{366}{366}·\dfrac{365}{366}·\dfrac{364}{366}·⋯·\dfrac{-(x-1)}{366}\\\\&\approx 1·e^\dfrac{-1}{366}·e^\dfrac{-2}{366}·⋯·e^\dfrac{-(x-1)}{366}=e^\dfrac{-x^2+x}{732}\\\\&\approx e^\dfrac{-x^2}{732}\end{split}$

$\begin{split}~~~~1-P(x)\end{split}$即為近似解

$~~~~1-P(23)=0.5145493264194203$

* [Birthday problem](https://en.wikipedia.org/wiki/Birthday_problem) 對資訊安全的影響在哪些層面？
[Birthday_attack](https://en.wikipedia.org/wiki/Birthday_attack) 的 由來命名來源是生日悖論，可以想像一個 9x9 的箱子可以隨機投入 k 顆球，其中有兩顆以上的格子的機率就如同生日問題一樣，實際上是個想像中反常的高的機率，而這樣的形式正好也如同 hash function 的 collision，也就是兩個不同 input 卻出現相同的 output 的機率，以 64-bits 的 hash 來舉例，總共有 $2^{64}~~(約1.8 × 10^{19})$ 種可能存在，我們可以利用上一題算出來的近似公式反推，當機率為 50% 可以產生碰撞的情況只需要 input 約 $5.1 × 10^9$ 次，而當 input $7.2 × 10^9$ 次時碰撞的機率高達 75% ，因此當兩方在傳遞訊息時是非常有機會受到第三方解密的，故如 [MD5](https://en.wikipedia.org/wiki/MD5) 此類的 hash function 演算法已經被證實無法防止碰撞。

* 像是 [Random Number Generator](http://stattrek.com/statistics/random-number-generator.aspx) 這樣的產生器，是否能產生「夠亂」的亂數呢？

我想符合[機率分佈](https://en.wikipedia.org/wiki/Probability_distribution)的就可說是亂數，以連結的亂數產生器為例，裡面有個選項是 Seed ，大一 C 語言就學過程式內若加入 ```Srand(time(NULL))``` 就可以防止亂數的重複，原因是亂數的演算法是先經過一個初始化用的 Seed ，他可能是數字或向量，在依循這個數字將後續的亂數計算出來，所以除了初始種子值之外其他是數值可以算是亂的，畢竟他也符合機率分佈，只不過每次產生的結果都相同就是了。而 [Random seed](https://en.wikipedia.org/wiki/Random_seed) 是 [Pseudorandom number generator](https://en.wikipedia.org/wiki/Pseudorandom_number_generator) 所使用的，簡言就是連種子都是 random 的就不會有結果都相同的情況發生了，不過重點是上述能夠說是「夠亂」嗎？由於每個數字都可以由 input 計算出將來會出現怎樣的 output ，因此這樣只能說是非常接近「亂數」，這項技術也使用在許多工程方面，像是 [GPS](https://en.wikipedia.org/wiki/Global_Positioning_System) 的衛星及接收者之間的同步序列。所以以演算法的方式似乎無法創造出真正夠亂的亂數，需要硬體的介入，[hardware random number generator](https://en.wikipedia.org/wiki/Hardware_random_number_generator) 透過一些物理方法產生亂數，像是放大器、換能器的訊號加入參考，可以模擬成現實生活中擲骰子這樣的隨機。

---

## Linux 風格的 linked list

* 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？

首先必須先回顧一下大一學過的 [Preprocessor](https://en.wikipedia.org/wiki/Preprocessor)，必須承認自己以前蠻不認真的，實在不是很有印象，因此把以前的C語言聖經拿出來啃了一下。 
像是'#include'、'define'有使用 '#' 的都稱為 preprocessor，而其用途是在 compiler 編譯前就將事先定義好的內容（可以是變數、條件式等等），轉為字串或是算式放置於檔案中，macro 即是期中一種用法，並不會存在於堆疊中，因此不需要有 push 或 pop 的時間，較為快速，但如果呼叫太多次會耗費記憶體空間。而 function call 則是相反，會一層層存在 stack 中，故較耗費時間，但較無記憶體問題，且程式易於管理。

* Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量

1. [linux/sched.h](https://github.com/torvalds/linux/blob/master/include/linux/sched.h) 內的 sched_rt_entity

    struct sched_rt_entity {
	struct list_head		run_list;
	unsigned long			timeout;
	unsigned long			watchdog_stamp;
	unsigned int			time_slice;
	unsigned short			on_rq;
	unsigned short			on_list;

	struct sched_rt_entity		*back;
    #ifdef CONFIG_RT_GROUP_SCHED
	struct sched_rt_entity		*parent;
	/* rq on which this entity is (to be) queued: */
	struct rt_rq			*rt_rq;
	/* rq "owned" by this entity/group: */
	struct rt_rq			*my_q;
    #endif
    } __randomize_layout;
    

Linux process 的排程採用 [CFS group scheduling](https://lwn.net/Articles/240474/)，主要概念是希望所有行程都可以公平對待，透過將 per-process scheduling information 封裝在 sched_entity structure 裡，因此這裡使用到 linked list 的結構來串連每個 process 的資訊，並且使用紅黑樹作為資料結構。
其中 rt_rq 是這個結構運行的 queue，my_q 為其兒子運行之 queue。

* GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？

typeof 建立一個型態的變數，並且可用來比對。用法如下：

    typeof(a) b;     //建立一個 a 型態的變數 b

typeof 提供了一個方便就可達到如C++的模板概念，如下程式碼：

    /*
     * swap - swap value of @a and @b
     */
    #define swap(a, b) \
        do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0)

參考：[typeof 在 kernel中的使用](http://deltamaster.is-programmer.com/posts/37253.html)

* 解釋以下巨集的原理

    #define container_of(ptr, type, member)                            \
        __extension__({                                                \
            const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
            (type *) ((char *) __pmember - offsetof(type, member));    \
        })

* 宣告一個 type 型別的指標指向 member，再利用此型別建立一個 __pmember 的指標指向 member 的位置。
* 最後將 __pmember 的位置減去一 struct 的 offset 得到其起始位置。

* 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？