20145201 《信息安全系统设计基础》第13周学习总结

教材学习内容总结

第十二章并发编程

如果逻辑流在时间上重叠，那么他们就是并发的，硬件异常处理程序、进程和UNIX信号处理程序都是熟悉的例子。并发现象不仅在内核中存在，在应用级别的程序中也存在。

访问慢速的I/O设备

与人交互

通过推迟工作以降低延迟

服务多个网络客户端

在多核机器上进行并行计算

操作系统提供了三种基本的构造并发程序的方法：

　　1、进程。每个逻辑控制流都是一个进程，由内核来调度和维护；

　　2、I/O多路复用。

　　3、线程。

一、基于进程的并发编程

在接受连接请求之后，服务器派生出一个子进程，这个子进程获得服务器描述表完整的拷贝。子进程关闭它的拷贝中监听描述符3，父进程关闭它的已连接描述符4的拷贝，因为不需要这些描述符了。

基于进程的并发 echo 服务器.父进程派生一个子进程来处理每个新的连接请求：

通常服务器会运行很长的时间，所以我们必须要包括一个 SIGCHLD 处理程序，来回收僵死 (zombie) 子进程的资源。因为当 SIGCHLD 处理程序执行时， SIGCHLD 信号是阻塞的，而 Unix 信号是不排队的，所以 SIGCHLD 处理程序必须准备好回收多个僵死子进程的资源。
父子进程必须关闭它们各自的 connfd 拷贝。这对父进程而言尤为重要，它必须关闭它的已连接描述符，以避免存储器泄漏。
因为套接字的文件表表项中的引用计数，直到父子进程的 connfd 都关闭了，到客户端的连接才会终止。

关于进程的优劣：
进程能够共享文件表，但不共享用户地址空间。

二、基于I/O多路复用的并发编程

1、面对困境——服务器必须响应两个互相独立的I/O事件：1）网络客户端发起的连接请求 2）用户在键盘上键入的命令，解决的办法是I/O多路复用技术。
基本思想是，使用select函数，要求内核挂起进程，只有在一个或多个I/O事件发生后，才将控制返回给应用程序。

select函数：

select函数处理类型为fd_set的集合，即描述符集合，并在逻辑上描述为一个大小为n的位向量，每一位b[k]对应描述符k，但当且仅当b[k]=1，描述符k才表明是描述符集合的一个元素。

使用select函数的过程如下：
第一步，初始化fd_set集，19~22行；
第二步，调用select，25行；
第三步，根据fd_set集合现在的值，判断是哪种I/O事件，26~31行。

只允许你对描述符集合做的三件事：
①分配他们
②将一个此种类型的变量赋值给另一个变量
③用FD_ZERO、FD_SET、FD_CLR和FD_ISSET宏指令来修改和检查它们

2、基于I/O多路复用的并发事件驱动服务器

I/O多路复用可以用做并发事件驱动程序的基础，在事件驱动程序中，流是因为某种事件而前进的，一般概念是把逻辑流模型化为状态机。一个状态机就是一组状态、输入事件和转移。

并发事件驱动程序中echo服务器中逻辑流的状态机，如下图所示：

3.I/O多路复用技术的优劣

优点
相较基于进程的设计，给了程序员更多的对程序程序的控制
运行在单一进程上下文中，所以每个逻辑流都可以访问该进程的全部地址空间，共享数据容易实现
可以使用GDB调试
高效
缺点
编码复杂
不能充分利用多核处理器

三、基于线程的并发编程
线程：运行在进程上下文中的逻辑流。线程由内核自动调度，每个线程都有它自己的线程上下文。
线程上下文包括:一个唯一的整数线程ID——TID、栈、栈指针、程序计数器、通用目的寄存器、条件码

线程执行模型
多线程的执行模型在某些方面和多进程的执行模型相似。每个进程开始生命周期时都是单一线程，这个线程称为主线程。在某一时刻，主线程创建一个对等线程，从在此刻开始，两个线程就并发地运行。
Posix线程

Posix线程是C程序中处理线程的一个标准接口。基本用法是：
线程的代码和本地数据被封装在一个线程例程中
每个线程例程都以一个通用指针为输入，并返回一个通用指针。

创建线程
调用pthread_create函数来创建其他线程

 # include <pthread.h>
typedef void *(func)(void *);

int pthread_create(pthread_t *tid, pthread_attr_t *attr, func *f, void *arg);

返回：成功返回0，出错返回非0

pthread_create函数创建一个新的线程，带着一个输入变量arg，在新线程的上下文运行线程例程f。
attr默认为NULL
参数tid中包含新创建线程的ID

新线程调用pthread_self函数来获得自己的线程ID

#include <pthread.h>

pthread_t pthread_self(void);

返回调用者的线程ID（TID）

终止线程

终止线程的几个方式：

①当顶层的线程例程返回时，线程会隐式终止；

②线程调用pthread_exit函数，线程会显示终止；如果主线程调用pthread_exit，它会等到所有其他对等线程终止，然后再终止主线程和整个线程，返回值为thread_return；
pthread_exit函数

#include <pthread.h>

void pthread_exit(void *thread_return);
若成功返回0，出错为非0

③某个对等线程调用exut函数，则函数终止进程和所有与该进程相关的线程；

④另一个对等线程调用以当前ID为参数的函数ptherad_cancel来终止当前线程。

#include <pthread.h>

void pthread_cancle(pthread_t tid);
若成功返回0，出错为非0

回收已终止线程的资源
调用pthread_join函数：

这个函数会阻塞，直到线程tid终止，将线程例程返回的(void*)指针赋值为thread_return指向的位置，然后回收已终止线程占用的所有存储器资源

分离线程

在任何一个时间点上，线程是可结合的，或是分离的。

一个可结合的线程能够被其他线程回收其资源和杀死，在被其他线程回收之前，它的存储其资源是没有被释放的；相反，一个分离的线程是不能被其他线程回收或杀死的。它的存储器资源是在它终止时系统自动释放的。默认情况下，线程被创建成可结合的。但现实程序中，有很好的理由要使用分离线程。

初始化线程：pthread_once函数

一个基于线程的并发服务器：

以上程序可能会出错，因为在对等线程的赋值语句和主线程的accept的语句见引入了竞争——如果赋值语句在下一个accept之前完成，则不会出错；如果赋值语句是在accept之后完成，那么对等线程的局部变量connfd就得到下一次连接的描述符。解决办法是，必须将每个accept返回的描述符分配到它自己的动态分配的存储器块（21~22行）
32行：动态内存空间释放，释放那个指向动态内存的指针即可，不一定非要是malloc当时生成的指针

四、多线程程序中的共享变量

每个线程都有它自己独自的线程上下文，包括线程ID、栈、栈指针、程序计数器、条件码和通用目的寄存器值。每个线程和其他线程一起共享进程上下文的剩余部分。寄存器是从不共享的，而虚拟存储器总是共享的。线程化的c程序中变量根据它们的存储器类型被映射到虚拟存储器：全局变量，本地自动变量（不共享），本地静态变量。

五、用信号量同步线程
共享变量引入了同步错误。
一般而言，没有办法预测操作系统是否将为你的线程选择一个正确的顺序。

进度图
借助进度图
1.进度图是将n个并发线程的执行模型化为一条n维笛卡尔空间中的轨迹线，原点对应于没有任何线程完成一条指令的初始状态。
当n=2时，状态比较简单，是比较熟悉的二维坐标图，横纵坐标各代表一个线程，而转换被表示为有向边

2.进度图将指令执行模型化为从一种状态到另一种状态的转换(transition)。转换被表示为一条从一点到相邻点的有向边。合法的转换是向右(线程 1 中的一条指令完成〉或者向上(线程 2 中的一条指令完成)的。两条指令不能在同一时刻完成一一对角线转换是不允许的。程序决不会反向运行，所以向下或者向左移动的转换也是不合法的。

3.一个程序的执行历史被模型化为状态空间中的一条轨迹线。

4.临界区：对于线程i，操作共享变量cnt内容的指令L,U,S构成了一个关于共享变量cnt的临界区。
不安全区：两个临界区的交集形成的状态
安全轨迹线：绕开不安全区的轨迹线
绕开不安全区的轨迹线叫做安全轨迹线 (safe trajectory)。相反，接触到任何不安全区的轨迹线就叫做不安全轨迹线 (unsafe trajectory)。

信号量
1.一种解决同步不同执行线程问题的方法，这种方法是基于一种叫做信号量 (semaphore) 的特殊类型变量的。信号量 s 是具有非负整数值的全局变量，只能由两种特殊的操作来处理，这两种操作称为 P 和 V:
①P(s):如果s是非零的，那么P将s减1，并且立即返回。如果s为零，那么就挂起这个线程，直到s变为非零，而一个V操作会重启这个线程。在重启之后，P 操作将s减1，并将控制返回给调用者。
②V(s):V操作将s加1。如果有任何线程阻塞在P 操作等待s变成非零，那么V操作会重启这些线程中的一个，然后该线程将s减1，完成它的P操作。

2.信号量的函数：

3.sem_init 函数将信号量 sem 初始化为 value. 每个信号量在使用前必须初始化。针对我们的目的，中间的参数总是0。程序分别通过调用 sem_wait 和 sem_post 函数来执行P和V操作。

4.P和V的包装函数：

使用信号量来实现互斥

基本思想：将每个共享变量（或者一组相关的共享变量）与一个信号量s（初始为1）联系起来，然后用P和V操作将相应的临界区包围起来。

概念：

二元信号量：用这种方式来保护共享变量的信号量叫做二元信号量，取值总是0或者1.
互斥锁：以提供互斥为目的的二元信号量
加锁：对一个互斥锁执行P操作
解锁；对一个互斥锁执行V操作
计数信号量：被用作一组可用资源的计数器的信号量
禁止区：由于信号量的不变性，没有实际可能的轨迹能够包含禁止区中的状态。

利用信号量来调度共享资源
信号量有两个作用：
实现互斥
调度共享资源

两个经典例子：
生产者-消费者问题，和读者-写者问题

六、使用线程提高并行性
1.顺序、并发和并行程序集合之间的关系：

2.并行程序常常被写为每个核上只运行一个线程。
3.并行程序的加速比通常定义为：

p 是处理器核的数量，凡是在 k个核上的运行时间。这个公式有时称为强扩展 (strong scaling)。当 T1 是程序顺序执行版本的执行时间时， Sp 称为绝对加速比.(absolute speedup)。当 T1 是程序并行版本在一个核上的执行时间时， Sp 称为相对加速比 (relative speedup)。绝对加速比比相对加速比能更真实地衡量并行的好处。
4.效率，定义为:

通常表示为范围在 (0， 100] 之间的百分比。效率是对由于并行化造成的开销的衡量。具有高效率的程序比效率低的程序在有用的工作上花费更多的时间，在同步和通信上花费更少的时间。

5.加速比还有另外一面，称为弱扩展 (weak scaling)，在增加处理器数量的同时，增加问题的规模，这样随着处理器数量的增加，每个处理器执行的工作量保持不变。加速比和效率被表达为单位时间完成的工作总量。

七、其他并发问题

线程安全
一个函数被称为线程安全的，当且仅当被多个并发线程反复的调用时，它会一直产生正确的结果。

四个不相交的线程不安全函数类以及应对措施：
不保护共享变量的函数——利用P和V这样的同步操作保护共享变量
保持跨越多个调用的状态的函数——重写，不用任何static数据。
返回指向静态变量的指针的函数——重写；使用加锁-拷贝技术。
调用线程不安全函数的函数

可重入性

可重入函数，其特点在于它们具有这样一种属性:当它们被多个线程调用时，不会引用任何共享数据。
可重入函数通常要比不可重人的线程安全的函数高效一些，因为它们不需要同步操作。更进一步来说，将第 2 类线程不安全函数转化为线程安全函数的唯一方法就是重写它，使之变为可重入的。

1.显式可重入的：

所有函数参数都是传值传递，没有指针，并且所有的数据引用都是本地的自动栈变量，没有引用静态或全剧变量。

2.隐式可重入的：

调用线程小心的传递指向非共享数据的指针。

在线程化的程序中使用已存在的库函数

使用线程不安全函数的可重入版本，名字以“_r”为后缀结尾。

竞争
1.原因：
一个程序的正确性依赖于一个线程要在另一个线程到达y点之前到达它的控制流中的x点。通常发生竞争是因为程序员假定线程会按照某种特殊的轨迹穿过执行状态空间，忘了一条准则规定：线程化的程序必须对任何可行的轨迹线都正确工作。

2.消除竞争：
动态的为每个整数ID分配一个独立的块，并且传递给线程例程一个指向这个块的指针。

死锁
当一个流等待一个永远不会发生的事件时，就会发生死锁。

代码实践

countwithmutex.c

引入互斥锁解决访问冲突的问题，程序首先定义了一个宏PTHREAD_MUTEX_INITIALIZER来静态初始化互斥锁。先创建tidA线程后运行doit函数，利用互斥锁锁定资源，进行计数，执行完毕后解锁。后创建tidB，与tidA交替执行。由于定义的NLOOP值为5000，所以程序最后的输出值为10000.程序的最后还需要分别回收tidA和tidB的资源。

condvar.c
生产者生产和消费者消费交替进行的过程。mutex用于保护资源，wait函数用于等待信号，signal函数用于通知信号,wait函数中有一次对mutex的释放和重新获取操作，因此生产者和消费者并不会出现死锁。
hello_multi.c
world之后换行打印hello，停1秒再打印相同内容，一共循环5次
hello_multi1.c
运行结果一直输出hello99
hello_single.c
先只运行print_msg("hello");
每隔一秒在屏幕上打印一个hello，总共打印5个hello，后输出5个world
incprint.c
最开始定义NUM=5，输出的count=1~5间隔一秒
twordcount1
用法：./twordcount1 [文件1] [文件2]
用来统计文件1及文件2两个文件的总字数
运行结果：
twordcount1：

twordcount2：

twordcount3.c：
先统计两个文件各自的字数，再统计两个的总字数
twordcount4.c
先输出两个文件各自的信息和字数，再统计两个文件的总字数

代码调试中的问题和解决过程

countwithmutex.c

编译时报错。发现pthread库不是linux系统默认的库，因此pthread_creat创建线程时，在编译中要加上-lpthread参数。

hello_multi.c
如果要打印5个完整的helloworld 修改代码

结果如下

其他

本周内容我发现有很多在操作系统课程中已经讲过，这次再学习更多是从代码的角度。不过认为会更抽象了一些。
进度图的引入，让我对线程并发的理解更清晰了，图像还是比较直观的。
现在所学的这些专业课相辅相成，互相促进理解，这样使得学习起来更轻松，也更全面。

本周代码托管截图

代码链接

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）	重要成长
目标	5000行	30篇	400小时
第一周	100/100	2/2	25/25	安装了虚拟机并学习掌握核心的linux命令
第二周	100/200	1/3	30/55	虚拟机上的C语言编程
第三周	150/350	1/4	10/65	计算机中信息的表示和运算
第四周	0/350	0/4	3/68	复习前几周内容
第五周	75/420	1/5	20/88	程序的机器级表示
第六周	125/545	1/6	20/108	Y86指令硬件语言控制HCL
第七周	72/617	1/7	20/128	磁盘存储器相关结构
第八周	0/617	2/9	20/148	期中总结
第九周	185/802	2/11	25/173	系统级的输入输出
第十周	669/1472	2/13	20/193	重点代码的学习
第十一周	669/1472	2/15	35/228	process代码的学习
第十二周	20/1492	3/18	35/228	前几周代码复习
第十三周	808/2300	1/19	35/228	网络编程、并发、进程、多线程