计算机操作系统学习笔记

特色图像作者pixivuid:54196186

Author:王之山??????

操作系统引论

操作系统是一组有效地组织和管理计算机硬件软件资源,合理地对各类作业进行调度,以及方便用户使用程序的集合。

  • 操作系统的目标:方便性 有效性 可扩充性 开放性
  • 操作系统的作用
    • OS作为用户与计算机硬件系统之间的接口
    • OS作为计算机系统资源的管理者
    • OS实现了对计算机资源的抽象
  • 操作系统作为用户计算机硬件系统之间的接口
  • 操作系统作为计算机系统资源的管理者:对处理机、存储器、IO设备、文件(数据和程序)进行有效的管理。
  • 操作系统实现了对计算机资源的抽象
  • 简述操作系统的发展历史
    • 第一代是手工操作方式 没有OS 用户独占全机并且CPU等待人工操作 CPU与IO设备之间的速度不匹配
    • 第二代是脱机输入/输出方式 优点:减少了CPU的空闲时间;提高了IO速度
    • 单道批处理系统 缺点还是系统中的资源得不到充分的利用
    • 多道批处理系统 优点:资源利用率高 系统吞吐量大 平均周转时间长 无交互能力
    • 分时系统 为了引入人机交互 共享主机 分时系统的特征:多路性 独立性 及时性 交互性
    • 实时系统 例如工业控制系统 信息查询系统 多媒体系统 嵌入式系统 任务分为周期性实时任务和非周期性实时任务/硬实时任务和软实时任务 特征:多路性 独立性 及时性 交互性 可靠性
    • 微机操作系统
      • 单用户单任务操作系统(MS-DOS)
      • 单用户多任务操作系统(windows)
      • 多用户多任务操作系统(Linux)
  • 操作系统的基本特征
    • 并发
      • 进程:在系统中能独立运行并作为资源分配的基本单位 多个进程之间可以并发执行和交换信息
    • 共享 系统中的资源可供内存中多个并发执行的进程共同使用
      • 互斥共享
      • 同时访问
    • 虚拟
      • 时分复用技术 虚拟处理机技术 虚拟设备技术
      • 空分复用技术 虚拟内存
    • 异步
  • 操作系统的主要功能
    • 处理机管理功能:处理机的分配都是以进程为基本单位的,因而对处理机的管理可归结为对进程的管理 主要功能有 创建和撤销进程 对进程的运行进行协调 实现进程之间的信息交换 按照一定的算法把处理机分配给进程
      • 进程控制
      • 进程同步
      • 进程通信
      • 调度 作业调度(从后备队列中按照一定的算法选择出若干个作业 为他们分配运行所需的资源) 和 进程调度(从进程的就绪队列中按照一定的算法选出一个进程 将处理机分配给他)
    • 存储器管理功能
      • 内存分配 静态分配和动态分配
      • 内存保护
      • 地址映射 将地址空间中的逻辑低址转换为内存空间中与之对应的物理低址
      • 内存扩充 请求调入功能 置换功能
    • 设备管理功能
      • 缓冲管理 缓和CPU和I/O设备之间速度不匹配的问题
      • 设备分配
      • 设备处理 设备驱动程序
    • 文件管理功能
      • 文件存储空间的管理
      • 目录管理
      • 文件的读写管理与保护
    • 操作系统和用户之间的接口
      • 用户接口
        • 联机用户接口
        • 脱机用户接口
        • 图形用户接口
      • 程序接口 用户程序取得操作系统服务的唯一途径
  • 课后习题
    1. 设计现代OS的主要目标是:有效性 方便性 可扩充性 开放性
    2. OS的作用表现在哪几个方面
      1. OS作为用户和计算机硬件系统之间的接口
      2. OS作为计算机系统资源的管理者
      3. OS实现了对计算机资源的抽象
    3. 为什么OS实现了对计算机资源的抽象OS首先在裸机上覆盖一层I/0设备管理软件,实现了对计算机硬件操作的第一层次抽象;在第一层软件上再覆盖文件管理软件,实现了对硬件资源操作的第二层次抽象。OS通过在计算机硬件上安装多层系统软件,增强了系统功能,隐藏了对硬件操作的细节,由他们共同实现了对计算机资源的抽象
    4. 推动多道批处理系统形成和发展的主要动力是什么主要来源于四个方面的社会需求和技术发展:不断提高计算机资源的利用率方便用户器件的不断更新换代计算机体系结构的不断发展
    5. 什么是脱机I/O和联机I/O脱机IO是指事先将装有用户程序和数据的纸带或卡片装入指代输入机,在外围机的控制下,把纸带或卡片的数据或程序输入到磁带上。该方式下的输入输出由外围机控制完成,是在脱离主机的情况下进行的。而联机IO方式是指程序和数据的输入输出都是在主机的直接控制下进行的。
    6. 试说明推动分时系统形成和发展的主要动力是什么?推动分时系统形成和发展的主要动力是更好的满足用户的需要,主要表现在:CPU的分时是用缩短了作业的平均周转时间;人机交互能力使用户能直接控制自己的作业;主机的共享使用多用户能同时使用同一台计算机,独立的处理自己的作业。
    7. OS的几大特征并发性 共享性 虚拟性 异步性
    8. 尝试描述什么是微内核OS
      1. 足够小的内核
      2. 基于C/S模式
      3. 应用机制与策略分离原理
      4. 采用面向对象技术
    9. 何谓微内核技术?在为内核中通常提供了哪些功能?把操作系统中更多的成分和功能放到了更高的层次(用户模式)中去运行,而留下一个尽量小的内核,用它来完成操作系统最基本的核心功能,称这种技术为微内核技术。在微内核中通常提供了线程管理、低级存储器管理、中断和陷入处理等功能。

进程的描述与控制

  • 程序的顺序执行:顺序性 封闭性 可再现性
  • 程序的并发执行 在不存在前趋关系的程序之间才有可能并发执行
    • 间断性 失去封闭性 不可再现性
  • 进程
    • PCB 进程控制块:进程 文件 线程 在系统中存在的唯一标志
    • 进程实体:PCB 程序段 相关的数据段
    • 创建进程 创建进程实体中的PCB 撤销进程 撤销进程中的PCB
    • 进程是进程实体的运行过程 是系统进行资源分配和调度的一个独立单位
    • 特征:
      • 动态性 并发性 独立性 异步性
    • 进程的各种状态:
      • 就绪状态 进程已分配到除CPU以外的所有必要资源后,只要获得CPU 就可以立即执行 系统中按一定的策略排成一个队列 这个队列叫做就绪队列
      • 执行状态 获得CPU 单处理机中 只能一个进程处于执行状态
      • 阻塞状态 正在执行的进程由于发生某事件暂时无法继续执行的状态 引起进程调度 把处理机分配个另一个进程 而让其处于暂停状态 同样也有阻塞队列
      • image-20200518162515620
      • 创建状态 申请一个PCB 之后转入就绪状态 但是内存不足 就成为了创建状态
      • 终止状态 终止需要两个步骤 首先是等待操作系统进行善后处理 最后将其pcb清零 并将Pcb返还系统。当一个进程达到了自然结束点/出现了无法克服的错误/被操作系统所中介/被其他有中止权的进程所终结 进入终止状态 不再执行 但是保留了数据
      • image-20200518162435541
      • 挂起状态 如果该程序正在执行 它将暂停执行 如果出于就绪状态 那么不接受调度 与之对应的是激活操作
      • image-20200518163439388
    • 进程管理中的数据结构 内存表 设备表 文件表 进程表(PCB)
      • PCB作为进程实体的一部分,记录了操作系统所需的,用于描述进程的当前情况以及管理进程运行的全部信息,是操作系统中最重要的记录型数据结构
      • 作用是 是一个在多道程序环境下不能独立运行的程序成为一个能独立运行的基本单位。
      • 作为独立运行的基本单位的标志。也是唯一标志
      • 能实现间断性运行方式 多道程序环境下 程序时采用走走停停间断性运行方式运行的 当进程因阻塞而暂停运行时,它必须保留自己运行时CPU信息,再次被调度时,要恢复其信息。
      • 提供进程管理所需要的信息
      • 提供进程调度所需要的信息
      • 实现与其他进程的同步与通信
    • PCB中的信息
      • 进程标识符 用于唯一的标识一个进程 分为内部标识符和外部标识符
      • 处理机状态 也成为处理机的上下文 主要是由处理机的各种寄存器中的内容组成的。通用寄存器 指令寄存器 程序状态字PSW 用户栈指针
      • 进程调度信息 进程状态 进程优先级 进程调度所需要的其他信息 时间
      • 进程控制信息 程序和数据的地址 进程同步和通信机制 资源清单 链接指针
    • 组织PCB的方式 一个系统中会有很多PCB 甚至上千
      • 线性方式 将所有的PCB都组织在一张线性表上 将该表的首址放在内存的一个专用区域中。实现简单 开销小 但是每次都要从头开始查 因此适用于进程数目不多的系统中
      • 链接方式 把具有相同状态的PCB组成一个队列 就绪队列往往按照进程的优先级进行排序 优先级高的PCB在前面
      • 索引方式 系统根据所有进程状态的不同 建立几张索引表 并把每个索引表的首地址记录在内存的一些专用单元中 感觉就是分级查找的意思
  • 进程控制:进程控制是进程管理中最基本的功能,主要包括创建新进程、终止已完成的进程、将因发生异常情况而无法继续进行的进程置于阻塞状态、负责进程运行中的状态转换等功能。
    • 操作系统内核 一般将OS划分为若干层次 再将OS的不同功能分别设置在不同的层次 为了防止OS本身及关键数据被破坏 处理机的执行状态为两种
      • 系统态:管态 内核态 能执行一切指令 访问所有寄存器和存储区 传统的OS都在系统态运行
      • 用户态:目态 相对较低
    • OS内核包含的功能
      • 支撑功能 提供基本的操作
        • 中断处理 内核最基本的功能 整个操作系统赖以活动的基础
        • 时钟管理 内核的一项基本功能
        • 原语操作 原语:由若干条指令组成的,用于完成一定功能的一个过程 是一种原子操作 不可分割 要么就不做 要么就全做 原子操作在系统态下执行 常驻内存。
      • 资源管理功能
        • 进程管理
        • 存储器管理
        • 设备管理 设备的驱动程序
    • 进程的创建
      • 允许一个进程创建一个进程 (可以套娃 子进程可以继承父进程的资源 撤销父进程时 子进程也随之消失(Linux) 但是windows中 不存在进程层次这个概念 但是有句柄这么个东西 可以进行传递
      • 能引起进程创建的事件
        • 用户登录
        • 作业调度
        • 提供服务
        • 应用请求
      • 创建过程:申请空白PCB 获得唯一的数字标识符 -> 为新进程分配其运行所需要的资源 从操作系统/父进程那里获得 对于批处理作业 内存大小在创建进程要求时提供 为应用进程创建子进程 同前 对于交互型作业 用户可以不给出内存而由操作系统分配一定的空间->初始化PCB 包括 初始化标识信息 初始化处理机状态信息 初始化处理机的控制信息(将进程设置为就绪状态/静止就绪状态)->如果进程就绪队列能够接纳新进程 那么就将新进程插入就绪队列
    • 进程的终止
      • 引起进程中止的事件
        • 正常结束
        • 异常结束 越界错 保护错 非法指令 特权指令错 运行超时 等待超时 算术运算错 I/0故障
        • 外界干预 操作员或操作系统干预 父进程请求 因父进程终止
      • 终止过程:根据被终止进程的标识符 找出PCB 读取该进程的状态 处于执行状态就终止 并且置标志为真 有子孙进程的话结束掉 将被终止进程的资源给父进程/系统将被终止进程从所在队列中移出
    • 进程的阻塞与唤醒
      • 引起阻塞或者唤醒的事件
        • 向系统请求共享资源失败
        • 等待某种操作的完成
        • 新数据尚未到达
        • 等待新任务的到达
      • 进程阻塞的过程是一种主动行为 先立即停止执行 改为阻塞状态 将PCB插入阻塞队列 转调度程序进行重新调度 将处理机分配给另一就绪进程 并进行切换
      • 进程唤醒过程 把被阻塞的进程从阻塞队列移出 将状态改为就绪 再将PCB插入就绪队列中
      • 阻塞与唤醒必须成对使用
    • 进程的挂起与激活
      • 挂起 先检查状态 首先检查被挂起进程的状态 活动就绪改为静止就绪 活动阻塞改为静止阻塞 为了方便用户/父进程考察 把PCB复制到指定的地方 如果被挂起的进程正在执行 则转向调度程序重新调度
      • 激活 先将进程从外存调入内存 检查并且改变状态 如果采用的是抢占调度策略 则每当有静止就绪进程被激活而插入就绪队列时 便应检测是否需要重新调度 就是比较一下优先级
  • 进程同步 为了保证多个进程能够有条不紊的运行,在多道程序系统中,必须引入进程同步机制
    • 临界资源:打印机、磁带机等硬件
    • 临界区:每个进程中访问临界资源的那段代码
    • 进入区:检查是否临界区正在被访问的代码段
    • 退出区:用于将临界区正在被访问的标志恢复为未被访问
    • 同步机制应遵循的规则
      • 空闲让进 无进程处于临界区时,表面临界资源处于空闲状态,应允许一个请求进入临界区的进程立即进入自己的临界区 以有效地利用临界资源
      • 忙则等待 有进程进入临界区时 表明临界资源正在被访问 其他试图进入临界区的进程必须等待 以保证对临界资源的互斥访问
      • 有限等待 对要求访问临界资源的进程 应保证在有限的时间内进入自己的临界区 避免陷入“死等”状态
      • 让权等待 当进程不能进入自己的临界区时 应立即释放处理机 以免进程陷入“忙等”状态
    • 整型信号量机制不符合让权等待 因为s<=0时候 就会一直while循环 进入了忙等状态
    • 记录型信号量 不存在忙等 由于会出现多个进程等待同一个资源的情况产生 所以要搞一个list
    • AND型信号量 需要获得两个或更多的资源之后才能执行其任务 基本思路 在整个运行的过程中将需要的所有资源 一次性的分配给进程
    • 信号量集就是一次管理多个资源的分配 而不是一个
    • 在利用信号量机制实现进程互斥时应该注意,P V操作应该成对的出现
    • 管程机制 由初始化代码 过程 数据结构组成一个管程定义了一个数据结构和能为并发进程所执行的一组操作 这组操作能同步进程和改变管程中的数据 模块化 抽象数据类型 信息屏蔽
      • 管程内的数据结构只能内部访问
      • 进程可以通过调用管程的一个过程进入管程
      • 一个事件只允许一个
    • 先执行对资源信号量的wait操作 再执行对互斥信号量的wait操作 不然可能引起进程死锁
    • 同步在外 互斥在内 不然会引起死锁
    • 关于哲学家就餐问题 理发师问题 读者写者问题等 很难去写些什么来记录 多去实际应用就会了
  • 进程通信
    • 共享存储器系统 在此系统中 相互通信的进程共享某些数据结构或共享存储区 进程之间能够通过这些空间进行通信 又分为基于共享数据结构的通信方式(低级通信) 基于共享存储区的通信方式(高级通讯)
    • 管道通信系统
    • 消息传递系统 最广泛 封装起来发送 计算机网络中成为报文
    • 客户机-服务器系统 套接字(适用于不同计算机间进程的通信)/远程过程调用和远程方法调用
  • 线程
    • 引入进程的目的是为了让多个程序并发执行 提高资源利用率和系统吞吐量 引入线程的目的是减少程序在并发执行是所付出的时空开销,使OS具有更好的并发性
    • 进程的两个基本属性 回顾一下 一是进程是一个可拥有资源的独立单位 运行需要有一定的资源 二是进程又是一个可独立调度和分派的基本单位
    • 线程引入的目的就是作为可独立调度和分派的基本单位
    • 线程是能独立运行的基本单位 当线程切换的时候 仅需保存和设置少量寄存器的内容,切换代价远低于进程 但是从一个进程中的线程切换到另一个进程中的线程的时候 必须引起进程的切换
    • 线程之间也存在并发性
    • 线程并不拥有系统资源 知识拥有一点必不可少的资源 并且允许多个线程共享其进程的资源
    • 线程的三种状态 执行状态 就绪状态 阻塞状态
    • 线程的实现方式
      • 内核支持线程KST
        • 优点
          • 多处理器系统中,内核能够同时调度同一进程中的多个线程并行执行
          • 如果进程中的一个线程阻塞了 内核可以调度进程中的其他线程占有处理器运行 也可以运行其他进程的线程
          • 内核支持线程具有很小的数据结构和堆栈,线程的切换比较快,开销比较小
          • 内核本身也可以采用多县城技术,可以提高系统的执行速度和效率
        • 缺点:对于用户的线程切换而言 开销比较大 在同一个进程在的不同线程切换的时候 需要从用户态到核心态进行,因为用户的线程是在用户态执行 而线程调度和管理是在内核实现的 开销比较大
      • 用户级线程ULT 内核完全不知道用户级线程的存在 调度仍是以进程为单位进行的 KST是以线程为单位
        • 优点
          • 线程的切换不需要转换到内核空间
          • 调度算法可以是进程专用的
        • 缺点
          • 系统调用的阻塞问题 当线程执行一个系统调用的时候 该进程下的所有线程均会阻塞
          • 在单纯的用户级线程实现方式中 多线程应用不能利用多处理机进行多重处理 也就是说 一个进程下只有一个线程能够运行 在它释放CPU之前 其他线程只能等待
  • 习题
    • 为什么程序并发执行会产生间断性
      • 程序在并发执行时,由于它们共享系统资源,为完成同一项任务需要相互合作,致使这些并发的进程之间,形成了相互制约关系,从而使得进程在执行期间出现间断性。
    • 程序并发执行为什么会失去封闭性和可再现性
      • 多个程序共享系统中的各种资源,因而这些资源的状态由多个程序改变,因此失去封闭性
    • 为什么要引入进程概念 作用呢
      • 为了使程序在多道程序环境下能够并发执行,并对并发执行的程序加以控制和描述,在操作系统中引入了进程概念 使得并发执行得以进行
    • 进程和程序的区别?
      • 动态性 动态性是进程最基本的特征 表现为由创建而产生 由调度而执行 因得不到资源而阻塞 由撤销而消亡 进程有一定的生命期 而程序知识一组有序的指令集和 是静态实体
      • 并发性 并发性是进程的重要特征 同时也是OS的重要特征 引入进程的目的正是为了使程序能和其他进程的程序并发执行 而程序时不能并发执行的
      • 独立性 独立性是指进程实体是一个能独立运行的基本单位,也是系统中独立获得资源和独立调度的基本单位 对于未建立任何进程的程序 不能作为独立单位参加运行
    • PCB的作用 为什么说PCB是进程存在的唯一标志
      • PCB是进程实体的一部分 是操作系统中最重要的记录型数据结构 作用是使一个在多道程序下不能独立运行的程序,成为一个能独立运行的基本单位,成为能和其他进程并发执行的进程。OS使根据PCB对并发执行的进程进行控制和管理的。
    • PCB提供了进程管理和进程调度所需要的哪些信息?
      • 进程管理:通用寄存器 指令计数器 程序状态字 用户栈指针
      • 进程调度:进程状态 进程优先级 事件 其他信息
    • 进程控制块的组织方式有哪几种
      • 线性方式 链接方式 索引方式
    • 什么是操作系统内核 内核的主要功能是什么
      • 现在操作系统一般将OS划分为多个层次,再将OS的不同功能分别设置在不同的层次中。通常将一些与硬件紧密相关的模块 入中断处理程序等 各种常用的设备驱动程序以及运行频率较高的模块 时钟管理 进程调度和许多模块所共用的一些基本操作 都安排在紧靠硬件的层次中 将他们常驻内存 即通常被称为OS内核
      • 支撑功能 中断处理 时钟管理 原语操作
      • 资源管理功能 进程管理 存储器管理 设备管理
    • 三个基本状态之间转换的典型原因
      • 就绪状态-执行状态 进程分配到CPU资源
      • 执行状态-就绪状态 时间片用完
      • 执行状态-阻塞状态 I/O请求
      • 阻塞状态-就绪状态 I/O完成
    • 为什么要引入挂起状态 挂起状态的性质
      • 引入挂起状态处于五种不同的需要 终端用户需要 父进程需要 操作系统需要 对换需要 负荷调节需要 处于挂起状态的进程不能接受处理机调度
    • 在进行进程切换时 需要保存哪些信息
      • 进程当前缓存信息
      • 下一指令地址信息
      • 进程状态信息
      • 过程和系统调用参数及调用地址信息
    • 引起进程创建的主要事件
      • 用户登录 作业调度 提供服务 应用请求
    • 引起进程撤销的主要事件
      • 正常结束 异常结束(越界错误 保护错 非法指令 特权指令错 运行超时 等待超时 算数运算错 IO故障)外界干预(操作员或操作系统干预 父进程请求 父进程终止)
    • 创建进程的步骤
      • OS发现请求创建新进程事件后,调用进程创建原语Creat()
      • 申请空白PCB
      • 为新进程分配资源
      • 初始化进程控制块
      • 将新进程插入就绪队列
    • 撤销一个进程的步骤
      • 根据被终止的进程标识符 从PCB中集中检索出进程PCB 读出该进程的状态
      • 如果处于执行状态 置调度标志为真 指示该进程被终止后重新调度
      • 如果有子进程 停止所有的子孙进程 以防编程不可控进程
      • 将终止进程拥有的全部资源 归还给父进程 或者归还给系统
      • 将被终止进程PCB从所在队列火列表中移出 等待其他程序搜集信息
    • 引起进程阻塞或者唤醒的主要事件是什么
      • 请求系统服务
      • 启动某种操作
      • 新数据尚未到达
      • 无新工作可做
    • 为什么要引入线程
      • 在操作系统中引入线程 是为了减少程序在并发执行时所付出的时空开销 使OS具有更好的并发性,提高CPU的利用率 进程是CPU分配资源的基本单位 线程则是系统调度的基本单位
    • 线程具有哪些属性?
      • 轻型实体
      • 独立调度和分配的基本单位
      • 可并发执行
      • 共享进程资源
    • 对进程和线程进行比较
      • 调度性 线程在OS中作为调度和分派的基本单位 进程只作为资源拥有的基本单位
      • 并发性 进程可以并发执行 一个进程的多个线程也可以并发执行
      • 拥有资源 进程始终是拥有资源的基本单位 线程只拥有运行时必不可少的资源 本身并不拥有系统资源 但是可以访问隶属进程的资源
      • 系统开销 操作系统在创建、撤销和切换进程时付出的开销显著大于线程
    • 用户级线程和内核支持线程
      • 用户级线程 仅存于用户空间中的线程,无需内核支持。这种线程的创建、撤销、线程间的同步与通信等功能,都无需利用系统调用实现。用户级线程的切换通常发生在一个应用进程的诸多线程之间,无需内核的支持。
      • 内核支持线程 在内核支持下运行的线程 无论是用户进程中的线程,还是系统进程中的线程。其创建、撤销和切换都是依靠内核,在内核空间中实现的。在内核空间里还未每个内核支持线程设置了线程控制块,内核根据该控制块感知某线程的存在并实施控制。
    • 多线程模型有哪几种类型?多对一模型有何优缺点
      • 多对一模型 一对一模型 和多对多模型
      • 缺点 如果一个线程访问内核时发生阻塞 则整个进程都会被阻塞 此为 在任一时刻 只有一个线程能够访问内核 多个线程不能同时在多个处理机上运行

处理机调度与死锁

新文档 06-01-2020 17.09.13

img
img
img
img
img
img

避免死锁

  • 避免死锁同样属于事先预防的策略,但并不是事先采取某种显示措施,破坏产生死锁的必要条件,而是在资源动态分配的过程中,防止系统进入不安全状态。
  • 安全状态和不安全状态:允许进程动态的申请资源 分配之前先计算此次分配资源的安全性 安全状态就是 系统能按某种进程推进顺序为每个进程分配其所需资源 直至满足每个进程对资源的最大需求,使每个进程都可顺利的完成。如果有这个序列 就是安全状态 如果没有这个序列就是不安全状态。
  • 银行家算法
    • 四个数据结构
      • 可利用资源向量Available
      • 最大需求矩阵Max
      • 分配矩阵Allocation
      • 需求矩阵Need
    • 没啥好说的 就是先分配 然后看看安不安全 不安全去找下一个再试

死锁的检测与接触

  • 死锁的检测 在系统中必须
    • 保存有关资源的请求和分配信息
    • 提供一种算法,它利用这些信息来检测系统是否已进入死锁
  • 死锁的解除
    • 抢占资源 从一个或多个进程中抢占足够数量的资源 分配给死锁进程 以接触死锁状态
    • 终止(或撤销)进程 终止系统中的一个或多个死锁进程 直至打破循环环路 使系统从死锁状态解除出来
      • 终止所有死锁进程
      • 逐个终止进程

习题

  • 高级调度和低级调度的主要任务 为什么引入中级调度
    • 高级调度主要任务是根据某种算法 把外存上处于后被队列中的那些作业调入内存
    • 低级调度是保存处理机的现场信息 按照某种算法选取进程 把处理器分配给进程
    • 引入中级调度的目的是为了提高内存利用率和系统吞吐量 使那些暂时不能运行的进程不再占用内存资源 将他们调至外存等待 把进程状态改为就绪驻外村状态或者挂起状态
  • 处理机调度算法的共同目标使什么 批处理系统调度的目标是什么
    • 资源利用率 公平性 平衡性 策略强制执行
    • 调度目标 平均周转时间短 系统吞吐量高 处理机效率高
  • 低级调度的主要功能
    • 保存处理机的现场信息
    • 按某种算法选取进程
    • 把处理机分配给进程
  • 抢占调度方式中 抢占的原则是什么
    • 时间片原则
    • 优先权原则
    • 短作业优先权原则等
  • 选择调度方式和调度方法时 应遵循的准则是什么
    • 面向用户的准则 周转时间短 响应时间快 截止时间的保证 优先权准则
    • 面向系统的准则 系统吞吐量高 处理机利用率好 各类资源的平衡利用
  • 批处理系统、分时处理系统、实时处理系统中 个采用哪几种进程调度算法
    • 批处理系统 短作业优先 优先权 高相应比优先 多级反馈队列调度算法
    • 分时处理系统 时间片轮转法
    • 实时处理系统 最早截止时间优先 最低松弛度优先
  • 确定进程优先级的依据
    • 进程类型
    • 进程对资源的需求
    • 用户要求
  • 时间片轮转算法中 如何确定时间片的大小
    • 应略大于一次典型的交互需要的时间 一般应该考虑三个因素 系统对相应时间的要求、就绪队列中的进程的数目和系统的处理能力

存储器管理

存储器的层次结构

image-20200602111743267
  • CPU寄存器和主存输出操作系统存储管理的内容 掉电后内容消失 辅存属于设备管理 存储信息长期保存
  • CPU寄存器和主存被称为可执行存储器 访问辅存很慢 要有中断
  • 主存储器 内存 主存 用于保存进程运行时的程序和数据 处理机从主存中取得指令和数据 由于 主存储器访问速度远低于CPU执行指令的速度 为缓和这一矛盾 在计算机系统中引入了寄存器和高速缓存
  • 寄存器 速度和处理机相同 价格十分昂贵
  • 高速缓存 介于寄存器和存储器之间的存储器 主要用于备份主存中比较常用的数据 以间少处理机对主存储器的访问次数 访问速度快于主存
  • 磁盘缓存 因为磁盘的I/O速度远低于对主存的访问速度 为了缓和两者之间速度的不匹配 用于暂时存放频繁使用的一部分磁盘信息。但是与高速缓存不同 不是一种实际存在的存储器 而是利用主存中的部分存储空间暂时存放从磁盘中读出的信息

程序的装入和链接

  • 程序运行需要的步骤
    • 编译 由编译程序对用户源程序进行编译,形成若干个目标模块
    • 链接 由链接程序将编译后形成的一组目标模块以及他们所需要的库函数链接在一起 形成一个完整的装入模块
    • 装入 由装入程序将装入模块装入内存
  • 程序的装入
    • 绝对装入方式 单道程序环境 用户程序编译后 将产生绝对地址的目标代码
    • 可重定位装入方式 多到程序环境 从0开始 地址变换通常是在进程装入时一次完成的 以后不再改变 故称为静态重定位
    • 动态运行时的装入方式 再把装入模块装入内存后 并不立即把装入模块中的逻辑地址转换为物理低址 而是把这种低址转换推迟到程序真正要执行时才进行 需要重定位寄存器的支持
  • 程序的链接
    • 静态链接方式 在程序运行之前 先将各目标模块及他们所需的库函数链接成一个完整的装配模块,以后不再拆开
    • 装入时动态链接this 边装入边链接 装入一个目标模块时,若发生一个外部模块调用事件,将引起装入程序去找出相应的外部模块 并将它装入内存 优点 便于修改和更新/便于实现对目标模块的共享
    • 运行时动态链接 对某些模块的链接推迟到程序执行时才进行,在执行过程中,当发现一个被调用模块尚未装入内存时,由OS去找到该模块,并将之装入内存,将其连接到调用者模块上。 不仅能加速程序的装入过程,可节省大量的内存空间。

连续分配存储管理方式

  • 单一连续分配 单道处理系统中仅装有一道程序 内存空间由该程序独占
  • 固定分区分配 多道处理系统 有几个区域就能有几个程序运行 大小可以相等也可以不相等
  • 动态分区分配 可变分区分配 数据结构有 空闲分区表 空闲分区链(双链表)
    • image-20200602165212140
    • image-20200602165946384
    • 基于顺序搜索的动态分区分配算法
      • 首次适应算法FF first fit 从低址开始找 顺着找 找到就放 该算法倾向于优先利用内存中低址部分的空闲分区 而保留了高址部分的大空闲区 缺点是低址不断被划分 会产生很多碎片 每次又是从低址开始找 很浪费时间
      • 循环首次适应算法 NF next first FF的进化 从上次位置开始找 而不是从头开始 会缺乏大的空闲分区
      • 最佳适应算法 BF best fit 将所有空闲分区按照从小到大排序 之后用最合适的 本质上还是会产生碎片 因为最适应的会剩下很小一点点 凑多了就全是碎片了
      • 最坏适应算法 WF worst fit 从大到小排 直接从最大开始试 效率高 对中小作业有利 对大作业不利
    • 基于索引搜索的动态分区分配算法
      • 快速适应算法 分类搜索法 将具有相同容量的分区归一归类 建立一个管理索引表 不分割内存 不会产生碎片 而且快 缺点是分区归还主存时算法复杂 浪费时间 而且一个分区存放一个进程 有点点浪费 空间换时间
      • 伙伴系统 2的幂次 就是多次分割 多次合并 都以2的幂次数的值为单位进行操作 速度慢于快速适应算法 但是浪费少
      • 哈希算法 利用哈希快速查找的优点 以及空闲分区在可利用空闲区表中的分布规律,建立哈希函数 构造一张以空闲分区大小为关键字的哈希表 每一个表项记录了一个对应的空闲分区链表表头指针
    • 动态可重定位分区分配
      • 紧凑 将多个碎片合成为一个之后把程序放进去 但是每次移动程序都要修改地址 相当麻烦而且影响了系统的效率
      • 动态重定位 替换起始址即可
      • 动态重定位分区分配算法
      • image-20200602204424023

对换

  • 概念 系统把所有的用户作业存放在磁盘上,每次只能调入一个作业进入内存,当该作业的一个时间片用完时,将它调至外存的后被队列上等待 再从后备队列上将另一个作业调入内存把内存中暂时不能运行的进程或者暂时不用的程序和数据换出到外存上,以便腾出足够的内存空间再把已具备运行条件的进程或进程所需要的程序和数据换入内存,直接提高了处理机的利用率和系统的吞吐量 因此必须实现 对对换空间的管理 进程的换出 进程的换入
  • 对换的类型
    • 整体对换 处理机的中级调度 以整个进程为单位
    • 页面(分段)对换 目的是为了支持虚拟存储系统
  • 对换空间的管理
    • 对换空间管理的主要目标
      • 文件区 文件区占用磁盘空间的大部分 用于存放各类文件 一般不怎么访问 因此主要提高文件存储空间的利用率 其次是提高对文件的访问速度 因此 对文件区空间的管理采用离散分配方式
      • 对换空间 小部分 操作频率高 主要目标是速度 其次是利用率 因此 采用连续分配的方式 较少考虑外存中碎片的问题
    • 对对换空间的分配与回收 和连续分配方式的回收方式一样 那四种 不说了
  • 进程的换入和换出
    • 进程的换出
      • 选择被换出的进程 选择进程时 检查所有驻留在内存中的进程 首先选择处于阻塞状态或者睡眠状态的进程 然后从中选择优先级低的进程 因此有些系统中要考虑进程的驻留时间(不然一下子就出去了 白进来了
      • 进程换出 注意只能换出非共享的程序段 先申请对换空间 申请成功启动磁盘 然后移动过去就成了
    • 进程的换入
      • 首先查看PCB集合中所有进程的转台 找出“就绪”状态但已换出的进程 找到已经被换出去最久的进程 申请内存 不行再换出去几个之后在换入 之后一直换
  • 在处理机正常运行时 不启动对换程序 但如果发现有许多进程在运行时经常发生缺页且显现出内存紧张的情况 启动对换程序

分页存储管理方式

  • 页面 分页存储管理将进程的逻辑地址空间分成若干个页,并为各页加以编号 相应的,也把内存的物理地址空间分成若干个块 在为进程分配时,以块为单位 将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块,而形成了不可利用的碎片 称为“页内碎片”
  • 页面大小 选择过小 减小内存碎片 减少内存碎片总空间 有利于内存利用率的提高 但另一方面却会造成每个进程占用过多的页面 从而导致进程的页表过长,占用大量内存。 此外还会降低页面换进换出的速率
  • 页面过大 虽然可以减小页表的长度,提高页面换进换出的速度 但却又会使页内碎片增大
  • 因此页面的大小应当选择适中,页面大小是2的幂,通常为1KB-8KB
  • 分页地址中的地址结构 前一部分为页号P 后一部分为偏移量W(页内地址) 0-11位为页内地址 每页的大小为4KB 12-31为页号 地址空间最多有1M页 一个逻辑地址空间中的地址为A 页面的大小为L 页号P和页内地址为p
  • 为保证进程能够正确运行 能在内存中找到相应的物理块 系统为每个进程建立个页表 作用是实现从页号到物理块号的映射
  • 页表由寄存器来实现 但是寄存器成本较高 且现在页表数量很大 所以不可能都用寄存器 大部分页表还是存在于内存中 在系统中只设置一个页表寄存器PTR,在其中存放页表在内存中的起始地址和页表的长度。平时进程为执行时 二者放在PCB中 调度到该进程时,装入页表寄存器image-20200603122847654
  • 快表 由于页表是放在内存的 CPU在没存取一个数据时 要访问两次CPU 第一次时访问内存中的页表 从中找到指定页的物理块号 再将块号和W拼接 形成物理地址 第二次访问内存才是从第一次获得的地址中获得数据(或者血) 然后就慢了 然后增设了快表 我的理解就是部分页表放在了地址变换机构中 不可能太大 一般就16-512个表项 中小作业的话足够了 但是大作业不太够 由于对程序和数据访问往往带有局限性 据统计 从快表中能找到所需页表项的概率可达90%以上 可接受
  • 访问内存的有效时间 从进程发出指定逻辑地址的访问请求 经过地址变换 到在内存中找到对应的实际物理地址单元并取出数据,所需要花费的总时间,称为内存的有效访问时间 计算时注意访问快表也需要时间就行了。。。
  • 两级和多级页表 外层页表 为页表简历页表 因为页表太大了 存不下 两级页表实质上并没有减少页表占用的空间 只不过是离散化了 用较少的内存空间存放页表的唯一方法是 仅把当前需要的一批页表项调入内存 以后再根据需要陆续调入
  • 反置页表 为每一个物理块设置一个表项 并将它们按物理块的编号进行排序

分段存储管理方式

  • 段可以是信息的逻辑单位
  • 优势 方便编程 信息共享 信息保护 动态增长动态链接
  • 段表 和页表相似 不过段表中存在起始地址和段的长度 最后是该段的起始地址和位移量相加 得到物理低址
  • image-20200603145515960
  • 分页和分段的主要区别
    • 页是信息的物理单位,采用分页存储管理是为了实现离散分配,以消减内存的外零头,提高内存的利用率。分页只是系统管理上的需要,完全是系统的行为,对用户是不可见的。 分段存储管理方式中的段则是信息的逻辑单位,它通常包含的是一组意义相对完整的信息。分段的主要目的在于更好的满足用户的需要。
    • 页的大小固定且由系统决定。在采用分页存储管理的系统中,在硬件结构上,就把用户程序的逻辑地址划分为页号和页内地址两部分,也就是说直接由硬件实现的,因而在每个系统中只能有一种大小的页面。而段的长度却不固定,决定于用户所编写的程序,通常由编译程序在对源程序进行编译时,根据信息的性质来划分。
    • 分页的用户程序地址空间是一维的。分页完全是系统的行为,在分页系统中,用户程序的地址是属于单一的线性地址空间,程序员只需利用一个记忆符即可表示一个低址。 分段是用户的行为,用户程序的地址空间是二维的,程序员在标识一个地址时,既需要给出段名,有需要给出段内地址。
  • 信息共享 分页比分段复杂 分段的时候注意得有自己的数据区
  • 段页式存储管理方式
    • 先将用户程序分成若干个段 再把每个段分成若干个页 同时具有段表页表 段表存的内容是页表初始地址和页表长度
    • image-20200603151954772
    • 三次访存 第一次访问段表 第二次页表 第三次访问第二次得到的地址中取出指令或者数据 当然也具有高速缓存

习题

  • 为什么配置层次式存储器
    • 设置多个存储器可以使存储器两端的硬件并行工作
    • 采用多级存储系统,特别是Cache技术,这是一种减轻存储器带宽对系统性能影响的最佳结构方案
    • 在微处理机中内部设置各种缓冲存储器,以减轻对存储器存取的压力。增加CPU中寄存器的属灵,也可大大缓解对存储器的压力。
  • 静态链接是什么 静态链接需要解决哪两个问题
    • 静态链接是指在程序运行之前,现将各自目标模块及他们所需的库函数,链接成一个完整的装入模块,以后不再拆开的链接方式。
    • 问题1 将相对地址进行修改。即将除第一个模块外的相对地址修改成装入模块中的相应的相对地址。
    • 问题2 变换外部调用符号。将每个模块中所用的外部调用符号,都变换为相对地址。
  • 装入时动态链接是什么 优点?返回上文
  • 运行时动态链接是什么 优点?(上面那种方法看起来并不是很好用。。。
    • 运行时动态链接是将对某些模块的链接推迟到程序执行时才进行链接,也就是,在执行过程中,当发现一个被调用的模块未装入内存时,立即由os去找到该模块并将之装入内存,把它链接到调用者模块上
    • 优点:凡是在执行过程中未被用过的目标模块,都不会被调入内存和被链接到装入模块上。这样不仅能加快程序得装入过程,而且可节省大量的内存空间。
  • 为什么要引入动态重定位?如何实现
    • 程序在运行过程中要经常在内存中移动位置,为了保证这些被移动了的程序还能正常执行,必须对程序和数据的地址加以修改,即重定位。引入重定位的目的就是为了满足程序得这种需要
    • 要在不影响指令执行速度的同时实现地址变换,必须有硬件地址变换机构的支持,即需在系统中增设一个重定位寄存器,用它来存放程序在内存中的起始地址。程序在执行时,真正访问的内存地址是相对地址与重定位地址寄存器的地址相加而成的。
  • 对换的类型
    • 将整个进程换入换出 将进程的一部分换入换出 前者为了解决内存不足 后者为了实现虚拟存储
  • 在以进程为单位进行对换时,每次是否将整个进程换出,为什么?
    • 在以进程为单位进行对换时,并非每次将整个进程换出
    • 因为
      • 从结构上讲,进程是由程序段、数据段和PCB组成的,其中PCB总有部分或全部常驻内存,不被换出
      • 程序段和数据段可能正被若干进程共享,此时也不能换出。
  • 为实现分页存储管理,需要哪些硬件支持
    • 页表机制 地址变换机构
  • 在具有快表的段页式存储管理方式中,如何实现地址变换?
    • 在CPU给出有效地址后,由地址变换机构自动将页号P送入高速缓冲寄存器,并将此页号与高速缓存中的所有页号比较,若找到匹配页号,表示要访问的页表项在快表中。可直接从快表读出该页对应物理块号,送到物理地址寄存器中。如果快表中没有对应页表项,则再访问内存页表。找到后,把从页表项读出物理块号送地址寄存器;同时修改快表,将此页表项存入快表。但若寄存器已满,则OS必须找到合适的页表换出。
  • 为什么说分段系统较之分页系统更易实现信息共享和保护?
    • 对于分页系统,每个页面是分散存储的,为了实现信息共享和保护,则页面之间需要一一对应起来,为此需要建立大量的页表项。
    • 而对于分段系统,每个段都从0开始编址,并采用一段连续的地址空间,这样在实现共享和保护时,只需为所要共享和保护的程序设置一个段表项,将其中的基址与内存地址一一对应起来即可。
  • 全面比较连续分配和离散分配方式
    • 连续分配是指为一个用户程序分配一个连续的地址空间,包括单一连续分配和分区式分配方式,前者将内存分为用户区和系统去,系统区供操作系统使用,用户区供用户使用,是最简单的一种存储方式,但只能用于单用户单任务的操作系统中。 分区式分配方式分为固定分区和动态分区,固定分区是最简单的多道程序的存储管理方式,因为每个分区的大小固定,必然会引起存储空间的浪费。动态分区是根据进程的实际需要,动态的为之分配内存空间,常用的几种算法:首次适应算法 循环首次适应 最佳适应算法 最坏算法
    • 离散分配方式分为分页式 分段式 段页式 前者为了系统 提高内存利用率 第二者为了用户的共享和保护 最后的集二者之和

其他章节内容

  • 文件
    • 用户关注的是逻辑层面的文件 文件怎么组织 怎么使用
    • 系统关注的是物理层面的文件 文件是怎么在磁盘上存储的
    • 文件是在逻辑上具有完整意义的一组相关信息的集和 通常被保存在外存上
    • 目录 目录也是文件 是一种特殊的文件 内容是另外一些文件的FCB
    • 文件目录可能是FCB 也可能是FCB的一部分
    • 文件组成是FCB(文件名 长度 位置 访问权限+ 文件体 对文件进行简历 描述 存储 读写 存储的时候是分开存储的 目录存放FCB(文件的和子目录的) 目录区 索引区 文件区
    • FMS 文件管理系统 操作系统的子系统 管理对象有目录 文件 用户管理目标
      • 方便用户
      • 提高磁盘空间利用率
      • 文件操作便捷且存取效率高
      • 实现逻辑文件与物理文件的组织与转换
    • 特点 安全 方便 接口的统一性
  • 虚拟存储管理
    • 主存扩充技术
      • 覆盖技术 在不同时刻把同一程序区分配给不同的数据段或者程序段 实现存储区共享的一种内存分配技术 通常与单一连续区分配,固定多分区分配和动态分区分配等存储管理技术配合使用。将一个程序分成若干段 非覆盖段 可覆盖段
      • 交换技术 将内存中的某进程暂时不同的程序和数据换出去 磁盘空间被分为文件区和交换区 不同点文件区交换区存储方式以文件形式存放 提高了空间利用率 采用离散分配的方式按照字符流方式存放,采用连续存储方式访问速度不同文件区存储空间大,为了提高检索效率一般建立目录 间接地址访问交换区空间小 按照外存地址直接访问 访问速度块存储时间不同存放长久的数据存放临时数据
        • 交换整个作业 单道系统中 模拟多道
        • 交换整个进程 连续分区存储管理(进程挂起 激活 中级调度)
        • 交换页面/段面 用于分页、分段存储管理技术
      • 虚拟存储技术 就是交换页面/段面 可随时装入
    • 实质是 将磁盘空间虚拟成内存使用
    • 结果是 进程的一部分在内存中 就能运行 程序的局部性原理
    • 特性 离散性 多次性 对换性 虚拟性
    • 请求分页存储管理 装入部分页面 如果不在内存中 产生缺页中断 进程阻塞 等待装入 使用换入换出技术 修改了页表 见了驻留位 修改位 访问位
  • 设备管理概述 操作系统中最庞大 最复杂的一个模块
    • 外部设备 用来担负数据输入输出的部件 简称“外设” 他们是计算机与外部世界进行沟通的桥梁 键盘鼠标啥的
      • I/O设备
      • 外存储设备
    • 流设备 块设备 独享设备 共享设备
    • 目标 方便用户使用 提高设备利用率 通过管理调度提高IO效率 通过软件方法扩充设备性能
    • 逻辑IO 设备IO 设备调度与驱动控制层

可算写完了 有很多不足的地方 毕竟这只是前四章(教学的内容) 各种排版方面都有很多不足

继续加油


愿风指引你的道路,愿你的刀刃永远锋利。