contributed by < JimmyLiu0530
>
進階電腦系統理論與實作
以下關於記憶體管理的描述,選出其中唯一正確的描述
Q1 = ?
(a)
在一個 buddy system 中,最高可達 50% 的空間可因內部碎片化 (fragmentation) 而被浪費(b)
平均來說,first-fit 演算法會比 best-fit 演算法來得慢(c)
只有在 free list 依照記憶體地址遞增排序時,使用邊界標記來回收 (reclaim) 才會快速(d)
buddy system 只會有內部碎片,不會有外部碎片什麼是 buddy memory allocation? [Video: Buddy System]
(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 演算法等價(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
。