↓Skip to main content
A cup of beer
  1. Posts/

操作系统学习笔记-ch3-5

·270 words·2 mins
笔记
Table of Contents

CH3 进程 #

进程间通信机制 IPC #

  • interprocess communication
  • 独立进程和协作进程
    • 如果一个进程只需要自己所拥有的信息就能完成工作，那么他是独立进程。
    • 如果需要与其他进程交换信息，那么是协作的。
      • 通常用于模块化设计（各模块之间共享信息）和并行计算。
  • IPC的基本通信方式
    • 共享内存
      • 速度非常快，等同于内存。只需要在建立时使用系统调用。因此内核时间开销小。其他时间都是被处理成正常的内存访问了。
      • 实现较为复杂与困难
    • 消息传递
      • 速度比共享内存慢。采用系统调用实现消息的传递，每次传递都要系统调用，所以内核时间开销大。
      • 传递信息量较少，因此几乎不会有冲突问题。无需避免冲突。
      • 易于实现，特别适合是计算机网络的通信。

共享内存系统 #

  • 在OS对内存的保护中，OS禁止进程把手伸到别人的口袋里。共享内存系统取消了这一限制，使得这段共享的内存，其中的数据完全取决于拥有这段共享内存的程序的处理，而与OS不再有关。
    • 因此，这个程序就需要建立合适的进程同步机制，防止并发访问带来的问题（例如：防止两个进程同时往里写数据）。因为OS已经不再管理这段内存了，所以需要程序自己做好工作。

共享内存系统的生产者-消费者模型概念 #

  • 在生产者-消费者模型（可以理解为计算机网络的C/S模型）中，接收方（消费者）和发送方（生产者）之间需要一段缓冲区来保证彼此的同步。
  • 在共享内存系统中，两个进程一个充当生产者（通信信息发送方），一个充当消费者（通信信息接收方），以这种模型来实现对这段共享内存的合理使用。这就需要一个缓冲区，而这段内存实际上就是这个缓冲区。
  • 缓冲区
    • 有限缓冲
      • 生产者当缓冲区满时停下来；消费者当缓冲区空时停下来。
    • 无限缓冲
      • 生产者可以一直产生新项；消费者当缓冲区空时停下来。

消息传递系统 #

  • 在分布式系统（即通过计算机网络连接起来的一批计算机）中特别有用。

直接通信和间接通信 #

需要建立通信线路才能进行通信。以下给出两种建立通信线路的方法：

  • 直接通信即消息传递的双方指名道姓。双方都知道要传递给谁，谁来接受。接收方和发送方都是明确指定在函数中的。
    • 对称寻址
      • 即发送方和接收方都需要把对方的名字显式传入消息函数。
    • 非对称寻址
      • 即发送方需要把接收方的名字显式传入消息函数，但是接收方不需要知道自己要接收谁发来的消息。它可以传入一个名字变量，当它接收到任何的消息，这个名字变量就显示了这条消息是来自于谁。
    • 缺点：是硬编码的。如果对方的名字改变，你所有的通信函数都得改。因此限制了模块化设计。
  • 间接通信即双方不直接以对方的名字作为标识符，而是以一个信箱来作为双方通信的公共区域。双方可以往这个信箱里放消息，也可以从中收取消息。
    • 每个邮箱都有唯一的标识符。
    • 提供更高级的连接：
      • 两个进程只有在共享至少一个邮箱的情况下才可能相互通信。
      • 一个进程可以与多个邮箱建立联系，从而建立多条通信线路（一个邮箱实际上就是一个通信线路），从而可以与多个其他进程通信。
      • 两个进程之间可以共享多个邮箱，因此两个进程之间也可以建立多条通信线路。
    • 在这种方式下，消息函数的传入参数不再是进程名称，而是邮箱名称。

关于邮箱 #

  • 邮箱如果由进程创建，则拥有者（即接收者）是进程本身，使用者（即发送者）可以是任何其他进程。
  • 一个进程创建了一个邮箱，则这个进程默认变成了拥有者。但是这个拥有权和接收特权可以转让给其他进程，这就导致这个邮箱的接收者可能不再唯一。
  • 一个邮箱具有唯一的标识符，如果创建它的进程terminated，那么此邮箱也会消失，其他想要发送消息给他的进程会被告知邮箱不存在。
  • 一个邮箱只能被一个进程同时接收。系统可能采用以下三种方式来实现这一机制:
    • 一条线路只允许与两个进程相连；
    • 不允许两个进程同时调用receive()；
    • OS随机选择一个进程来接收；

同步（阻塞）和异步（非阻塞）进程通信 #

  • 阻塞即调用了send()或者receive()后，进程立即阻塞，除非通信成功，否则不能干别的；
  • 非阻塞即调用了后，仍然可以继续之前的工作。

进程通信缓冲 #

  • 规定：如果缓冲区已经满，那么发送方必须阻塞，等待缓冲区空出来，把消息发出去，才能进行其他操作。
  • 三种分类
    • 零容量：每次都是已满。因此相当于发送方以同步的方式进行通信。
    • 有限容量：如果未满，那么发送方以异步方式发送，否则以同步方式发送。
    • 无限容量：每次都是空。因此相当于发送方以异步的方式进行通信。
  • 两种分类
    • 没有缓冲的系统
      • 即”零容量“。
    • 自动缓冲的系统
      • 即有限容量和无限容量。

CH4 线程 #

线程 #

  • 进程的资源调度的基本单位，线程是CPU利用的基本单位。
  • 线程的构成
    • 线程ID
    • PC、栈、寄存器集合（程序运行三大件，这样才能独立运行）
      • PC让程序跑起来；栈满足函数调用等功能；寄存器实现实时运算。
  • 线程之间的共享资源
    • 代码段、数据段（执行同一份程序）、打开的文件
    • 其他所有分配给进程的资源
  • 少量系统线程在Linux的内核中运行，例如内存管理。
  • 为什么有了进程还引入线程
    • 线程之间共享代码段。因此意味着它们可能是为了做同一件事情更快才被创建。但是如果创建两个相同的进程，它们之间完全一样（完全继承），那么完全没有必要花费这个开销，因为没有意义。
      • 于是，允许同一段内存空间上跑多个不一样的控制线程。（注意，线程是共享内存的。）
      • 在Solaris中，进程创建的时间花费是线程创建的40倍，进程切换的时间是线程切换的5倍。
    • 利于多CPU结构的充分利用：如果进程是单线程的，那么它只能在一个CPU上执行。但是如果是多线程的，它的不同线程可以同时交给不同的CPU执行。这就使一个进程能在多个CPU上并行执行。不再出现”==一核有难，多核围观==“的尴尬境地。（现代处理器中，一个核心就是一个CPU。）

用户级线程到内核线程的映射 #

  • 为什么要映射
    • 用户级线程只能被理解为PC、栈、寄存器取值的集合，并不能实际被执行。
    • 这堆东西要被映射到一个内核线程上才能执行。因为内核线程是真正的线程，==只有内核线程才能被处理机调度==。
    • 线程库负责选择一个用户线程（线程库负责用户线程的调度），按照规则映射到一个内核线程上。
  • 主要模型
    • 多对一模型
      • 多个用户线程都只能选择同一个内核线程进行映射。因此如果其中一个线程在执行时发生阻塞，那么其他线程也不能映射此内核了。而且由于只有一个内核线程可供映射，显然这个内核线程只能属于一个CPU，所以这种映射方式不能使进程在多个CPU上并行执行。
      • 缺点：不支持多核并行处理；无法解决阻塞问题（即：并没有带来并行性）。
      • 例子：Solaris
    • 一对一模型
      • 用户级线程每创建一个，系统也相应创建一个内核线程去接收其映射。
      • 由于内核在保证流畅度的情况下能允许的内核线程数十分有限，OS一般会对用户创建的线程数给予限制。
      • 缺点：用户不能创建无限个线程。
      • 例子：Windows98、WindowsXP、Linux。
    • 多对多模型
      • 多对多模型即在用户线程数小于等于内核线程数的情况下，进行有效的多路复用，合理调度其映射关系，使得大家都有饭吃。
      • 完美消除了多对一、一对一的缺点，其支持多核并行处理，支持多线程并行，而且用户可以任意创建很多进程。
    • 二级模型
      • 在多对多的基础上加一个VIP Option。即可以允许将一个内核线程和一个用户级线程绑定，让这个用户级线程吃独食。
      • 其他方面和多对多模型一致。

线程库 #

  • 线程库是攻程序员创建和管理线程的API。
    • 用户空间中的线程库：这种库没有内核支持，所有的数据结构和代码都存在用户空间中，调用库函数只是在用户空间内的本地调用。
    • 内核级别的线程库：这种库直接由操作系统的内核提供支持。的数据结构和代码存在于内核中，如果调用此库实际上就是系统调用。
    • 主流的线程库包括Linux下常用的POSIX Pthread、Windows下的内核级线程库Win32、JVM的Java。
  • Java多线程
    • JVM的多线程库实现取决于宿主操作系统。例如在Windows下，JVM采用Win32线程库；在Linux下，JVM采用Pthread库。因此，JVM中，用户线程和内核绑定方式的模型也会根据系统的不同而不同。例如由于Win32，其是一对一的。

多线程问题 #

  • fork和exec问题
    • 如果一个线程调用了fork，那么新创建的进程是应该复制所有原有的线程构成新进程，还是只复制调用fork的这个线程构成新进程？不同OS有不同的解决方式。
    • exec没有什么问题。任意线程调用了exec，都会把所在进程的代码全都替换。由于所有的线程都共享此代码，所以所有线程所执行的任务都改变了。
  • 线程取消问题
    • 线程取消即在线程正常结束前停止其工作。例如按下浏览器上的”停止“按钮。
    • 异步取消：立即终止此线程。这会带来一些未知错误，例如资源无法得到合理释放。如果取消的同时，线程正在与其他线程交换数据，这就更加麻烦，可能连累其他线程产生错误。
    • 延迟取消：收到取消命令后，线程不断检查自己能否停止工作。如果可以了，就在合理的时机停止即可。这种相对安全的取消时机称为”取消点“。

多线程下的信号处理 #

  • 信号是Unix系统的概念，表示某个事件已经发生。用于通知某进程。信号由某特定事件的发生而产生，发送到进程，且一旦收到必须要被处理。
  • 同步信号：自己进程发送给自己进程的信号。例如除以0、访问非法内存。
  • 异步信号：一个进程发送给另一个进程的信号。该信号由接收进程之外的事件所导致。例如Ctrl+C、计时器到期。
  • 信号的处理方式
    • 信号由信号处理方式进行处理。分为默认信号处理程序和用户定义的信号处理程序（通过==改写==默认信号处理程序来实现。）
  • 多线程下的问题
    • 信号是针对进程的。其收发单位都是进程。因此如何最终让某个线程来处理呢（因为实际干活的是线程）？
    • Unix系统下，不同线程描述自己期望接受的信号类型。
    • Windows系统下，提出APC（异步过程调用，Asynchronous Procedure Call）的新概念，其类似于Unix中的信号，但是其收发单位是线程。

线程池概念 #

  • 为什么引入线程池
    • 考虑一个多线程的服务器模型，为了保证服务器的畅通，需要为每个到来的请求开一个线程供其执行。
      • 但是开线程需要时间，释放线程也需要时间——每个服务来都需要一点点的额外开销，强迫症非常难受；
      • 如果服务过多，就要创建过多的线程。对于并行能力不那么强的CPU，这么多线程它无法胜任。
  • 线程池的思想
    • 在进程创建时，就开好若干数量的线程，放在池子里等待。然后，来一个任务，就从池子里拿出一个线程，安排给他干活，然后等干完了再回到池子中。如果任务到来但是线程池空，那么任务只能等待。
    • 优点：
      • 没有了那些创建和释放的额外时间开销。
      • 限制了线程的数量，防止系统开销过大导致的崩溃。
    • 有的线程池支持动态调整线程池中线程的数量，这样能在低负载时降低系统开销，节约资源。

LWP #

  • 引入一种数据结构（轻量级进程 LWP）。这种数据结构在用户看来，是一种可以调度用户线程进行允许的虚拟处理器。在用户看来，用户线程直接运行在了虚拟存储器上面。
  • 一个LWP只能执行一个线程。一个LWP只与一个内核线程相连。因此LWP的两端分别接一个用户级线程和一个内核线程。
  • 如果内核线程阻塞，那么阻塞信息逐级向上传播：内核阻塞，然后LWP阻塞，然后用户线程阻塞。
  • OS需要给用户进程分配一定数量的LWP，以支持多线程运行。实际上，LWP就对应了一个内核线程，所以采用什么样的映射模型，实际上在表面上就体现为了用户级线程和LWP之间的映射模型。
    • 因此考虑一种多对多的情况，且LWP数量小于用户线程的数量，那么抢不到LWP的用户线程就需要等有LWP空出来了才能继续。

调度程序激活 #

  • 调度程序激活解决了内核和线程库之间的通信问题。
  • ==upcall==
    • 即内核通过层层传递，告诉用户程序某一特定事件。因此upcall是一种事件传递机制。
    • upcall处理程序用于调度在LWP上运行的线程。例如当某一LWP阻塞，upcall就保存其运行状态 （上下文），然后释放此LWP给其他线程使用；当某一线程阻塞完成，其调度其在一个LWP上继续执行。
    • upcall处理程序必须在一个LWP上运行。因此，例如当一个LWP阻塞，此时要调用upcall处理程序，系统内核分配一个新的LWP给进程，然后在此新LWP上运行upcall处理程序，或直接抢占一个运行中的LWP来执行upcall处理程序。

句柄 #

Windows系统为每个进程在内存中分配一定的区域，用来存放各个句柄，即一个个32位无符号整型值（32位操作系统中）。每个32位无符号整型值相当于一个指针，指向内存中的另一个区域（我们不妨称之为区域A）。而区域A中存放的正是对象在内存中的地址。当对象在内存中的位置发生变化时，区域A的值被更新，变为当前时刻对象在内存中的地址，而在这个过程中，区域A的位置以及对应句柄的值是不发生变化的。这种机制，用一种形象的说法可以表述为：有一个固定的地址（句柄），指向一个固定的位置（区域A），而区域A中的值可以动态地变化，它时刻记录着当前时刻对象在内存中的地址。这样，无论对象的位置在内存中如何变化，只要我们掌握了句柄的值，就可以找到区域A，进而找到该对象。而句柄的值在程序本次运行期间是绝对不变的，我们（即系统）当然可以掌握它。这就是以不变应万变，按图索骥，顺藤摸瓜。

CH5 CPU调度 #

CPU调度的基本概念 #

  • 进程的CPU区间和IO区间
    • 进程的整个执行过程由CPU区间和IO区间交替构成。即：一段CPU，再一段IO，再一段CPU，…，到了最后是一段CPU，这段程序请求停止执行。这些区间称为CPU区间（CPU Burst），IO区间（IO Burst）。
    • 一般情况下，CPU Burst的区间时间不会太长，因此很多程序都是IO约束程序，即IO时间占比大于CPU时间。此外，还存在CPU时间占比大于IO时间的程序，称为CPU约束程序。合理分配CPU约束程序和IO约束程序的比例，可以提升CPU利用率。
    • 注意，单次IO一般都不需要太长时间，因此IO约束程序主要是IO的请求次数非常多。因此，给予IO约束程序更高的优先级，能够提升效率。（否则，好不容易拿到CPU了，一小会就又去IO了）
  • 短程调度程序
    • CPU的调度是由前面所说的短程调度程序实现的。其对就绪队列中的PCB块进行选择。
  • 分派程序dispatcher
    • 负责将CPU的控制权短程调度程序指派的程序。
    • 因此，dispatcher需要完成上下文切换工作。
    • dispatcher一定要够快，因为每次上下文切换都要用他。为了完成上下文切换，分派程序的工作时间开销称为分派延迟。

CPU短程调度发生的四个时间节点 #

  • 非抢占的：
    • 进程从运行态到阻塞态
    • 进程从运行态结束
  • 抢占的：
    • 进程从运行态到就绪态（例如高优先级的进程突然收到中断请求）
    • 进程从阻塞态到就绪态（例如高优先级的进程IO完成）
  • 从这里可以看出，非抢占调度时，装入新程序都是顺理成章的，不存在把原有执行程序直接赶走的情况，因为原有执行程序要么执行完了，要么没有条件执行（主动让出）了。但是抢占调度时，是直接把原有进程赶走。
  • 需要注意，抢占调度会存在数据不一致的风险。这和前面说的异步取消一个线程是一样的道理。
  • 如果一个操作系统只支持非抢占式调度，那么称此OS的调度是非抢占的。这种OS下，当前运行的进程只能永远占用CPU的控制权，除非结束或阻塞（即主动出让）。

开关中断 #

  • 有的代码会被中断所影响。为了防止该代码被影响，可以在进入执行前关闭中断响应，在结束后开启中断响应。

调度算法的衡量标准 #

  • CPU吞吐量：单位时间内完成的进程的数量。
    • 注意，吞吐量是只追求数量，不追求质量的。即，如果进程都是很长的进程，那么吞吐量可能很小。
  • CPU使用率：我们调度的目的就是提升CPU使用率，即多道程序的degree。
  • 周转时间：从程序提交执行到完全结束之间的时间。
  • 等待时间：进程在就绪队列中的时间之和。
  • 响应时间：从程序提交执行到产生第一个输出之间的时间。
    • 它和周转时间的区别：一个好的程序会尽可能快地产生第一个输出。例如要算10个数，每算一个就输出1个，那么响应时间就是第一个数输出就可以了，但是周转时间是到第10个输出后结束。
    • 对于交互式系统，主要把经历放在响应时间的优化上。

调度算法 #

  • 先来先服务FCFS

    • 对于就绪队列，把它看成一个简简单单的队列，每次取队首元素给予其CPU控制权。
    • 是典型的非抢占调度。获得CPU控制权的进程除非退出或阻塞，否则不可能让出CPU。
      • 产生问题：护航效应。
      • 考虑一个CPU约束进程和很多IO约束进程。一开始，CPU约束进程长时间占用CPU，其他IO约束进程只能在就绪队列等待；等到CPU约束进程终于开始IO了，其他IO约束进程一个一个地非常快地占用完CPU就开始IO阻塞，等到IO完成，纷纷在就绪队列排到CPU约束进程的后面，重复上述过程。可见，这些IO约束进程几乎拿不到CPU时间。大部分时间都在等待。
    • 护航效应和饥饿效应的区别
      • 护航效应中，处于劣势的进程虽然很不舒服，但是只要时间足够长，还是可以拿到CPU时间的。
      • 饥饿效应中，处于劣势的进程可能这辈子都拿不到CPU时间了。例如MIT关闭IBM 7094时，发现一个6年前的进程还没有被执行。

  • 最短作业优先SJF、最短剩余时间优先SRTF

    • 抢占式版本的SJF称为SRTF，因为如果抢占了，那么进程的CPU时间只能用“剩余”来衡量了（因为可能其所在的这段CPU Burst已经被执行过一些了，只是中间被其他VIP抢占了。）。

    • SJF的概念：对于就绪队列中的PCB，选择其下一段CPU Burst最短的一个，作为调度结果。

    • SJF算法是理论上最佳的CPU调度算法，因为如果把短进程拿到长进程之前执行，那么短CPU Burst进程节约的等待时间（=长进程CPU Burst时间）要比长CPU Burst进程增加的等待时间要长（=短进程CPU Burst时间）。这直接将平均等待时间拉到最低。

    • SJF的问题在于你没法准确知道下一CPU Burst是多长，故在短程调度程序中无法被实现。因此一般只用于长程调度。其CPU Burst实际上直接就是用户填写的极限执行时间。这实际上不怎么精确，但是对于长程调度，不同任务之间的差距可能比较大，还好点。

    • 近似SJF调度：虽然我们无法准确知道下一CPU Burst具体长度，但是我们可以预测其长度。采用如下公式： $$ t_{n+1}=at_n+(1-a)at_{n-1}+(1-a)^2at_{n-2}+…+(1-a)^{n+1}t_0 $$

      • 实际上就是一个加权平均。其中，t_i是第i个CPU Burst的时间，这里我们利用从第0个到第n个CPU Burst的时间（显然是已知的）预测第n+1个CPU Burst的时间。控制a的值可以控制上一次CPU Burst的时间和从第0个以来CPU Burst的历史时间两者的考虑比重。但是无论如何，可以看到，越是久远的t的历史，其权重越小，因为1-a是>0，<1的。

  • 优先级调度

    • 将每个进程赋予一个优先级的值。相同优先级的进程按FCFS调度。
    • SJF是一种特殊的优先级调度，其优先级是下一CPU Burst的倒数。
    • 有的系统认为数字小了优先，有的系统认为数字大了优先。
    • 内部定义优先级和外部定义优先级
      • 内部定义优先级一般是OS根据CPU Burst、IO Burst、内存限制等要素计算出来的。
      • 外部定义优先级一般是人为设置的，一般涉及到政治因素。
    • 缺点：饥饿现象。
      • 如何解决饥饿现象：引入“老化（aging）”，即进程的优先级随着时间的流逝而递增，一个最低优先级的进程总有一天变成最高的。
↑