sysprog2020
目的: 檢驗學員對 CS:APP 第 9 章和高效 Web 伺服器開發的認知
1
以下關於記憶體管理的描述,選出其中唯一正確的描述
作答區
Q1 = ?
(a)
在一個 buddy system 中,最高可達 50% 的空間可因內部碎片化 (fragmentation) 而被浪費(b)
平均來說,first-fit 演算法會比 best-fit 演算法來得慢(c)
僅在 free list 依據記憶體地址遞增排序時,使用邊界標記來回收 (reclaim) 才會快速(d)
buddy system 只會有內部碎片,不會有外部碎片2
以下關於記憶體管理的描述,選出其中唯一正確的描述
作答區
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 演算法等價3
考慮以下是利用 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;
}
請補完程式碼,使得程式行為符合預期。
作答區
MASK1 = ?
(a)
EPOLLIN
(b)
EPOLLOUT
MASK2 = ?
(a)
EPOLLIN
(b)
EPOLLOUT
COUNT = ?
(a)
16(b)
26(c)
36(d)
46(e)
56(f)
66(g)
86回歸第一手資料,透過反思 C 語言程式設計的細節,重新學習電腦原理
Jul 21, 2025自 Linux 核心原始程式碼編譯出 User-mode Linux 並運用工具來建構實驗所需的檔案系統
Jul 20, 2025系統的 throughput 是評斷排程器優劣的重要效能
Jul 19, 2025無論是作業系統核心、C 語言函式庫內部、程式開發框架,到應用程式,都不難見到 linked list 的身影,包含多種針對效能和安全議題所做的 linked list 變形,又還要考慮到應用程式的泛用性 (generic programming),是很好的進階題材。
Jul 17, 2025or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up