安徽大学操作系统复习资料.doc

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.32M 资料格式：doc 举报版权申诉

第1页 / 共25页

第2页 / 共25页

第3页 / 共25页

第4页 / 共25页

第5页 / 共25页

第6页 / 共25页

第7页 / 共25页

第8页 / 共25页

文本预览

绪论：批处理系统、分时系统、实时系统的概念与特点，原语与原子操作。安徽大学操作系统复习资料 1.批处理操作（1）单道批处理系统概念单道批处理系统是指系统通过作业控制语言将作业组织成批，使其能自动连续运行，但是，在内存中任何时候只有一道作业的系统。单道批处理系统特征顺序性单道性自动性（2）多道批处理系统概念系统对作业的处理是成批进行的，并且在主存中能同时保留多道作业的系统。多道批处理系统的主要目标是提高系统吞吐率和各种资源的利用率。多道批处理系统特征无序性多道性调度性 2.分时系统（1）概念分时操作系统是指在一台主机上连接了多个联机终端，并允许多个用户通过终端以交互的方式使用主计算机，共享主机资源的系统。（2）分时系统的主要目标是实现人与系统的交互性。分时系统设计的目标是保证用户响应时间的及时性。（3）分时系统的特征多路性独立性及时性：满足用户对响应时间的要求交互性 3.实时操作系统（1）概念实时操作系统是指系统能够及时响应外部（随机）事件的请求，并能在规定的时间内完成对该事件的处理，控制系统中所有的实时任务协调一致地工作。（2）实时操作系统的特征多路性独立性及时性：满足实时任务截止时间的要求交互性可靠性 4.原语：操作系统内核或微核提供核外调用的过程或函数称为原语，是由若干条指令构成，用于完成特定功能的一段程序。原语在执行过程不允许被中断。 5.原子操作：执行中不能被其它进程（线程）打断的操作就叫原子操作。当该次操作不能完成的时候，必须回到操作之前的状态，原子操作不可拆分。进程管理：什么是进程？进程与程序的区别与联系？进程的特征有哪些？进程之间的关系有哪些？什么是信号量？信号量的物理含义？ 1.进程定义可并发执行的程序在一个数据集合上的运行过程，是系统进行资源分配和调度的基本单位。 2.进程特征（1）动态性（2）并发性（3）独立性（4）异步性（5）结构特征： 3.进程与程序的关系（1）程序是一组指令的集合，是静态的概念；进程是程序的执行，是动态的概念。(本质区别) （2）进程有生命周期，它的存在是暂时的；程序的存在是永久的。（3）进程包括程序代码、数据和“进程控制块”三部分。（4）进程是一个独立的运行单位，是系统进行资源分配和调度的独立单位。（5）一个程序在执行中可对应多个进程，一个进程也可能包含多个程序段。

4，进程的基本状态（1）运行状态（Running):已得到 CPU，正在执行的状态。（2）就绪状态（Ready)：得到了除 CPU 以外的所有资源，正在等待 CPU 的状态。（3）等待状态（Blocked，也称阻塞状态）：进程等待某一事件的发生而暂时停止运行的状态。 5. 进程之间的关系有哪些同步互斥 6.什么是信号量？信号量是实现进程同步的一种变量。是一种有效的进程同步工具，可分为：整型信号量、结构型信号量、信号量集等。 7.信号量的物理含义 S>0 表示有 S 个资源可用 S=0 表示无资源可用 S<0 则| S |表示 S 等待队列中的进程个数 P(S):表示申请一个资源 V(S)表示释放一个资源。信号量的初值应该大于等于 0 设备管理：设备的分类按数据传输单位，设备可分成：  字符设备（输入输出设备）：字符设备中存储和传送的是不定长的数据，是以字符为单位发送或和接收一个字符流，传输速度低、不可寻址(源地址或目标地址)。如打印机、键盘、网卡和显示器等。  块设备（存储设备）：块设备中存储是定长的、且可随机访问的数据块，每个块都有自己的地址，信息处理的基本单位是数据块，传输速度高、可寻址。如磁盘，CD-ROM。按传输速率，设备可分成：  低速——键盘、鼠标器、语音的输入和输出设备  中速——行式打印机、激光打印机  高速——磁带机、磁盘器、光盘机按共享属性，设备可分成：  独占设备：一次只允许一个进程访问的设备。  共享设备：一段间内允许多个进程同时访问的设备。  虚拟设备：虚拟技术将一台独占设备转换为若干台逻辑设备，共多个进程同时使用。按使用属性，设备可分成：  存储设备：相同中存储信息的主要设备，外存及后备存储器。  人机交互设备（输入/输出设备）：输入、输出和集成输入和输出的设备。文件管理：什么是文件的逻辑结构和文件的物理结构？文件的逻辑结构有哪些？文件的物理结构有哪些？ 1.文件的逻辑结构（1）概念是指用户可以直接处理的文件组织形式，也称文件组织。文件逻辑结构选取的主要考虑因素：存取速度、维护方便和可靠性等。（2）分类从逻辑结构上，文件分为：有结构文件（记录式文件）和无结构文件（字符流文件，是一种顺序文件。）有结构文件（记录式文件） ①根据文件中记录特性分：定长记录文件变长记录文件 ②文件的组织方式（逻辑结构）：顺序文件索引文件索引顺序文件 2.文件物理结构

（1）概念是指文件在外存上的存储结构，也称文件存储结构。文件的物理结构决定了文件信息在存储设备上的存放位置。（2）物理结构的类型连续文件串联文件（链接文件）索引文件 hash 文件简答 1.进程的概念与特点、进程的同步与互斥。进程概念关于进程的定义有多种，其中最具代表性的定义有以下几个：（1）进程是程序的一次执行（2）进程是可以与别的计算并发执行的计算（3）进程是一数据结构及能在其上进行操作的一个程序（4）进程是一个程序及其数据在处理机上顺序执行时所发生的活动（5）进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位进程特征（1）动态性：动态性是进程的基本特性。进程具有生命周期，它由创建而产生，经调度而执行，由撤消而消亡。（2）并发性：在内存中的多个进程实体能在一段时间内同时运行。（3）独立性：进程是系统进行资源分配和调度的一个基本单位，是一个能够进行独立运行的基本单位。（4）异步性：每个进程在运行时都在以不可预知的速度向前推进。（5）结构特征：进程实体实际上是由三部分所组成：程序段、数据段和进程控制块 PCB。在 UNIX 系统中，也把这三部分称为“进程映像”。进程同步与互基本概念（1）并发进程之间的协作控制通常称为进程同步。——直接制约关系（协作）（2）并发进程之间的竞争控制通常称为进程互斥。——间接制约关系（竞争）进程同步与互斥的主要任务就是保证多个并发进程能有效地合作并共享系统资源，使并发进程的执行结果具有可再现性。 2.死锁的概念、死锁产生的原因、死锁的预防和避免方法、资源分配图的简化、死锁定理。（1）死琐概念死锁是指多个并发执行的进程因资源争夺而出现的一种彼此都不能继续向前推进的僵持局面。（2）产生死琐的原因 ①竞争资源——竞争非剥夺性资源（如，打印机）和竞争临时资源（如，某进程生产的数据、消息） ②进程推进的顺序非法（3）死琐的预防 ①避开“ 请求和保持”条件：一次性请求，一次性分配。在进程运行期间不再提出资源请求。这种方法也称“预先静态分配法”。 ②避开 “不剥夺”条件：进程逐个提出资源请求，当前请求不能满足时，必须释放它所拥有的全部资源。 ③避开“环路等待”条件：将所有资源按类型进行线性排队，并赋予不同序号，要求进程申请资源时按序号递增的次序提出。这种方法也称“有序资源分配法”。（4）死锁的避免——银行家算法，死锁的预防——资源有序分配法。（5）资源分配图的简化从图找一个进程结点 pi，若它对资源 Rj（1≤j≤m）的请求满足（既非阻塞也非孤立）： abs(Pi,Rj) + 其中：Wj 表示 j 类资源的总数，（Pi,Rj）表示进程 Pi 申请 j 类资源的数量，（ Rj, pk）表示分配给进程 Pk 的 j 类资源数。简化操作：

①释放 pi 所占有的资源，即去掉它所有的请求边和分配边使其成为一个孤立结点。 ②重复执行前两步，直到找不到满足条件的进程结点为止。（6）死锁定理系统状态 S 为死锁状态的充分条件，当且仅当 S 状态的系统资源分配图是不可完全简化的。（至少有一个进程结点不能简化为孤立结点。）该充分条件被称为死锁定理。 3.文件的多级目录结构（文件的物理结构、文件控制块、索引节点等）文件物理结构（1）概念是指文件在外存上的存储结构，也称文件存储结构。文件的物理结构决定了文件信息在存储设备上的存放位置。（2）物理结构的类型连续文件串联文件（链接文件）索引文件 hash 文件文件控制块（1）概念是文件存在的标志，为提高查找速度，通常把 FCB 集中起来组织成文件目录(目录文件)。目录项分两种：子目录和文件的 FCB。一个文件由 FCB 和文件体（文件内容）两部分组成。 FCB 是操文件系统为每个文件建立的唯一管理数据结构，FCB 主要包括下列信息：  文件标识符和控制信息：文件名、用户名、存取权限、文件类型和文件口令等  逻辑结构信息：记录类型、记录个数和记录长度等  物理结构信息：设备号、文件物理结构类型、文件索引位置等  使用信息：共享进程数、文件最大长度、当前大小和修改情况等  管理信息：文件的建立日期、访问日期和保留期限等（2）文件目录一个文件系统中所有 FCB 的有序集合称为文件目录。一个 FCB 就是一个文件目录项。一个文件目录也被看作是一个文件，称为目录文件。（3）索引结点（i 结点）是由除文件名外的其他文件描述信息所构成的一种数据结构。为什么要引入索引结点？ ①文件目录占用大量的盘块，检索时间长 ②在检索目录文件过程中只用到文件名种类 ①磁盘索引结点存放在外存上的索引结点。基本信息包括：文件主标识符、文件类型、文件存取权限、文件物理地址（磁盘上的地址）、文件长度、和文件存取时间等信息。 ②内存索引结点存放在内存上的索引结点。内存索引结点包含磁盘索引接点的全部信息，并增加内存索引结点编号、状态、访问计数、文件所属的逻辑设备号和链接指针等信息。（4）文件的目录结构 ①单级目录结构整个文件系统只建立一张目录表，每个文件在目录表中占有一目录项。缺点：  查找速度慢  不允许重名  不方便实现文件共享

②两级目录结构在系统中建立一个主文件目录 MFD，同时还为每个用户建立一用户文件目录 UFD。优点：  解决了文件的重名问题和文件共享问题----用户名|文件名  提高了目录检索的速度，降低查找时间缺点：增加了系统开销 ③树型目录结构（多级）在两极目录的基础上，允许用户创建自己的子目录，子目录创建自己的子目录，依次类推。优点：层次结构清晰，便于管理和保护；有利于文件分类；解决了文件的重名问题；提高了文件的检索速度；能进行存取权限的控制缺点：查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响存取速度。 4.磁盘调度（磁盘调度方法：FCFS、SSTF，SCAN）（1）先来先服务 FCFS 根据进程请求访问磁盘的先后次序进行调度。缺点：平均寻道时间长（2）最短寻道时间优先 SSTF 选择与当前磁头所在的磁道距离最近的磁盘访问请求服务。缺点：出现“饥饿”现象。（3）扫描（SCAN）算法（电梯调度算法）首先考虑磁盘请求的磁头移动方向，在方向一致的情况下选择与当前磁头最近的磁盘请求服务。若同方向没有请求，磁头转向反方向移动。寻道时间 Ts（启动磁臂时间 s+磁头移动时间） Ts=m×n+s (移动 n 条磁道) 旋转延迟时间 Tr=1\2r 传输时间 Tt =b\Rn 其中，b 为传输的字节数，N 为一条磁道上的字节数，r 为磁盘每秒的转数。 5.虚拟设备、缓冲技术、SPOOLING 系统虚拟设备操作系统使用共享设备来模拟独占设备的操作，经过操作系统虚拟技术处理后的设备称为虚拟设备。在虚拟设备环境中，一个独占设备可以允许两个或两个以上的进程并行使用，并且每个进程都感觉在独占使用该设备。缓冲技术（1）为什么要引入缓冲技术  缓和 CPU 和 I/O 设备之间速度不匹配的矛盾  减少对 CPU 的中断次数。  提高 CPU 和 I/O 设备之间的并行性（2）缓冲的种类单缓冲双缓冲循环缓冲缓冲池 SPOOLing 系统 SPOOLing 技术是实现虚拟设备以提高独占设备利用率的技术，也是一种以空间换时间的技术。 SPOOLing 技术是在批处理操作系统时代引入的，即假脱机输入输出技术。把这种技术实质就是对输入／输出数据成批处理。（1）概念 SPOOLing 技术是指在联机情况实现的同时外围操作，也称假脱机操作。它通过共享设备来模拟独占设备的动作，使独占设备成为共享设备，也称为虚拟设备技术。（2）SPOOLing 技术实现原理 SPOOLing 输入————作业预输入（输入机输入井） SPOOLing 输出————作业缓输出（输出井输出机）由 SPOOLing 程序控制通道完成

（3） SPOOLing 系统的组成 ①输入井和输出井（外存：暂存 I/O 设备传送的数据） ②输入缓冲区和输出缓冲区（内存：匹配 CPU 与磁盘之间速度不匹配的矛盾） ③输入进程和输出进程（假脱机进程）（4） SPOOLing 系统的优点与缺点优点： ①提高了 I/O 速度。用户程序对慢速独占设备的独占时间大大缩短了，提高了慢速独占设备的利用率； ②用户程序本身的执行时间大大缩短了,提高了系统吞吐量和资源的利用率。 ③使独占设备成为共享设备，实现了虚拟设备的功能。缺点：必须有高速、大容量和可随机存取的外存的支持。综合应用题 1. 多道系统、作业调度、进程调度、抢占式调度、非抢占式调度、周转时间、带权周转时间（1）概念作业调度：是指按一定的作业调度算法，从外存的后备作业队列中选择若干个作业调入主存的过程。进程调度：按一定的进程调度算法，从已在内存的进程中选择一个进程并把 CPU 分配给它的过程。作业周转时间：从作业提交进入系统到结束退出系统所经历的一段时间。平均周转时间：多道作业周转时间的平均值。系统吞吐量(吞吐率)：单位时间系统所完成的总工作量（一般用作业数表示）。（2）调度可分为三个层次：作业调度：也称高级调度或长期调度，决定每次接收多少个作业和接纳哪些作业的问题。交换调度：主要负责内外存上的进程交换。一般通过“挂起”和“解挂”的方法来实现，也称“中期调度”。进程/线程调度：将处理器分配给一个或多个进程/线程的调度方法，也称“低级调度”和“短期调度”和“处理器调度”。带权周转时间=周转时间/运行时间例 1：先来先服务调度（非抢占）在一个单道批处理系统中，一组作业的提交时刻和运行时间如下表所示，请计算其平均周转时间 T 和平均带权周转时间 W。作业提交时刻运行时间 1 2 3 4 8.0 8.5 9.0 9.1 1.0 0.5 0.2 0.1 执行次序提交时刻运行时间等待时间开始时刻完成时刻周转时间带权周转时间 1 2 3 4 8.0 8.5 9.0 9.1 1.0 0.5 0.2 0.1 0 0.5 0.5 0.6 作业平均周转时间作业平均带权周转时间例 2：若采用抢占的高优先级调度算法，进程的调度次序是什么？（假定优先数越小的作业，优先权越高。）作业提交时刻运行时间优先数 1 2 3 4 8.0 8.5 9.0 9.1 1.0 0.5 0.2 0.1 3 1 2 1 时间：8.0 作业： 1 8.5 9.0 9.1 9.2 9.3 9.8 2 3(2) 4 3(4) 1(3)(1)

例 3：短作业优先调度（短作业优先调度算法产生的平均周转时间短，系统吞吐量大。非抢占）开始时刻完成时刻周转时间带权周转时间作业提交时刻运行时间 1 2 3 4 8.0 8.5 9.0 9.1 1.0 0.5 0.2 0.1 执行次序提交时刻 1 3 4 2 8.0 9.0 9.1 8.5 运行时间 1.0 0.2 0.1 0.5 作业平均周转时间作业平均带权周转时间例 4：最短剩余时间优先调度（最短作业优先调度算法产生的平均周转时间最短，系统吞吐量最大。抢占式）开始时刻完成时刻周转时间带权周转时间作业提交时刻运行时间 1 2 3 4 8.0 8.5 9.0 9.1 1.0 0.3 0.2 0.1 执行次序提交时刻 1 3 4 2 8.0 9.0 9.1 8.5 运行时间 1.0 0.2 0.1 0.3 作业平均周转时间作业平均带权周转时间例 5：时间片轮转调度算法（是一种基于时间片的抢占式调度算法。）假定系统规定的时间片大小为 0.3，不考虑切换开销。作业提交情况如下表所示：作业提交时刻运行时间 1 2 3 4 8.0 8.1 8.2 8.3 1.0 0.5 0.2 0.1 执行次序提交时刻运行时间运行及完成时刻周转时间带权周转时间 1 2 3 4 8.0 8.0 8.0 8.0 1.0 0.5 0.2 0.1 作业平均周转时间作业平均带权周转时间例 6：高响应比调度（非抢占）响应比 Rp= 等待时间+要求服务时间 = 响应时间要求服务时间要求服务时间作业提交时刻运行时间 1 8.0 1.0 执行次序提交时刻运行时等待时间开始时刻完成时刻周转时间带权周转时间 1 2 8.0 8.5 间 1.0 0.5

2 3 4 8.5 9.0 9.1 0.5 0.2 0.1 eg1：在一个具有两道作业的批处理系统中，作业调度采用短作业优先的调度算法，进程调度采用优先数为基础的抢占式调度算法（作业优先数即为进程优先数，优先数越小优先权越高），忽略进程切换和调度开销。问题：根据下表求它们的平均周转时间。作业名到达时间运行时间优先数 A B C D 10：00 40 分钟 5 10：20 30 分钟 3 10：30 50 分钟 4 10：50 20 分钟 6 执行次序提交时刻运行时间优先数运行及完成时刻周转时间带权周转时间 A B C D 10:00 10:20 10:30 10:50 5 40 分钟 3 30 分钟 4 50 分钟 6 20 分钟作业平均周转时间作业平均带权周转时间 eg2:在某多道程序系统中，用户当前可使用的系统资源：内存空间 100K，磁带机 2 台，打印机 1 台。系统采用可变式分区分配方式管理内存，对磁带机和打印机采用静态分配方式，并假设输入输出操作的时间忽略不计。假设作业调度采用先来先服务算法，内存分配采用首次适应算法且不准移动已在内存中的作业，进程调度采用短作业优先的调度算法。作业序列情况如下表。作业号提交时间运行时间内存需求申请磁带机打印机 8：00 8：20 8：20 8：30 8：35 30 分钟 10 分钟 20 分钟 20 分钟 15 分钟 15K 30K 60K 20K 10K 1 0 1 1 1 1 1 0 0 1 1 2 3 4 5 问题：（1）求作业调度的次序，并给出每道作业进驻内存的时刻（5 分）。（2）计算每道作业的周转时间（5 分）。解：（1）（5 分）作业调度的顺序：1→3→4→2→5 进驻内存的时刻分别为：8：00，8：20，8：30， 8：50，9：00 ……(5 分) （2）（5 分）作业的周转时间=作业的完成时间 - 作业到达系统的时间。每道作业的周转时间如下：1 号作业：30（分钟） 2 号作业：40（分钟） 3 号作业：30（分钟） 4 号作业：65（分钟）

分享到：

赞收藏

资料库

安徽大学操作系统复习资料.doc

相关推荐

课程资源

热门标签

最新资料