Try   HackMD

2020q3 Homework12 (quiz 12)

contributed by < JimmyLiu0530 >

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

測驗一:

以下關於記憶體管理的描述,選出其中唯一正確的描述

Q1 = ?

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

Solution

什麼是 buddy memory allocation? [Video: Buddy System]

  • 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 = EPOLLINMASK2 = EPOLLOUT

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