# 2020q3 Homework12 (quiz 12)
contributed by < `JimmyLiu0530` >

###### tags: `進階電腦系統理論與實作`

## 測驗一:
以下關於記憶體管理的描述，選出其中唯一正確的描述

Q1 = ?
- `(a)` 在一個 [buddy system](https://en.wikipedia.org/wiki/Buddy_system) 中，最高可達 50% 的空間可因內部碎片化 (fragmentation) 而被浪費
- `(b)` 平均來說，first-fit 演算法會比 best-fit 演算法來得慢
- `(c)` 只有在 free list 依照記憶體地址遞增排序時，使用邊界標記來回收 (reclaim) 才會快速
- `(d)` [buddy system](https://en.wikipedia.org/wiki/Buddy_system) 只會有內部碎片，不會有外部碎片

### Solution
什麼是 [buddy memory allocation](https://en.wikipedia.org/wiki/Buddy_memory_allocation)? [[Video: Buddy System](https://www.youtube.com/watch?v=1pCC6pPAtio)]
- A memory alloction method that divides memory into partitions, which are usually powers of 2, to try to satisfy a memory request as suitably as possible.
- Suffer from external and internal fragmentation
- Blocks with their buddies unavailable will cause external fragmentation
- About 50% space is wasted in the worst case due to internal fragmentation
- e.g. request 128.001K, which is given 256K block
- More percisely, statement `(a)` should be "接近、大約" -> anyway, it's the anwser.

-----------------------------------------------------

## 測驗二:
以下關於記憶體管理的描述，選出其中唯一正確的描述

Q2 = ?
- `(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 演算法等價

### Solution
`(a)` 仍然會有外碎的問題。
e.g. free list: 800K, 500K, 200K. request: 230K, 520K 會造成外碎。

`(b)` free list 應按照 block size 遞增排序，如此一來，找到的第一個府符合的 block 即為最佳。

`(c)` 應為 "最小"。

-----------------------------------------------------

## 測驗三:
考慮以下是利用 Linux epoll 系統呼叫開發的網頁伺服器，預期應該持續接受客戶端的連線 (port 55688) 並提供靜態內容。

> 透過網頁瀏覽器可取得 Users Static Files 字樣

#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;
}

請補完程式碼，使得程式行為符合預期。

### 程式說明
`EPOLLIN`: 代表對應的文件可以讀
`EPOLLOUT`: 代表對應的文件可以寫
因此，`MASK1 = EPOLLIN`，`MASK2 = EPOLLOUT`。

COUNT 即為 `content` 所指的字串的 char 個數，因此，`COUNT = 84`。