进程与线程
进程将一个单独的CPU变成多个虚拟的CPU
2.1 进程
●伪并行：一个瞬间只能运行一个进程，但一段时间内运行多个进程，产生并行的错觉
●多处理器系统：两个或更多CPU，真正的并行
2.1.1进程模型
一个进程是某种类型的活动，有程序，输入，输出，状态。单个处理器被若干进程共享，处理器使用某种调度算法决定进程的切换。
●多道程序设计：(伪)并行中CPU在不同进程中快速的切换
2.1.2进程的创建
4种主要事件会导致进程创建
1.系统初始化
2.正在运行的程序执行了创建进程的系统调用
3.用户请求创建新进程
4.批处理作业的初始化
上面的情形中，新进程都是由于已存在的进程执行了一个用于创建进程的系统调用而创建的，这个进程可以是运行的用户进程，鼠标键盘启动的系统进程等
UNIX中，fork用来创建新进程，父进程会创建一个与调用进程相同的副本(子进程)，两个进程拥有相同的内存映象、环境字符串、打开文件。通常子进程执行execve改变内存映像并运行新的程序。
Windows中，win32函数调用CreateProcess创建进程，把正确的程序装入新的进程。父进程和子进程一开始地址空间就不同。
●守护进程：停留在后台等待被唤醒的进程，如打印
2.1.3进程的终止
进程的终止情况
●自愿：1.正常退出 2.出错退出
●非自愿：1.严重错误 2.被其他进程杀死
2.1.4进程的层次结构
每个进程只有一个父进程，但可以有任意个子进程
●UNIX启动时创建init进程，所有进程都由init创建，整个系统的所有进程都属于以init为根的一棵树。
●Windows中没有进程层次的概念，父进程得到句柄，可以用来控制子进程，但可以传给其他进程。
2.1.5进程的状态
进程的三种状态：
1.运行态(占用CPU)
2.就绪态(可以运行，但是CPU被其他进程占用)
3.阻塞态(等待外部事件转为就绪态)
调度程序决定应当运行哪个进程，何时运行，以及运行多长时间
2.1.6进程的实现
●进程表：由操作系统维护，包含进程状态的重要信息，包括进程由运行态转出必须保存的信息如程序计数器，堆栈指针等等，从而保证进程随后能再次启动，像从未被中断。
2.1.7多道程序设计模型
增加内存来增加同时运行的进程数可以提高CPU利用率。
2.2线程
2.2.1 线程的使用
使用多线程的理由
1.多线程共享同一个地址空间和可用数据，多进程不行
2.线程更轻量级，比进程更容易创建与撤销
3.性能更好，如果存在大量计算和I/O处理，多线程允许这些活动彼此重叠进行，加快速度。
●多线程：可以一边磁盘操作一边运行别的线程
●单线程：Web服务器等待磁盘操作时，服务器就阻塞，不处理任何到来的其它请求。
●有限状态机：启动非阻塞的磁盘操作，磁盘操作时服务器可以接收请求，磁盘的回答和请求哪个先来处理哪个。
阻塞：动作完成之前必须等待，如read阻塞模式，有效输入来之前必须一直等，read非阻塞模式就是就算没有输入也可以立即读。
2.2.2 经典的线程模型
进程把资源集合到一起，线程是CPU上被调度执行的实体。
进程之间是竞争关系，而线程是合作关系，共享资源，相互信任，之间没有保护。
线程的状态转换和进程一样，有阻塞，就绪，运行
每个线程有自己的堆栈，因为每个线程会调用不同的过程，有自己的执行历史，所以需要堆栈。
通常所有的线程都是平等的，有时有父子关系。
线程库过程
●thread_exit：完成工作后退出
●thread_join：阻塞直到特定线程退出
●thread_yield：允许线程放弃CPU让另一个线程运行，因为线程不同于进程，无法利用时钟中断强制让出CPU，只能主动让出CPU。
2.2.3POSIX线程
2.2.4 在用户空间实现线程
2.2.5 在内核中实现线程
用户级线程优点：
1.切换线程比陷入内核切换快很多
2.允许每个进程有自己的调度算法
3.扩展性强
缺点：
1.不能处理好阻塞，阻塞系统调用时会停止所有线程
2.缺页中断问题：程序跳转到不在内存的指令上，内核负责内存，但不知道有用户级线程存在。
3.进程内部没有时钟中断，调度线程难，调用系统时钟中断开销大
4.内核可以运行不同进程内的线程，用户级线程始终运行自己线程中的进程，直到被剥夺CPU
2.2.7 2.2.8 2.2.9未看
2.3进程间通信
进/线程通信考虑的问题
1.如何传递信息(线程中较简单)
2.两个或更多进程在关键活动中不会交叉
3.保持正确的顺序
2.3.1 竞争条件
竞争条件：两个或多个进程读写共享数据，最后的结果取决于进程运行的精确时序。
2.3.2 临界区
●互斥：确保一个进程使用共享变量或文件时，其他进程不能做同样操作。
●临界区：对共享内存进行访问的程序片段称作临界区。两个进程不同时处于临界区就能避免竞争条件。
●好的解决竞争条件的方案：
1.任何两个进程不能同时处于临界区
2.不应对CPU的速度和数量做任何假设
3.临界区外运行的进程不能阻塞其他进程
4.不得使进程无限期等待进入临界区
2.3.3忙等待的互斥
1.屏蔽中断
对于操作系统有用，对于用户不合适
2.锁变量
还会出现和假脱机目录一样的疏漏。
3.严格轮换法
违反了上面的条件3
4.peterson解法
对进程调用enter_region与leave进入与离开临界区。
5.TSL指令/XCHG指令
TSL RX，LOCK称为测试并加锁，该指令结束前其他处理器不允许访问该内存字。执行TSL的CPU将锁住内存总线，防止其他CPU在本指令结束前访问内存。
Peterson与TSL/XCHG解法都是正确的，但都有忙等待的缺点，本质都是：当一个进程想进入临界区时，先检查是否允许进入，若不允许，则该进程将原地等待，直到允许为止。
忙等待浪费CPU时间，也可能引起预想不到的结果。
2.3.4 睡眠与唤醒
sleep和wakeup是进程间通信原语，在无法进入临界区时将阻塞，而不是忙等待。sleep是引起调用进程阻塞的系统调用，即被挂起，wakeup唤醒进程。
生产者-消费者问题中可能出现竞争条件，消费者刚读取count还未判断进入睡眠时切换到了生产者，于是生产者生产并唤醒消费者，消费者并未睡眠，丢失了wakeup信号，下次进入消费者时，从判断进入睡眠开始执行，进入睡眠，生产者生产满了也进入睡眠。
问题的本质在于尚未睡眠进程的wakeup丢失,可以加唤醒等待位弥补。wakeup发给清醒进程时置1，该进程将要睡眠时，如果为1，置0并保持清醒。
2.3.5信号量
用一个整型变量累计唤醒次数供以后使用，信号量的取值可以为0(无保存下来的唤醒操作)或者正值(一个或多个唤醒操作)。
用down和up代替sleep和wakeup，对进程执行down操作时，信号量为0才睡眠，不为0减一。整个down过程的检查数值修改变量以及是否睡眠为原子操作。
●原子操作：不可分割，要么都执行，要么都不执行。单CPU可以屏蔽系统中断来实现，多CPU可以用TSL/XCHG指令来实现。(这里使用指令只需几ms，而使用指令忙等待解决2.3.3的问题需要很长时间)。
●二元信号量：如mutex，初值为1，供两个或多个进程使用，保证同时只有一个进程可以进入临界区，用于互斥。
2.3.6互斥量mutex
互斥量只需一位，有两种状态，解锁和加锁，可以用TSL或XCHG指令实现。
有两个过程，lock与unlock，访问临界区时，调用mutex_lock，如果互斥量解锁，调用成功，可以进入，如果加锁，阻塞，知道临界区内的进/线程调用mutex_unlock。
mutex与enter_region的区别就是进入临界区失败时，前者阻塞，将CPU让出，而后者始终重复测试锁(忙等待)。
进程间如何共享数据？
1.共享数据结构如信号量放在内核中，并且只能通过系统调用访问
2.多数操作系统提供一种方法，让进程间共享部分地址空间。
●快速用户区互斥量futex
实现了基本的锁(像互斥锁)，但避免陷入内核，改善了性能。
进程间共享通用锁变量为一个对齐的32位帧数锁。
●pthread中的互斥量
锁定和解锁的互斥量保护临界区
条件变量：允许线程阻塞，等待一些条件
2.3.7管程
●死锁：使用信号量和互斥量时，很小的错误容易造成大麻烦，如进程一直阻塞下去。
●管程：任一时刻管程中只能有一个活跃进程，这一特性使得管程能有效完成互斥。
2.3.8消息传递
用消息传递的方法而不是共享内存。
设计要点：1.确认，因为消息可能丢失 2.身份认证
2.3.9屏障
应用中划分了若干阶段，除非所有进程都就绪准备下一阶段，否则任何进程都不能进入下一个阶段。可以通过在每个阶段安装屏障来实现。
2.3.10避免锁：读-复制-更新
最快的锁是根本没有锁，没有锁时也不能对共享数据结构进行并发读写进行访问。
读-复制-更新是写操作时复制一份副本对其进行操作，在适当的时机将原数据用副本替换。
2.4 调度
●调度程序：从就绪的进程/线程中选择合适的运行
进程行为：
●计算密集型：大部分时间花在计算上
●I/O密集型：等待I/O上话费很多时间
何时调度：
●抢占式：时钟中断时进行调度
●非抢占式：时钟中断时不会发生调度
调度算法分类：批处理、交互式、实时
线程调度
用户级线程性能更好：不同进程间的线程切换代价高于相同进程的线程切换。
用户级线程可以使用为应用程序定制的线程调度程序。如web服务器中优先运行分派线程。而内核不了解每个线程的作用。
2.5经典的IPC问题
2.5.1哲学家就餐(有限资源竞争)
流行的局域以太网中，两台计算机同时发包，那么每台计算机等待一段随机时间后再尝试，该方案工作良好但不完全稳定，如核电站安全系统中。
使用互斥量时，有性能的局限，5把叉子可以让两位哲学家进餐，而使用互斥量只能允许一位。
2.5.2读者-写者问题(数据库模型)
2.6 有关进程与线程的研究
进程问题已经有了成熟的方案，几乎所有系统都把进程视为容器，用以管理相关资源，如地址空间、线程、打开的文件、权限保护等。
2.7小结