"计算机操作系统"

  "操作系统的精髓和原理"

Posted by Xu on March 25, 2018


第一章、计算机系统概述

1.基本构成

计算机四大组件:

  • 处理器
  • 内存
  • 输入/输出模块
  • 系统总线

four_component

  • PC = 程序计数器
  • IR = 指令寄存器
  • MAR = 内存地址寄存器
  • MBR = 内存缓存寄存器
  • I/O AR = 输入/输出地址寄存器
  • I/O BR = 输入/输出缓存寄存器

2.指令的执行

指令周期分为两步:

  • 取指阶段
  • 执行阶段

cmd_exe

PC->IR:程序计数器PC保存每个指令的地址,每执行完一个指令,程序递增,指到下一条指令。取出该指令后寄存到指令寄存器IR。

指令(16位):4位操作码+12位数据地址;指令主要分为四类

  • 处理器<->存储器
  • 处理器<->I/O
  • 数据逻辑计算处理
  • 控制指令,改变指令执行顺序

3.中断

目的:用于提高处理器效率的手段,防止一个设备或程序垄断CPU资源。

分类:

  • 程序中断:指令执行的过程引起的中断,如算法溢出,除数为0等
  • 时钟中断:处理器内部的计时器产生,允许操作系统定时执行某个函数
  • I/O中断:I/O控制器产生
  • 硬件失效中断

当加入中断时,指令周期将会添加一个步骤:中断阶段

cmd_exe2

4.中断处理

中断处理流程:

  1. 设备->处理器发送中断信号
  2. 处理器结束当前执行的指令
  3. 处理器向设备发送确认信号,允许设备取消中断信号
  4. 处理器将控制权移交到中断处理程序,并保存当前程序的信息(程序状态字PSW和程序计数器PC)。
  5. 将中断处理程序的入口地址压入到程序计数器PC

  6. 除了PSW和PC,还需要保存其它的一些信息如寄存器
  7. 中断处理程序开始处理中断
  8. 中断处理结束,保存的寄存器的值进行恢复
  9. 恢复PSW和PC的值,回到之前的程序

interrupt

被中断程序的信息保存包括程序状态字,程序计数器,寄存器信息等保存到控制栈中去。

interrupt_save

多个中断

处理多个中断同时发生时处理办法有两种:

  1. 当正在处理一个中断时,禁止发生其它中断
  2. 定义中断优先级,允许高优先级的中断打断低优先级的中断

multi_interrupt

5.存储结构

storage

从上往下:

  • 价格递减
  • 容量递增
  • 存取时间递增
  • 处理器访问存储器频率递减

6.高速缓存

高速缓存是为了解决处理器速度和内存速度严重不匹配的问题,使得处理器的速度尽量不受到存储周期的影响。所以利用局部性原理来提升处理器速度

cache

上图中的高速缓存通常会多级使用,分为一级缓存L1,二级缓存L2,三级缓存L3

  • 速度:L1>L2>L3
  • 容量:L1<L2<L3

为了方便缓存到内存的映射:

cache_memory

  • 内存可视为有一个个固定大小的块(block)组成。每个块包含有K个字。
  • 高速缓存则可视为由一个个槽(slots)组成,每个槽中有K个字
  • 一个槽映射一个块,但这个映射关系是为变动的,所以每个槽有一个标签标示当前存储的是哪个块,标签通常是地址的较高的若干位,表示以这些位开始的地址

高速缓存读取操作: cache_read

针对高速缓存的设计有一系列问题需要解决:

  • 尺寸问题:高速缓存大小和块大小
  • 映射函数:内存中的块要存放在高速缓存中的哪个单元
  • 置换算法:若高速缓存中的所有存储槽满后,新块到来时该置换掉哪个块(例如LRU最近最少使用算法)
  • 写策略:当缓存中的数据别修改时,如何将其写回内存。

7.直接内存存取DMA

执行I/O操作有三种方式:

当处理器执行程序需要I/O操作时,要给相应I/O模块发送指令

  • 可编程I/O操作:I/O模块执行请求的动作并设置I/O的状态,不会通知处理器,处理器需要不断询问I/O操作是否完成,由I/O模块完成数据传输
  • 中断驱动I/O:当I/O模块准备好与处理器交换数据时,它将打断处理器的执行并请求服务,然后由处理器来执行数据传送
  • 直接内存存取:处理器给DMA模块产生一条命令,发送读写相关的信息,然后DMA和存储器直接交互完成数据传输,每次传送一个字。数据传输结束后,DMA将给处理器发送一个中断信号提示传输结束 ,相较于前两种处理器需要控制传输过程方法,DMA不需要处理器去干预数据传输的过程,只有在数据传输开始和结束时,处理器才会参与

第二章、操作系统概述

1.目标和功能

操作系统是控制应用程序执行的程序,是应用程序和计算机硬件间的接口,操作系统可以理解为资源的统一抽象表示,他有三个目标:

  1. 方便: 使计算机更方便使用
  2. 有效:以更有效的方式使用计算机资源
  3. 扩展能力:有效开发、测试、引入新的系统功能

操作系统的基本职责是控制进程的执行,包括交替执行的方式和给进程分配资源

2.操作系统的发展

  1. 串行处理:每个程序都需要人工装载
  2. 简单批处理系统,计算机操作员将一批任务组合在一起交给计算机处理,计算机处理完一个任务后会自动装在下个用户程序
  3. 多道批处理:当处理器处理一个任务时,发生中断需要等待I/O操作,当内存空间可以容纳两个甚至多个用户程序时,这时可以将处理器切换到另一个用户程序执行。
  4. 分时系统,将时间分成时间片,每个时间片分给不同的用户使用,使得多个用户可以同时通过中断使用处理器

3.现代操作系统

  • 微内核体系结构:只给内核分配一些最基本的功能,包括地址空间,进程间通信和基本的调度,其它的操作系统服务则由允许在用户模式且与其它应用程序类似的进程提供(对应大内核,包括调度,文件系统,网络,设备管理器,存储管理等功能的内核)
  • 多线程:把执行一个应用程序的进程划分为可以同时运行的多个线程。

    • 线程:可分派的工作单元。包括处理器上下文环境,栈中自身的数据区域,线程顺序执行且可以中断,因此处理器可以转到另一个线程
    • 进程:一个或多个线程和相关系统资源(如包含数据和代码的存储器空间,打开的文件和设备)的集合
  • 对称多处理(SMP):具有多个处理器,可以将进程或线程调度到所有的处理器上运行
  • 分布式操作系统:多机系统具有单一的内存空间,外存空间等
  • 面向对象设计:用于给小内核增加模块化的扩展

第三章.进程

1.什么是进程

进程有如下定义:

  • 一个正在执行中的程序
  • 一个正在计算机上执行的程序实例
  • 能分配给处理器并由处理器执行的实体
  • 一组执行的指令,一个当前状态和一组相关的系统资源表征的活动单元

也可以把进程看作是由一组元素组成的实体,进程可以视为程序代码和与代码相关联的数据集以及进程控制块组成

进程控制块:由操作系统创建和管理,进程控制块包含了充分的信息,因此可以根据控制块来实现进程的中断,然后恢复进程的执行。

ps_control

2.进程的状态

2.1进程的创建

将一个新进程添加到正在被管理的进程集中去:

  1. 操作系统需要建立用于管理该进程的数据结构
  2. 并在内存中给他分配地址空间
  3. 然后初始化进程控制块
  4. 并设置正确的连接保存到相应队列

2.2五状态模型

运行态:正在被处理器执行的进程的状态,如果只有一个处理器则同时最多只有一个进程处于运行态。 就绪态:进程做好了准备。只要有机会就开始执行。 阻塞/等待态:进程在某些事件发生前不能执行,如I/O操作完成 新建态:刚刚创建的进程,操作系统还未把它加入到可执行进程组,通常是进程控制块已经被创建但还没有加载到内存中的新进程。 退出态:操作系统从可执行进程组中释放出的进程,要么它自身已停止要么它因某种原因被取消。

five_state

新建态意味着操作系统已经执行了创建进程的必须动作,但未执行的进程状态,因为有时候可能会因为性能不高或内存不足限制系统中的进程数量,但进程本身没有进入内存,系统所需的该进程的系统信息保存在内存的进程表中,但进程本身还未进入内存。也就是说即将执行的程序代码不在内存中而是在外存保存

进程退出也分为两步,首先,进程被终止,进入退出态,此时不再执行进程,与作业相关和其他信息会临时被操作系统保留,实用程序可能为了分析性能和利用率需要提取进程的历史信息,这些信息提取完后,操作系统就会删除该进程以及该进程相关的数据

运行态->就绪态: 1)超时,超过了分配给它的最长时间段 2)抢占,优先级高的抢占优先级低的进程

为了方便进程管理,我们可以用多个队列来维护进程的状态,每个队列对应不同的事件和不同的优先级,可以使得处理器迅速找到下一个应该执行的进程。

这些队列中维护的信息就是每个进程的控制块信息

block_queue

其中多个队列,每个队列对应不同的阻塞等待的事件。

2.3引入“挂起态”的进程模型

为何引入挂起态的原因:就是为了腾出内存空间

  • 由于处理器速度远快于I/O速度,为了充分利用处理器而不让处理器处于“空闲状态”,防止多个进程都在等待I/O的状态,我们可以通过两个方式解决这个问题:
    • 增加内存空间,使多道处理的程序尽可能多,但限制于内存的价格
    • 交换,即把内存中某个进程的一部分或全部移出磁盘,换出到挂起队列。此后操作系统要么从挂起队列中取出另一个进程,要么接收一个新进程的请求放入内存运行

hang_up

只要是在挂起的状态,进程就在外存中,还没有加载到内存。

  • 就绪/挂起->就绪:1) 当没有就绪态程序时,需要调入一个进程继续执行时 2) 或者当处于就绪/挂起的进程优先级更高时。
  • 就绪->就绪/挂起:1)一般都是选择挂起阻塞态的进程,但是如果释放空间以得到足够空间的唯一方法是挂起一个就绪态进程,也会出现这种转换。2)操作系统确信高优先级的阻塞态进程会很快就绪,也会选择去挂起一个低优先级的就绪态的进程
  • 新建->就绪/挂起:进程创建需要为其分配内存空间,但没有足够的内存空间时会进行这种转换
  • 阻塞/挂起->阻塞:如果一个进程终止,释放了一些内存,此时阻塞/挂起进程的优先级比所有的就绪状态进程的优先级都高,操作系统还确信该阻塞的事件会很快发生,会进行这种转换
  • 运行->就绪/挂起:如果位于阻塞/挂起队列中的具有较高优先级的进程变得不再阻塞,操作系统抢占这个进程并直接把这个进程转换到就绪/挂起,因为内存空间依然不足。

3.进程的描述

操作系统是管理资源的实体,操作系统如果要通过进程并管理资源,操作系统需要哪些信息?这些信息就叫做进程的描述。

操作系统管理进程和资源,必须掌握每个进程和资源的当前状态,普遍采用的方法是操作系统构造并维护其管理的每个实体的信息表。这些表大致分为四类:

  • 内存表:用于跟踪内(实)存和外(虚)存,内存某些部分留给操作系统使用,剩余部分给进程使用
  • I/O表:管理I/O设备和通道
  • 文件表:提供文件是否存在,文件在外存中的位置,当前状态和其它属性的信息
  • 进程表:内存,I/O和文件是代表进程而被管理的,所以进程表中必须有这些资源的直接或间接引用

control_table

3.1进程控制结构

操作系统在管理和控制进程是,首先要知道进程的位置,然后要知道进程的属性

  • 进程位置:进程的物理表示其实就是一段内存空间,该内存空间里面包含了要执行的代码和所需的数据

所以我们常用进程映像来描述一个进程,包括:程序、数据、栈和进程控制块。在最简单的情况下,进程映像一般保存在连续的内存块中,但当引入虚拟内存后,存在分页内存来支持进程映像。

ps_iso

进程映像结构:

ps_iso_consturct

  • 进程属性:操作系统将会用到的信息,这里分为三类
    • 进程标识信息:进程标识符可以简单理解为主进程表的索引,内存表和一些其它的表可以使用这些进程标识符来构建和进程的映射关系,如进程的内存映射。标识信息还包括,父进程标识符,用户标识符。
    • 进程状态信息:处理器状态信息,运行一个进程时,它的相关状态信息一定会保存在一组成为程序状态字的寄存器中。
    • 进程控制信息:调度和状态信息(进程状态,优先级,调度相关信息如调度算法,事件),数据结构,进程间通信,进程特权,存储管理,资源所有权和使用情况

4.进程控制

4.1执行模式

大多数处理器支持两种执行模式:

  • 用户态
  • 内核态:访问指定内核内存,可以完全控制所有指令,寄存器和内存

使用这两种模式可以保护操作系统的结构不受用户程序干扰

程序如何知道它处于什么模式?如何改变该模式?

  • 程序状态字中存在一个指示执行模式的位,该位会随着事件的改变而变化。
  • 进入内核态 :调用操作系统服务或中断触发系统例程时
  • 进入用户态:系统服务返回到用户进程时

4.2进程创建

之前有提过,见书P88

4.3进程切换

在发生系统中断系统调用的时候,会将控制权交给操作系统:

  • 系统中断分为两类:
    • 中断:与当前正在运行的程序无关的某种外部事件相关引起的,如时钟中断,I/O中断,内存失效
    • 陷阱:与当前指令执行相关,处理一个错误或异常。1)系统首先判断错误和异常是否致命,若是,则进程被换出到退出态,发生进程切换 2)若不是,则看操作系统的设计,可能进行进程切换也可能继续执行
  • 系统调用:转移到操作系统代码一部分的一个例程上执行,通常,使用系统调用会将进程置为阻塞态

模式切换:部分中断发生时,控制权交给操作系统,执行完中断处理程序后继续执行正在运行的程序,不需要改变运行态状态,保存上下文和恢复上下文只需要很小的开销

进程切换:部分中断发生时,如时钟中断,控制权先交给操作系统,当前进程的事件片已经用完,需要调度另一个进程,所以需要进行进程切换,将进程的状态进行改变,此时操作系统需要让处理器等环境发生实质性变化。

进程切换的步骤:

  1. 保存处理器上下文环境(程序计数器和其它寄存器)
  2. 更新当前处于运行态进程的进程控制块,包括修改进程状态
  3. 将进程控制块移到相应队列
  4. 经过调度,选择下一个要运行的程序
  5. 更新所选择的进程状态和进程控制块信息
  6. 更新内存管理数据结构
  7. 载入该选择进程的程序计数器和其它寄存器先前的值,处理器也恢复为之前的上下文。

进程切换一定有模式切换;模式切换不一定有进程切换(中断会发生模式切换,但是在大多数操作系统中,中断的发生并不是必须伴随着进程的切换的。可能是中断处理器执行之后,当前正在运行的程序继续执行);

第四章.线程

1.进程和线程

  • 进程是操作系统进行资源分配的基本单位,所有线程共享进程状态和资源(相当于一个进程隔离一片资源视图)
  • 线程是调度的基本单位,从处理器切换进程状态和调度的视角来区分

为什么进程和线程难以区分?因为在单线程方法的处理模式中,线程的概念还没有被提出来,一个进程就是资源和调度的基本单位,后来多线程方法出现后支持一个进程中有多个线程并发执行的能力。从而进程和线程一直难以区分。

线程共享进程的状态和资源,线程都驻留在同一地址空间中,进程和线程关系如下:

thread_model

从性能上比较,线程具有如下优点:

  1. 在一个进程中创建新线程的时间远少于创建一个新进程的时间
  2. 终止线程要比终止进程花的时间少
  3. 同一进程内线程间切换的时间要少于进程间切换的时间
  4. 线程提高了不同执行程序间通信的效率,同一进程中的多个线程共享文件和内存无序通过调用内核就可以实现

使用线程的场景:1)前台和后台 2)异步处理 3)执行速度 4)模块化程序结构

2.线程分类

线程状态就绪态,运行态,阻塞态(当一个线程需要等待另一个线程执行完毕才能继续执行时进入阻塞态),(挂起态对于线程没有意义,因为是共享内存空间)

线程的实现分为两大类:

  • 用户级线程:有关线程的管理工作都由应用程序完成(使用线程库),内核意识不到线程的存在
  • 内核级线程:有关线程管理的工作都由内核完成,应用程序部分没有进行线程管理的代码 thread_class

2.1用户级线程

在用户级线程中,进程和线程的状态切换可能有如下过程: user_thread

  • a)->b):线程2中执行的应用程序代码进行系统调用,阻塞了进程B。例如,进行一次I/O调用。这导致控制转移到内核,内核启动I/O操作,把进程B置于阻塞状态,并切换到另一个进程。在此期间,根据线程库维护的数据结构,进程B的线程2仍处于运行状态。值得注意的是,从处理器上执行的角度看,线程2实际上并不处于运行态,但是在线程库看来,它处于运行态
  • a)->c):时钟中断把控制传递给内核,内核确定当前正在运行的进程B已经用完了它的时间片。内核把进程B置于就绪态并切换到另一个进程。同时,根据线程库维护的数据结构,进程B的线程2仍处于运行态
  • a)->d):线程2运行到需要进程B的线程1执行某些动作的一个点。此时,线程2进入阻塞态,而线程1从就绪态转换到运行态。进程自身保留在运行态

前两种情况下,内核切换进程之间的调度对线程来说是不可见的,虽然进程及内部的线程都是阻塞的,但对于进程内的其它线程来说,该线程依然是运行态,只要进程切换回来时,该线程继续执行。

    • 线程调度:在进程内部的调度,状态的切换都是相对于进程内部所有的线程而言的,不关心进程外部的其它线程,所以处理器调度是从进程的角度来进行调度,它执行的内容却是具体到进程中的线程中去,处理器只要调度处理合适的进程,而具体执行该进程中哪一个线程就由线程调度来决定。比如进程A中的线程2正在运行,当线程2需要进行系统调用时,会将进程A置于阻塞态,但线程2依然是运行态,只有当线程2运行到该进程内部其它的线程1需要执行时才会变为阻塞态。因为它的状态只相对内部线程视角来看的
    • 进程调度::处理器进行调度的视角是从进程的视角进行调度的,但处理器处理的基本单位却是具体的线程

用户级线程优点

  1. 进程内部切换线程不需要进行模式切换,不需要进入内核态,节省了两次模式切换的时间
  2. 调度只需应用程序相关,算法可以量身定做而不会扰乱底层操作系统的调度程序
  3. 可以在任何操作系统上执行

用户级线程缺点

  1. 用户级线程执行系统调用时,不仅该线程被阻塞,该进程内的所有其它线程也会被阻塞
  2. 一个多线程应用不能使用多处理技术,因为内核一次只能把一个进程分配给一个处理器,所以该进程内部的线程一次只能执行一个,不能并发执行。

2.2内核级线程

内核能意识到线程的存在,所有线程的调度和管理都由内核完成

内核级线程优点

  1. 多处理技术:内核可以用多个处理器同时处理一个进程内部的多个线程,因为线程由内核管理
  2. 如果进程中内部的一个线程阻塞了,可以切换到该进程内部的其它线程执行
  3. 内核例程自身也可以使用该多线程技术

内核级线程缺点

  1. 在把控制权从一个线程切换到同一个进程内的线程时需要进行两次状态切换,先切换到内核态,再回到用户态。

2.3混合方案

混合使用用户级线程和内核级线程,克服两种实现的缺点,利用两种方法的优点。

第五章.并发

操作系统设计的核心问题是进程和线程的管理,管理过程中的问题的基础是并发的问题,并发是所有问题的基础,也是操作系统设计的基础,并发包括很多设计问题:进程间通信、资源共享和竞争,进程活动的同步、进程分配处理器时间等

要想解决并发的问题,我们首要需求就是赋予进程互斥的能力,而如何提供互斥的能力是通过三种方法来实现的:

  • 信号量
  • 管程
  • 消息传递

一些并发相关的术语解释:

concurrency

  • 共享代码区域规则:一次只允许一个进程进入该共享代码区域
  • 竞争条件:当两个进程想要同时修改更新一个数据,需要进行竞争,竞争的”失败者”将决定该数据最终的值。

进程的交互分为三类:

  • 进程之间相互不知道对方的存在(资源竞争):他们不会一起工作,操作系统需要知道他们对资源的竞争情况
  • 进程间接知道对方的存在(共享合作):通过共享某些对象,但不知道对方ID,如共享I/O缓冲区,有合作行为
  • 进程间直接知道对方存在(通信合作):通过ID直接通信,合作完成某种活动,合作行为

ps_interactive

  • 进程间资源竞争:进程不知道其它进程的存在,当访问某些资源(这类资源包括I/O设备,存储器,处理器,时钟)时,要和其它进程竞争,而在不知道其它进程的前提下能够竞争资源,我们就必须要为进程赋予互斥能力。这类不可共享的资源为临界资源,访问临界资源的代码称为临界区。而引入互斥后我们随之产生两个额外的问题:死锁和饥饿
  • 进程间通过共享合作:进程可能使用冰修改共享变量数据(不同于资源,这里的数据是在代码级别的数据),并且知道其它进程也会访问同一数据,所以需要合作确保共享的数据得到正确的管理。由于数据是存储在资源设备上的,所以也会涉及到互斥,死锁和饥饿的问题,除此之外还有一个新要求:数据一致性
  • 进程通过通信合作:由于在通信的过程中,进程间没有共享任何对象,所以不存在互斥现象,但是会存在死锁和饥饿的现象,(死锁:两个进程都被阻塞,每个都在等待来自对方的通信。饥饿:P3想和P1通信,P1一直在和P2交换信息,导致P3一直阻塞处于饥饿状态)

1.1互斥的硬件支持

1)中断禁用(只对单处理器有效):为保证互斥,只需要在访问临界区时保证一个进程不被中断即可

while(true){
   /*禁用中断*/
   /*临界区*/
   /*启用中断中断*/

}

问题:

  • 处理器被限制只能交替执行程序,执行效率明显降低
  • 不能用于多处理器结构

2)专用机器指令:由于多处理器之间的行为是无关的,表现出一种对等关系,没有支持互斥的中断即止,所以我们需要在硬件级别上设计一些机器指令,在硬件的层次实现对数据的原子性操作,从而达到互斥的目的。

最常用的两种指令:

  • 比较和交换指令(原子执行):compare&swap,测试word是否为测试值testval,是则返回true,并修改word,实现互斥
  • exchange指令(原子执行):交换bolt到寄存器中来do while测试是否为0,为0进临界区,不为0则继续do while循环测试

自旋等待:进程在得到临界区访问权之前只能继续执行测试变量的指令来得到访问权,进入临界区的进程选择取决于哪个进程正好执行compare_and_swap来进行测试。

/*比较和交换指令*/
int bolt;
void P(int i)
{
    while(true){
        while(compare_and_swap(bolt,0,1) == 1)//测试bolt是否为0,为0则进入临界区,并将bolt设为1实现互斥
            /*不做任何事*/;
        /*临界区,访问临界资源*/
        bolt = 0;//访问临界资源结束后,恢复该信号量为0
        /*其余部分*/
    }
}

int compare_and_swap(int *word,int testval,int newval)//测试word是否为测试值testval,是则返回true,并修改word,实现互斥
{
    int oldval;
    oldval = *word;
    if(oldval == testval) *word = newval;
    return oldval;
}

/*交换指令*/
int bolt;
void P(int i)
{
    int keyi = 1;
    while(true){
        do exchange (&keyi,&bolt);//通过交换操作将bolt值放入到keyi
        while(keyi != 0);//测试keyi,如果等于0则可以进入临界区,不等于零则不断do while循环测试
        /*临界区*/
        bolt = 0;
        /*其余部分*/
    }
}

void exchange (int *register.int *memory)
{
    int temp;
    temp = *memory;
    *memory = *register;
    *register = temp;
}

缺点:

  • 使用忙等待(进入临界区之前会一直循环检测,会浪费处理器时间)
  • 可能饥饿(存在一些忙等的进程一直无法进入临界区)
  • 可能死锁(P1在临界区中被高优先级进程P2抢占,此时P2请求该临界区请求不到,因为P1还没有释放)

1.2互斥的软件支持

软件支持包括操作系统和用语提供并发性的程序语言机制,常见并发机制如下:

concurrency_mechanism

1) 信号量

非二元信号量也称为计数信号量或一般信号量

基本原理:两个或多个进程同时操作信号量,根据信号量信息得到资源的使用情况。

实现:可以把信号量视为一个具有整数值的变量,定义三个操作:

  1. 一个信号量可以初始化为非负数
  2. semWait:操作使得信号量减一(说明要等待使用相关资源),若值变为负数,说明资源正在被使用,故阻塞发起semWait操作的进程。否则直接使用该资源。负数的绝对值为阻塞队列中的进程数量
  3. semSignal:操作使得信号量加一(说明资源使用完毕后释放资源),若值依然为小于等于0,说明有进程正在等待使用该资源,所以解除发起semWait的进程阻塞状态,使其获得资源的使用权,只要发起semSignal信号,就会唤起另一个进程,解除阻塞的进程要没有要么为1。

信号量原语(原子操作)的定义:

struct semaphore{
    int count;
    queueType queue;//阻塞队列
};

void semWait(semaphore s)
{
    s.count--;
    if(s.count < 0){
        /*把当前进程插入到队列当中*/;
        /*阻塞当前进程*/;
    }
}

void semSignal(semaphore s)
{
    s.count++;
    if(s.count <= 0){
        /*把进程P从队列中移除*/;
        /*把进程P插入到就绪队列*/;
    }
}

2) 二元信号量

二元信号量有更为严格的形式,二元信号量只能是0或1,具有三个操作:

  1. 二元信号量可以被初始化为0或1
  2. semWaitB操作检查信号的值,为0则阻塞,为1,则执行并将信号改为0。
  3. semSignalB操作检查队列是否有进程受阻,有则唤醒,没有则将信号设置为1
struct binary_semaphore{
    enum {zero,one} value;
    queueType queue;
};

void semWaitB(binary_semaphore s)
{
    if(s.value == one)
        s.value = zero;
    else{
        /*把当前进程插入到队列当中*/;
        /*阻塞当前进程*/;
    }
}

void semSignalB(binary_semaphore s)
{
    if(s.queue is empty())
        s.value = one;
    else{
        /*把进程P从等待队列中移除*/;
        /*把进程P插入到就绪队列*/;
    }
}

与二元信号量相关的一个概念就是互斥锁:

  • 二元信号量:多个进程同时操作信号量,根据信号量协调合作,可能出现一个进程对信号量进行加锁,另一个进程可以对该信号量进行解锁。相当于生产者和消费者在不同的进程。
  • 互斥锁:只能是同一个进程来对互斥量进行加锁和解锁操作。

  • 强信号量:队列设计为FIFO,被阻塞最久的进程最先从队列中释放(保证不会饥饿)
  • 弱信号量:没有规定进程从队列中移出顺序

使用信号量实现互斥

const int n = /*进程数*/
semaphore s = 1;

void P(int i)
{
    while(true){
        semWait(s);//请求信号
        /*临界区*/;
        semSignal(s);//释放信号
        /*其它部分*/;
    }
}

void main()
{
    parbegin(P(1),P(2),...,P(n));
}

信号量实现互斥及进程间合作提供了一个原始但功能强大且灵活的工具,但使用一个信号量设计正确的程序是很难的,难点在于semWait()和semSignal()分布在整个程序中,因为二元信号量可以由不同的进程来进行加锁和解锁,所以在理解资源的互斥上没有一个整体宏观的视角,这些信号的控制分散在进程之间,难以统一管理。

生产者和消费者问题有两点需要理解清楚:

  • 一次只能有一个实体(生产者和消费者)进入缓冲区来进行产品信息的变动,信号量s。
  • 缓冲区是否有产品来供消费者进行消费需要信号量来控制,信号量delay(不同线程进行加锁解锁)。

3)管程

管程(管理过程的工具)是一种程序设计语言结构,其实就是把信号量部分的相同处理代码抽象出来封装,它可以提供一个或多个过程、一个初始化序列和局部数据块组成的软件模块,主要特点如下:

  1. 局部数据变量只能被管程的过程访问,任何外部过程不能访问
  2. 一个进程通过调用管程的一个过程进入棺材
  3. 在任何时候,只能有一个进程在管程中执行,调用管程的其它进程都被阻塞
  • 管程会提供一种互斥机制,管程内部会有一个共享数据结构,管程会对这些数据提供保护和互斥机制。
  • 为了实现同步,管程必须包含同步工具(一次只有一个进程进入管程),管程会使用条件变量提供对同步的支持,这些变量包含在管程中,只有管程可以访问
    • cwait(c)
    • csignal(c)

管程的结构如下:

monitor

管程优于信号量在于,管程将所有的同步机制都封装在管程内部,因此,我们可以很容易对同步的过程进行管理,只要管程编写是正确的,同步访问资源的逻辑就是正确的。而对于信号量而言,所有同步的处理分布在对资源访问的步骤上,必须所有访问的逻辑是正确的,才能实现同步,难以管理

4)消息传递

最小操作集:

  • send(destination,message)
  • receive(source,message)

阻塞:当发送方send和接收方receive都会有两种可能:1)阻塞等待消息传递成功 2)不阻塞,继续发送和接受

通常有三种组合:阻塞send/阻塞receive,无阻塞send/阻塞receive,无阻塞send/无阻塞receive

发送者send和接收者receive之间有一层寻址关系,寻址方式分为两种

  1. 直接寻址
    • send显式指定目标进程标示号
    • receveive:1)显式指定源端口号 2)不可能指定所希望的源进程时,通过source参数保存相应信息
  2. 间接寻址:发送方通过向一个共享数据结构队列(“信箱”)发送消息,接收方去取消息,这里的发送者和接收者具有:一对一,一对多,多对弈,多对多的关系

消息格式:变长消息的典型格式

message_format

信息传递实现互斥:利用信箱实现,只给信箱传递一条信息时,相当于只有一个令牌(拥有该令牌就有进入临界区的权利),所以只设置一个令牌时就可以实现互斥

const int n = /*进程数*/;
void P(int i)
{
    message msg;
    while(true){
        receive(box,msg);
        /*临界区*/;
        send(box,msg);
        /*其它部分*/;
    }
}

void main()
{
    create mailbox (box);
    send(box,null);//发送一个令牌,实现互斥
    parbegin(P(1),P(2),...,P(n));
}

消息处理生产者和消费者问题:假设缓冲区容量为n,所以我们首先需要给信箱发送n个令牌,代表可以生产n个产品的权利,同时生产一个产品的同时,给消费者信箱发送一个消费令牌,表示可以消费一个产品的能力。具体代码见1.3

1.3两个经典问题

在设计同步和并发机制时,可以与一些经典问题联系起来,以检测该问题的解决方案对原问题是否有效

1)生成者/消费者问题

有一个或多个生产者生产某种类型的数据,并放置在缓冲区中;有一个消费者从缓冲区中取数据,每次取一项;

任何时候只有一个主体(生产者或消费者)可以访问缓冲区。要确保缓存满时,生产者不会继续添加,缓存为空时,消费者不会从中取数据

实现代码:

  • 当缓冲无限大时(二元信号量,对应图5.10;信号量,对应图5.11)
  • 当缓冲有限时(信号量,对应图5.13;管程,对应图5.16;消息传递,对应图5.21)

1)读者/写者问题

有一个由多个进程共享的数据区,一些进程只读取这个数据区中的数据,一些进程只往数据区中写数据;此外还满足以下条件:

  • 任意数量的读进程可以同时读这个文件
  • 一次只能有一个进程可以写文件
  • 如果一个进程正在写,禁止读文件

读优先:只要至少有一个读进程正在读,就为进程保留这个数据的控制权

read_first

写优先:保证当有一个写进程想写时,不允许新的读进程访问该数据

write_first

第六章.并发:死锁和饥饿

死锁定义:一组进程中的每个进程都在等待某个事件,而只有在这组进程中被阻塞的进程才能触发该事件,形成一个触发事件的闭包

假设两个进程的资源请求和释放序列如下:

ps_deadlock

联合进程图,x,y轴分别代表一个进程的执行路线,图中给出几种可能的执行路线,产生死锁的区域称为敏感区域:

union_ps

1.资源分类

  • 可重用资源:一次只能供一个进程安全的使用,并不会因为使用而耗尽的资源(包括处理器,I/O通道,内外存,设备等)
  • 可消耗资源:可以被进程创建和消耗的资源。(包括中断、信号、消息和I/O缓冲区里的消息)

资源分配图可以帮助我们很好理解死锁问题:

res_allocate

2.死锁的条件

死锁条件:

  1. 互斥:一次只有一个进程可以使用一个资源
  2. 占有且等待:当一个进程等待其它进程时,继续占有已经分配的资源
  3. 不可抢占:不能抢占进程已经占有的资源
  4. 循环等待:形成一个封闭的循环资源等待闭环

1,2,3是死锁可能发生的必要条件,4是死锁发生的结果(充分条件),也就是说当1,2,3成立时并且发生了4循环等待的情况就说明死锁发生

3.死锁预防

死锁预防分为两类:间接死锁预防(防止三个必要条件的发生)和直接死锁预防(防止充分条件的发生)的方法

死锁避免的方法都会导致低效的资源使用和低效的进程运行

3.1间接死锁预防:

  • 预防互斥:不可能禁止
  • 预防占用且等待一次性请求所有资源,有如下缺点:
    • 低效,进程为请求资源阻塞时间长
    • 资源被进程占有可能大部分时间不会用,但其它进程也不能使用
    • 一个进程可能事先并不能知道它所需要的所有资源
  • 预防不可抢占
    • 进程请求资源被拒绝时,释放掉自己占有的资源。必要时再申请
    • 进程请求被另一个进程占有的资源时,根据优先级抢占另一个进程的资源

3.2直接死锁预防:

预防循环等待:定义资源的线性顺序,一个进程若占有一个编号为i的资源,就不能请求那些编号小于i的资源

4.死锁避免

死锁避免不是通过预防可能使死锁发生的必要条件来实现的,而是在更多的考虑并发性的情况下,分析每个进程的资源请求是否会产生死锁,若会产生死锁则调用死锁避免

两种死锁避免的方法: 1. 进程启动拒绝:如果一个进程的请求会导致自锁,则不启动该进程 2. 资源分配拒绝:如果一个进程增加的资源请求会导致死锁,则不允许此分配

进程启动拒绝

一个有n个进程,m种不同类型资源的系统。定义如下向量和矩阵:

res_ps_matrix

从中可以看出以下关系成立: relation

对于进程n+1的新进程要请求资源j时要满足下面关系才能启动: condition

资源分配拒绝(银行家算法)

当进程请求一组资源时,假设同意该请求,从而改变了系统的状态,然后确定其结果是否处于安全状态。如果是,则同意该请求,如果不是,阻塞该该进程直到同意该请求后系统状态仍然是安全的。

安全状态:至少有一个资源分配序列不会导致死锁,其实也就是判断,该进程i对任意资源j的需求量Cij减去进程i对j的占有量Aij要少于j资源的剩余量Vij:Cij-Aij≤Vij 不安全状态:非安全的状态,所有的分配序列都不可行

下图为一个安全序列:

safe_seq

下图为一个不安全序列: unsafe_seq

这个不安全序列并不是一个死锁状态,仅仅是有可能死锁。

优点

  • 不需要死锁预防中的抢占和回滚进程,并且比死锁预防的限制少,允许更多并发

缺点

  • 必须事先声明每个进程请求的最大资源(需求量)
  • 所讨论的进程必须是无关的,也就是说,他们执行的顺序没有任何同步要求的限制
  • 分配的资源数码必须是固定的
  • 在占有资源时,进程不能退出

5.死锁检测

死锁检测不限制访问资源,只要有可能就会给进程分配其所请求的资源,然后操作系统周期性地执行一个算法来检测前面的条件4(循环等待)

常见的死锁检测算法: deadlock_detect

这种算法的策略是查找一个进程,使得可用资源可以满足该进程的资源请求,然后假设同意这些资源,让该进程运行直到结束,再释放它的所有资源。然后算法再寻找另一个可以满足资源请求的进程

这个算法并不能保证防止死锁,释放死锁要取决于将来同意请求的次序,它所做的一切是确定当前是否存在死锁

恢复

一旦检测到了死锁,就需要某种策略来恢复死锁的状态,有以下几种方法来恢复:

  • 取消所有死锁进程(操作系统最常用)
  • 回滚每个死锁进程到前面定义的检查点
  • 连续取消死锁进程直到不再存在死锁(基于最小代价)
  • 连续抢占资源直到不再死锁(基于代价选择,每次抢占后需要重新调用算法检测,被强占的进程需要回滚)

6.死锁“预防/避免/检测”总结

deadlock_summary

7.经典问题:哲学家问题

philosopher

哲学家的生活除了思考就是吃面,每个哲学家吃面都要使用两把叉子,按先左后右的方式取叉子。要设计一套算法,保证互斥(每个叉子只能被一个哲学家使用),且不会发生死锁和饥饿。

方法一(基于信号量,可能死锁):

每位哲学家首先拿起左边的叉子。吃完面后,把叉子放回,如果所有哲学家同时拿左边的叉子,会产生死锁。

ph_signal

第二种方法,不会死锁,增加一个服务员(信号量),来控制只能有四个哲学家同时进餐,因而不会形成闭环,造成死锁

ph_signal_no_dl

方法二(基于管程,不会死锁):

这里管程的操作将取叉子(左和右)封装到管程的内部,且一次只能有一个进程进入管程,说明拿叉子(两边叉子)的动作一次只有可能一个哲学家在做。

ph_monitor

8.UNIX并发机制

UNIX为进程间的通信和同步,提供了下列重要的通信机制:

  • 提供进程间传递数据的方法
    • 管道
    • 消息
    • 共享内存
  • 触发其它进程的行为
    • 信号量
    • 信号

8.1管道、消息、共享内存、信号量、信号的概念和使用详见博客-进程间通信

9.Linux内核并发机制

Linux包含了在其它UNIX系统中出现的所有的并发机制,除此之外还包括

  • 原子操作
  • 自旋锁
  • 信号量
  • 屏障

9.1原子操作

Linux提供了一组操作以保证对变量的原子操作。这些操作能够用来避免简单的竞争条件。原子操作执行时不会被打断或被干涉

* 在单处理器上:线程一旦启动原子操作,则从操作开始到结束的这段时间内,线程不能被中断
* 在多处理器上:原子操作所针对的变量是被锁住的,以免被其他的进程访问,直到原子操作执行完毕

Linux中定义了2种原子操作:

* 针对整数变量的整数操作:定义了一个特殊的数据类型atomic_t,原子整数操作仅能用在这个数据类型上,其它操作不允许用在这个数据类型上
* 针对位图中某一位的位图操作:操作由指针变量指定任意一块内存区域的位序列中的某一位。因此没有和原子整数操作中atomic_t等同的数据类型

Linux原子操作表: atomic_op

9.2自旋锁

自旋锁是Linux中保护临界区的最常用技术,在互斥的硬件支持中,我们看到了比较和交换指令中需要不断while循环测试是否bolt为0,为0则获得进入临界区的权限,这里自旋锁相当于把这个过程封装了一次,省去了while循环,同时可以一直尝试获取lock锁,如果没有获得,就会一直尝试(忙等)直到获得该帧。

  • 普通自旋锁:占有该锁后,其它进程不能占有
  • 读者-写者自旋锁:允许多个线程同时以只读方式访问同一数据结构,只有当一个线程想要更新时,才会互斥访问

自旋锁操作表:

selflock_op

9.3信号量

内核的信号量不能通过系统调用直接被用户程序访问。内核信号量是作为内核内部函数实现的,比用户可见的信号量更高效

  • 二元信号量:在Linux中也称为互斥信号量MUTEX
  • 计数信号量
  • 读者-写者信号量:允许多个并发的读者,仅允许一个写者。事实上,对于读者使用的是一个计数信号量,而对于写者使用的是一个二元信号量

Linux提供3种版本的down操作,这里down相当于semWait,up相当于semSignal

  • down:对应于传统的semWait操作
  • down_interruptible:允许因down操作而被阻塞的线程在此期间接收并响应内核信号
  • down_trylock:可在不被阻塞的同时获得信号量,如果信号量不可用,返回非0值,不会阻塞线程,只是尝试获取锁

信号量操作: semaphore

9.4屏障

屏障用于保证指令执行的顺序。如,rmb()操作保证了之前和之后的代码都没有任何读操作会穿过屏障

对于屏障操作,需要注意2点:

  1. 屏障和机器指令相关,也就是装载和存储指令(高级语言a=b会产生2个指令)
  2. 编译方面,屏障操作指示编译器在编译期间不要重新排序指令;处理器方面,屏障操作指示流水线上任何屏障前的指令必须在屏障后的指令开始执行之前提交 barrier()操作是mb()操作的一个轻量版本,它仅仅控制编译器的行为

屏障操作表:

barrier

第七章、内存管理

  • 单道程序设计系统:内存划分为两部分,一部分供操作系统使用,一部分供应用程序使用
  • 多道程序设计的系统:必须在内存中进一步细分出”用户”的部分,满足多个进程的要求,细分的任务由操作系统完成,这就叫内存管理。

内存管理的需求:

  • 重定位:程序在从磁盘换入内存时,换入要放到相同的内存区域会很困难,要可以被装载到内存中的不同区域。
  • 保护:处理器保证其它进程不能在未经授权访问该进程的内存单元
  • 共享:任何保护机制都必须具有一定灵活性,以允许多个进程访问内存的同一部分
  • 逻辑组织
  • 物理组织

内存管理中的地址

  • 逻辑地址:指与当前数据在内存中的物理分配地址无关的访问地址,执行对内存访问前必须转换成物理地址(类似页码,门牌号,ip地址),将物理内存组织成逻辑结构
  • 相对地址:逻辑地址的一个特例,是相对于某些已知点(通常是程序开始处)的存储单元
  • 物理地址(绝对地址):数据在内存中的实际位置(实际地址,MAC地址)
  • 虚拟地址:虚拟内存中的逻辑地址

1.内存分区

1.1固定分区

系统生成阶段,内存被划分成许多静态(大小,容量固定不变)分区,两种固定分区:

  • 分区大小相等
  • 分区大小不等

放置策略:

  1. 对于分区大小相等的固定分区

    • 只要存在可用分区就可以分配给内存

    • 缺点:

      • 对于大内存进程,一个分区可能无法装下,需要使用覆盖技术设计程序。
      • 对于小内存进程,也要占用一个内存分区,导致内存利用率低。出现很多内部碎片没得到使用
  2. 对于分区大小不等的

    • 每个进程分配到能容纳它的最小分区:每个分区维护一个队列(当全是小进程时,大内存分区一直得不到使用,小分区一直存在排队现象)
    • 每个进程分配到空闲且能容纳它的最小可用分区:只需要维护一个队列

存在内部碎片,活动进程数固定

1.2动态分区

并不进行预先分区,在每次需要为进程分配时动态划分

外部碎片(随着时间的推移,内存中的分区外的碎片越来越多,与前面提到的分区内的内部碎片对应)

dynamic_partition

压缩:动态移动进程的内存分区,使得所有碎片整合到一整块,但这个操作非常耗时,需要动态重定位的能力。

放置算法:由于压缩非常耗时,因此需要巧妙的把进程分配到内存中,塞住内存的”洞”

  • 最佳适配:选择与要求大小最接近的块(性能最差,虽然每次浪费的空间最小,但是很快产生许多小碎片)
  • 首次适配:选择大小足够的第一个块,只要适配就装进去(最简单,最好,最快,容易在首部产生碎片)
  • 下次适配:也是遇到可以容纳的分区就装进去,但不同于首次适配的是,下一次适配不是从头扫描,而是从这次适配的位置继续扫描

1.3伙伴系统

固定分区限制了活动进程数量,并且内存空间利用率低,动态分区,维护复杂,且需要引入压缩解决外部碎片产生额外的开销,所以我们需要一种折中的方案:伙伴系统,克服了这些缺陷。

伙伴系统原理:内存最大块和最小块的尺寸是M和L。在为一个进程分配空间时,如果需要的内存大于L/2,则分配L的内存,否则,将大小为L的块分成两个L/2的块,继续上述步骤;如果两个相邻的块(伙伴)都未分配出去(如前面的进程释放后),则将其合并

通俗的理解就是将首次适合该进程内存的分区不断进行二分适配,尽量提高内存的利用率,并且当内存释放后,出现之前划分的伙伴分区L/2,L/2都没被使用,则进行合并。

1.4分区中的地址转换

逻辑地址->物理地址的转换:

redirection

程序的换入和换出必须要设置这两个寄存器:基址寄存器和界限寄存器,然后程序可以利用相同的相对地址来访问程序,即使被装入的内存地址和之前不一样,程序依然可以正确重定位到指定位置。同时这种方案提供了一种对进程映像的保护,根据基址寄存器和界限寄存器限制其它进程的访问。

2.分页

内存被划分为大小固定的块,且块相对比较小,每个进程也被分成同样大小的小块,那么进程中称为页的块可以指定到内存中称为页框的可用块。和固定分区的不同在于:一个程序可以占据多个分区,这些分区不要求连续

使用分页技术在内存中每个进程浪费的空间,仅仅是最后一页的一小部分(内部碎片)

page_partition

  • 页:相对于进程的地址空间而言
  • 页框:相对于内存中的固定分区

将进程运行在系统中,操作系统需要维护一个页表来记录进程中的页和内存中的页框的映射关系

逻辑地址:包括一个页号和偏移量,操作系统首先找到该页号对应的页框,再根据偏移量定位得到物理地址(页框号,偏移量)

logic_address

3.分段

段有一个最大长度限制,但不要求所有程序的所有段长度都相等。分段类似于动态分区,区别在于:一个程序可以占据多个不连续的分区

分段同样会产生外部碎片,但是进程被划分成多个小块,因此外部碎片也会很小

由于进程的段可能不连续,因此也不能仅靠一个简单的基址寄存器,地址转换通过段表实现。由于段的大小不同,因此段表项中还包括段的大小

segment_patition

4.内存安全

4.1缓冲区溢出

缓冲区溢出是指输入到一个缓冲区或者数据保存区域的数据量超过了其容量,从而导致覆盖了其它区域数据的状况。攻击者造成并利用这种状况使系统崩溃或者通过插入特制的代码来控制系统

被覆盖的区域可能存有其它程序的变量、参数、类似于返回地址或指向前一个栈帧的指针等程序控制流数据。缓冲区可以位于堆、栈或进程的数据段。这种错误可能产生如下后果:

  1. 破坏程序的数据
  2. 改变程序的控制流,因此可能访问特权代码

最终很有可能造成程序终止。当攻击者成功地攻击了一个系统之后,作为攻击的一部分,程序的控制流可能会跳转到攻击者选择的代码处,造成的结果是被攻击的进程可以执行任意的特权代码(比如通过判断输入是否和密码匹配来访问特权代码,如果存在缓冲区漏洞,非法输入导致存放“密码”的内存区被覆盖,从而使得“密码”被改写,因此判断为匹配进而获得了特权代码的访问权)

第八章.虚拟内存

一个进程只能在内存中执行,因此这个存储器称为实存储器,简称实存(确确实实在内存中)。但是程序员或用户感觉到的是一个更大的内存,通常它被分配在磁盘上,称为虚拟内存,简称虚存(只有部分运行在内存中)

虚存使得程序不必完全载入内存才能运行,每次可以只有部分驻留在内存中。如果处理器访问一个不在内存中的逻辑地址,则产生一个中断,说明产生了内存访问故障。操作系统把被中断的进程置于阻塞态。为了能继续执行这个进程,操作系统必须把包含引发访问故障的逻辑地址的进程块读入内存。为此,操作系统产生一个磁盘I/O读请求。在此期间,可以调度另一个进程运行。一旦需要的块被读入内存,则产生一个I/O中断,操作系统把由于缺少该块而被阻塞的进程置为就绪态

系统抖动:如果一个块正好在将要被用到之前换出,操作系统就不得不很快把它取回来。太多这类操作会导致一种称为系统抖动的情况,处理器大部分时间都用于交换块,而不是执行指令

虚拟内存和简单分页分段内存的地址转换过程是一致的,只不过虚拟内存通过页表和段表访问的内存页不在内存中,需要读入到磁盘,同时置换其它页面写入到磁盘,而简单分页分段的进程所有内存页面都在内存中

1.分页

1.1页表

  • 每个进程都有自己的页表
  • 由于进程某些页可能不在内存中,所以页表项中有一位(P)表示该页是否在内存中
  • 页表项有一位(M)表示该页(从上次载入)是否已经被修改,dirty,如果没有修改则换出时,不用更新磁盘。
  • 页表的长度可以基于进程的长度而变化,因此不能在寄存器中保存它(对于占据大量虚存空间的程序,其页表很大,因此页表通常保存在虚存中,因此页表也服从分页管理)
  • 一个程序正在运行时,页表至少有一部分必须在内存中

1.2一级分页系统中的地址转换

一级分页系统中的虚拟地址和页表项: page_table

地址转换: address_convert

1.3两级分页系统中的地址转换

两级页表结构(假设页大小为4KB,每个页表项大小为4B):

twoclass_pagetable

地址转换:

twoclass_add_convert

1.4倒排页表

一级和两级分页系统中的页表存在一个缺陷:页表的大小与虚拟地址空间的大小成正比

一种替代方法是使用一个倒排页表,其结构如下:

reverse_table

页表结构之所以称为”倒排“,是因为它使用页框号而非虚拟页号来索引页表项

1.5转换检测缓冲区(TLB)

原则上,每次虚拟内存访问可能引起两次物理内存访问:一次取相应的页表项,一次取需要的数据。因此,简单的虚拟内存方案会导致内存访问时间加倍

TLB保存在高速缓冲存储器(相对于内存访问速度越快)中,它记录了最近用到过的页表项。给定一个虚拟地址,处理器首先检查TLB:

  • 如果需要的页表项在其中,则检索页框号并形成实地址
  • 如果未找到需要的页表项,则处理器用页号检索进程页表,并检查相应的页表项。
    • 如果”存在位“置位,则页在内存中,处理器从页表项中检索页框号形成实地址。并更新TLB
    • 如果”存在位”没置位,表示需要的页不在内存中,这时发生缺页中断,因此离开硬件作用范围,调用操作系统,操作系统负责载入所需要的页,并更新页表

tlb_pagetable

虚拟机制必须与高速缓存系统进行交互,一个虚拟地址通常为页号、偏移量的形式。首先,内存系统查看TLB(对页表进行高速缓存)中是否存在匹配的页表项,如果存在,通过把页框号和偏移量组合起来产生实际地址(物理地址);如果不存在,则从页表中读取页表项。一旦产生了一个由标记和其余部分组成的实地址,则查看高速缓存(对内存中的内容进行缓存)中是否存在包含这个字的块。如果有,把它返回给CPU;如果没有,从内存中检索这个字。(页表和内存内容两部分利用高速缓存,都是利用了局部性原理

cache&memory

2.分段

  • 每个进程都有一个唯一的段表。
  • 进程可能只有一部分段在内存中,所以段表项中有一位表明相应段是否在内存中
  • 段表项有一位修改位表明相应段从上一次载入起是否被改变
  • 根据进程大小,段表长度可变,而无法在寄存器中保存

2.1分段系统中的地址转换

segment_add_convert

2.2保护和共享

分段有助于实现保护与共享机制。由于每个段表项包括一个长度和一个基地址,因而程序不会不经意地访问超出该段的内存单元。为实现共享,一个段可能在多个进程的段表中被引用

3.段页式

  • 分页对程序员是透明的,它消除了外部碎片,而已可以更有效地使用内存
  • 分段对程序员是可见的,它具有处理不断增长的数据结构的能力以及支持共享和保护的能力

可以将分页和分段结合,即段页式

在段页式系统中,用户的地址空间被程序员划分成许多段。每个段依次划分成许多固定大小的页,页的长度等于内存中的页框大小。如果某一段的长度小于一页,则该段只占据一页。从程序员角度看,逻辑地址仍然由段号和段偏移量组成;从系统角度看,段偏移量可视为指定段中的一个页号和页偏移量。

段以页为最小单位动态分配内存,系统的内存管理是分页,程序员的视角则是分段,中间进行段页转换。

page_segment_add

4.内存管理中的相关策略

4.1读取策略

读取策略确定一个页何时取入内存:

  • 请求分页:只有当访问到某页中的一个单元时才将该页取入内存
  • 预先分页:读取的页并不是缺页中断请求的页,如果一个进程的页被连续存储在辅存中,则一次读取许多连续的页

4.2放置策略

放置策略决定一个进程块驻留在实存中的什么地方

  • 在一个纯粹的分段系统中,放置策略并不是重要的设计问题(诸如最佳适配、首次适配等都可供选择)
  • 对于纯粹的分页系统或段页式系统,如何放置通常没有关系,因为地址转换硬件和内存访问硬件可以以相同的效率为任何页框组合执行它们的功能

4.3置换策略

置换策略决定在必须读取一个新页时,应该置换内存中的哪一页

页框锁定:如果一个页框被锁定,当前保存在该页框中的页就不能被置换。大部分操作系统内核和重要的控制结构就保存在锁定的页框中。此外,I/O缓存区和其它对时间要求严格的区域也可能锁定在内存的页框中

基本置换算法

  • 最佳(OPT):置换下次访问距当前时间最长的那些页,该算法能导致最少的缺页中断(由于要求操作系统必须知道将来的事件,因此不可能实现,而是作为一种标准来衡量其它算法的性能
  • 最近最少使用(LRU):置换内存中上次使用距当前最远的页,LRU性能接近于OPT,但是难以实现(一种方法是为每一页添加一个最后一次访问的时间戳,但是开销较大)
  • 先进先出(FIFO):把分配给进程的页框视为一个循环缓冲区,按循环的方式移动页。实现简单,但性能较差(隐含的逻辑是置换驻留在内存中时间最长的页,经常会出现部分程序或数据在整个程序的生命周期中使用频率都很高的情况,如果使用FIFO这些页会需要反复地被换入换出
  • 时钟:时钟策略是试图以较小的开销接近LRU性能的一种算法,最简单的时钟策略需要给每一页关联一个附加位,称为使用位。当某一页首次装入内存中时,该页的使用位设置为1;当该页随后被访问到时,它的使用位也会被置为1。当需要置换一页时,操作系统扫描缓冲区,以查找使用位被置为0的一个页框。每当遇到一个使用位为1的页框时,就将该位重新置为0,等待下次循环扫描若还为0则被置换

page_stream

4.4驻留集管理

对于分页式的虚拟内存,在准备执行时,不需要也不可能把一个进程的所有页都读入内存。因此,操作系统必须决定读取多少页,即给特定的进程分配多大的内存空间。需要考虑以下几个因素:

  • 分配给一个进程的内存越少,在任何时候驻留在内存中的进程数就越多(这就增加了操作系统至少找到一个就绪进程的可能)
  • 如果一个进程在内存中的页数比较少,尽管有局部性原理,缺页率仍然相对较高
  • 如果分配过多页,由于局部性原理,该进程的缺页率没有明显的变化

基于上述因素,通常采用两种策略:

  1. 固定分配策略:为一个进程在内存中分配固定数目的页框用于执行时使用,这个数目在最初加载时(创建进程时)决定(可以根据进程类型或程序员的需要确定)。一旦发生缺页中断,进程的一页必须被它所需要的页面置换
  2. 可变分配策略:允许分配给一个进程的页框在进程的生命周期中不断地变化。如果缺页中断多,则多分配一些;缺页中断少,适当减少分配。这种方法的难点在于要求操作系统评估活动进程的行为

置换范围

  • 局部置换策略(置换时只考虑本进程内存空间):仅仅在产生缺页的进程的驻留页中选择
  • 全局置换策略(置换时从全局内存空间考虑):把内存中所有未被锁定的页都视为置换的候选页,而不管它们属于哪个进程

可变分配、全局范围:发生缺页时,如果存在空闲页框,则使用空闲页框;否则在全局页框中选择置换 可变分配、局部范围:不时评估进程的页框分配情况,增加或减少分配给它的页框

replace_strategy

4.5清除策略

清除策略与读取策略相反,它用于确定在何时将一个被修改过的页写回辅存,通常有2种选择

  • 请求式清除:只有当一页被选择用于置换时,才被写回辅存(可以减少写页,但意味着发生缺页中断的进程在解除阻塞之前必须等待两次页传送,这可能降低处理器的利用率)
  • 预约试清除:将被修改的多个页在需要用到它们占据的页框之前成批地写回辅存(并没有太大意义,因为这些页中大部分常常会在置换之前又被修改,辅存传送能力有限,不应该浪费在不太需要的清楚操作上)
  • 比较好的方法是结合页缓冲技术:利用空闲页链表和修改页链表来缓存内存页,被置换页的页表项被添加到这两个链表中,且依然在内存中,且已修改按蔟写回,大大减少了I/O操作

4.6加载控制

加载控制决定驻留在内存中的进程数目,称为系统并发度

并发度太低会导致处理器利用率不高,并发度太高会发生系统抖动

第九章.单处理器调度

1.进程调度类型

schedule_type

调度类型和进程状态转换:

schedule_convert

长程调度:决定哪一个程序可以进入系统中处理,因此控制着系统的并发度 中程调度:将进程从磁盘换入到内存的过程 短程调度:将进程在内存中直接切换状态

在批处理系统或者操作系统的批处理部分,新提交的作业被发生到磁盘,并保存在一个批处理队列中。在长程调度程序运行的时候,从队列中创建相应的进程。这里涉及两个决策:

  • 调度程序决定何时操作系统接纳一个进程或者多个进程
  • 调度程序决定接收哪个作业或哪些作业,并将其转变成进程

schedule_procedure

长程调度执行频率较低,并且仅仅是粗略地决定是否接受新进程及接受哪一个

该章剩余内容主要关注短程调度,即处理器选择一个进程执行时的调度决策。短程调度执行得最频繁,并且精确地决定下一次执行哪个进程

2.调度算法

2.1 短程调度准则

调度算法的设计需要考虑如下方面(以下为从一种维度的划分):

  • 面向用户的准则:延迟(侧重于用户)
  • 面向系统的准则:效果、利用率、吞吐量(侧重于系统)

2.2 优先级调度

  • 每个进程被指定一个优先级,调度程序总是优先选择具有较高优先级的进程
  • 低优先级进程可能饥饿

2.3 选择调度策略

  • 周转时间:等待时间 + 服务时间
  • 归一化周转时间:周转时间/服务时间

1)先来先服务(FCFS)

  • 非抢占
  • 对短进程不利(相对于I/O密集型的进程,更利于处CPU密集型的进程);一种改进是与优先级结合,每个优先级一个队列,同一队列内部使用FCFS

2)轮转(时间片)

  • 以时间片为周期产生时钟中断,切换运行
  • 主要设计问题是时间片的长度,太短时间片会带来频繁的进程上下文切换开销。时间片过长(比最长进程还长),算法就退化成了FCFS

3)最短进程优先(SPN)

  • 非抢占
  • 每次调度选择(所需总)处理时间最短的进程。可能饥饿长进程
  • 难点在于需要估计每个进程所需要的处理时间

4)最短剩余时间(SRT)

  • 抢占
  • 每次选择剩余处理时间最少的进程,可能饥饿长进程
  • 也需要估计每个进程所需的处理时间。同时,维护过去的服务时间也会增加开销

5)最高响应比(HRRN)

  • 非抢占
  • 调度选择归一化周转时间最大的进程,归一化时间越大说明进程“年龄”越大。当偏向短作业时(小分母产生大比值),长进程由于得不到服务,等待的时间不断增加,从而增大了比值,最终在竞争中可以胜出
  • 同样需要预估每个进程所需的处理时间

6)反馈法

  • 抢占
  • 反馈法为了解决SPN、SPT和HRRN必须预估进程所需处理时间的问题(不能获得剩余执行时间就关注已经执行了的时间)。通过处罚运行时间较长进程的方法来偏向短进程。进程每被抢占一次(说明进程还未运行完,可能是个长进程),就移入更低优先级的队列。在这种机制下,短进程在降级过多前就能运行完,长进程会一直降级,如果已经处于最低级队列,则再次被抢占后返回该队列。
  • 这种方法的问题是长进程的周转时间可能惊人的增加,导致饥饿,一种方法是可以增加低优先级队列中进程运行的时间片,但仍可能饥饿,还有一种方法是如果在低级队列中时间过长,提升到高优先级队列中

调度策略对比总结:

性能比较

调度策略的性能是选择调度策略的一个关键因素。但是由于相关的性能取决于各种各样的因素,包括各种进程的服务时间分布、调度的效率、上下文切换机制、I/O请求的本质和I/O子系统的性能,因而不可能得到明确的比较结果

2.4 调度实例分析

给出如下进程以及到达时间和服务时间:

使用各种调度策略:

第十章.I/O管理与磁盘调度

1.I/O缓冲

缓冲技术:在输入请求发出之前就开始执行输入传送,并且在输出请求发出一段时间之后才开始执行输出传送,这项技术称为缓冲

两类I/O设备:

  • 面向块的I/O设备:将信息保存在块中,块的大小通常是固定的,传送过程中一次传送一块
  • 面向流的I/O设备:以字节流的方式输入/输出数据,没有块结构

1.1 单缓冲

对于面向块的I/O设备

  • 输入传送的数据被放到系统缓冲区中。当传送完成时,进程把该块移到用户空间,并立即请求另一块
  • 相对于无缓冲的情况,这种方法通常会提高系统速度。用户进程可以在下一数据块读取的同时,处理已读入的数据块。由于输入发生在系统内存中而非用户进程内存中,因此操作系统可以将该进程换出

对于面向流的I/O设备

单缓冲方案能以每次传送一行的方式或者每次传送一个字节的方式使用

1.2 双缓冲(缓冲交换)

分配2个缓冲区。在一个进程往一个缓冲区中传送数据(从这个缓冲区中取数据)的同时,操作系统正在清空(或者填充)另一个缓冲区

1.3 循环缓冲

双缓冲方案可以平滑I/O设备和进程之间的数据流。如果关注的焦点是某个特定进程的性能,那么常常会希望相关I/O操作能够跟得上这个进程。如果该进程需要爆发式地执行大量的I/O操作,仅有双缓冲就不够了,在这种情况下,通常使用多于两个的缓冲区方案来缓解不足

1.4 I/O缓冲的作用

I/O缓冲是用来平滑I/O需求的峰值的一种技术,但是当进程的平均需求大于I/O设备的服务能力时,缓冲再多也不能让I/O设备与这个进程一直并驾齐驱。即使有多个缓冲区,所有的缓冲区终将会被填满,进程在处理完每一大块数据后不得不等待。但是,在多道程序设计环境中,当存在多种I/O活动和多种进程活动时,缓冲是提高操作系统效率和单个进程性能的一种方法

2.磁盘调度

2.1 磁盘性能参数

  • 寻道时间:磁头定位到磁道所需的时间
  • 旋转延迟:选好磁道后,磁头到达扇区开始位置的时间
  • 存取时间:寻道时间+旋转延迟
  • 传输时间:磁头定位到扇区开始位置后,数据读写的时间
  • 排队时间

2.2 磁盘调度算法

在多道程序环境中,操作系统为每个I/O设备维护一个请求队列。因此对一个磁盘,队列中可能有来自多个进程的许多I/O请求。如果随机地从队列中选择请求,那么磁道完全是被随机访问的,这种情况下性能最差。随机调度可用于与其他调度算法进行对比

1)先进先出(FIFO)

  • 按顺序处理队列中的请求
  • 如果有大量进程竞争一个磁盘,这种算法在性能上往往接近于随机调度

2)优先级

  • 这种方法不会优化磁盘利用率,但可以满足操作系统的其它目标
  • 通常比较短的批作业和交互作业的优先级比较高。长作业可能饥饿
  • 可能会导致部分用户采用对抗手段:把作业分成小块,以回应系统的这种策略。对于数据库系统,这种算法往往性能较差

3)最短服务时间优先(SSTF)

  • 选择使磁头臂从当前位置开始移动最少(最小寻道时间)的磁盘I/O请求
  • 但是,总是选择最小寻道时间并不能保证平均寻道时间最小,不过能提供比FIFO更好的性能
  • 磁头臂可以沿两个方向移动

3)SCAN

  • 运行类似电梯。磁头臂沿某一方向移动,并在途中满足所有未完成请求,直到到达最后一个磁道,或者该方向上没有更多请求。接着反转服务方向
  • 偏向接近最靠里或最靠外的磁道的请求,并且偏向最近的请求,可能发生饥饿

4)C-SCAN

  • 沿某个方向的扫描结束后,返回到相反方向的末端,再次扫描
  • 减少了新请求的最大延迟
  • 可能饥饿

5)N-step-SCAN(N步扫描)

SSTF、SCAN和C-SCAN可能在一段很长时间内磁头臂都不会移动(比如一个或多个进程对一个磁道有较高的访问速度,通过重复的请求这个磁道垄断整个设备),从而饥饿其它请求

  • 把请求队列分成长度为N的子队列,每一次用SCAN处理一个子队列。在处理一个子队列时,新请求必须添加到其它某个队列中
  • 对于比较大的N值,性能接近SCAN;当N=1时,实际上就是FIFO

2.3 磁盘调度算法比较

假设有一些I/O请求,需问这些磁道:55、58、39、18、90、160、150、38、184

使用不同磁盘调度算法的结果如下:

3.磁盘高速缓存

一个磁盘高速缓存是内存中为磁盘扇区设置的一个缓冲区,它包含有磁盘中某些扇区的副本。当出现一个请求某一特定扇区的I/O请求时,首先进行检查,以确定该扇区是否在磁盘高速缓存中。如果在,则该请求可以通过这个高速缓存来满足;如果不在,则把请求的扇区从磁盘读到磁盘高速缓存中