操作系统相关知识回顾与总结(不定期更新)

进程与线程

进程

• 什么是进程？

  进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位；在引入进程实体的概念后，我们可以把传统操作系统中的进程定义为：进程是进程实体的运行过程，是系统进行资源分配和调度的一个基本单位。

• 进程的特征

  1. 动态性
  2. 并发性
  3. 独立性
  4. 异步性
  5. 结构性

• 进程的状态与转换

  1. 运行状态：进程正在处理机上运行。在单处理机环境下，每一时刻最多只有一个进程处于运行态；

  2. 就绪状态：进程已经处于准备运行的状态，即进程获得了除了处理机之外的一切所需资源，一旦得到处理机即可运行；

  3. 阻塞状态，又称等待状态：进程正在等待某一事件而暂停运行，如等待某资源为可用（不包括处理机）或等待输入/输出完成。即使处理机空闲，该进程也不运行；

  4. 创建状态：进程正在被创建，尚未转到就绪状态。创建进程需要多个步骤：首先申请一个空白的PCB，并向PCB中填写一些控制和管理进程的信息，然后由系统为该进程分配运行时所需的资源；最后把该进程转入到就绪状态；

  5. 结束状态：进程正从系统中消失，这可能是进程正常退出或其他原因中断退出运行。进程需要结束运行时，系统首先设置该进程为结束状态，然后再进一步处理资源释放和回收等工作。

     状态转换

     • 就绪状态->运行状态：处于就绪状态的进程被调度后，获得处理机资源（分派处理机时间片），于是进程由就绪状态转换为运行状态；
     • 运行状态->就绪状态：处于运行状态的进程在时间片用完之后，不得不让出处理机，从而进程由运行状态转换为就绪状态。此外，在可剥夺的操作系统中，如果有更高优先级的进程就绪时，调度程序将正执行的进程转换为就绪状态，让更高优先级的进程执行；
     • 运行状态->阻塞状态：当进程请求某一资源（如外设）的使用和分配或等待某一事件的发生（如I/O操作的完成）时，它就从运行状态转换为阻塞状态。进程以系统调用的形式请求操作系统提供服务，这是一种特殊的、由运行用户态程序调用操作系统内核过程的形式；
     • 阻塞状态->就绪状态：当进程等待的事件到来时，如果I/O操作结束或者中断结束时，中断处理程序必须把相应进程的状态由阻塞状态转换为就绪状态。

     需要注意的是，有就绪状态变成阻塞状态是一个主动的行为，而从阻塞状态变为就绪状态是一个被动的行为，需要其他进程的协助。

  ​

  注意区分就绪状态和等待状态

  就绪状态是指进程仅缺少处理机，只要获得处理机资源就立即执行；而等待状态是指进程需要其他资源（除了处理机）或等待某一事件。之所以把处理机和其它资源划分开，是因为在分时系统的时间片轮转机制中，每个进程分到的时间片是若干毫秒。也就是说，进程得到处理机的资源短暂且频繁，进程在运行过程中实际上是频繁切换到就绪状态的；而其他资源（如外设）的使用和分配或者某一事件的发生（如I/O操作的完成）对应的时间相对来说很长，进程切换到等待状态的次数也相对较少。这样来看，就绪状态和等待状态是进程生命周期中两个完全不同的状态，很显然需要加以区分。

进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。在操作系统中，一般把进程控制用的程序段称为原语，原语的特点是执行期间不允许中断，它是一个不可分割的基本单位。

进程通信

1. 共享存储

   在通信的进程之间存在一块可直接访问的共享空间，通过对这片共享空间进行写/读操作实现进程之间的信息交换。在对共享空间进行写/读操作时，需要使用同步互斥工具来控制。共享存储可以分为两种：低级方式的共享是基于数据结构的共享，高级方式是基于存储区的共享。操作系统只负责为通信线程提供可共享使用的存储空间和同步互斥工具，而数据交换则由用户自己安排读/写指令完成；

2. 消息传递

   • 直接通信方式：发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列取得消息；
   • 间接通信方式：发送进程将消息发送到某个中间实体中，接收进程从中间实体取得消息。这种中间实体一般称为信箱，这种通信方式又称为信箱通信方式。该通信方式广泛应用于计算机网络中，相应的通信系统称为电子邮件系统。

3. 管道通信

   管道通信是消息传递的一种特殊方式。所谓“管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。向管道（共享文件）提供输入的发送进程（即写进程），以字符流形式将大量的数据送入（写）管道；而接收管道输出的接收进程（即读进程），则从管道中接收（读）数据。为了协调双方的通信，管道机制必须提供以下三方面的协调能力：互斥、同步和确定对方的存在。从管道读数据是一次性操作，数据一旦被读取，它就从管道中被抛弃，释放空间以便写更多的数据。管道只能采用半双工通信，即某一时刻只能单向传输。要实现父子进程双方互动通信，需要定义两个管道。管道可以理解为是共享存储的优化和发展。因为在共享存储中，如果某进程要访问共享存储，必须是该空间没有别的进程在里面进行写操作，否则访问行为就会被阻塞。而管道通信中，存储空间进化成了缓冲区，缓冲区只允许一边写入，另一边读取，那么，只要缓冲区中有数据，进程就能从缓冲区中读出，不必担心会因为别的进程在里面写操作而遭到阻塞，因为写进程会先把缓冲区写满了，然后才让读进程读，当缓冲区里还有数据的时候，写进程不会往缓冲区写数据。

线程

引入线程的目的，是为了更好地使多道程序并发执行，以提高资源利用率和系统吞吐量，增加并发程度；而引入线程，则是为了减小程序在并发执行时所使用付出的时空开销，提高操作系统的并发性能。线程最直接的理解就是“轻量级进程”，它是一个基本的CPU执行单位，也是程序执行流的最小单位。

线程与进程的比较

1. 调度。在传统的操作系统中，拥有资源和独立调度的基本单位都是进程。在引入线程的操作系统中，线程是独立调度的基本单位，进程是资源拥有的基本单位；
2. 拥有资源。不论是在传统的操作系统中还是在设有线程的操作系统，进程都是拥有资源的基本单位，而线程不拥有系统资源（也有一点必不可少的资源），但是线程可以访问其隶属进程的系统资源。
3. 并发性。在引入线程的操作系统中，不仅进程之间可以并发执行，而且多个线程之间也可以并发执行，从而是操作系统具有更好的并发性，提高了系统的吞吐量；
4. 系统开销。由于创建或撤销进程时，系统都要位置分配或回收资源，如内存空间、I/O设备等，因此操作系统所付出的开销远大于创建或撤销线程时的开销。类似的，在进行进程切换时，设计当前执行线程CPU环境保存及新调度到进程CPU环境的设置，而线程切换时只需保存和设置少量寄存器内存，开销很小。此外，由于同一进程内的多个线程共享进程的地址空间，所以这些线程之间的通信与同步非常容易实现，甚至无需操作系统的干预；
5. 地址空间及资源：进程的地址空间之间相互独立，同一进程的各线程间共享进程的资源，某进程内的线程对其他进程不可见；
6. 通信方面：进程间通信需要进程同步和互斥手段的辅助，以保证数据的一致性，而线程件可以直接读/写进程数据段（如全局变量）来进行通信。

线程的实现方式

线程的实现可以分为两类：用户级线程和内核级线程。内核级线程又称为内核支持的线程；

• 在用户级线程中，有关线程管理的的所有工作都有应用程序完成，内核意识不到线程的存在。应用程序可以通过使用线程库设计成多线程程序。通常，应用程序从单线程起始，在该线程中开始运行，在其运行的任何时刻，可以通过调用线程库中的派生例程创建一个在相同进程中运行的新线程。
• 在内核级线程中，线程管理的所有工作由内核完成，应用程序没有进行线程管理的代码，只有一个到内核级线程的编程接口。内核为进程及其内部的每个线程维护上下文信息，调度也是在内核基于县城架构的基础上完成的。

多线程模型

• 多对一模型：将多个用户级线程映射到一个内核级线程，线程管理是在用户控件完成。此模式中，用户级线程对操作系统透明

  优点：线程管理在用户空间进行，效率较高

  缺点：当一个线程在使用内核服务时被阻塞，那么整个进程都会被阻塞；多个线程不能并行地运行在多处理机上；

• 一对一模型：将每个用户级线程映射到一个内核级线程

  优点：当一个线程被阻塞之后，其他线程可以继续执行，并发能力强

  缺点：每创建一个用户级线程都需要创建一个内核级线程与之对应，这样创建线程的开销比较大，影响应用程序的性能；

• 多对多模型：将n个用户线程映射到m个内核级线程上，要求m<<n

  特点：在多对一模型和一对一模型中取了个折中，克服了多对一模型的并发度不高的特点，又克服了一对一模型的一个用户进程占用太多内核级线程，开销太大的缺点。又拥有多对一模型和一对一模型各自的有点。

进程调度算法

• 先来先服务(FCFS)调度算法

• 短作业优先(SJF)调度算法

• 优先级调度算法

• 高响应比优先调度算法

  响应比=（等待时间+要求服务时间）/要求服务时间

• 时间片轮转调度算法

• 多级反馈队列调度算法（集合了前几种算法的优点）

进程同步

• 信号量
• 管程

内存管理

内存管理的概念

操作系统对内存的划分和动态分配，就是内存管理的概念。

内存管理的功能有：

• 内存空间的分配和回收：由操作系统完成主存储器空间的分配和管理，使程序员摆脱存储分配的麻烦，提高编程效率；
• 地址转换：在多道程序环境下，程序中的逻辑地址与内存中的物理地址不可能一致，因此存储管理必须提供地址变换功能，把逻辑地址转换成相应的物理地址；
• 内存空间的扩充：利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存；
• 存储保护：保证各道作业在各自的存储空间内运行，互不干扰。

在进行具体的内存管理之前，需要了解进程运行的基本原理和要求

1. 程序装入和链接

   创建进程需要将程序和数据装入内存。将用户源程序变为可在内存中执行的程序，通常需要以下几个步骤：

   • 编译：由编译程序将用户源代码编译成若干个目标模块；
   • 链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块；
   • 装入：由装入程序将装入模块装入内存运行。

   程序的链接有以下三种方式：

   • 静态链接：在程序运行之前，先将各模块及它们所需的库函数链接成一个完整的可执行程序，以后不再拆开；
   • 装入时动态链接：将用户源程序编译后得到一组目标模块，在装入内存时，采用边装入边链接的链接方式；
   • 运行时动态链接：对某些模块的链接，是在程序执行中需要改目标模块时，才对它进行的链接。其优点是便于修改和更新，便于实现对目标模块的共享。

   内存的装入模块在装入内存时，有以下三种方式：

   • 绝对装入：在编译时，如果知道某些目标模块的将驻留在内存的某个位置，编译程序将产生绝对地址的目标代码。绝对装入程序按照装入模块中的地址，将程序和数据装入内存。由于程序中的逻辑地址与实际内存地址完全相同，故不需要对程序和内存的地址进行修改。绝对装入方式只适用于单道程序环境。另外，程序中所使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。而通常情况下在程序中采用的是符号地址，编译或汇编时再转换为绝对地址；
   • 可重定位装入：也称为动态重定位，程序在内存中如果发生移动，就需要采用动态的装入方式。装入程序在把装入模块装入到内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址均为相对地址。这种方式需要一个重定位寄存器的支持。动态重定位的特点是可以将程序分配到不连续的存储区中：在程序运行之前可以只装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存：便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间。