二、进程与线程

1.进程

• 1.进程模型：
  • 1.有自己的程序地址空间，程序计数器、寄存器和变量当前值。
  • 2.切换进程的时候程序计数器、寄存器会装载到真正的相应物理硬件上。
  • 3.每个进程的内存是不共享的，进程所要执行的代码被称为程序
• 2.创建进程：
  • 1.UNIX中用fork创建一个新进程，该进程与父进程完全相同，所以fork之后需要设置自己的程序地址空间。
  • 2.Window中创建进程则是直接将新的程序装载进进程中。
• 3.进程终止：正常退出、出错退出、严重错误退出、被其他进程杀死。前两个属于自愿，后两个属于非自愿
• 4.进程的层次结构：UNIX中进程有父子关系，进程及其后裔会组成一个进程组。Window中进程没有父子关系，所有进程地位相同。
• 5.进程状态：
  • 运行态：表现为进程占用CPU，可转化为就绪态（程序调度将CPU片时间交给其他进程）和阻塞态（进程进行IO的时候，该进程会阻塞而挂起）。
  • 就绪态：表现为可以运行，但是CPU片时间还没被分配给该进程。可转化为运行态（CPU片时间被分配给该进程）
  • 阻塞态：表现为等待某个外部事件发生，如等待IO结束或等待网络请求返回。可转化为就绪态（外部事件发生了，此时进程可以继续运行，不过得等待CPU片时间被分配给该进程）
• 6.进程的实现：为了实现进程模型，操作系统维持了一张进程表。表中的每个数据结构（也称进程控制块）就代表一个进程。进程控制块由以下几部分构成：
  • 1.进程管理：寄存器、程序计数器、进程状态、优先级、堆栈指针等等
  • 2.储存管理：代码段指针、数据段指针、堆栈段指针
  • 3.文件管理：根目录、工作目录、用户ID等等
• 7.多道程序设计模型：
  • 多个进程能提高CPU的利用率
  • 由于进程会用IO操作，一旦进行IO操作CPU就会空闲下来
  • 所以假设进程IO的时间占总时间的p，那么n个进程同时IO的概率就是p的n次方。
  • 所以CPU会有1-（p的n次方）的利用率。
  • 我们可以看出n越大，CPU利用率越高

2.线程

• 1.线程：
  • 1.一个进程可以看成一个应用，用户使用应用必然会进行IO操作。此时为了用户体验我们不可能切换到别的进程，我们需要的是让该进程继续响应用户的操作。所以我们需要在一个进程中使用到多个迷你进程，这就是线程。
  • 2.线程比进程更加轻量，创建一个线程的速度是进程的10-100倍
• 2.线程模型：线程共享进程的内存和代码，但是有自己的程序计数器、寄存器、堆栈和本地变量
• 3.POSIX线程：IEEE定义了Pthread，大部分UNIX系统都支持该标准，并实现了一些系统调用来进行对Pthread的操作。
• 4.用户空间线程：将线程包放在用户空间来在一些不支持多线程的系统上模拟多线程。此时每个进程都有自己的线程表以记录线程模型中的数据。这种方式有以下优点
  • 1.当某个线程阻塞的时候，系统不需要去调用内核操作，而是直接使用几个命令就能切换线程，这样的速度比陷入内核快一个数量级。
  • 2.这样的切换，不需要陷阱，不需要上下文切换，也不需要对高速内存缓存进行刷新，所以更加快捷。
  • 3.每个进程制定自己的线程调度算法。
  • 4.这种方式还具有很好的扩展性，由于线程表是分散在各个进程中的，所以避免了内核线程数量巨大而带来的空间问题。
• 5.内核空间线程：操作系统的内核直接支持多线程，线程表放在内核之中。有以下优点
  • 1.在用户线程中单独的进程内部是没有时钟中断的，所以用户线程无法进行轮转调度，但是内核线程可以。
  • 2.用户线程很难实现阻塞系统调用，如果让一个用户线程去调用阻塞系统调用，那么该进程的所有线程都会停止。而内核线程可以方便的检查该进程中还有没有其他线程能够运行。
• 6.混合实现：由程序员确定一个进程中有多少个内核线程，然后对每个线程进行多路复用，此时就将两种线程实现方式取长补短了。

3.进程间通信

• 1.竞争条件：因为进程间不共享内存，所以可以共享一些公共存取区域（如硬盘文件）。此时当两个进程对一起对这个文件进行读写的时候，会产生原子性的问题。
• 2.临界区：为了解决上面一个问题，我们可以将公共存取区域设为临界区，同一时刻只能有一个进程进行访问，这样就解决了刚刚的问题。此时会产生并发效率问题，所以还需要下面几个条件
  • 1.临界区外的进程部阻塞其他进程
  • 2.进程不可无限期等待进入临界区
• 3.互斥方案：
  • 1.屏蔽中断：单CPU实现上面的简单方法是，在每个进程进入临界区后屏蔽所有中断，离开的时候打开所有中断。由于CPU切换是在时钟中断之后，所以此时其他进程不会被切换到临界区内。这种方法有严重的缺点：
    • 1.对于多处理器，无法实现
    • 2.一旦该进程将中断屏蔽之后就不再打开的话，那么系统可能就终止了，所以将中断权利交给用户进程是不明智的。
  • 2.锁变量：类似于信号量，但是还是无法保证原子性
  • 3.peterson解法：
  • 4.TSL指令：硬件支持原子性操作。
• 4.睡眠与唤醒：上面的互斥方案都会出现忙等的情况，此时可以将不使用的进程挂起。参考生产者-消费者问题。
• 5.信号量：可以解决生产者-消费者问题
• 6.互斥量：信号量的简化版，适用于两个进程
• 7.管程：上面两个会产生死锁问题，此可以用这个
• 8.消息传递
• 9.内存屏障

4.调度

• 1.介绍：为了让不同的进程进行合理的运行，需要在不同的时刻将CPU的时间片分给不同的进程，这就是进程的调度。主要有两类：批处理（非抢占）、交互式（抢占）
• 2.批处理的调度：
  • 1.先来先服务
  • 2.最短作业服务
• 3.交互式的调度：
  • 1.轮转调度：每个进程都有固定的时间片进行运行，时间片太长会造成短请求的响应时间长，时间片太短会造成进程切换频繁导致CPU利用率下降
  • 2.优先级调度：按优先级分进程，然后对同优先级的进程使用轮转调度，会造成低优先级的进程饥饿。
  • 3.多级队列
  • 4.最短进程优先

5.经典IPC问题

• 1.哲学家就餐
• 2.读者-写者问题

三、存储管理

2.存储器抽象：地址空间

• 1.地址空间：使用基址寄存器和界限寄存器将每个进程的地址空间映射到物理内存中。
• 2.交换技术：当内存空间不足以放下所有进程的时候，我们需要使用交换技术，将空闲的进程放回磁盘，等待要用的时候就取回。这样一来会造成内存碎块，而且如果进程所需内存会增大，那么就会存在空间不足的问题。
• 3.空闲内存管理：
  • 1.使用位图管理内存，将内存进行划分成块，每个块对应位图中的一个字节。这种方法会浪费一定量的内存，并且要找出连续的空闲空间比较麻烦。
  • 2.链表内存管理：维护空闲内存链表和已分配内存链表

3.虚拟内存

• 1.介绍：由于软件的容量持续变大，内存常常不能放下一个完整的程序，所以就使用这个技术来替代交换技术，使用虚拟内存可以只将程序的一部分放入内存中其他部分可以放在磁盘上。
• 2.基本思想：每个程序有自己的地址空间，被分为多个块。并不是所以块都要在内存中才能运行程序，当程序引用到在物理内存中的地址空间的时候，硬件会去执行该引用的映射。而如果程序引用的部分不在物理内存中的地址空间的时候，操作系统需要将缺失的部分装入物理内存中并重新执行指令。
• 3.分页：如一个计算机可以产生16位的地址，虽然可以编写64k的程序，但是此时物理内存只有32k。这时候可以将64k的虚拟空间分成固定大小的页面，在物理内存中只要装入目前必须的页面就行了，剩下的程序可以有虚拟地址，但是只需要在磁盘上就行。
• 4.页表：一种分页的简单实现，从虚拟地址到物理地址的映射可以分为两部分：1.虚拟地址的页号2.该页上面的偏移量。如果一块虚拟内存导入到了物理内存中，此时虚拟内存上就会标上物理内存的页号，此时我们就可以通过页号找到，某块物理内存。再通过虚拟内存上的偏移量，就能找到物理内存上的实际地址。页表就是一个映射的集合
• 5.加速分页的过程：分页系统需要考虑两个问题：1.映射需要很快。2.如果虚拟内存很大，那么页表也会很大。可以使用TLB来加速虚拟地址到物理地址的转变，除此之外还可以使用多级页表。
• 6.页面置换算法：在缺页的时候操作系统会将一个需要的页面替换进物理内存中，此时就需要通过算法来找到最何时的页面被替换出去。
  • 1.最优页面置换：理想状态下的算法，将最大接下来的指令不会使用到的页面替换出去。
  • 2.最近未使用页面置换：找到所有页面中，最常时间没被使用的页面，替换出去。
  • 3.先进先出页面置换：找出所有页面中，最先被放入物理内存中的页面，替换出去
  • 4.第二次机会页面置换：将2，3结合，找到又没被使用，又最先被放入物理内存中的页面，替换出去
  • 5.时钟页面置换：
  • 6.最近最少使用页面置换：LRU
• 7.分段