csapp读书笔记part3

前言

本部分包含《深入理解计算机系统》第三版第三部分的内容,主要就是讲述进程如何利用系统提供的服务来与IO设备和其他进程(可能是别的机器上的进程)进行通信。

第十章 系统级IO

10.1 Unix IO

文件本质上是什么,是一个m个字节的序列。所有的IO设备(网络、磁盘这些)都被抽象化成一个文件,这样内核就能够用一种优雅的方式来整合所有的IO操作,也就是可以理解有一种全新的套路来对文件进行操作:

  • 打开文件。应用程序通过系统调用告知内核,要求打开相应的文件。内核就会返回给它一个非负的整数,称为文件描述符。
  • shell在创建进程的时候,默认就有三个打开文件,分别是标准输入(0)、标准输出(1)、错误输出(2),可以直接使用数字来进行代替。
  • 改变文件的位置。文件打开的时候,内核会默认为设置文件位置为0,也就是从文件开头开始的字节偏移量。应用程序通过seek能够改变对应的偏移量,内核会维护一个文件的当前位置k。
  • 读写文件。读操作的本质是什么?从位置k开始复制n个字节到对应的内存,然后将k设置成k+n。如果k已经超过了(或者等于)文件的大小,那么会触发一个EOF,应用程序能够检测到这个条件。注意!在文件的末尾并不是真正有一个符号! 写操作其实就是从内存复制了n个字节,复制到文件k开始的位置处,并且更新k。
  • 关闭文件。关闭文件的本质其实是,内核释放了文件打开时的数据结构,并且释放对应的文件描述符。

10.2 文件

linux下每个文件都有对应的一个类型:

  • 普通文件。普通文件细分又可以分为文本文件和二进制文件。但是在内核眼里完全没有区别。
  • 目录。目录是包含一组链接的文件。每个链接就是将一个文件名映射到一个文件。一个目录最最起码也会有两个映射,一个是.映射到了目录自身,而..则是映射到了父目录。那这里有一个问题,最顶层的那个目录(文件)中的..指向的是谁?它自己。
  • 套接字。用来和另一个进程进行跨网络通信的文件。
  • 其他。包含了命名管道、符号链接、字符和块设备,不在本书范畴内。

内核把所有的文件都组织成了一个目录层次结构,从根目录开始。其中每一个进程都有一个当前工作目录,因为shell也是一个进程,所以可以通过cd来改变当前工作目录。

10.3 打开和关闭文件

进程可以通过调用open函数来打开一个已经存在的文件,或者是创建一个新文件。

1
2
3
4
5
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

int open(char *filename, int flags, mode_t mode);

flag指定了进程打算如何访问这个文件,而mode参数指定了新文件的访问权限位。而每个进程都是携带一个umask的,所以最终的文件格式其实就是mode & ~umask

10.4 读和写文件

应用程序是通过read和write系统调用来完成输入输出的。

1
2
3
4
5
#include <unistd.h>

ssize_t read(int fd, void *buf, size_t n);
ssize_t write(int fd, const void *buf, size_t n);
// ssize_t = long size_t = unsigned long,因为read可能会返回-1

关于read和write,比较在意的就是它们可能会出现不足的情况,所以在实际中需要多次调用read和write来确保满足需要。

10.5 用RIO包健壮读写

底层其实是对read/write的一个封装,不过可以保证不发生不足值的情况。同样增加了缓冲区功能,这样就可以有效提高效率。

10.6 读取文件元数据

元数据相当于文件的一些属性的数据,下图所示就是所有的属性:

image-20201029142733698

我们只关心红框框起来的两个部分。

10.7 读取目录

略。

10.8 共享文件

内核用了三个数据结构来表示对应的打开的文件:

  • 描述符表。每个进程都会有一个它所打开的文件描述符的表,并且可以通过文件描述符找到文件表中对应的表项。简单来说就是一个map,然后key是文件描述符,value是下面的文件表的key,也就是进程能够通过文件描述符找到下面的文件表中的项目。
  • 文件表。这个文件表是由所有的进程来共享的。这个表格中的每一项就是目前操作系统中打开的文件(可能会存在重复)。由于可能会有多个进程同时打开一个文件,所以这里的表项里面有一个叫做引用计数的东西,只有当引用计数归零,内核才会删除这一项。每一条记录里面存放了文件位置、引用计数、指向vnode的指针。
  • vnode表。每一个表都对应了文件的一个stat,然后根据stat就可以获取到文件的一些信息了。

这里需要注意的是,首先如果在一个进程中利用open打开一个文件两次,那么在文件表中会创建两个item,尽管他们最终指向了相同的文件。在这里引用计数完全没有发挥它应有的作用。其次是,当父进程使用fork创建了一个子进程的时候,此时他们的之间对应的fd会指向相同的文件表的item,此时引用计数就变成了2。也就是说,如果利用了open来打开文件,那么一定会在文件表里面创建一个新的item。

10.9 IO重定向

shell中提供了IO重定向的操作符。如果希望在编程中实现,那么可以使用dup2函数。这个函数会复制一个描述符表中的一项到另外一项上去。重定向的本质其实就是把描述符表里的一个fd指向了另外一个fd所指向的文件。

由于文件表如果引用计数归零会导致清除表项,所以重定向可能会导致无法切换回原来的文件。

第十一章 网络编程

11.1 客户端-服务器模型

网络应用都是采用的客户端-服务器模型,客户端服务器模型中,最基本的操作是事务(transaction),由以下四步组成:

  1. 客户端需要服务的时候,主动发起一个请求,也就是事务开启了。
  2. 服务器收到请求之后解释这个请求,并且解释这个请求,用适当的方式操作资源。
  3. 服务器给客户端发送一个响应。
  4. 客户端收到请求并且处理它。

注意!服务器和客户端都是进程,跟机器完全没有关系。而且这里的事务和数据库里的事务是完全不同的。

11.2 网络

讲了最最基础的网络。

11.3 全球因特网

客户端通过一个系统调用进入内核态,然后由内核代码进行TCP/IP的封装,然后通过中断把数据交给硬件(网络适配器),随后硬件把消息发送出去。

通常都是把套接字函数实现为系统调用,陷入内核之后调用各种内核模式的TCP/IP函数。

11.3.1 IP地址

IP地址本质上是一个32位的无符号整数。用如下的数据结构表示:

1
2
3
4
struct in_addr
{
uint32_t s_addr;
}

看上去非常蠢,明明里面只有一个成员,为什么还要使用结构体?但是历史原因,很多程序已经基于这个结构了,所以只能忍忍了。

不同的主机之间有不同的主机字节顺序,目前一般的主机都是小端序,而网络中传输的是大端序,所以系统提供了对应的函数进行转化。由于IP地址只有32位,所以只提供了16位和32位的转化函数,并没有对应的函数。

同时也提供了对应的函数来实现IP地址和点分十进制串进行转换。

11.3.3 因特网连接

一个套接字是一个连接的端点,一个套接字的地址是“地址:端口”,所以两个对端的套接字,也就是客户端IP地址:客户端端口:服务器IP地址:服务器端口这么一个四元组构成了一个连接。

11.4 套接字接口

套接字接口本质上是一组函数,用来创建网络接口。幸运的是linux、windows和macOS都实现了这一组接口,下图是一个最明显的范例:

image-20201030092534163

11.4.1 套接字地址结构

套接字本质上是一个struct结构,由以下的成员变量:

1
2
3
4
5
6
7
8
9
10
11
12
13
struct sockaddr_in
{
uint16_t sin_family; // 对于因特网,这个值是AF_INET
uint16_t sin_port; // 端口
struct in_addr sin_addr; // ip地址,用一个整数代替
unsigned char sin_zero[8]; // 填充
}

// 和connect bind accept关系密切的另外一个结构体
struct sockaddr{
uint16_t sa_family;
char sa_data[14];
}

11.4.2 socket函数

客户端服务器都使用这个函数来创建对应的套接字描述符。

1
2
3
4
#include <sys/types.h>
#include <sys/socket.h>

int socket(int domain, int type, int protocol);

该函数返回一个文件描述符,值得注意的是,这个文件描述符是部分打开的,此时还不能用于读写。

11.4.3 connect函数

客户端用这个函数来建立和服务器的连接。这个函数会阻塞到连接成功建立或是发生错误,只要成功了,文件描述符就可以说现在准备好读写了。

11.4.4 bind 函数

bind函数是告诉内核,把套接字地址和套接字描述符联系在一起。

11.4.5 listen函数

在默认的情况下,内核认为,socket创建的描述符是主动描述符,也就是存在于客户端的描述符。而listen就是相当于告诉内核,这个套接字是被服务器使用的,而不是被客户端使用。

11.4.6 accept函数

这个函数就有点意思了,我们都知道是通过调用它,让服务器进入阻塞状态。

1
2
3
#include <sys/socket.h>

int accept(int listenfd, struct sockaddr *addr, int *addrlen);

accept这个函数等待来自客户端的请求到达listenfd,也被叫做侦听描述符,然后把客户端的地址存入addr里面,然后返回一个已连接描述符。监听描述符只会被创建一次,并且存在于服务器的整个生命周期。而已连接描述符则是客户端和服务器之间已经建立连接的一个端点,每次服务器接受连接的时候都会创建一次,它只和一个客户端对应。

11.5 web服务器

11.5.2 web内容

web的内容是由一个叫做MIME字段控制的,而web服务器一般用两种不同的方式来向客户端提供内容:

  • 从磁盘中取一个文件,并将它的内容返回给客户端。也就是常见的静态页面等内容。
  • 执行一个文件,并将它的输出返回给客户端。

最简单的辨识方法是,观察URL里面有没有加对应的参数,如果加了肯定是执行一个文件所需的参数,但是其实也不准确,因为每个服务器都有自己的一套标准。

/index.html不是意味着这个文件在根目录下,而是指的是被请求内容类型的主目录。如果仅仅是有一个/,则服务器会将其扩展成某个默认的主页,一般通过配置得到。

而如果用户仅仅在浏览器输入了网址,浏览器其实是会添加上缺失的/,并将其传递给服务器的。

11.5.3 HTTP事务

我们可以使用telnet来模拟HTTP事务。

HTTP请求

格式是一个请求行+0个或者多个请求头+一个空行+请求体

请求行的形式是:method uri version,目前流行的HTTP版本是1.1,而1.0是从96年开始延续到现在的。其中1.1定义了一些附加的报文,为诸如缓冲和安全等高级特性提供了支持,当然最显著的特点就是允许长连接了。而且1.0和1.1是互相支持的,因为1.0的客户端和服务器会忽略掉1.1的报头。

请求头中比较重要的应该就是那个host报头了。这个报头在1.0是不需要的,但是在1.1中是需要的。

HTTP响应

响应和请求是相似的,也是一个响应行+0个或者多个响应头+一个空行+响应体

11.5.4 服务动态内容

动态内容的话,需要解决一些问题:客户端怎么把程序参数传递给服务器?服务器是如何把这些参数传递给创建的子进程?子进程处理完之后该怎么做呢?为了解决这些问题,有一个标准诞生了,就是CGI(Common Gateway Interface)。

客户端怎么传递参数给服务器?

如果是GET请求,那么就在URI参数中传递。利用?分割了文件名和参数、每个参数之间用&分割,参数中是不能有空格,如果要表示的话需要用%20来表示。

如果是POST请求,那么就在请求体中传递。

服务器怎么把参数传递给子进程

首先肯定是fork来创建子进程,然后利用execve来执行对应的程序。而一般来说CGI程序都是Perl脚本编写的,所以参数是在fork之后,在execve之前,设置对应的环境变量就可以了。

服务器把其他信息给子进程

一样的,还是通过环境变量,具体如下:

image-20201030114116409
子进程把输出发送到哪里

一种简单的想法就是发回给服务器,然后服务器来处理。那为什么不进一步呢?在子进程加载CGI程序之前,它可以直接把标准输出重定位到已连接描述符(connfd),这样直接往标准输出中输出就可以直接到客户端里面去了。

这里需要注意的是,由于动态内容是子进程来负责的,所以父进程(也就是服务器主进程)并不知道length这样的属性,所以这些内容需要子进程来负责。

11.6 开发一个Tiny服务器

这部分就看书吧。

第十二章 并发编程

并发其实之前已经看到过一些应用了,比如使用Ctrl+C来终止进程就是用到的信号机制。其他的还有:

  • 访问慢速IO设备。当一个应用如果在等待慢速IO设备(磁盘),那么内核会运行别的进程来让CPU繁忙。
  • 与用户交互。用户移动鼠标、敲击键盘就是例子。
  • 推迟工作来达到更好的效率。简单来说就是推迟工作,这样可以让更多的操作能有机会合二为一。
  • 服务器中能够服务多个用户。显然之前的服务器如果一个客户端很慢,那么其他的客户端就会阻塞,很明显不符合要求。

而现代操作系统提供了三种方法来支持构造并发程序:

  • 进程。进程由内核来进行调度和维护,而且进程之间通信需要依赖IPC,没那么方便。
  • IO多路复用。应用程序在一个进程的上下文中显式地调度它们自己的逻辑流。只有一个进程,所以完全没有调度问题。
  • 线程。线程是运行在一个单一进程上下文中的逻辑流。也是由内核进行调度的。

12.1 基于进程的并发编程

最容易想到的并发编程就是利用多进程了。比如在构造服务器的时候,就利用了fork创建一个子进程,由它进行处理。

首先父进程会创建一个监听文件描述符,这里假设是3。然后一个连接进来了,假设这个新连接的已连接描述符为4。接下来,服务器就开始创建子进程。然后这个子进程会获取到所有的文件描述符,接着就是最最重要的一步。父进程需要关闭它的已连接描述符4,而子进程需要关闭它的监听描述符3。如果不这样做,那么这些文件描述符就永远无法关闭,导致内存泄露。

12.1.2 进程的优劣

显然,在父子之间,文件描述符(文件表)是共享的,但是用户的地址空间是不共享的,这个不共享既是优点也是缺点。独立的空间可以保证不会互相之间覆盖数据,但是会让数据共享变得麻烦。

12.2 基于IO多路复用的并发编程

服务器最基本的两个功能:一个是接受连接,一个是响应用户的请求,反应到程序里就是accept和read这两个调用。但是很遗憾,这两个调用都是阻塞的,也就是一旦阻塞在了一个函数上,另外一个就没办法执行了。

所以解决办法就是让内核挂起进程,只有当某些IO事件发生之后,才把控制权返回给应用程序。这些事件可以是:

  • 当集合{1,2}中任意描述符准备好读的时候返回。
  • 当集合{1,3,65}中任意描述符准备好写的时候返回。
  • 在某个IO事件中等待了某个时间,就超时。

select是一个比较复杂的函数,这里只讨论第一种情况,即等待一组描述符准备好读。

描述符集合其实就是一个bitmap,而select的参数有两个最重要的,一个就是这个bitmap(称为fdset),另外一个是集合的基数(实在不知道怎么说,就当成是1024吧…)。然后调用select会一直阻塞,直到有至少一个描述符准备好读了就返回。select会有一个副作用,就是每次调用select之前必须初始化fdset,因为select会修改这个数据结构。

用一个例子就可以很清楚明白这个了:

1
2
3
4
fd_set read_set;
FD_ZERO(&read_set); // 初始化,即目前这个bitmap为全0.
FD_SET(STDIN_FILENO,&read_set); // 把标准输入加入到这个bitmap中,置1
FD_SET(listenfd,&read_set); // 同理把监听的文件描述符也加入到bitmap中

也就是可以类比这个“数组”:

image-20201030162700802

一旦select返回,就可以用对应的FD_ISSET宏来判断对应的文件描述符是不是有数据,有的话就可以进行对应的操作,如下面的代码所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
while (1)
{
ready_set = read_set; // 因为内核会修改传入的set,所以这里相当于复制一份
select(listenfd + 1, &ready_set,NULL, NULL, NULL);
if (FD_ISSET(STDIN_FIFLNO, &ready_set))
{
// do something with input,such as read()
}
if (FD_ISSET(listenfd, &ready_set))
{
// do something with listenfd,such as accept()
}
// 当然也可以用循环,一样的意思
}

12.2.1 基于IO多路复用的并发事件服务器

IO多路复用可以用作并发事件驱动(event-driven)程序的基础。简单来说就是某些事件会导致程序往下走,其实本质上就是一个状态机,而状态机本质上就是一组状态(等待描述符k准备好可读)、输入事件(描述符k可以读了)和转移(从描述符k中读取一个)。

12.2.2 IO多路复用技术的优劣

优点就是可以让程序员更好地进行调试程序,而且是运行在一个进程的上下文中的,因此每个逻辑流都能够访问全部的地址空间,最大最大的优点就是性能会很好,因为它们不需要进程切换。

缺点也很明显:无法充分利用多核处理器,而且编码比较复杂。但是总体来说还是利大于弊的。

12.3 基于线程的并发编程

线程的方法其实可以说是这两种的混合。每个线程都有自己的线程上下文,包括一个Thread ID、栈、栈指针、程序计数器、通用目的寄存器和条件码。简单来说就是CPU+栈。

线程和进程一样,是由操作系统的内核自动调用的,和多路复用一样,所有的线程共享进程虚拟地址空间中的所有东西——代码段、数据、共享库和打开的文件。

12.3.1 线程执行模型

一开始是只有一个主线程,然后主线程在某一时刻创建对等线程。然后也是通过一个系统调用或者中断,就有可能把控制权切换到对等线程中。

因为线程的上下文比进程的上下文小得多,自然切换快的多。其次第二个不同的是,进程是有明确的父子关系的,线程更像是一个平等的关系,任何一个线程都可以杀死它的对等线程。主线程和别的线程的区别仅仅是它是第一个运行的。

12.3.2 posix线程

posix线程,即pthreads线程是一个标准接口,能够在所有的linux系统上可用。一个简单的demo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

void *thread(void *vargp);

int main(void)
{
pthread_t tid;
pthread_create(&tid, NULL, thread, NULL);
pthread_join(tid, NULL);
exit(0);
}

void *thread(void *vargp)
{
printf("hello world!\n");
return NULL;
}

编译的时候需要带上-pthread选项,该选项为预处理器和链接器设置标志。

12.3.6 分离线程

线程是可结合(joinable)或者是分离的(detached)。一个可结合的线程能够被其他线程回收和杀死,而分离的线程是不能够被其他线程回收或者杀死的的,它的内存资源由系统在它终止的时候自动释放。

默认情况下创建的线程都是可结合线程,线程可以分离别的线程,也可以分离自己,一旦分离,就无法结合了。这个有什么用处呢?

在Web服务器中当主线程为每个新来的链接创建一个子线程进行处理的时候,主线程并不希望因为调用pthread_join而阻塞(因为还要继续处理之后到来的链接),这时可以在子线程中加入代码 pthread_detach(pthread_self())或者父线程调用 pthread_detach(thread_id)(非阻塞,可立即返回) 。这将该子线程的状态设置为detached,则该线程运行结束后会自动释放所有资源。

12.4 多线程程序中的共享变量

对于程序员来说,尤其是java程序员,多线程很有吸引力的一个方面是很容易共享变量,而且程序的效率很高。但是需要了解线程的基础内存模型、根据对应的模型,内存的变量实例是如何映射过去的、

12.4.1 线程内存模型

每个线程有自己独立的线程上下文,包括线程ID、栈、栈指针(RSP)、程序计数器、条件码和通用目的寄存器值(8个通用的,不包括RSP)。除此之外,进程的其余部分,即其余的整个用户虚拟空间都是共享的——包括只读代码段、读写数据、堆、所有的共享库、所有打开的文件。

一般来说栈是独立的,但是如果线程能够获得别的栈的地址(比如用全局变量),那么仍然是可以读写别的栈的内容的。

12.4.2 将变量映射到内存

C语言根据变量的作用域不同,把它们分配到虚拟内存里面:

  • 全局变量。分配在了虚拟内存的读/写内存。
  • 本地自动变量。定义在函数内部,但是没有static的变量。显然是存放在线程的栈里的。
  • 本地静态变量。定义在函数内部,但是有static的变量。

12.5 用信号量同步线程

12.5.1 进度图

进度图简单来说就是把线程执行的每一步都用横竖坐标表示,然后把那些关键的步骤用方框框起来,这样就可以看两条对应的执行路线,如果这条路线没有穿过那个方框框,就意味着不会发生线程安全问题,否则就有可能会出问题。

12.5.2 信号量

Dijkstra提出了使用信号量来解决同步问题。信号量s是一个非负整数,而且是一个全局变量,而只有两个操作能够操作这个数字:

  • P(s)操作:如果s大于零,那么把s减1,然后返回。如果s是零,那么就需要挂起线程,直到V操作来重启这个线程。
  • V(s)操作:将s加一。如果有任何线程阻塞在P操作上,那么v操作会重启其中的一个。

PV操作是原子操作,也就是它们是不可打断的。值得注意的是,V操作必须重启一个正在等待的线程,而这也意味着,当多个线程等待同一个信号量的时候,完全无法预知V操作会重启哪一个线程。

12.5.3 使用信号量来实现互斥

如果将信号量初始化为1,那么就是最常见的二元信号量,也就是俗称的互斥锁(mutex)。而对应的P操作就是加锁操作,而V操作则是解锁操作。由于PV操作自身就保证了不会出现不安全区,所以能够保证不论指令顺序如何,都能正确增加计数器。

12.5.4 利用信号量来调度共享资源

生产者消费者问题

生产者消费者共享一个有n个槽的缓冲区,然后生产者线程放入到缓冲区中,消费者从缓冲区取出数据。其实生产者-消费者的典型应用场景是键盘鼠标这种外设。生产者检测到鼠标和键盘事件,然后把这些事件放入到缓冲区中,然后消费者基于某种优先级从缓冲区中取出这些事件,并且显示在屏幕上。

读者-写者问题

读者只进行数据的读取,写者只进行数据的写入操作。

这个主要看读者和写者之间的优先级高低来决定。一类是读者优先,除非已经把权限交给写者了,否则读者就应该先读。第二类是写者优先,写者准备好了就可以写入。

在java中,使用了更高级别的抽象机制——监视器monitor来控制同步,监视器可以用信号量实现。

12.6 使用线程提高并发性

书中提出了一个计算多个数字和的这么需求,然后希望通过创建线程,每个线程负责其中的一部分求和计算,其实就是在对一个全局共享变量进行加锁操作,然后线程把属于自己这部分加到对应的全局变量中,最后解锁。

这个由于加锁的存在,所以其实效率反而更差。这个例子也说明了,同步的开销是非常非常大的。

真正的做法应该是,给每个线程分配一个空间,这样每个线程可以把自己的那一部分的和存放在空间中,最后进行一次计算即可。

12.7 其他并发问题

12.7.1 线程安全

线程安全的定义非常简单,当且仅当一个函数被多个并发线程反复地调用,都能产生正确的结果,那么就说这个函数是线程安全的。

下面四个线程不安全的函数类:

  • 不保护共享变量。最典型的就是对全局变量进行自增操作了。解决办法很容易,只需要上锁即可,缺点也是同步状态的开销比较大,程序性能下降的比较厉害。
  • 保持跨越多个调用的状态的函数。随机数生成函数rand是线程不安全的,因为它依赖于上一次的调用结果,所以在多线程中是不可靠的,因为它依赖于上一次的结果。注:我个人觉得这样反而更加随机了…
  • 函数返回一个指向静态变量的指针。很简单,因为静态变量可能会被别的线程所修改,而指针却无法意识到这一点,就会发生意想不到的错误。
  • 调用一个线程不安全函数的函数。比较简单的解决办法就是手动给这些函数上锁,避免它们线程不安全。

之后还介绍了race和死锁,但是讲的都太简单了…..