深入理解计算机系统 第12章 习题解析
这次回顾第12章部分习题。
电子书地址：
参考资料：
https://dreamanddead.github.io/CSAPP-3e-Solutions/chapter12/
说明：
19~20是难题，21，23，26以及31之后习题略过。
12.16
代码：
#include "csapp.h"
void *thread(void *vargp); //line:conc:hello:prototype
int main(int argc, char **argv) //line:conc:hello:main
{
int n = -1;
if (argc != 2) {
fprintf(stderr, "you should enter a positive number!\n");
exit(0);
}
n = atoi(argv[1]);
if (n == -1) {
fprintf(stderr, "you should enter a positive number!\n");
exit(0);
}
pthread_t tid; //line:conc:hello:tid
for (int i = 0; i < n; i++) {
Pthread_create(&tid, NULL, thread, NULL); //line:conc:hello:create
Pthread_join(tid, NULL); //line:conc:hello:join
}
exit(0); //line:conc:hello:exit
}
void *thread(void *vargp) /* thread routine */ //line:conc:hello:beginthread
{
printf("Hello, world!\n");
return NULL; //line:conc:hello:return
} //line:conc:hello:endthread编译：
gcc -o 16 16.c -lpthread运行：
$ ./16 3
Hello, world!
Hello, world!
Hello, world!12.17
A
主线程没有等待对等线程终止。
B
代码：
/*
* hellobug.c - "hello, world" program with a bug
*/
/* $begin hellobug */
/* WARNING: This code is buggy! */
#include "csapp.h"
void *thread(void *vargp);
int main()
{
pthread_t tid;
Pthread_create(&tid, NULL, thread, NULL);
// add
Pthread_join(tid, NULL);
exit(0); //line:conc:hellobug:exit
}
/* Thread routine */
void *thread(void *vargp)
{
Sleep(1);
printf("Hello, world!\n");
return NULL;
}
/* $end hellobug */编译：
gcc -o 17 17.c -lpthread运行：
$ ./17
Hello, world!12.18
A
$H_{2}, L_{2}, U_{2}, H_{1}, L_{1}, S_{2}, U_{1}, S_{1}, T_{1}, T_{2}$
不安全。
B
$H_{2}, H_{1}, L_{1}, U_{1}, S_{1}, L_{2}, T_{1}, U_{2}, S_{2}, T_{2}$
安全。
C
$H_{1}, L_{1}, H_{2}, L_{2}, U_{2}, S_{2}, U_{1}, S_{1}, T_{1}, T_{2}$
不安全。
说明：19~21比较难，目前还没完全理解。
12.19
给writer增加自己的锁wg，这样在V(&wg)执行之后，等候的reader就可以执行，因为此时wg为1。
代码：
/*
* Readers-writers solution with weak reader priority
* From Courtois et al, CACM, 1971.
*/
#include "csapp.h"
/* $begin reader1 */
/* Global variables */
int readcnt; /* Initially = 0 */
sem_t mutex, w, wg; /* Both initially = 1 */
void reader(void)
{
while (1) {
P(&mutex);
readcnt++;
if (readcnt == 1) /* First in */
P(&w);
V(&mutex);
/* Critical section */
/* Reading happens */
P(&mutex);
readcnt--;
if (readcnt == 0) /* Last out */
V(&w);
V(&mutex);
}
}
/* $end reader1 */
/* $begin writer1 */
void writer(void)
{
while (1) {
P(&wg);
P(&w);
/* Critical section */
/* Writing happens */
V(&w);
V(&wg);
}
}
/* $end writer1 */12.20
代码：
#include "csapp.h"
#define N 10
/* $begin reader1 */
/* Global variables */
sem_t cnt; /* Initially = N */
sem_t mutex; /* Both initially = 1 */
void reader(void)
{
while (1) {
P(&cnt);
/* Critical section */
/* Reading happens */
V(&cnt);
}
}
/* $end reader1 */
/* $begin writer1 */
void writer(void)
{
while (1) {
P(&mutex);
// 只有当reader全部结束时才能执行完循环, 循环结束时cnt = 0
for (int i = 0; i < N; i++) {
P(&cnt);
}
V(&mutex);
/* Critical section */
/* Writing happens */
for (int i = 0; i < N; i++) {
V(&cnt);
}
// 此时mutex = 1, cnt = N, reader和writer谁先执行的概率相同
}
}
/* $end writer1 */12.22
思路：看到\n就返回。
代码：
/* $begin select */
#include "csapp.h"
void echo(int connfd);
void command(void);
int main(int argc, char **argv)
{
int listenfd, connfd;
socklen_t clientlen;
struct sockaddr_storage clientaddr;
fd_set read_set, ready_set;
if (argc != 2) {
fprintf(stderr, "usage: %s <port>\n", argv[0]);
exit(0);
}
listenfd = Open_listenfd(argv[1]); //line:conc:select:openlistenfd
FD_ZERO(&read_set); /* Clear read set */ //line:conc:select:clearreadset
FD_SET(STDIN_FILENO, &read_set); /* Add stdin to read set */ //line:conc:select:addstdin
FD_SET(listenfd, &read_set); /* Add listenfd to read set */ //line:conc:select:addlistenfd
while (1) {
ready_set = read_set;
Select(listenfd+1, &ready_set, NULL, NULL, NULL); //line:conc:select:select
if (FD_ISSET(STDIN_FILENO, &ready_set)) //line:conc:select:stdinready
command(); /* Read command line from stdin */
if (FD_ISSET(listenfd, &ready_set)) { //line:conc:select:listenfdready
clientlen = sizeof(struct sockaddr_storage);
connfd = Accept(listenfd, (SA *)&clientaddr, &clientlen);
echo(connfd); /* Echo client input until EOF */
Close(connfd);
}
}
}
void command(void) {
char buf[MAXLINE];
if (!Fgets(buf, MAXLINE, stdin))
exit(0); /* EOF */
printf("%s", buf); /* Process the input command */
}
/* $end select */
void echo(int connfd)
{
int n;
char buf[MAXLINE];
rio_t rio;
Rio_readinitb(&rio, connfd);
while((n = Rio_readlineb(&rio, buf, 1)) != 0) {
Rio_writen(connfd, buf, n);
// add
if (buf[0] == '\n') {
return;
}
}
}12.24
代码：
ssize_t Rio_readn(int fd, void *ptr, size_t nbytes)
{
ssize_t n;
if ((n = rio_readn(fd, ptr, nbytes)) < 0)
unix_error("Rio_readn error");
return n;
}
void Rio_writen(int fd, void *usrbuf, size_t n)
{
if (rio_writen(fd, usrbuf, n) != n)
unix_error("Rio_writen error");
}
void Rio_readinitb(rio_t *rp, int fd)
{
rio_readinitb(rp, fd);
}
ssize_t Rio_readnb(rio_t *rp, void *usrbuf, size_t n)
{
ssize_t rc;
if ((rc = rio_readnb(rp, usrbuf, n)) < 0)
unix_error("Rio_readnb error");
return rc;
}
ssize_t Rio_readlineb(rio_t *rp, void *usrbuf, size_t maxlen)
{
ssize_t rc;
if ((rc = rio_readlineb(rp, usrbuf, maxlen)) < 0)
unix_error("Rio_readlineb error");
return rc;
} 都是隐式可重入的。
12.25
代码：
void echo_cnt(int connfd)
{
int n;
char buf[MAXLINE];
rio_t rio;
static pthread_once_t once = PTHREAD_ONCE_INIT;
Pthread_once(&once, init_echo_cnt); //line:conc:pre:pthreadonce
Rio_readinitb(&rio, connfd); //line:conc:pre:rioinitb
while((n = Rio_readlineb(&rio, buf, MAXLINE)) != 0) {
P(&mutex);
byte_cnt += n; //line:conc:pre:cntaccess1
printf("server received %d (%d total) bytes on fd %d\n",
n, byte_cnt, connfd); //line:conc:pre:cntaccess2
V(&mutex);
Rio_writen(connfd, buf, n);
}
}
/* $end echo_cnt */说明：
- 线程安全的，因为调用了$P,V$；
- 不是可重入的，因为调用了静态变量mutex；
12.27
如果在执行
fpout = fdopen(sockfd, "w");之后创建并发流，那么可能会执行多次
fclose(fpin);
fclose(fpout);从而产生问题。
12.28
都不会死锁。
A
图示：
B
图示：
C
图示：
D
图示：
12.29
不会死锁。
a vs b：
a vs c:
b vs c:
12.30
A
利用代码模拟结果：
import copy
one = [-1, -2, 2, -3, 3, 1]
two = [-3, -2, 2, 3, -1, 1]
three = [-3, 3, -2, -1, 1, 2]
n = len(one)
actions = [one, two, three]
state = [0, 1, 1, 1]
index = [0, 0, 0]
# 标记是否访问过状态
flag = [[[0 for i in range(n + 1)] for j in range(n + 1)] for k in range(n + 1)]
# 将数字转为字母
num2char = ['', 'a', 'b', 'c']
def judge(state):
res = [0, 0, 0, 0]
for i in range(1, 4):
if state[i] < 0:
res[i] += 1
return res
def print_res(res, action):
if res != [0, 0, 0, 0]:
sen = f"thread"
for i in range(3):
# 动作i为P, 并且对应的结果为负数
if action[i] < 0 and res[i + 1]:
sen += f" {i + 1}"
sen += ","
cnt = 0
for i in range(1, 4):
if res[i]:
cnt += 1
sen += f" {num2char[i]}"
if (cnt > 1):
print(sen)
def update(state, action, i):
index = abs(action[i])
delta = 1
if (action[i] < 0):
delta = -1
state[index] += delta
def dfs(state, actions, index, n):
tmp = True
for i in range(3):
if index[i] != n:
tmp = False
break
if tmp:
return
if flag[index[0]][index[1]][index[2]]:
return
flag[index[0]][index[1]][index[2]] = 1
action = [0, 0, 0]
for j in range(3):
i = index[j]
if (i > 0 and actions[j][i - 1] < 0):
action[j] = -1
print_res(judge(state), action)
for i in range(3):
if index[i] < n:
old_state = copy.deepcopy(state)
update(state, actions[i], index[i])
index[i] += 1
dfs(state, actions, index, n)
index[i] -= 1
state = copy.deepcopy(old_state)
dfs(state, actions, index, n)实验结果：
thread 2, a b
thread 1 3, a c
thread 1 3, a c
thread 2 3, b c
thread 1 2 3, a b c
thread 2, b c
thread 1 3, a c
thread 2, a b
thread 1, a b
thread 1 2, a b
thread 1 2, a b
thread 1 2, a b
thread 1, a b
thread 1, a b
thread 2 3, b c
thread 1 2, a b
thread 1 2, a b
thread 1, a b
thread 1 2, a b线程1占用的互斥锁：
a和c, a和b。
线程2占用的互斥锁：
a和b, b和c。
线程3占用的互斥锁：
a和c, b和c。
B
线程2,3，因为违反了顺序。
C
加锁顺序相同即可。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Doraemonzzz！
相关推荐
评论
ValineLivere