进程和线程的区别

  1. 进程是资源的分配和调度的一个独立单元，而线程是CPU调度的基本单元。
  2. 同一个进程中可以包括多个线程，并且线程共享整个进程的资源（寄存器、堆栈、上下文），一个进程至少包括一个线程。
  3. 进程的创建调用fork或者vfork，而线程的创建调用pthread_create，进程结束后它拥有的所有线程都将销毁，而线程的结束不会影响同个进程中的其他线程的结束。
  4. 线程是轻量级的进程，它的创建和销毁所需要的时间比进程小很多，所有操作系统中的执行功能都是创建线程去完成的。
  5. 线程中执行时一般都要进行同步和互斥，因为他们共享同一进程的所有资源。
  6. 线程有自己的私有属性TCB，线程id，寄存器、硬件上下文，而进程也有自己的私有属性进程控制块PCB，这些私有属性是不被共享的，用来标示一个进程或一个线程的标志。

线程和协程的区别

协程是一种用户态的轻量级线程，协程的调度完全由用户控制。

  1. 一个线程可以多个协程，一个进程也可以单独拥有多个协程，这样python中则能使用多核CPU。
  2. 线程进程都是同步机制，而协程则是异步。
  3. 协程能保留上一次调用时的状态，每次过程重入时，就相当于进入上一次调用的状态。

进程间通信的方式

  • 管道
    速度慢，容量有限，只有父子进程能通讯。
  • FIFO
    FIFO，也称为命名管道，它是一种文件类型。任何进程间都能通讯，但速度慢。
    特点：
    1）FIFO可以在无关的进程之间交换数据，与无名管道不同。
    2）FIFO有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中。
  • 消息队列
    容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题。
  • 信号量
    不能传递复杂消息，只能用来同步。
  • Socket
    使用网络进行交互。
  • 共享内存区
    共享内存是分配一块能被其他进程访问的内存，实现是通过将内存映射到共享它的进程的地址空间，使这些进程间的数据传送不再涉及内核，即进程间通信不需要通过进入内核的系统调用实现。共享内存几乎没有上限，它也不局限于父子进程，因为内存是共享的，不存在单向的限制；最大的问题就是需要应用程序自己实现互斥。
    最大优点：数据赋值只需2次，一次是从输入文件到共享内存区，一次是从共享内存区到输出文件。其他的通信方式需要四次：服务器将输入文件读入自己的进程空间，再从自己的进程空间写入管道/消息队列等；客户进程从管道/消息队列读出数据到自己的进程空间，最后输出到用户指定的文件中。因此共享内存是最快的进程间通信方式，因为它不涉及内存的交互，所以效率很高。

    线程间通讯方式

  1. volatile;
  2. Object的wait()与notify()；
  3. 并发工具类，如CountDownLatch;
  4. 基本LockSupport实现线程间的阻塞和唤醒。

    线程共享与独占的资源

共享内容

代码段、数据段、堆空间、进程打开的文件描述符、进程的当前目录以及进程的用户ID和组ID。

独占内容

栈、线程ID、寄存器的值、错误返回码以及线程的信号屏蔽码。

作业调度算法

  • 先来先服务调度算法
    按作业到达的先后次序进行调度。
  • 短作业优先调度算法
    优先调度运行时间最短的作业。
  • 响应比高者优先调度算法
    响应比R=1+W/T，W为作业在后备状态队列中的等待时间，T为该作业估计需要的执行时间。
  • 轮转法
    将CPU的处理时间分成固定大小的时间片，时间片长度q的选择是根据系统对相应时间的要求R和就绪队列中所允许的最大进程数Nmax确定的：q=R/Nmax。
  • 优先级法
    根据事先设置好的优先级进行调度。

进程分配的内存空间

  • 栈区：由编译器自动分配和释放，存放函数的参数值，局部变量的值等。
  • 堆区：一般有程序员分配和释放，若程序员不释放，程序结束后可能有OS回收。线程共享。
  • 全局区（静态区static）：全局变量和静态变量存储在这一区域，初始化的全局变量和静态变量在这一区域，未初始化的全局变量和未初始化的静态变量在相邻的另一区域。程序结束后由系统释放。
  • 文字常量区：常量字符串存放在这一区域。程序结束后由系统释放。
  • 程序代码区：存放函数体的二进制代码。

存储管理

主要有页式管理、段式管理和段页式管理。

  • 页式管理
    基本原理是将各进程的虚拟空间划分为若干个长度相等的页。把内存空间按页的大小划分为片或者页面，然后把页式虚拟地址与内存地址建立一一对应的页表，并用相应的硬件地址转换机构来解决离散地址变换问题。
    优点：没有外碎片，每个内碎片不超过页的大小。
    缺点：程序全部装入内存，要求有相应的硬件支持，如地址变换机构缺页中断的产生和选择淘汰页面等都要求有相应的硬件支持。增加了机器成本和系统开销。

    快表

    CPU每次要存取一个数据，都要两次访问内存（访问页表、访问实际物理地址）。为提高地址变换速度，增设一个具有并行查询能力的特殊高速缓冲存储器，称为“联想存储器”或“快表”，存放当前访问的页表项。

  • 段式管理
    基本思想是把程序按内容或过程函数关系分成段，每段有自己的名字。一个用户作业或者进程所包含的段对应一个二维线性虚拟空间，也就是一个二维虚拟存储器。段式管理程序以段为单位分配内存，然后通过地址映射机构把段式虚拟地址转换为实际内存物理地址。
    优点：1）具有逻辑独立性，易于维护，也便于多道程序共享。2）段长可以动态改变，允许自由调度。3）方便编程。
    缺点：会产生碎片。
  • 段页式管理
    先分段，后分页。系统必须为每个作业或者进程建立一张段表以管理内存分配与释放、缺段处理等。另外由于一个段又被划分为若干个页，每个段必须建立一张页表以把段中的虚页变换为内存中的实际页面。显然与页式管理时相同，页表也要有相应的实现缺页中断处理和页面保护等功能的表项。
    段页式管理是段式管理和页式管理相结合而成，具有两者的优点。缺点是，由于管理软件的增加，复杂性和开销也增加。另外需要的硬件以及占用的内存也有所增加，使得执行速度下降。

页面置换算法/内存调度

  • 随机淘汰算法
  • 轮转法
  • 最佳置换算法（OPT）
    这是一种理想情况下的页面置换算法，但实际上是不可能实现的。该算法的基本思想是：发生缺页时，有些页面在内存中，其中有一页将很快被访问（也包含紧接着的下一条指令的那页），而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可 [1] 以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法只是简单地规定：标记最大的页应该被置换。
  • 先进先出置换算法（FIFO）
    最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。

  • 最近最久未使用算法（LRU）
    它的实质是，当需要置换一页时，选择在之前一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法。java使用LinkedList实现LRU算法： 

    1. /**
    2. * className: LRUCache
    3. * description: 用双向链表实现LRU
    4. * 链表尾表示最近被访问的元素，越靠近链表头表示越早之前被访问的元素.
    5. *
    6. * @author lamar
    7. * @version 1.0
    8. * @date 2020/2/29 22:52
    9. */
    10. public class LRUCache {
    11.  private LinkedList<Node> cache;
    13.  private int capacity;
    15.  private LRUCache(int capacity) {
    16.      this.cache = new LinkedList<>();
    17.      this.capacity = capacity;
    18.  }
    20.  public int get(int key) {
    21.      Iterator<Node> iterator = cache.iterator();
    22.      int result = -1;
    23.      while (iterator.hasNext()) {
    24.          Node node = iterator.next();
    25.          if (node.key == key) {
    26.              result = node.val;
    27.              iterator.remove();
    28.              // 添加到链表尾部
    29.              put(key, result);
    30.              break;
    31.          }
    32.      }
    33.      return result;
    34.  }
    36.  private void put(int key, int value) {
    37.      // 遍历，如果存在，直接删除
    38.      Iterator<Node> iterator = cache.iterator();
    39.      while (iterator.hasNext()) {
    40.          Node node = iterator.next();
    41.          if (node.key == key) {
    42.              iterator.remove();
    43.              break;
    44.          }
    45.      }
    46.      // 找不到且容量已满，删除链表头部
    47.      if (capacity == cache.size()) {
    48.          cache.removeFirst();
    49.      }
    50.      // 添加到链表尾部
    51.      cache.add(new Node(key, value));
    52.  }
    54.  class Node {
    55.      int key;
    56.      int val;
    58.      Node(int key, int val) {
    59.          this.key = key;
    60.          this.val = val;
    61.      }
    62.  }
    63. }

死锁条件与解决方式

死锁概念及产生原理

概念：多个并发进程因争夺系统资源而产生相互等待的现象。

原理：当一组进程中的每个进程都在等待某个事件发生，而只有这组进程中的其他进程才能触发该事件，这就称这组进程发生了死锁。

本质原因：

  • 系统资源有限
  • 进程推进顺序不合理

必要条件

  1. 互斥条件：一个资源每次只能被一个进程使用。
  2. 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
  3. 不剥夺条件：进程已获得的资源，在未使用完之前，不能强行剥夺。
  4. 循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。

死锁预防

  • 破坏请求与保持条件
    所有的进程在开始运行之前，必须一次性地申请其在整个运行过程中所需要的全部资源。
  • 破坏不可剥夺条件
    当一个已经持有了一些资源的进程在提出新的资源请求没有得到满足时，它必须释放已经保持的所有资源，待以后需要使用的时候再重新申请。会很大程度上影响系统吞吐量。
  • 破坏循环等待条件
    可以通过定义资源类型的线性顺序来预防，可将每个资源编号，当一个进程占有编号为i的资源时，那么它下一次申请资源只能申请编号大于i的资源。

死锁避免

死锁避免是利用额外的检验信息，在分配资源时判断是否会出现死锁，只在不会出现死锁的情况下才分配资源。

两种避免办法：

  1. 如果一个进程的请求会导致死锁，则不启动该进程。
  2. 如果一个进程的增加资源请求会导致死锁，则拒绝该申请。

避免死锁的具体实现通常利用银行家算法。

死锁的检测与解除

常用的接触死锁的方法：

  1. 抢占资源：从一个或多个进程中抢占足够数量的资源分配给死锁进程，以解除死锁状态。

  2. 终止（或撤销）进程：终止或撤销系统中的一个或多个死锁进程，直至打破死锁状态。

    死锁避免可操作

  3. 避免一个线程同时获取多个锁；

  4. 避免一个线程在锁内同时占用多个资源，尽量保证每个锁只占用一个资源；
  5. 尝试使用定时锁，使用lock.tryLock来替代使用内部锁机制；
  6. 对于数据库锁，加锁和解锁必须在一个数据库连接里，否则会出现解锁失败的情况。

fork()系统调用

fork()的作用就是创建一个该进程下的子进程，在其exit 或 exec之前，和他共享代码。

  • fork系统调用之后，父进程和子进程交替执行，并且它们处于不同空间中。
  • fork()函数的一次调用返回2次返回，此时二个进程处于独立的空间，它们各自执行着自己的东西,不产生冲突，所以返回2次。创建成功后，对于父进程来说是返回子进程的ID，而对于子进程来说就是返回0。而至于是先子进程还是父进程先执行,这没有确切的规定,是随机的。创建失败返回-1。
  • fork()的子执行过程在fork()之后并不是从头开始,因为在fork()之前,父进程已经为子进程搭建好了运行环境了。

exec()

fork会创建一个子进程。子进程的是父进程的副本。

exec函数的作用就是：装载一个新的程序（可执行映像）覆盖当前进程内存空间中的映像，从而执行不同的任务。

  • exec系列函数在执行时会直接替换掉当前进程的地址空间。

Copy-On-Write

写时复制， 是一种计算机程序设计领域的优化策略，多个调用者可以请求相同的资源，只有修改时，系统会复制一份副本给要修改的调用者，而其他调用者看到的仍是最初的资源。

联系fork()

如果按传统的做法，会直接将父进程的数据拷贝到子进程中，拷贝完之后，父进程和子进程之间的数据段和堆栈是相互独立的。但是子进程往往会执行自己想要实现的功能，从而清空父进程的数据，导致拷贝失效。于是就有了COW。

  • fork创建出的子进程，与父进程共享内存空间。也就是说，如果子进程不对内存空间进行写入操作的话，内存空间中的数据并不会复制给子进程，这样创建子进程的速度就很快了！(不用复制，直接引用父进程的物理空间)。
  • 并且如果在fork函数返回之后，子进程第一时间exec一个新的可执行映像，那么也不会浪费时间和内存空间了。

优点

  • COW技术可减少分配和复制大量资源时带来的瞬间延时。
  • COW技术可减少不必要的资源分配。比如fork进程时，并不是所有的页面都需要复制，父进程的代码段和只读数据段都不被允许修改，所以无需复制。

缺点

如果在fork()之后，父子进程都还需要继续进行写操作，那么会产生大量的分页错误(页异常中断page-fault)，这样就得不偿失。

僵尸进程和孤儿进程

僵尸进程

创建子进程后，如果子进程比父进程早结束，而且父进程迟迟没有结束，那么子进程就会进入一个Z状态——僵尸状态，并且占用系统资源。僵尸状态对操作系统是有害的，kill -9 也无法处理，只能等父进程来处理。

解决方法：

  • 进程等待
    让父进程等待子进程，子进程工作完父进程再执行工作。
  • 托付给Init进程
    用子进程再创建一个子进程，此时子进程就成了 子进程的子进程 的父进程，然后让子进程结束，那么 子进程的子进程 接受本应该子进程接受的任务，而且 子进程的子进程 此时成了孤儿进程，他的生死父进程也不会过问，交给1号进程init来解决。

孤儿进程

子进程还在世的时候父进程却结束了，对系统无害。init进程会收养孤儿进程，孤儿进程结束时第一时间回收他们的退出信息，保证他们不一直成为僵尸进程。

系统调用、异常和中断

  • 系统调用：应用程序主动向操作系统发出的服务请求。
  • 异常：非法指令或其他原因导致当前指令执行失败后的处理请求。
  • 中断：来自硬件设备的处理请求。

无论任何一种都可能发生用户态到内核态之间的转换。

用户态和内核态

内核态与用户态是操作系统的两种运行级别，当程序运行在3级特权级上时，就可以称之为运行在用户态。因为这是最低特权级，是普通的用户进程运行的特权级，大部分用户直接面对的程序都是运行在用户态，在其需要操作系统帮助完成某些它没有权力和能力完成的工作时就会切换到内核态；当程序运行在0级特权级上时，就可以称之为运行在内核态。
区别：

  • 处于用户态执行时，进程所能访问的内存空间和对象受到限制，其所处于占有的处理器是可被抢占的。
  • 处于内核态执行时，则能访问所有的内存空间和对象，且所占有的处理器是不允许被抢占的。

这个状态，连最无情的kill -9 也无法处理，只能等父进程来处理。

操作系统执行一个程序的过程

以helloworld为例：

  1. 使用Javac命令进行编译，编译通过后生成对应的字节码文件（.class结尾）；
  2. 启动JVM，运行类加载器；
  3. 类加载器找到对应的字节码文件，找到后装载到JVM中；
  4. JVM中有解释器，通过解释器将字节码文件转换为二进制文件，交给操作系统；
  5. 操作系统执行二进制文件与硬件交互，运行成功。

    虚拟内存

    每个进程创建加载的时候，会被分配一个大小为4G的连续的虚拟地址空间，虚拟的意思就是，其实这个地址空间是不存在的，仅仅是每个进程“认为”自己拥有4G的内存，而实际上，它用了多少空间，操作系统就在磁盘上划出多少空间给它，等到进程真正运行的时候，需要某些数据并且数据不在物理内存中，才会触发缺页异常，进行数据拷贝。
    更准确一点的说，系统将虚拟内存分割为称为虚拟页(Virtual Page,VP)的大小固定的块，每个虚拟页的大小为P = 2^p字节，类似地，物理内存被分割为物理页(Physical Page,PP)，大小也为P字节（物理页也称为页帧(page frame)）。
    在任意时刻，虚拟页面都分为互不相交的三种：
  • 未分配的：系统还未分配（或者创建）的页。未分配的块没有任何数据和它们相关联，因此也就不占用任何磁盘空间
  • 未缓存的：没有缓存在物理存储器中的已分配页
  • 缓存的：当前缓存在物理存储器中的已分配页

下图是一个示例：
image.png
操作系统向进程描述了一个完整的连续的虚拟地址空间供进程使用，但是在物理内存中进程数据的存储采用离散式存储(提高内存利用率)，但是其实虚拟内存和物理内存之间的关系并不像上图中那样直接，其中还需要使用页表映射虚拟地址与物理地址的映射关系，并且通过页表实现内存访问控制。这个页表又是何方神圣？

页表

页表是一种特殊的数据结构，存放着各个虚拟页的状态，是否映射，是否缓存。进程要知道哪些内存地址上的数据在物理内存上，哪些不在，还有在物理内存上的哪里，这就需要用页表来记录。页表的每一个表项分为两部分，第一部分记录此页是否在物理内存上，第二部分记录物理内存页的地址(如果在的话)。当进程访问某个虚拟地址，就会先去看页表，如果发现对应的数据不在物理内存中，则发生缺页异常。
image.png

工作原理

当一个进程试图访问虚拟地址空间中的某个数据时，会经历下面两种情况的过程：

  1. CPU想访问某个虚拟内存地址，找到进程对应的页表中的条目，判断有效位， 如果有效位为1，说明在页表条目中的物理内存地址不为空，根据物理内存地址，访问物理内存中的内容，返回
  2. CPU想访问某个虚拟内存地址，找到进程对应的页表中的条目，判断有效位，如果有效位为0，但页表条目中还有地址，这个地址是磁盘空间的地址，这时触发缺页异常，系统把物理内存中的一些数据拷贝到磁盘上，腾出所需的空间，并且更新页表。此时重新执行访问之前虚拟内存的指令，就会发现变成了情况1。

    为什么要使用虚拟内存?

    直接使用物理内存有如下的问题：
    1、内存空间利用率的问题
    各个进程对内存的使用会导致内存碎片化，当要用malloc分配一块很大的内存空间时，可能会出现虽然有足够多的空闲物理内存，却没有足够大的连续空闲内存这种情况，东一块西一块的内存碎片就被浪费掉了。
    2、读写内存的安全性问题
    物理内存本身是不限制访问的，任何地址都可以读写，而现代操作系统需要实现不同的页面具有不同的访问权限，例如只读的数据等等。
    3、进程间的安全问题
    各个进程之间没有独立的地址空间，一个进程由于执行错误指令或是恶意代码都可以直接修改其它进程的数据，甚至修改内核地址空间的数据，这是操作系统所不愿看到的。
    4、内存读写的效率问题
    当多个进程同时运行，需要分配给进程的内存总和大于实际可用的物理内存时，需要将其他程序暂时拷贝到硬盘当中，然后将新的程序装入内存运行。由于大量的数据频繁装入装出，内存的使用效率会非常低。

    PCB

    PCB使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位， 一个能与其它进程并发执行的进程。或者说， OS 是根据 PCB 来对并发执行的进程进行控制和管理的，包括进程同步，通信，访问文件，进程状态（暂停等）。
    image.png
    系统创建进程时，随之创建一个PCB，进程结束时回收PCB。PCB经常被OS的多个模块读或修改（调度程序，资源分配程序，中断处理程序，监督和分析程序）。故PCB常驻于OS专门开辟的PCB区。

    内容

    1、进程标识符
    作用： 唯一标识一个进程，一个进程有两种标识符。
  • 内部标识符
    在操作系统中唯一，主要为了方便系统调用。
  • 外部标识符
    用户（进程）在访问该进程时使用。为了描述进程的亲缘关系，还应设置父进程标识及子进程标识，还可以设置用户标识。

2、处理机（CPU）状态
CPU的状态信息存储于CPU中的各种寄存器中，CPU在运行时，许多信息放在寄存器中，当CPU被中断时，所有的CPU信息应从寄存器保存到PCB中，以便该进程重新执行时，能从断点继续执行。

  • 寄存器种类
    • 通用寄存器
      又称用户可视寄存器，用户程序可以访问，暂存信息。
    • 指令计数器
      存放了要访问下一条指令的地址。
    • 程序状态字PSW
      含有状态信息，如条件码，执行方式，中断屏蔽标志
    • 用户栈指针
      每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。

3、进程调度信息

  • 进程状态
    进程的当前状态，作为进程调度和兑换时的依据。
  • 进程优先级
    CPU执行进程的优先程度。
  • 调度相关的其他信息
    与进程的调度算法相关，比如：进程已等待CPU的时间总和，进程已执行的时间总和。
  • 事件
    进程的阻塞原因

4、进程控制信息

  • 程序和数据的地址
    进程的程序和数据所在外存的首地址，进程再次调度时从PCB找出该信息。
  • 进程同步和通信机制
    实现进程同步和进程通信的必须机制，如消息队列指针，信号量。
  • 资源清单
    一张出CPU以外的，进程所需要的全部资源及已经分配到该进程的资源清单。
  • 链接指针
    本进程的PCB所在队列中的下一个进程PCB的首地址。

参考链接：https://www.jianshu.com/p/80a27dd874bd

TCB

操作系统中一个线程对应着一个TCB（Thread Control Block），叫做线程控制模块，控制着线程的运行和调度。

内容

  1. threadID：线程的唯一标识；
  2. status：线程的运行状态；
  3. register：线程关于CPU中寄存器的情况；
  4. PC程序计数器：线程执行的下一条指令的地址；
  5. 优先级：线程在操作系统调度的时候的优先级；
  6. 线程的专属存储区：线程单独的存储区域；
  7. 用户栈：线程执行的用户方法栈，用来保存线程当前执行的用户方法的信息；

  8. 内核栈：线程执行的内核方法栈，用来保存线程当前执行的内核方法信息。

    文件读写基本流程

    读文件
    1、进程调用库函数向内核发起读文件请求；
    2、内核通过检查进程的文件描述符定位到虚拟文件系统的已打开文件列表表项；
    3、调用该文件可用的系统调用函数read()
    3、read()函数通过文件表项链接到目录项模块，根据传入的文件路径，在目录项模块中检索，找到该文件的inode；
    4、在inode中，通过文件内容偏移量计算出要读取的页；
    5、通过inode找到文件对应的address_space；
    6、在address_space中访问该文件的页缓存树，查找对应的页缓存结点：

  9. 如果页缓存命中，那么直接返回文件内容；

  10. 如果页缓存缺失，那么产生一个页缺失异常，创建一个页缓存页，同时通过inode找到文件该页的磁盘地址，读取相应的页填充该缓存页；重新进行第6步查找页缓存；

7、文件内容读取成功。
写文件
前5步和读文件一致，在address_space中查询对应页的页缓存是否存在：
6、如果页缓存命中，直接把文件内容修改更新在页缓存的页中。写文件就结束了。这时候文件修改位于页缓存，并没有写回到磁盘文件中去。
7、如果页缓存缺失，那么产生一个页缺失异常，创建一个页缓存页，同时通过inode找到文件该页的磁盘地址，读取相应的页填充该缓存页。此时缓存页命中，进行第6步。
8、一个页缓存中的页如果被修改，那么会被标记成脏页。脏页需要写回到磁盘中的文件块。有两种方式可以把脏页写回磁盘：
（1）手动调用sync()或者fsync()系统调用把脏页写回
（2）pdflush进程会定时把脏页写回到磁盘
同时注意，脏页不能被置换出内存，如果脏页正在被写回，那么会被设置写回标记，这时候该页就被上锁，其他写请求被阻塞直到锁释放。