【读厚 CSAPP】知识点复习

考试的目的在于明晰知识点,复习的目的在于温故知新,理解最重要。和实验中考察的不同,这一讲我们结合往年的测试题,来回顾下重点的理论知识点。


易错

  • 只有已退出(Exited)的进程才能被回收
  • 带合并的 malloc 的空间利用率可能更高、可能一样、可能更低(相对于不带合并的 malloc
  • 执行 exec 之后被阻塞的信号会保留
  • 执行 exec 可能会有 0 次或 1 次返回,取决于执行有没有发生错误,有错才会返回
  • 已初始化的变量保存在 ELF 二进制文件中的 .data 部分
  • fork 之后父进程和子进程会立即共享 open file struct
  • fork 之后会复制 file descriptor table
  • 进程没有办法处理 SIGKILL 信号
  • 链接器的输入可以是 .o.a
  • 增加 cache 中的 line size 可以减少 compulsory miss
  • int *(*f[3])(); 的意思是 an array of pointers to functions that return pointers to int
  • User stack 不在 ELF 中

大部分概念在例题讲解中都有介绍,这里就不专门列出了。以下这部分是关键:

  • 内部碎片包括 header 和 footer,不只是 payload 的部分
  • IO 题目的顺序需要注意,加上 fork 之后需要非常仔细
  • 信号量部分需要仔细阅读题目,尤其是会阻塞相同的信号这里
  • 移位数目超过数据本身的位数会出现不定结果
  • 注意活锁和饥饿的区别

例题

进程控制 1

假设下面代码中 fork, exec, waitprintf 都不会失败,每次调用 printf 之后 stdout 都会被清空(flushed)

int global_x = 0;
int main(int argc, char *argv[])
{
global_x = 17;
// 这里 fork 永远不会失败
if (!fork()) {
// 这里是子进程
global_x++;
printf("Child: %d\n", global_x);
}
else
{
// 这里是父进程
wait(NULL);
global_x--;
printf("Parent: %d\n", global_x);
}
return 0;
}

前面代码的输出是什么?

这题考察的是对 fork 做的事情了不了解,简单来说,fork 之后不同的进程中 global_x 各有一份,所以子进程加 1 变成 18,父进程减 1 变成 16,具体的流程已经在注释中标出。

Child: 18
Parent: 16

另外需要注意的是父进程中的 wait 函数,下一题会涉及。

如果不调用 wait 函数,输出会有什么变化?

如果没有了 wait 函数,那么父进程不会等待子进程完成,所以可能会在子进程输出之前打印对应的语句。但是无论顺序怎么变,值是不会变化的,子进程中是 18,父进程中是 16.

如果程序改为下面的片段,输出是否会变化?

int global_x = 0;
int main(int argc, char *argv[])
{
global_x = 17;
// 这里 fork 永远不会失败
if (!fork())
{
global_x++;
// 这里 exec 永远不会失败
execl("./my_child", "./my_child", NULL);
printf("Child finished\n");
}
else
{
wait(NULL);
global_x--;
printf("Parent: %d\n", global_x);
}
return 0;
}
// 下面是 my_child 的代码
int global_x;
int main(int argc, char *argv[])
{
printf("Child: %d\n", global_x);
return 0;
}

父进程的输出不变,因为代码并没有什么变化,也没有其他会改变的地方。但是对于子进程来说,因为在 my_child 中的 global_x(同名变量)是未初始化,所以 exec 会把原来的 18 给刷掉,输出可以认为是 Child: 0(当然也有可能被随机初始化为 18,但是这里姑且这么考虑)

进程控制 2

下面代码的输出是什么?

pid_t pid;
int counter = 2;
void handler1(int sig)
{
counter = counter - 1;
printf("%d", counter);
fflush(stdout);
exit(0);
}
int main()
{
signal(SIGUSR1, handler1);
printf("%d", counter);
fflush(stdout);
if ((pid = fork()) == 0)
{
while (1) {};
}
kill(pid, SIGUSR1);
waitpid(-1, NULL, 0);
counter = counter + 1;
printf("%d", counter);
exit(0);
}

和前面的比较类似,只要意识到无论是 fork 出去的进程,还是 signal handler 都有自己的一套变量,所以可以很容易得到最终的答案是 213

动态内存分配

这部分题目关键在于读题,给出的条件会极大影响最终的答案。本题中所有的问题是基于下面代码的:

#define N 32
void *pointers[N];
int i;
for (i = 0; i < N; i++)
pointers[i] = malloc(4);
for (i = 0; i < N; i++)
free(pointers[i]);
for (i = 0; i < N; i++)
pointers[i] = malloc(56);

假设 malloc 是用 implicit list 实现的,header 为 8 字节,没有 footer,每个 block 都需要跟 8 字节对齐(也就是大小是 8 的倍数)。使用 first-fit 策略,如果没有足够的空间,就会调用 sbrk 来申请满足要求的是 8 的倍数的大小的空间。不会合并和分隔 block。

上面代码执行完毕,sbrk 函数一共申请了多少空间?

$$(8+8)\times 32 + (8+56)\times 32 = 2560 \; bytes$$

第一个 8 是 header,必须要有的,后面第二个 8 是因为要对齐,因为不合并,所以前面申请的空间在第三次循环的时候并不能用,需要重新申请。

代码执行完毕后,已分配的空间大小为?(包括 header 和内部碎片)

$$(8+56) \times 32 = 2048$$

第一次循环中申请的空间在第二次循环中释放了,所以只剩下第三次循环的空间是已分配的

代码执行完毕后,未分配的空间大小为?(包括 header)

$$(8+8)\times 32=512$$

其实就是第二次循环中释放的部分

用户申请的空间占使用 sbrk 得到的空间的比例是多少?

这里注意是用户申请的而不是已分配的

$$56 \times 32 \div (16 \times 32 + 64 \times 32) = 7/10$$

换个条件

其他条件一致,只是这次 sbrk 的实现中最少需要分配 64 字节的空间,重新回答前面的四个问题:

上面代码执行完毕,sbrk 函数一共申请了多少空间?

$$(8+56)\times 32 = 2048 \; bytes$$

因为第一次和第三次可以用同样的,所以无须其他空间

代码执行完毕后,已分配的空间大小为?(包括 header 和内部碎片)

$$(8+56) \times 32 = 2048$$

因为第一次和第三次可以用同样的,所以无须其他空间

代码执行完毕后,未分配的空间大小为?(包括 header)

0

因为第一次和第三次可以用同样的,所以无须其他空间

用户申请的空间占使用 sbrk 得到的空间的比例是多少?

这里注意是用户申请的而不是已分配的

$$56 \times 32 \div (64 \times 32) = 7/8$$

虚拟内存

假设我们有一个页大小为 4KB 的 32 位系统,我们通过具体的计算来比较一下 1-level 页表和 2-level 页表的表现。

对于 2-level 页表来说

这里 page directory 和 page table 的大小都是 4KB,也就是一页的大小

Page directory 中有多少条记录

32 位系统中一个地址有 32 比特也就是 4 字节,一页的大小是 4K 字节,所以能够保存 4K/4 = 1K = 1024 个地址,对应 1024 个 page table 的地址。

Page table 中有多少条记录

32 位系统中一个地址有 32 比特也就是 4 字节,一页的大小是 4K 字节,所以能够保存 4K/4 = 1K = 1024 个地址,对应 1024 个虚拟的地址。

另外一个角度可以这么看,一共 32 位,一页 4KB 也就是 12 位,还剩 20 位就平均分,两层嘛,各 10 位。

Page directory 和 page table 一共要占多少空间

我们一共需要 1 个 page directory 和 1024 个 page table,所以就是 4KB + 4MB

对于 1-level 页表来说

注意这里没有给出页表的大小

页表中需要有多少条记录

看位数,一共 32 位,一页是 4KB 也就是 12 位,剩下的 20 位都必须塞到页表中,所以页表中一共有

$$2^{20} 条记录 = 1,048,576 \;条记录$$

Page table 需要占据多少空间

一条记录 4B,那么 1,048,576 条记录就需要 4MB(4,194,304B)

从前面的比较可以看出,2-level 的比 1-level 的占的空间要多,为什么实际我们反而不用 1-level 的呢?

因为实际使用的时候,我们对于内存的需要是离散的,很少需要一个完整的 2-level 页表,所以大部分情况下 2-level 只需要在内存中映射很小的一部分,占用的空间也比较少

假设我们有一个进程,其地址空间如下,对应填写 page directory 中的内容,可选的有 unallocated, stack, heap, text and datakernel memory

+---------------------------+ 0xFFFFFFFF
| 9MB Stack |
+---------------------------+
| ... Unused |
+---------------------------+
| 6MB Heap |
+---------------------------+
| 4MB Unused |
+---------------------------+
| 12MB Text and Data |
+---------------------------+
| 16MB Kernel Memory |
+---------------------------+ 0x00000000

这里需要注意的就是顺序是相反的,page directory 的第 0 项就从 0x00000000 开始,然后前面也知道 page directory 中的一项表示 4MB,对照填写即可,如下:

----------------------
| 0 | kernel memory |
|--------------------|
| 1 | kernel memory |
|--------------------|
| 2 | kernel memory |
|--------------------|
| 3 | kernel memory |
|--------------------|
| 4 | text and data |
|--------------------|
| 5 | text and data |
|--------------------|
| 6 | text and data |
|--------------------|
| 7 | unallocated |
|--------------------|
| 8 | heap |
|--------------------|
| 9 | heap |
|--------------------|
| 10 | unallocated |
|--------------------|
| 11 | unallocated |
|--------------------|
| 12 | unallocated |
|--------------------|
|....| unallocated |
|--------------------|
|n-12| unallocated |
|--------------------|
|n-11| unallocated |
|--------------------|
|n-10| unallocated |
|--------------------|
| n-9| unallocated |
|--------------------|
| n-8| unallocated |
|--------------------|
| n-7| unallocated |
|--------------------|
| n-6| unallocated |
|--------------------|
| n-5| unallocated |
|--------------------|
| n-4| unallocated |
|--------------------|
| n-3| stack |
|--------------------|
| n-2| stack |
|--------------------|
| n-1| stack |
----------------------

TLB 相关

假设我们的系统设定为:

  1. two way associative TLB
  2. TLB 有 8 条记录
  3. 页大小为 2 的 8 次方
  4. 虚拟内存大小为 2 的 16 次方

TLB 中的数据如下:

用以上的信息填写下表,如果信息不够的话,则不需要填写

虚拟地址 物理地址
0x7E85 ?
0xD301 ?
? 0x3020
0xD040 ?
? 0x5830

要做这题,需要一幅图:

或者说,一定要理解具体的地址翻译过程,这里使用 TLB 而没有给出页表,所以如果 TLB 中没有的,或者是 Valid 为 0 的,都可以认为是信息不够。

我们先来看看第一个虚拟地址 0x7E85,为了表示方便,先写成二进制形式

# 16 进制
0x7E85
# 2 进制
0111 1110 1000 0101
# 一页的大小为 2^8,也就是说前 8 位是 VPN,后面是 VPO
# VPO 也就是实际的 PPO
# 又因为 TLB 一共有 4 个 set,所以需要 2 位
# 重写之后是这样
01 1111 10 1000 0101
# 前 6 位是 TLB tag,之后 2 位是 TLB index
# 所以对应的 tag 是
0x1F
# 对应的 index 是
2
# 从 TLB 表中查询有
# index 为 2 时 且 tag 为 0x1F 对应的物理地址是
0x95
# 拼接上原来的 VPO 就是
0x9585

按照这个方法,可以发现 0xD3010xD040 都没有办法找到有效的 TLB 项。

然后我们来看看从物理地址到虚拟地址的翻译,以 0x3020 为例,首先因为后 8 位是一样的,所以不用关系,也就是说只需要关注 TLB 表中 0x30 的项目(Valid 同样需要为 1)。我们在 set 0 中找到了,所以知道 TLB index 为 0,然后 Tag 为 0x13,对应写出来就是 01 0011 00,拼成完整地址是 0100 1100 0010 0000 也就是 0x4C20

根据这样的方法,最终的答案是:

虚拟地址 物理地址
0x7E85 0x9585
0xD301
0x4C20 0x3020
0xD040
0x5830

链接 1

下面给出两个代码片段,写下各个符号的各个属性,具体如下表所示

// main.c
int x = 5;
int y;
static int z = 3;
int main()
{
printf("%x\n", z());
x = 0xdeadbeef;
printf("%x\n", z());
}
// foo.c
short x;
int y = 0x12345678;
int z()
{
return y;
}

对应的表格是:

---------------------------------------------------------------
| File | Symbol | Strength/scope | Value | ELF section |
|-------------------------------------------------------------|
| | x | strong global | 5 | .data |
| |----------------------------------------------------|
| | y | weak global | - | .data |
| main.o |----------------------------------------------------|
| | z | local | 3 | .data |
| |----------------------------------------------------|
| | main | strong global | - | .text |
|-------------------------------------------------------------|
| | x | weak global | - | .data |
| |----------------------------------------------------|
| foo.o | y | strong global | 0x12345678 | .data |
| |----------------------------------------------------|
| | z | strong global | - | .text |
---------------------------------------------------------------

链接 2

给出下面两段代码,编译执行之后的输出是什么?

// main.c
#include <stdio.h>
static int a = 1;
int b = 2;
int c;
int main()
{
int c = 3;
foo();
printf("a=%d, b=%d, c=%d\n", a, b, c);
return 0;
}
// foo.c
int a, b, c;
void foo()
{
a = 4;
b = 5;
c = 6;
}

这里最终输出 a=1, b=5, c=3

具体说明一下,a 是 static 的,可以认为不受其他函数影响,所以仍然是原来的 1;b 在 main 中有初始化,所以是 strong 的,在 foo 中对 b 的引用实际上是引用 main 的 b,所以 b 变成 5;最后 c 会被局部变量覆盖,就是 3.

输入输出

下面的代码会输出什么呢?假设所有的系统调用都会成功,且 read()write() 是原子的。foo.txt 中的内容是 ABCDEFG

// 这个函数每次读取一个字符,输出后清空缓冲区
void read_and_print_one(int fd)
{
char c;
read(fd, &c, 1);
printf("%c", c);
fflush(stdout);
}
int main(int argc, char *argv[])
{
// 均为只读的 file descriptor
int fd1 = open("foo.txt", O_RDONLY);
int fd2 = open("foo.txt", O_RDONLY);
read_and_print_one(fd1); // 读取 fd1 第一个字符并输出 A
read_and_print_one(fd2); // 读取 fd2 第一个字符并输出 A
if (!fork()) // fork 之后继承所有的 fd
{
read_and_print_one(fd2); // 读取 fd2 第二个字符并输出 B
read_and_print_one(fd2); // 读取 fd2 第三个字符并输出 C
close(fd2); // 关闭 fd2
fd2 = dup(fd1); // 把 fd2 指向 fd1
read_and_print_one(fd2); // 继续读取 fd1/2 第二个字符并输出 B
}
else
{
wait(NULL);
read_and_print_one(fd1); // 继续读取 fd1/2 第二个字符并输出 C
read_and_print_one(fd2); // 继续读取 fd1/2 第二个字符并输出 D
printf("\n");
}
close(fd1);
close(fd2);
return 0;
}

输出是 AABCBCD,而 foo.txt 中内容不变,因为是只读的。具体的解释参见代码注释

并行、竞争与同步

下面五段代码都试图做同样的事情:主线程创建另外两个线程,每个线程都打印出自己的线程 id,我们需要判断其中的 myid 会不会出现竞争(race)

// 版本一
void *foo(void *vargp)
{
int myid;
myid = *((int *)vargp);
Free(vargp);
printf("Thread %d\n", myid);
}
int main()
{
pthread_t tid[2];
int i, *ptr;
for (i = 0; i < 2; i++)
{
ptr = Malloc(sizeof(int));
*ptr = i;
Pthread_create(&tid[i], 0, foo, ptr);
}
Pthread_join(tid[0], 0);
Pthread_join(tid[1], 0);
}

这个版本不会出现竞争,因为在循环中每次创建不同的指针,在不同位置,严格来说不是共享同一个变量。


// 版本二
void *foo(void *vargp)
{
int myid;
myid = *((int *)vargp);
printf("Thread %d\n", myid);
}
int main()
{
pthread_t tid[2];
int i;
for (i = 0; i < 2; i++)
Pthread_create(&tid[i], NULL, foo, &i);
Pthread_join(tid[0], NULL);
Pthread_join(tid[1], NULL);
}

这个版本会出现竞争,指针会指向同一个 myid。一般来说这种直接塞指针,又没有重新分配的,会有问题。


// 版本三
void *foo(void *vargp)
{
int myid;
myid = (int)vargp;
printf("Thread %d\n", myid);
}
int main()
{
pthread_t tid[2];
int i;
for (i = 0; i < 2; i++)
Pthread_create(&tid[i], 0, foo, i);
Pthread_join(tid[0], 0);
Pthread_join(tid[1], 0);
}

这个版本不会出现竞争,因为是直接传值而不是传引用的(注意和上一个版本的区别)


// 版本四
sem_t s; // Semaphore s
void *foo(void *vargp)
{
int myid;
P(&s);
myid = *((int *)vargp);
V(&s);
printf("Thread %d\n", myid);
}
int main()
{
pthread_t tid[2];
int i;
sem_init(&s, 0, 1); // 这里初始化值为 1
for (i = 0; i < 2; i++)
Pthread_create(&tid[i], 0, foo, &i);
Pthread_join(tid[0], 0);
Pthread_join(tid[1], 0);
}

这个版本会出现竞争条件,理解了信号量机制之后就会发现,这个代码的信号量其实等于没用。具体自己感受下(或者参考后面一个版本)


// 版本五
sem_t s; // Semaphore s
void *foo(void *vargp)
{
int myid;
myid = *((int *)vargp);
V(&s);
printf("Thread %d\n", myid);
}
int main()
{
pthread_t tid[2];
int i;
sem_init(&s, 0, 0); // 这里初始化值为 0
for (i = 0; i < 2; i++)
{
Pthread_create(&tid[i], 0, foo, i);
P(&s);
}
Pthread_join(tid[0], 0);
Pthread_join(tid[1], 0);
}

这个版本不会有竞争条件,自己模拟跑一次就会发现实际上这种写法限制了具体执行的顺序,所以是可以的。

总结

其实我觉得如果认真上了整个学期的课,也看完了我写的整个系列,考试还是蛮简单的。

捧个钱场?