# 2020q3 期末作業 (quiz12)
contributed by < `chi-ming5566` >
> [測驗題](https://hackmd.io/@sysprog/2020-quiz12)
---
### `測驗一`
以下關於記憶體管理的描述，選出其中唯一正確的描述
* `(a)` 在一個 buddy system 中，最高可達 50% 的空間可因內部碎片化 (fragmentation) 而被浪費
* `(b)` 平均來說，first-fit 演算法會比 best-fit 演算法來得慢
* `(c)` 僅在 free list 依據記憶體地址遞增排序時，使用邊界標記來回收 (reclaim) 才會快速
* `(d)` buddy system 只會有內部碎片，不會有外部碎片
`(a)` `(d)`與其他技術相比(如動態分配)，buddy system 幾乎沒有外部碎片(但並非完全沒有)，而且可以以較低的開銷來壓縮記憶體。buddy system 釋放記憶體的速度很快，而所需的最大壓縮次數為log2。
但 buddy system 仍然存在內部碎片的問題，因為對記憶體的需求比 small block 大一些，但卻比 large block 小很多。
由於 buddy system 的工作方式，如果請求 66k 的容量，則記憶體會分配 128K ，那就會有 62k 被浪費。不過這個問題可以透過 slab allocation 來解決，其可以提供更細節的分配。
`(b)` 在連續記憶體分配，有三個最常見的演算法， first-fit 、 best-fit 和 worst-fit。
* worst-fit：記憶體分配會優先使用最大的分區塊，這樣所剩餘下來的區塊會比較大，也比較有機會提供其他空間需求使用，缺點是記憶體空間使用率較差。
* best-fit：記憶體分配會使用與需求最接近的區塊，這樣使用分配後，所剩餘下來的各可分配記憶體區塊會最小，在記憶體的空間使用率較佳，缺點是所剩餘下來的區塊會比較零碎，而不足讓其他記憶體需求使用。
* first-fit：記憶體分配足夠大就使用，優點是簡單、分配速度快速，記憶體使用率也不算太差。
`(c)` free list 是一種用來實現特定動態記憶體分配方案的資料結構。free list 的核心原理是將若干未分配的記憶體塊用link list連接起來，將未分配區域的第一個字作為指向下一個未分配區域的指標使用。
用 free list 實現記憶體的分配和回收非常簡單：回收記憶體時只需將記憶體塊鏈入 free list ；分配時也只需從 free list 的一端取下即可直接使用。如果記憶體塊的大小不一，則分配前還需要在自由表中搜尋足夠大的記憶體塊，可能有一定的額外消耗。
因為 free list 使用了 link list 結構，所以也繼承了它的劣勢：存取局部性低下，難以利用快取。
所以正確選項為 `(a)`
---
### `測驗二`
以下關於記憶體管理的描述，選出其中唯一正確的描述
* `(a)` 在按照 block size 遞減排序的 free list 中，使用 first-fit 演算法會導致配置的效能低落，但可避免外部碎片
* `(b)` 對於 best-fit 演算法，free list 應該按照記憶體地址的遞減順序來排序
* `(c)` best-fit 會選擇與請求記憶體區段匹配的最大 free list
* `(d)` 安照 block size 遞增排序的 free list 上，使用 first-fit 和 best-fit 演算法等價
`(a)` 在 free list 中使用 first-fit 演算法並不會導致效能低落，其優點是速度快，但缺點是可能把較大塊拆分成較小的塊，導致後來對大塊的申請難以滿足。
`(b)` 對於 best-fit 演算法，會要求節點從小到大排列，而不是從大到小。之後找到第一個大於等於所需空間的節點即分配。
`(c)` best-fit 並不是會選擇與請求記憶體區段匹配的最大 free list ，而是會請求分配記憶體區段大小範圍較廣的 free list 。
所以正確答案為 `(d)`
---
### `測驗三`
考慮以下是利用 Linux epoll 系統呼叫開發的網頁伺服器，預期應該持續接受客戶端的連線 (port 55688) 並提供靜態內容。
```cpp
#include <errno.h>
#include <fcntl.h>
#include <netinet/in.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/epoll.h>
#include <unistd.h>
#define MAX_EVENTS 4096
#define BACKLOG 1024
#define PORT 55688
#define CRLF "\r\n"
#define DOUBLE_CRLF CRLF CRLF
#define SOCKET_NON_BLOCKING(fd) \
int flags = fcntl(fd, F_GETFL, 0); \
if (flags == -1) \
abort(); \
flags |= O_NONBLOCK; \
if (fcntl(fd, F_SETFL, flags) == -1) \
abort();
#define EPOLL_CTL(efd, a, cfd, evs) \
if (epoll_ctl( \
efd, a, cfd, \
&(struct epoll_event){.events = evs, .data = {.fd = cfd}}) == -1) \
exit(EXIT_FAILURE);
static const char *content =
"HTTP/1.1 200 OK" CRLF "Content-Length: 18" CRLF
"Content-Type: text/html" DOUBLE_CRLF "Users Static Files" DOUBLE_CRLF;
static void do_use_fd(int epollfd, struct epoll_event *d)
{
if (d->events & MASK1) {
char buf[512] = {0};
int n = read(d->data.fd, buf, 512);
if (n > 0) {
EPOLL_CTL(epollfd, EPOLL_CTL_MOD, d->data.fd, EPOLLOUT);
} else {
if (n == 0) {
EPOLL_CTL(epollfd, EPOLL_CTL_DEL, d->data.fd, 0);
close(d->data.fd);
return;
}
}
} else if (d->events & MASK2) {
int n = write(d->data.fd, content, COUNT);
if (n > 0) {
EPOLL_CTL(epollfd, EPOLL_CTL_MOD, d->data.fd, EPOLLIN);
} else {
if (n == 0) {
EPOLL_CTL(epollfd, EPOLL_CTL_DEL, d->data.fd, 0);
close(d->data.fd);
}
if (errno != EAGAIN && errno != EWOULDBLOCK)
close(d->data.fd);
}
} else {
EPOLL_CTL(epollfd, EPOLL_CTL_DEL, d->data.fd, 0);
close(d->data.fd);
}
}
int main(void)
{
int listen_sock = socket(AF_INET, SOCK_STREAM | SOCK_NONBLOCK, IPPROTO_TCP);
if (listen_sock == -1)
exit(EXIT_FAILURE);
struct sockaddr_in server_addr = {.sin_family = AF_INET,
.sin_addr.s_addr = htonl(INADDR_ANY),
.sin_port = htons(PORT)};
if ((bind(listen_sock, (struct sockaddr *) &server_addr,
sizeof(server_addr))) != 0)
exit(EXIT_FAILURE);
if ((listen(listen_sock, BACKLOG)) != 0)
exit(EXIT_FAILURE);
struct linger linger = {.l_onoff = 1, .l_linger = 0};
if (setsockopt(listen_sock, SOL_SOCKET, SO_REUSEADDR,
(const char *) &linger.l_onoff,
sizeof(linger.l_onoff)) == -1)
exit(EXIT_FAILURE);
if (setsockopt(listen_sock, SOL_SOCKET, SO_LINGER, (const void *) &linger,
sizeof(struct linger)) == -1)
exit(EXIT_FAILURE);
int epollfd = epoll_create1(0);
if (epollfd == -1)
exit(EXIT_FAILURE);
struct epoll_event ev = {.events = EPOLLIN, .data.fd = listen_sock};
if (epoll_ctl(epollfd, EPOLL_CTL_ADD, listen_sock, &ev) == -1)
exit(EXIT_FAILURE);
struct epoll_event events[MAX_EVENTS];
for (;;) {
int nfds = epoll_wait(epollfd, events, MAX_EVENTS, -1);
if (nfds == -1)
exit(EXIT_FAILURE);
for (int n = 0; n < nfds; ++n) {
if (events[n].data.fd == listen_sock) {
ev.data.fd = accept(listen_sock, NULL, NULL);
if (ev.data.fd == -1)
exit(EXIT_FAILURE);
SOCKET_NON_BLOCKING(ev.data.fd);
ev.events = EPOLLIN;
if (epoll_ctl(epollfd, EPOLL_CTL_ADD, ev.data.fd, &ev) == -1)
exit(EXIT_FAILURE);
} else
do_use_fd(epollfd, &events[n]);
}
}
return 0;
}
```
首先解釋何為 `epoll`:
`epoll` 是 linux2.6 內核的一個新的系統調用，`epoll` 在設計之初，就是為了替代 `select` , `poll` 線性複雜度的模型，`epoll` 的時間複雜度為O(1)，也就意味著，`epoll` 在高並發場景，隨著文件描述符的增長，有良好的可擴展性。
下表展示了 file descriptors (fd) 和 CPU 耗時
|Number of file descriptors|poll() CPU time|select() CPU time|epoll() CPU time|
| --- | --- | --- | --- |
|10|0.61|0.73|0.41|
|100|2.9|3|0.42|
|1000|35|35|0.53|
|10000|990|930|0.66|
```cpp
// size 為監視的 file descriptors 數量
int epoll_create(int size)；
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event)；
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);
```
* 函式解釋
* `epoll_create` : 當產生了 epoll 後，會佔用一個 fd value，不同於 select 必須提供最大監視 fd 數量 +1，size 並不是該 epoll 能監視的 fd 數量上限，而是配置 kernel 內部資料的建議參數。
* `epoll_ctl` : 將監聽的 file descriptors 添加到 epoll 實例中
* `epoll_wait` : 等待 epoll 事件從 epoll 實例中發生， 並返回事件和對應 file descriptors
* epoll 對 file descriptors(fd) 的操作有兩種模式，edge-triggered (ET) 和 level-triggered (LT)
* level-triggered
* 當 `epollwait` 偵測到 fd 事件發生，將該事件通知 process，該 process 可不立刻處理該 event，當下次呼叫 `epollwait` 時，會再次通知 process 這個事件
* edge-triggered
* 當 `epollwait` 偵測到 fd 事件發生，將該事件通知 process，該 process 必須立刻處理該 event，如果沒有處理，當下次呼叫 `epollwait` 時，不會再次通知 process 這個事件
* edge-triggered 僅觸發一次，level-triggered 會一直觸發。
* `epoll_event` ，告訴 kernel 要監視什麼 event
```cpp
struct epoll_event {
__uint32_t events; /* Epoll events */
epoll_data_t data; /* User data variable */
};
```
* `events`，是以下幾個 macro 的集合：
* EPOLLIN ： 表示對應的 file descriptors 可以讀（包括SOCKET的正常關閉）；
* EPOLLOUT： 表示對應的 file descriptors 可以寫；
* EPOLLPRI： 表示對應的 file descriptors 有緊急的數據可讀；
* EPOLLERR： 表示對應的 file descriptors 發生錯誤；
* EPOLLHUP： 表示對應的 file descriptors 被掛斷；
* EPOLLET： 將EPOLL設為 Edge Triggered 模式 ，這是相對於 Level Triggered 來說的。
* EPOLLONESHOT： 只監聽一次事件，當監聽完這次事件之後，如果還需要繼續監聽這個 socket 的話，需要再次把這個 socket 加入到 EPOLL 隊列裡。
MASK1 = `(a)` `EPOLLIN`
MASK2 = `(b)` `EPOLLOUT`
COUNT 即為 `content` 所指的字串的 char 個數，因此，`COUNT = 86` 。
COUNT = `(g)` `86`
Sign in with Wallet
Connect another wallet