操作系统概论--学习笔记(1—4章+5章部分-详细版).doc

操作系统概论 学习笔记（14章+5章部分 详细版）第一章 引论1.1 计算机系统计算机系统包括： 计算机硬件、计算机软件1.1.1 计算机硬件是计算机系统的最内层计算机硬件的组成：1.中央处理器（运算器、控制器）：对信息进行高速运算和处理。2.存储器（主存储器、辅助存储器）：存放各种程序和数据。3.输入和输出控制系统：管理外围设备与主存储器之间的信息传递。4.各种输入输出设备：是计算机与用户间的交互接口部件。1.1.2 计算机软件是计算机系统的最外层计算机软件定义：人与计算机硬件之间的接口界面计算机软件分类：1. 系统软件：是计算机系统中最靠近硬件层次的软件，是不可缺少的软件。（例：操作系统（计算机系统软件的核心）、编译程序、监控管理程序）2.支撑软件：是支撑其他软件的开发与维护的软件。（例：接口软件、软件开发工具、环境）3.应用软件：是特定应用领域的专用软件。是解决用户实际问题的软件。（例：订票软件、办公软件等）1.2 操作系统1.2.1 什么是操作系统操作系统概念：是管理计算机系统资源、控制程序的执行、改善人机界面和为应用软件提供支持的一种系统软件。1.2.2 操作系统的作用 1.管理计算机系统的资源 2.为用户提供方便的使用接口 3.具有扩充硬件的功能，为用户提供良好的运行环境 计算机配置了操作系统后可提高效率，且便于使用。1.2.3 操作系统的功能 1.处理器管理：多道程序环境下的处理器调度 2.内存管理：内存的分配回收、地址重定位、内存共享与保护、内存扩充 3.文件管理：文件的“按名存取”；文件的存储、检索、共享、保护等问题 4.设备管理1.3 操作系统的形成与基本类型1.3.1 批处理操作系统1. 单道批处理系统：每次只允许一个作业执行2. 多到批处理系统：内存中同时有多个作业，它们共享计算机系统中的资源优点：提高了处理器的利用率；系统吞吐量大缺点：一旦将作业提交给系统，用户无法控制作业的执行1.3.2 分时操作系统分时操作系统概念：1. 若干个用户分享处理器的时间 如何分享：轮流占用处理器，规定每个用户占用处理器的时间，称为时间片。2. 多个用户排成循环队列，当一个用户的时间片用完，就重新排到队尾3. 由于时间片很小，每一个用户都没有感觉到其他用户的存在 特点： 及时性：系统对用户的请求及时响应“独占”性：用户感觉不到计算机为其他人服务，就像整个系统为他所独占 交互性：用户根据系统响应结果进一步提出新请求（用户直接干预每一步） 多路性：同时有多个用户使用一台计算机1.3.3 实时操作系统首先强调：实时性、可靠性 其次考虑：系统效率分两类：实时控制系统；实时信息处理系统 特点：及时性、独立性、交互性、多路性1.4 操作系统的发展1.4.1 微机操作系统 特点：每次只允许一个用户使用功能：文件管理、输入输出控制、命令语言的解释单用户微机操作系统1.4.2 网络操作系统将分布在不同地理位置上的计算机通过通信线路和通信设备连接起来，（功能：）以实现信息通信、资源共享、均衡负载，提高系统可靠性安全性的操作系统用户必须知道所用资源的物理位置，IE的地址栏的内容1.4.3 分布式操作系统物理架构与网络操作系统一样由统一操作系统控制，资源深度共享（健壮性，多机合作），采用客户机/服务器结构特点：1. 统一性：用户使用该系统时就像使用一个“单一的计算机系统”，感觉不到该系统由多台计算机构成2. 透明性：用户不知道系统资源所在，更不知道是否还有其他用户在与其竞争资源1.4.4 嵌入式操作系统家电，手机中的操作系统嵌入式操作系统定义：运行在嵌入式系统中对各种部件、装置等资源进行统一协调、处理和控制的系统软件需要嵌入式软件的支持特点：微型化、实时性1.4.5 当前流行的操作系统Windows ：图形界面，单用户多任务Unix ：特点：1.交互式分时操作系统；2.短小精悍；3.具有可装载的多层次文件系统；4.可移植性好；5.网络通信功能强。Linux ：特点：1.自由软件；2.支持TCP/IP协议；3.能与其他网络集成；4.支持并行处理和实时处理1.5 处理器的工作状态1.5.1 特权指令特权指令定义：只允许操作系统执行的指令例：清内存、I/O指令（启动外围设备进行数据传输指令）、设置控制寄存器的值、设置中断屏蔽等1.5.2 管态和目态处理器的工作状态：（定义）管态：处理器正在执行操作系统的程序目态：处理器正在执行用户程序如果在目态下遇到一条特权指令，操作系统就认为出错，发生中断1.5.3 程序状态字（PSW）PSW定义：是用来控制指令执行顺序并且保留和指示程序有关的系统状态用来指示处理器的状态：（内容）1. 程序基本状态指令地址指出下一条指令的存放地址条件码指出指令执行结果的特征目态/管态当设置为管态时，程序执行时可使用包括特权指令在内的一切指令； 当设置为目态时，程序执行时不可使用特权指令。等待/计算置为计算状态时，处理器按指令地址顺序执行指令； 置为等待状态时，处理器不执行任何指令。2.中断码：保存程序执行时当前发生的中断事件3.中断屏蔽位：指出程序执行中发生中断事件时，要不要响应出现的中断事件 在单处理器的计算机系统中，整个系统设置一个用来存放当前运行程序的PSW的寄存器，该寄存器称为程序状态字寄存器（PSW寄存器）1.6 操作系统与用户的接口为了使用户能方便的使用计算机系统，操作系统提供了两类使用接口： 1.程序员接口：指一组系统功能调用 2.操作员接口：指一组操作控制命令1.6.1 系统调用 操作系统编制了许多不同功能的子程序，供用户程序执行中调用，这些由操作系统提供的子程序称为系统功能调用，简称系统调用 访管指令：是一条可以在目态下执行的指令，用户程序中要调用操作系统的功能时，就安排一条访管指令并设置一些参数。当处理器执行到访管指令时，就产生一个访管中断，实现用户程序与系统调用程序之间的转换。1.6.2 操作控制命令交互式应用下：操作控制命令（终端命令、图形用户界面：菜单）批处理系统下：作业控制语言（书写作业控制说明）第二章 处理器管理2.1 多道程序设计2.1.1 程序的顺序执行程序依照编制的程序的顺序执行特点：1. 封闭性：程序的结果，运行速度只和程序本身有关，与环境无关2. 可再现性2.1.2 程序的并行执行处理器和设备之间，设备和设备之间并行工作的能力程序并行执行的缺点：并发进程相互制约；程序和计算不再是一一对应；不可再现。2.1.3 多道程序设计多道程序设计定义：允许多个程序同时进入一个计算机系统的主存储器并启动进行计算的方法（内存中同时有多个作业，它们共享计算机系统中的资源，轮流使用处理机）优点：1. 提高了处理器的利用率2. 充分利用系统中的资源3. 系统吞吐量大（吞吐量：单位时间内完成作业的数量）缺点：一旦将作业提交给系统，用户无法控制作业的执行2.2 进程的概念2.2.1 进程的定义把一个程序在一个数据集上的一次执行称为一个进程进程是动态的，程序是静态的一个程序可以对应多个进程2.2.2 为什么要引入进程1.提高资源利用率2.正确描述程序的执行情况2.2.3 进程的属性1. 进程是动态的，它包含了数据和运行在数据集上的程序2. 多个进程可以含有相同的程序3. 多个进程可以并发执行4. 进程有三种基本状态：（重点） 等待态等待某事件发生。如：读磁盘，等待输入信息等 就绪态等待系统分配处理器运行（最多有n-1个进程为该状态，n为内存中的进程数） 运行态正在占有处理器运行（最多只有一个进程为该状态）进程状态的转换：运行态等待态：进程运行中等待分配资源，等待排除干预状态等待态就绪态：外围设备工作结束（一个结束等待的进程必须先转换成就绪态，当分配到处理器后才能运行）运行态就绪态：分配给进程占用处理器的时间用完；或有更高优先级的进程要运行迫使其让出处理器就绪态运行态：等待分配处理器的进程占用处理器 等待态运行态这个转换是不可能有的！进程的特性：并发性：系统中同时存在若干进程动态性：进程状态不断变化异步性：以不可预知的速度向前推进独立性：进程是分配资源的独立单位交往性：与其他进程交换信息结构性：一个进程包括三个部分：程序、数据、进程控制块2.3 进程控制块（PCB）定义：对进程进行管理和调度的信息集合（描述进程外部特性的数据结构）。它包含四类信息：（内容）1.标识信息：用于标识一个进程（进程标识符） 特征：当前状态2.说明信息：用于说明进程情况（进程状态、等待原因、进程程序存放位置、进程数据存放位置）3.现场信息：记录进程释放出处理器时的现场信息（通用寄存器内容、控制寄存器内容、PSW寄存器内容）4.管理信息：用于管理进程（进程优先数，队列指针）作用：PCB是进程存在的唯一标志。进程的动态、并发特性通过PCB表现出来每一个进程都有生命周期：从创建到消亡原语的定义：操作系统中设计的能完成特定功能且不可中断的过程。特点：不可中断用于控制进程的原语有：1. 创建原语：创建一个进程 流程：申请一个PCB确定有运行内存为新进程分配资源加入就绪队列2. 撤消原语：回收进程占有的资源 流程：找到要撤销的进程收回进程占有的资源将PCB加入空PCB队列终止其所有子进程3. 阻塞原语：进程的运行态就绪态 流程：保存现场信息在PCB中将进程状态改变为等待状态将进程PCB加入相应的等待队列转进程调度（将就绪队列中的一个进程变为运行态）4. 唤醒原语：实现进程等待态就绪态转换 流程：从等待队列中找到该进程将其状态改为“就绪”将其加入就绪队列若进程具有较高优先级，则设置重新调度标志导致进程被撤销的情况：进程正常终止；某种错误导致非正常终止；祖先进程要求撤销某个子进程。2.4 进程队列为方便管理，经常把处于相同状态的进程链接在一起，称“进程队列”进程的基本队列：就绪队列、等待队列出队：一个进程从所在的队列退出的操作入队：一个进程排入到一个指定的队列的操作系统中负责进程入队和出队的工作称为进程管理2.5 中断和中断处理2.5.1 中断定义：一个进程占用处理器运行时，由于自身或者外界的原因（出现了事件）使运行被打断，让操作系统处理所出现的事件，到适当的时候再让被打断的进程继续运行，这个过程被称为中断。中断源：引起中断的事件中断处理程序：对出现的事件进行处理的程序2.5.2 中断类型从中断事件的性质分类：1.强迫性中断事件：1) 硬件故障中断：由机器故障造成2) 程序中断：程序本身原因导致的中断3) 外部中断：由外部事件引起的中断4) 输入/输出中断：输入输出控制系统发现外围设备完成了操作而引起的中断2. 自愿性中断事件：访管中断：执行访管指令引起的中断2.5.3 中断响应硬件即中断装置操作中断响应定义：处理器每执行一条指令后，硬件的中断装置立即检查有误中断事件发生，若有中断事件发生，则暂停现行进程的执行，而让操作系统的中断处理程序占用处理器，这一过程称为“中断响应”。当中断装置发现中断事件后：（交换PSW寄存器中的值）1. 首先把出现的中断事件保存到程序状态字寄存器中的中断码位置；2. 然后把程序状态字寄存器中的“当前PSW”作为“旧PSW”存放到于先约定好的主存固定单元保存起来3. 再把已经确定好的操作系统处理程序的“新PSW”送到程序状态字寄存器，成为“当前PSW”当前PSW：当前正在占用处理器的进程的PSW新PSW：中断处理程序的PSW旧PSW：保护好的被中断进程的PSW中断响应的过程就是“交换PSW”的过程PSW寄存器只有一个！2.5.4 中断处理软件即操作系统操作各类中断事件的处理原则：1. 硬件故障中断事件的处理：必须人工干预，系统知识输出出错信息2. 程序中断事件的处理：交给用户自己处理3. 外部中断事件的处理：执行特定的例行程序4. 输入/输出中断事件的处理：分正常结束和异常结束5. 访管中断事件的处理：根据系统调用类型号，查“系统调用程序入口表”，找到程序入口地址把处理转交给实现调用功能的程序执行2.6 处理器调度2.6.1 处理器的两级调度在操作系统中，把磁盘上用来存放作业信息的专用区域称为输入井。把在输入井中等待处理的作业称为后备作业。处理器调度流程：进程调度作业调度进程“运行”（一个进程占用CPU）作业被装入主存，作业进程“就绪”预输入作业进入“输入井”等待执行作业流2.6.2 作业调度算法作业：用户让计算机完成的一次算题作业步：算题的步骤。编译、连接、运行作业控制方式：交互式和批处理方式后备作业：成批进入输入井的作业作业调度定义：从输入井中选取后备作业装入主存储器的工作（从后备作业中选取若干个作业让他们进入主存，使他们有机会去获得处理器运行，作业调度的过程就是创建进程的过程）作业调度的必要条件：系统现有的尚未分配的资源可以满足被选作业的资源要求调度算法的设计原则：1. 公平性：不能无故或无限制拖延一个作业的执行2. 平衡资源使用：尽可能的使系统资源都处于忙碌（均衡利用资源）3. 极大的流量：在单位时间内尽可能多的作业服务，保证计算机系统的吞吐能力（吞吐量）常用算法：（综合题出题点）1. 先来先服务算法 注：不是先进入的一定先被选中，只有满足资源需求的作业才可能被选中2. 计算时间短的作业优先算法 该算法以用户估计的计算时间为标准（超过估计时间加价）3. 响应比高者优先算法 响应比=等待时间/运行时间4. 优先级调度算法：优先级高者先被选取5. 均衡调度算法：根据作业对资源的要求进行分类，作业调度轮流从不同类的作业中去挑选作业运行计算题解题思路：1. 作业调度的时机：一个作业到达后备队列；一个作业执行完毕2. 先决条件：必须先满足作业的资源需求3. 考虑调度的算法2.6.3 进程调度算法进程调度定义：从就绪进程中选取一个进程，让它占用处理器的工作进程切换：一个进程让出处理器由另一个进程占用处理器的过程。通常，进程的切换是由进程状态的变化引起的。进程的切换与中断事件有关（交换进程的PSW来实现）进程调度的时机：1.正在运行的进程运行完毕；2.正在执行的进程被阻塞，加入等待队列；3.时间片到时；4.高优先级的进程进入就绪队列。进程调度的评价指标：1. 进程的等待时间2. CPU的利用率3. 系统资源的利用率4. 响应时间5. 周转时间6. 一般用平均周转时间来衡量一个调度算法的好坏进程调度算法：1. 先来先服务调度算法：根据进程到达就绪队列的次序。总是选择先到达的进程运行。 优点：公平性；管理简单（队列）。 缺点：由于进程到达的随机性，可能使系统中的短作业等待时间长。2. 最高优先级调度算法：对每个进程给出一个优先级（给出优先数），进程调度总是让当时具有最高优先级的进程先使用处理器。 如何确定优先级：1.进程类别（高低：系统进程用户进程前台后台）；2.进程运行时间（运行时间短的优先级高）；3.作业的优先级等。 当一个更高优先级进程到达就绪队列时，如何处理：1.抢占式（一个进程在运行时若出现一个更高优先级的就绪进程，则这个正在运行的进程要让出处理器给更高的那个进程）实时系统采用；2.非抢占式（一旦分配CPU，就一直占用直到主动放弃） 如果一个低优先级进程在就绪队列中等待时间太长怎么办：动态优先数（进程的优先级随等待时间而调整高优先级） 对具有相同优先级的进程可使用先来先服务算法。3. 时间片轮转调度算法（在分时系统中使用） 时间片：系统允许进程一次使用处理器的最长时间。 工作原理：就绪队列中的进程，每次最多使用一个时间片。 硬件支持：计时器。时间片到，发生“计时中断” 时间片的长短如何确定：1.就绪队列长短：越长，时间片越短2.响应时间的要求：越高，时间片越短3.计算机的性能：越强，时间片越短4.进程切换的系统开销：开销越大，时间片越短2.7 线程的概念2.7.1 什么是线程进程的角色：分配资源的基本单位；进程调度的基本单位出现问题：进程切换的系统开销很大；进程数目不能太多线程定义：把用户的一个计算问题或一个应用问题作为一个进程，把该进程中可以并发执行的各部分分别作为线程。线程是进程中可独立执行的子任务线程是进程中的一个实体，是系统调度的基本单位。线程几乎不拥有资源（除了少数的寄存器内容外）。进程汇总的所有线程共享进程的资源。同一进程中的不同线程也可以并发执行。2.7.2 为什么要引入线程 进程可以提高CPU的利用率，进程之间的切换是非常耗费资源和时间的，为了能更进一步的提高操作系统的并发性，从而引进线程。2.7.3 线程的属性1. 同一进程中的各线程驻留在分配给进程的主存地址空间中，且共享该进程的所有资源。2. 一个线程被创建后便开始了它的生命周期，直到执行结束而终止。线程在生命周期内也会经历等待态，就绪态和运行态。3. 线程是处理器的独立调度单位，多个线程可以并发执行。4. 不同线程可以执行相同的程序，即同一个服务程序被不同用户调用时，操作系统为它们创建不同的线程。第3章 存储管理3.1 计算机系统中的存储器1. 寄存器：只用来存放临时的工作数据和控制信息。（价格最贵，存取速度最快，容量小） 常用寄存器：指令寄存器、通用寄存器、控制寄存器2. 高速缓存存储器：用于存放经常被访问的单元信息（从主存中复制而来），以提高主存的速度。3. 主存储器（内存）：用于存放用户当前需执行的程序和数据，以及操作系统进行控制和管理的信息。4. 辅助存储器（外存）：用于存放当前暂不参与运行的程序和数据以及一些需要永久保存的信息。（存取速度较慢） 存储器管理的功能：1.内存空间的分配和回收2.地址变换3.内存共享与保护4.虚拟存储器3.2 重定位3.2.1 绝对地址和逻辑地址绝对地址（物理地址）：内存中的地址编号。逻辑地址：用户程序中使用的从“0”地址开始的连续空间。3.2.2 重定位地址重定位：把逻辑地址转换成物理地址的过程地址重定位方式：根据定位的时机不同，分为静态地址重定位和动态地址重定位：1. 静态地址重定位：在作业装入内存时，进行的重定位（在作业开始前集中完成转换工作）。 程序中的地址都是物理地址优点：简单，无需增加硬件地址转换机构缺点：一旦装入，就不能在内存中移动位置；无法实现内存共享2. 动态地址重定位：在程序运行时进行的地址重定位（由硬件地址转换机构转换成绝对地址）硬件支持：重定位寄存器（基址寄存器）程序中的地址是逻辑地址物理地址=基址寄存器+逻辑地址优点：程序占用的内存空间动态可变；容易实现内存共享缺点：需要硬件支持（基址寄存器），增加成本；管理软件比较复杂现代计算机中普遍采用动态地址重定位。3.3 单用户连续存储管理1. 基本原理 内存分为两部分：用户区、系统区 任何时刻，内存中最多只有一个用户作业（适合单道运行的计算机系统）2.内存分配算法 3. 存储保护：保护系统程序不会遭到用户程序的破坏。 措施：设置一个界限寄存器存放当前可供用户使用的主存区域的起始地址。4. 多用户共享（分时系统）情况下 对换技术：让多个用户的作业轮流进入主存储器。 硬件支持：大容量高速辅助存储器（硬盘）。5. 地址重定位方式：静态地址重定位绝对地址=逻辑地址+界限地址缺点：区域利用率低，浪费内存3.4 固定分区存储管理基本原理：在作业加载内存之前，将内存划分为若干个连续的区域。一旦划分好后，主存储器的分区个数和大小就确定了，不能改变。各个分区的大小可以不同（小作业区和大作业区）。3.4.1主存空间的分配与回收存储管理设置一张“分区分配表”，用来说明各分区的分配和使用情况。表中指出各分区的起始地址和长度，并为每个分区设置一个标志位。当标志位为“0”时，表示分区空闲，非“0”时表示分区已被占用。如下：分区号起始地址长度占用标志（状态）1aL10（空闲）2bL2Job1（已分配）3cL30（空闲）分配算法：从分区分配表中查找一个状态是“空闲”、大小满足作业要求的分区，并将状态改为“已分配”。回收算法：只需要将分区分配表中的“状态”值改为“空闲”即可。流程：3.4.2 地址转换和存储保护地址转换：静态重定位存储保护：上下限地址法处理器设置一对寄存器：上限寄存器和下限寄存器，作业地址应满足：下限地址绝对地址上限地址（中断事件）。否则，发生“地址越界”中断事件。存在问题：内存利用率很低3.4.3 如何提高主存空间的利用率1. 按统计规律划分分区2. 按分区大小顺序排列，低地址部分是较小的分区，在分区分配表中按从小到大顺序登记。为作业分配满足条件的最小的分区3. 按作业对主存储器的需求量排成多个队列，每个作业队列中的作业只能依次装入一个分区中3.5 可变分区存储管理1.在作业要求装入主存时，根据作业的大小从空闲内存中“切出”一片连续的区域。2.分区的长度（大小）和个数是不预先固定的。（“量体裁衣”） 初始时，系统中只有一个连续的用户区域，随着作业的到达和撤销，用户区就被划分为若干个大小不等的区域。3.5.1 主存空间的分配与回收空闲区的管理：1.空闲分区表（包含字段：序号、起始地址、大小、状态（空闲/已使用）2.空闲分区链（空闲区大小：下一空闲区起始地址）知道一个空闲区地址就能知道下一个空闲区地址分配算法：1. 最先适应分配算法空闲分区表按地址从小到大排列，从第一个开始，找到第一个满足条件的分区，根据作业的大小切出一片连续的区域。分配流程：缺点：碎片（不连续的空闲区）过多，使主存空间的利用率降低。2. 最优适应分配算法：（对大作业有利）原理：将空闲区按长度从小到大排列，将满足需求的最小的空闲区分配给作业。优点：为了更好的满足大作业的需求。缺点：这样切下的空闲区容易变成“碎片”算法流程与最先适配法相同。3. 最坏适配算法：（对小作业有利）从满足需求的最大空闲区中为作业分配空间；空闲分区表按大小从大到小排列。优点：切完后的空闲区仍能满足某个作业的需求，减少碎片的数量。缺点：对大作业不利。分配流程：如何判断待回收区是否与空闲区相连？ 地址+长度=下一空闲区首地址（等式成立则相连）空闲区的管理：为了便于空闲区的合并，采用链接结构。 按地址从大到小排序。3.5.2 地址转换和存储保护采用动态地址重定位硬件支持：基址寄存器和限长寄存器；加法线路、比较线路物理地址=基址寄存器地址+逻辑地址内存保护：物理地址必须满足以下条件：1. 基址寄存器内容物理地址（绝对地址）限长寄存器内容（否则：发生地址越界中断）2. 基址寄存器和限长寄存器总是存放当前运行（占用处理器）的作业所占分区的始址（基址）和末址（限长）K：长度 c：逻辑地址3.5.3 移动技术碎片问题：一些很小的内存区域移动：把作业从一个存储区域移动到另一个存储区域的工作移动技术：将离散的碎片集合在一起移动技术的限制：1. 不是任何时候都可以移动：如果作业在执行过程中正等待与外围设备传输信息则不能移动；2. 2.需要很大的系统开销；3. 3.保护问题：界限地址法：基址和长度寄存器。移动技术的目的：1.集中分散的空闲区；2.便于作业动态扩充主存3.6 页式虚拟存储管理3.6.1 页式存储管理的基本原理 “等分”内存：把内存划分为若干个大小相同的“块” 把用户作业空间划分为大小相同的“页”（操作系统划分） 页和块的大小相同 分页式存储期的逻辑地址由页号和页内地址组成 在把作业加载到内存时，页和页之间不再连续，但页内连续。 也不必把所有的页都一次性加载内存，只需要加载那些马上要用到的页。其余的页在需要时再加载。3.6.2页式主存空间的分配与回收主存（内存）分配用户需求：需要多少块？内存空闲块的管理：位示图位示图：在内存中划出一片区域，用一位代表一个块，该位的值表示所代表的块的状态（0：空闲，1：已分配） 块号与字号、字长的关系：系统的字长一定，内存块从0开始编号，则有： 分配块号=字号x字长+位号 字号=归还块号/字长 （ 表示取整的意思） 位号=块号 mod 字长 （mod表示取余数部分）3.6.3页表和地址转换逻辑地址：页号+页内地址如何转变为内存物理地址？物理地址=块号x块长+页内地址块长度一定，块内地址与页内地址相同问题变为：如何根据页号得到块号？地址变换过程：（综合题出题点）1. 根据页号查页表，得到块号2. 根据块号和页内地址计算物理地址（物理地址=块号x块长+页内地址）3. 例题：用户编程空间32个页：逻辑地址页号占5位（2的5次方）每页大小1024B：页内地址10位（2的10次方）内存16KB：内存分16个块需掌握十六进制转换为二进制的算法及位、字节、字之间的转换知识页表的实现-快表 从上述地址变换过程可以看出：CPU每取一条指令或数据，都必须经过页表。 因此，页表的每一个表项都是一个动态重定位机构。如何实现页表，将影响系统效率。 方式：1. 硬件实现：用寄存器组。（代价太高，特别是内存很大时，是不可能的。）2. 软件实现：将页表放在内存中。每取一条指令，要两次访问内存。3. 软硬件结合：将页表中使用最频繁的表项（页表的一个子集）放在cache（高速缓冲存储器）中。称为“快表” Cache也称为“联想寄存器”，它不是根据地质二是根据所存信息的全部特征或部分特征进行存取，在这里为页号。 若要访问的页在cache中，则只需一次访问内存，若不在，则到内存中去找，同时把新的页表表项写入cache。（例题中：1=1次访问，2=2次访问）3.6.4 页的共享和保护保护的实现：在页表上添加一个保护位。在做地址变换时，检查对页面的访问是否合法。共享的实现：根据地址转换过程可知：如果在不同用户的页表上填上相同的页表表项（块号），就能够访问相同的内存空间。3.6.5 什么是虚拟存储器虚拟存储器：内存扩充技术，为用户提供一个比实际内存大得多的内存空间。3.6.6 页式虚拟存储管理的实现实现虚拟的三个重要条件：1. 程序中的哪些页已经加载内存 页式虚拟的基本原理：加载作业时，只加载那些最活跃的页，其余的页需要时再加载。（“请求调页技术”和“预调页技术”）如何知道哪些已在内存在页表中添加一个标志位（中断位），标志该页是否已在内存（0：不在 1：在内存）2. 当要访问的页不在内存时，如何将其调入内存？ 发生缺页中断 缺页中断的处理过程： 1.保存现场（保存到PCB） 2.在内存中找到一个空闲块 3.从磁盘上找到要调入的页 4.读磁盘到内存 5.恢复现场 6.重新调度运行 3. 若此时（调入内存时）内存空间已满，如何选择换出的页？ 进行“页面替换”（综合题考点）从内存中选择一个页调出内存，为新调入的页让出空间。 如果替换的不合适，则发生“抖动”或“颠簸”现象（页面替换过程中替换不合适，使得该页在内外存之间频繁调入调出，系统开销大）页面调度：1. 先进先出调度法（FIFO：firs in firs out）：将最先调入内存的页调出内存2. 最近最久未使用调度算法（LRU：least recently used）：将最近一段时间内没有用过的页调出内存3. 最近最不经常使用调度算法（LFU：least ferquently used）：最近一段时间内使用次数最少的页调出内存为每一个在内存的页设置一个计数器，选择计数器中的值最小的调出。注意：LRU、LFU之间的区别程序区页不能参与页面替换，刚开始数据区空：缺页中断页式存储管理的缺陷：从理论上讲，不同用户共享程序段或数据很简单，只需在不同用户的页表中填上相同的块号，经地址变换后，一定能访问相同的内存空间。但是，由于页的划分是由系统自动进行的，很可能用户要共享的页分布在不同的页中，给共享和保护造成了麻烦。3.6.7 多级页表执行程序的局部性原理没有必要把整个页表都一直保存在内存中多级页表结构：相当于把页分成了1024个页面组，一个组内有1024个页。一级页表：存放二级页表的存放地址二级页表：指出页的存放地址地址转换过程：1. 按逻辑地址中的页号1查一级页表，找出对应的表项2. 根据表项中的标志位确定二级页表是否已在主存3. 若在主存，就按照页号2得到页在内存中的块号好处：节约内存空间第4章 文件管理4.1 概述4.1.1 文件和文件系统文件：命名了的数据项的集合（逻辑上具有具有完整意义的信息集合）。每一个文件都有一个唯一的文件名。对文件实现“按名存取”用户只需给出文件的名字，就可以方便的使用文件，而不必关心文件的物理存储位置文件系统：1.存取和管理外存储器上的文件机构2.统一管理信息资源的一种软件3.管理文件的存储、检索、使用4.提供安全、可靠的共享和保护手段5.并且方便用户使用4.1.2 文件系统的功能功能：1. 实现从逻辑文件到物理文件的转换 逻辑文件：用户角度去看的文件2. 有效地分配文件的存储空间3. 建立文件目录（实现文件的“按名存取”）4. 提供合适的存取方式以适应各种不同的应用5. 确保文件的安全性6. 提供一组文件操作4.1.3 文件的分类按用途分类： 1.系统文件：操作系统和各种系统应用程序和数据组成的文件。用户只能通过系统调用访问。 2.库文件：标准子程序及常用应用程序组成的文件 3.用户文件：用户委托系统保存的文件按保存期限分： 1.临时文件：用来存放中间结果，一旦作业完成，文件会自动删除。（temp目录，.tmp文件） 2.永久文件：数据需要长期保存的文件 3.档案文件：保存在作为“档案”用的磁带或光盘等永久介质上，以备查证和恢复时使用的文件。按文件组织方式分：逻辑文件、物理文件 UNIX系统中的文件类型 1.普通文件：由一般信息组成的文件。 2.目录文件：由文件的目录构成的特殊文件：用来检索文件的目录信息。 3.特殊文件：把设备看作是文件。对文件的操作转化成对设备的操作。与设备驱动程序紧密联系。按文件的保护级别分：只读文件、读写文件、执行文件、不保护文件按设备类型分：磁带文件、磁盘文件按信息流向分：输入文件（键盘）、输出文件（打印机）、输入输出文件（磁盘）4.2 文件的存储介质存储介质的概念：可以用来记录信息的磁带、硬磁盘组、软磁盘片、光盘、卡片等称为存储介质主流的存储介质：磁带、磁盘几个常用概念 卷：存储介质的物理单位 块（物理记录）：存储介质上可连续存储信息的一个区域（块是主存储器与存储设备交换信息的物理单位）磁带的存储原理（顺序存取的存储设备）1. 记录只能按在磁带上的物理顺序存取2. 记录之间的空隙是必须的，且长度只与磁带的物理特性有关3. 为了提高磁带的利用率，采用成组技术，即将若干个记录放在一个记录块中4. 但在读取时，需要缓冲区和程序的支持例题：磁盘的存储原理（按地址直接存取的存储设备）1. 硬盘：若干个盘片摞在一起2. 地址：柱面号+磁头号+扇区号（每个参数均从0开始编号） 柱面号（磁道的编号）从最外编号，从0开始； 磁头号（所有的读写磁头从上到下的编号）从最上面编号，从0开始； 扇区号按盘片转动的反方向编号。3.磁盘读写时间：寻找时间+延迟时间+传输时间4.3 文件的组织文件的组织是指文件的构造方式文件的逻辑结构：用户把能观察到的且可以处理的信息根据使用要求构造成文件的构造方式文件的存储结构：在存储介质上的文件构造方式4.3.1 文件的逻辑结构逻辑文件：用户组织的文件无结构的字符流式文件：构成文件的基本单位是字符（源程序文件，目标代码文件等）有结构的记录文件：构成文件的基本单位是记录（定长记录文件：根据记录号和记录长度来确定逻辑记录地址；不定长记录文件；记录的主键）4.3.2 文件的存储结构物理文件：存放在存储介质上的文件1. 顺序结构：把一个文件在逻辑上连续的信息存放到磁盘上依次相邻的块中，便形成顺序结构。物理顺序和逻辑顺序一致存储介质：磁带只读或只写文件（备份和恢复）适合顺序存取优点：存取信息速度快缺点：磁盘存储空间利用率不高2. 链接结构：存储空间是不连续的（存储介质一般为：磁盘）文件的逻辑记录顺序与磁盘上的存储空间顺序独立文件信息占用的第一块的物理地址登记在文件目录中每一个物理块的最后一个单元存放下一块的链接指针（如果链接指针为0，表示文件结束）又称“链接文件”或“串联文件”（只能顺序存取，便于插入和删除）优点：允许用户扩充文件（插入，删除）只适合于对记录按先后顺序进行存取的文件3. 索引结构：索引文件：非连续存储的一种方法索引表：记录号与地址的对应表顺序存取或随机存取便于增、删文件的记录额外的开销（索引表）4.3.3 文件的存取方式（建立）逻辑结构与物理结构之间的关系顺序存取和随机存取 顺序存取：按文件的逻辑顺序或记录顺序依次进行读/写的方式 随机存取：按任意次序读/写存取方式、存储介质、存储结构之间的关系：4.3.4 记录的成组和分解成组：将若干个逻辑记录存放在同一个物理块中（当访问某个逻辑记录是，必须将整个块先读到内存中）分解：从物理块中读取某个逻辑记录硬件支持：缓冲区块因子：一个物理块中包含的逻辑记录的个数块因子=物理块/逻辑块 （ 表示取整）上例中：512/125=4 所以，块因子为4，就是说一个物理块中可以存放4个逻辑记录 总共需要：20/4=5个物理块分解的过程：第一步：计算记录所在的块： 逻辑记录号：1285/125+1=11 所在块：11/4+1=3第二步：将第三块读入内存缓冲区第三步：从缓冲区中读取逻辑记录： 计算相对记录号：11 mod 4=3 将第三个记录读到内存区4.4 存储空间的分配用一个位代表一个磁盘块。如果字长为32位，则字号、位号、块号之间的关系是：块号=字号x字长+位号字号=块号/字长位号=块号 mod 字长4.4.1 位示图法柱面号、磁头号、扇区号与块号之间的关系： 已知块号，求块的物理地址（柱面号，磁头号，扇区号）：柱面号=块号/每个柱面上的块数磁头号=块号 mod 每个柱面上的块数扇区号=（块号 mod 每个柱面上的块数）mod 每个磁道的扇区数 已知物理地址，求块号： 块号=柱面号x每个柱面上的块数+磁头号x每个磁道的扇区数+扇区号例题：分析：答案：4.4.2 空闲块链接法空闲空间链：在空闲块中利用几个字节，存放下一空闲块的块号两种链： 1.单块链 2.成组链：把若干个空闲块的块号存放在一个空闲块中（比如100块），这样每读一次磁盘，就可以得到100个空闲块号，大大减少了读写磁盘的次数，提高了整个系统的效率。在组成链中，有一个特殊的块叫专用块，存放的是不足一组的空闲块的块号。系统初始时先把专用块读到内存，由于第一块中存放的是另一组的地址，不能首先分配，因此分配时时从下往上的，如下图所示：先分配23块，再分配98块，最后分配67块 当遇到最后内存专用块一块时，不能马上分配出去，必须首先把该块中存储的内容（即100个空闲的块号）读到内存中专用块的位置，才能分配该块。如果专用块在内存中的起始地址为L，第一个单元中存放的是空闲块数的话，则过程描述如下： 分配一个空闲块：查L单元中的内容（空闲块数）（1） 若空闲块数1 i=L+空闲块数 取出i单元中的值，即为要分配的空闲块号 将该块分配给申请者 空闲块数-1（2）若空闲块数=1 取出L+1单元中的内容，其值为用来存放下一组空闲块的块号 若其值为0，则说明无空闲块，申请者等待 归还一个空闲块：取L单元中的内容（空闲块数）（1） 若空闲块数100 i=L+空闲块数 空闲块数+1 j=L+空闲块数 归还块号填入j单元（2） 若空闲块数=100 把主存中的登记信息写入归还块中 把归还块号填入L+1单元 将L单元置成14.5 文件目录文件目录是文件系统实现按名存取的重要手段。文件组成：文件控制块和文件体。文件控制块：描述文件信息的数据结构。每一个文件都有一个文件控制块（FCB）。FCB中的内容：满足操作系统对文件管理和控制的需求，如逻辑地址到物理地址的转换、文件共享、文件保护等等。 每一个文件都有一个文件控制块（FCB），当访问一个文件时，根据文件名查FCB，得到文件的物理地址（根据文件名去查FCB，从查到的FCB中找出物理地址） 磁盘容量很大，FCB也很多，如何提高查找的效率： FCB的组织-目录（FCB的有效集合） 注意：目录与目录项、目录文件和文件目录的区别 4.5.1 一级目录若不同的用户为文件起了相同的名字，怎么办？ 严重问题：文件重名问题4.5.2 二级目录解决文件重命名问题，实现共享和保护问题：当文件数量多的时候不便于分类管理4.5.3树形目录便于文件的分类组织，便于查找和管理路径：相对路径和绝对路径将整个目录放在内存中，不现实。当前目录：在内存中开辟一个缓冲区，将当前目录信息放在内存中。例如：在DOS的CONFIG中，有一条命令LASTDRV，用来确定缓冲区的多少。4.6 文件的安全性4.6.1 文件的保护保护的含义：防止文件被非授权的用户窃取、破坏等。保护的措施：1. 防止天灾人祸：备份2. 防止系统故障造成的破坏：转移存储3. 防止用户共享文件造成的破坏：存取权限Unix系统的文件保护措施：4. 防止计算机病毒的侵害：4.6.2 文件的保密保密的含义：防止他人窃取文件保密的措施：1. 口令2. 加密技术4.7 基本文件操作及其使用4.7.1 基本文件操作1. “建立”操作用户使用创建（create）命令来通知系统要建立一个新文件在命令中，用户需要说明要创建的文件名、用户名、存储设备、存取方式等参数。系统接到命令后，做如下处理：1. 让用户在指定的存储设备上安装存储介质2. 查找目录，检查是否已有同名文件存在3. 在目录中为文件建立一个空目录项，填入相应信息4. 确定文件的存储结构5. 做上该文件已“建立”的标志2. “打开”操作当用户要打开一个文件时，文件系统要做的工作：1. 让用户在指定的存储设备上安装存储介质2. 找出该用户的文件目录，当文件目录不在主存储器时，把它读到主存储器中3. 找出与用户文件符合的目录项，得到文件的物理地址4. 核对用户口令5. 核对存取方式是否与建立时一致6. 找出文件存放在存储介质上的起始位置7. 如果是索引文件，需将索引表读入内存8. 做上该文件已“打开”的标志3. “读”操作1.确认文件是否打开2.核对存取方式是否合理3.顺序存取：当前块读入内存4.随机存取：先计算记录地址4.“写”操作1.核对文件是否建立2.寻找空闲的存储空间3.对采用索引结构的文件须登记索引项5.“关闭”操作1.检查是否是文件打开者或者建立者请求关闭2.检查目录是否被修改过（若是，则把他们重新保存到存储介质上）3.清除文件已“打开”或“建立”的标志6.“删除”操作1. 在指定的设备上让用户安装含有该文件的存储介质2. 检查文件是否已关闭3. 在文件目录中删除该文件的目录项4. 收回该文件占有的存储空间4.7.2 文件操作的使用为了保证文件系统对文件的