首页  思维导图  详情

考研计算机408

2023-08-22 12:18:47   0  举报





AI智能生成

往年真题练习。易错较难题

考研

考证

作者其他创作

大纲/内容

操作系统

操作系统引论

什么是操作系统

操作系统（Operation System）,简称os,是管理计算机硬件与软件资源的计算机程序

计算机系统的构成：用户、应用程序、操作系统、硬件（裸机）

（是一种）系统软件：

1.与硬件交互 2.对资源共享进行调度管理 3.解决并发操作处理中存在的协调问题 4.数据结构复杂，外部接口多样化，便于用户反复使用

主要作用

管理与配置内存

决定系统资源供需的优先次序

控制输入设备与输出设备

操作网络与管理文件系统等基本事务

提供一个让用户与系统交互的操作界面

功能

目标

有效性（提高系统资源利用率、提高系统的吞吐量）—管理系统资源

方便性—方便用户使用

可扩充性、开放性—作为扩充机器

功能

os作为计算机系统资源的管理者

处理机管理

进程控制 进程同步 进程通信 调度

存储器管理

内存分配 内存保护 地址映射 内存扩充

I/O设备管理

缓冲管理 设备分配 设备处理

文件管理

文件存储空间的管理 目录管理 文件的读/写管理和保护

os作为用户与计算机“硬件系统”之间的接口

程序接口

命令接口

GUI（Graphical User Interface）,图形用户接口

os实现了对计算机资源的抽象

将具体的计算机硬件资源抽象成软件资源，方便用户使用

开放了简单的访问方式，隐藏了实现细节

特征

并发性（concurrence）

同一时间间隔内执行和调度多个程序的能力

并发：同一时间间隔（时间段）发生的事件数量 并行：同一时刻（时间点）发生的事件数量

特点：宏观上，处理机同时执行多道程序 微观上，处理机在多道程序间高速切换（分时交替执行） 关注单个处理机同一时间段内处理任务数量的能力

共享性（Sharing）

即资源共享，系统中的资源供多个并发执行的应用程序共同使用

同时访问方式：同一时段允许多个程序同时访问共享资源 互斥共享方式：也叫独占式，允许多个程序在同一个共享资源上独立而互不干扰的工作（共享打印机、音频设备、视频设备）

并发和共享互为存在条件： 共享性要求OS中同时运行着多道程序（若只有单道程序正在运行，则不存在共享的可能） 并发性难以避免的导致多道程序同时访问同一个资源（若多道程序无法共享部分资源，则无法并发）

虚拟（Virtual）

使用某种技术把一个物理实体变成多个逻辑上的对应物

时分复用技术（TDM，Time Division Multiplexing）        虚拟处理机技术：四核八线程        虚拟设备技术：虚拟打印机 空分复用技术（SDM，Space Division Multiplexing）        虚拟磁盘技术：将一块硬盘虚拟出若干个卷        虚拟存储器技术

异步（Asynchronism）

多道程序环境下，允许多个程序并发执行 单处理机环境下，多个程序分时交替执行

程序执行的不可预知性（获得运行的时机、因何暂停、每道程序需要多少时间、不同程序的性能，比如计算多少，I/O多少） 宏观上“一气呵成”，微观上“走走停停 ”

发展历程

手工操作阶段(此阶段无操作系统)         人工操作方式（用户独占全机、CPU等待人工操作）         脱机输入/输出方式（解决了人机矛盾、减少了CPU的空闲时间、提高了I/O速度、一次只能执行一个程序）

批处理阶段(操作系统开始出现)          单道批处理系统（OS前身；自动性、顺序性、单道性、内存中只有一道程序、CPU需要等待I/O完成）（有监视程序）        （主要解决CPU、内存和I/O设备利用率不足的问题）          多道批处理系统（提高CPU的利用率、可提高内存和I/O设备利用率、增加系统吞吐量、平均周转时间长、无人机交互）（有调度程序）      （主要解决I/O操作时CPU闲置问题）

分时操作系统

Time Sharing System:一台主机连接多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。 为什么需要分时系统：人机交互、共享主机、便于用户上机 需要解决的问题：及时接收、及时处理（作业提前进入内存，并能够与用户交互）

特征： 1.多路性：时间片轮转机制 2.独立性：用户彼此独立 3.及时性：用户能在短时间内获得相应 4.交互性：用户可以请求多种服务 缺点：作业/用户优先级相同，不能优先处理紧急任务

实时操作系统

Real Time System:系统能即时相应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行

应用需求：实时控制、实时信息处理 实时任务：周期/非周期性实时任务（根据周期性）                硬/软实时任务（根据截止时间）

与分时系统比较：多路性、独立性、及时性：以用户能接受的等待时间为准、交互性          可靠性：多级容错，保障系统和数据的安全

网络操作系统(资源共享、远程通信） 分布式操作系统（分布性、并行性） 微机操作系统...

微机操作系统的发展：单用户单任务（CP/M、MS-DOS）                                 单用户多任务（Windows1.0-XP）                                 多用户多任务（Unix os:Solaris、Linux、Mac                                                         MS-DOS:Windows 10）

推动OS发展的动力：不断提高计算机资源的利用率、方便用户、器件的不断更新换代、计算机体系结构的不断发展

结构设计

传统的操作系统结构

第一代：无结构OS（一系列过程或程序的集合，过程间可以相互调用；结构复杂且混乱，难以调试、阅读和维护）

第二代：模块化结构OS（基于“分解”和“模块化”原则；按照功能划分模块/子模块，规定模块间的接口；模块独立性标准：高内聚、低耦合）

第三代：分层式结构OS

有序分层法，自顶向下一次依赖 设计时，自底向上：每一步建立在可靠的基础上

优缺点：容易保证系统正确性；容易扩充和维护；自上而下的层次通信，导致系统效率降低

第四代：微内核OS结构

概念：1.足够小的内核，只实现OS核心功能                      与硬件处理紧密相关的部分，比如硬件处理、客户与服务器通信和其他基本功能                      一些较基本的功能                      客户和服务器之间通信（2.客户/服务器模式）           3.应用“机制与策略分离”原理           4.采用面向对象技术

优点：提高OS的可扩展性、可靠性、可移植性；支持分布式系统；融入了面向对象技术 缺点：相较早期OS，降低了一定的效率

进程管理

概念

进程，Process,是一个具有一定独立功能的程序关于某个数据集合的一次运行活动，是系统进行资源分配和调度的一个独立单位

要点：1.进程是程序的一次执行，an instance of a computer program that is being executed 2.进程是一个程序及其数据在处理机上顺序执行时所发生的的活动 3.进程是程序在一个数据集合上运行的过程 4.进程是系统进行资源分配和调度的一个独立单位（或基本单位）

进程的结构：控制块、数据段、程序段

进程的特征

动态性：由创建而生，由撤销而亡 并发性：多个进程同时运行 独立性：独立资源分配 异步性：相互独立、互不干扰

线程

Thread,进程的轻型实体，也叫“轻量级进程”，是一系列活动按事先设定好的顺序依次执行的过程，是一系列指令的集合 是一条执行路径，不能单独存在，必须包含在进程中 线程是OS中运算调度的最小单位

引入线程的原因：提高OS的并发性

线程的属性： ①轻型实体。它不拥有系统资源，只是有一点必不可少的、能保证独立运行的资源。 ②独立调度和分派的基本单位。在多线程OS中，线程是独立运行的基本单位，因而也是独立调度和分派的基本单位，但由于线程很轻，故线程的切换非常迅速且开销小。 ③可并发执行。在一个进程中的多个线程之间可以并发执行，甚至允许在一个进程中的所有线程都能并发执行；同样，不同进程中的线程也能并发执行。 ④共享进程资源。

进程和线程的区别 概念加区别

调度：线程是独立调度的最小单位，进程是资源分配的基本单位 拥有资源：进程拥有资源，线程共享同一进程内的资源 并发性：进程有上限，受限于资源和空间的大小，线程几乎无上限 系统开销：进程开销大，线程开销小 地址空间和其他资源：进程的地址空间相互独立，同一进程间线程共享地址空间和资源 通信：进程间通信需要通过同步或互斥等手段，同一进程间线程共享信息，通信方便 线程相对于进程，大大降低了创建、撤销和切换可执行实体的成本和难度

线程的实现方式

用户级线程（ULT） User Level Thread

内核级线程（KLT） Kernel Level Thread

运行机制

进程的状态

三种基本状态

就绪（Ready） 执行（Running） 阻塞（Blocked）

两种特殊状态

创建（New） 终止（Terminated）

终止三种情况：正常结束、异常结束、被外界干预结束

进程控制

即OS对进程实现有效的管理，包括创建新进程、撤销已有进程、挂起、阻塞和唤醒、进程切换等多种操作。OS通过原语（Primitive）操作实现进程控制

原语

原语：由若干条指令组成，完成特定的功能，是一种原子操作（Action Operation） 特点：1.原子操作，要么全做，要么全不做，执行过程不会被中断 2.在管态/系统态/内核态下执行，常驻内存 3.是内核三大支撑功能（中断处理/时钟管理/原语操作）之一

进程控制： 创建原语：create 阻塞原语：block 唤醒原语：wakeup 撤销原语：destroy

进程控制（为了系统和用户观察和分析进程） 挂起原语：suspend        静止就绪：放外存，不调度        静止阻塞：等待事件 激活原语：active        活动就绪：等待调度        活动阻塞：等待唤醒

进程调度 （处理机调度）

概念：根据一定的算法和原则将处理机资源进行重新分配的过程 前提：作业/进程数远远大于处理机数 目的：提高资源利用率，减少处理机空闲时间 调度程序：一方面要满足特定系统用户的需求（快速响应），另一方面要考虑系统整体效率（系统平均周转时间）和调度算法本身的开销

调度的层次

高级调度/作业调度

把后备作业调入内存 只调入一次，调出一次

中级调度/内存调度

将进程调至外存，条件合适再调入内存 在内、外存对换区进行进程对换

低级调度/进程调度

从就绪队列选取进程分配给处理机 最基本的调度，频率非常高（相当于一个时间片完成）

调度的层次

调度方式

剥夺式/抢占式调度

立即暂停当前进程 分配处理机给另一个进程 原则：优先权/短进程优先/时间片原则

非剥夺/非抢占式调度

若有进程请求执行 等待直到当前进程完成或阻塞 缺点：适用于批处理系统，不适用分时/实时系统

调度时机

进程运行完毕 进程时间片用完 进程要求I/O操作 执行某种原语操作 高优先级进程申请运行（剥夺式调度）

调度过程

1.保存镜像：记录进程现场信息 2.调度算法：确定分配处理机的原则 3.进程切换：分配处理机给其它进程 4.处理机回收：从进程收回处理机

调度算法指标

调度算法

先来先服务（FCFS,First Come First Served）

算法内容：调度作业/就绪队列中最先入队者，等待操作完成或阻塞 算法原则：按作业/进程到达顺序服务（执行） 调度方式：非抢占式调度 适用场景：作业/进程调度 优缺点：有利于CPU繁忙型作业，充分利用CPU资源             不利于I/O繁忙型作业，操作耗时，其它饥饿

短作业优先（SJF，Shortest Job First）

算法内容：所需服务时间最短的作业/进程优先服务（执行） 算法原则：追求最少的平均（带权）周转时间 调度方式：SJF/SPF非抢占式 适用场景：作业/进程调度 优缺点：平均等待/周转时间最少             长作业周转时间会增加或饥饿             估计时间不准确，不能保证紧迫任务及时处理

高响应比优先调度（HRRN，Highest Response Ratio Next）

算法内容：结合FCFS和SJF，综合考虑等待时间和服务时间计算响应比，高的优先调度 算法原则：综合考虑作业/进程的等待时间和服务时间 调度方式：非抢占式 适用场景：作业/进程调度 响应比计算：             响应比=（等待时间+服务时间）/服务时间，≥1             只有当前进程放弃执行权（完成/阻塞）时，重新计算所有进程响应比             长作业等待越久响应比越高，更容易获得处理机

优先级调度（PSA，Priority-Scheduling Algorithm）

算法内容：又叫优先权调度，按作业/进程的优先级（紧迫程度）进行调度 算法原则：优先级最高（最紧迫）的作业/进程先调度 调度方式：抢占/非抢占式（并不能获得及时执行 适用场景：作业/进程调度 优先级设置原则：             静态/动态优先级             系统>用户；交互型>非交互型；I/O型>计算型             低优先级进程可能会产生饥饿

时间片轮转调度（RR，Round-Robin）

算法内容：按进程到达就绪队列的顺序，轮流分配一个时间片去执行，时间用完则剥夺 算法原则：公平、轮流为每个进程服务，进程在一定时间内都能得到响应 调度方式：抢占式，由时钟中断确定时间到 适用场景：进程调度 优缺点：             公平，响应快，适用于分时系统             时间片决定因素：系统响应时间、就绪队列进程数量、系统处理能力             时间片太大，相当于FCFS;太小，处理机切换频繁，开销增大

多级反馈队列调度（MFQ，Multileveled Feedback Queue）

算法内容：设置多个按优先级顺序的就绪队列                  优先级从高到低，时间片从小到大                  新进程采用队列降级法                              进入第一级队列，按FCFS分时间片                              没有执行完，移到第二级，第三级……                  前面队列不为空，不执行后续队列进程 算法原则：集前几种算法优点，相当于PSA+RR 调度方式：抢占式 适用场景：进程调度 优缺点：             对各类型相对公平；快速响应             终端型作业用户：短作业优先             批处理作业用户：周转时间短             长批处理作业用户：在前几个队列部分执行

进程间协作

进程通信

概念：进程通信即进程间的信息交换         进程是资源分配的基本单位，各进程内存空间彼此独立         一个进程不能随意访问其他进程的地址空间

特点

共享存储 Shared-Memory

缺点：数据收发双方不可见，存在安全隐患

基于共享数据结构的通信方式          多个进程共用某个数据结构（OS提供并控制）          由用户（程序员）负责同步处理          低级通信：可以传递少量数据，效率低

基于共享存储区的通信方式         多个进程共用内存中的一块存储区域         由进程控制数据的形式和方式         高级通信：可以传递大量数据，效率高

消息传递 Message-Passing

直接通信：点到点发送         发送和接收时指明双方进程的ID         每个进程维护一个消息缓冲队列

间接通信：广播信箱         以信箱为媒介，作为中间实体         发进程将消息发送到信箱，收进程从信箱读取         可以广播，容易建立双向通信链

多处理机系统、分布式系统、计算机网络系统等。应用多

管道通信 Pipe

管道        用于连接读/写进程的共享文件，pipe文件        本质是内存中固定大小的缓冲区

半双工通信        同一时段只能单向通信，双工通信需要两个管道        以先进先出（FIFO）方式组织数据传输        通过系统调用read() /write()函数进行读写操作

进程同步

概念：协调进程间的相互制约关系，使它们按照预期的方式执行的过程 前提：      进程是并发执行的，进程间存在着相互制约关系                 并发的进程对系统共享资源进行竞争                 进程通信，过程中相互发送的信号称为消息或事件 两种相互制约形式            间接相互制约关系（互斥）：进程排他性地访问共享资源            直接相互制约关系（同步）：进程间的合作，比如管道通信

互斥的访问临界资源

访问过程：1.进入区：尝试进入临界区，成功则加锁（lock）                  2.临界区：访问共享资源                  3.退出区：解锁（unlock）,唤醒其它阻塞进程                 4.剩余区：其它代码

访问原则：空闲让进：临界区空闲，允许一个进程进入                 忙则等待：临界区已有进程，其它进程等待（阻塞状态）                 有限等待：处于等待的进程，等待时间有限                 让权等待：等待时应让出CPU执行权，防止“忙等待”

软件实现方法：

单标志法：违背“空闲让进”

双标志法先检查：违背“忙则等待”

双标志法后检查：违背“空闲让进”、“有限等待”

皮特森算法（Peterson's Algorithm）：违背“让权等待”，会发生“忙等”

硬件实现方法

中断屏蔽方法：关中断/开中断

禁止一切中断，CPU执行完临界区之前不会切换 关中断可能会被滥用 关中断时间长影响效率 不适用于多处理机，无法防止其它处理机调度其它进程访问临界区 只适用于内核进程（该指令运行在内核态）

Test-And-Set(TS指令/TSL指令

读出标志并设置为true，返回旧值，原子操作 也被称作TSL指令（Test-And-Set-Lock） 违背“让权等待”，会发生忙等

Swap指令（EXCHANGE、XCHG）指令

交换两个变量的值，原子操作 违背“让权等待”

信号量（Semaphore)机制

PV操作       P操作：wait原语，进程等待       V操作：signal原语，唤醒等待进程

整型信号量：违背“让权等待”，会发生忙等

记录型型号量：进程进入阻塞状态，不会忙等

子主题

管程（Monitor，监视器）

概念：“管理进程”，即用于实现进程同步的工具。是由代表共享资源的数据结构和一组过程（进行PV操作的函数）组成的管理程序（封装）。

组成：  管程名称            局部于管程内部的共享数据结构            对该数据结构操作的一组过程（函数）            管程内共享数据的初始化语句

管程的基本特性：是一个模块化的基本程序单位，可以单独编译                           是一种抽象数据类型，包含数据和操作                           信息掩蔽，共享数据只能被管程内的过程访问

条件变量/条件对象：进入管程的进程可能由于条件不满足而阻塞                       此时进程应释放管程以便其他进程调用管程                    进程被阻塞的条件（原因）有多个，移入不同的条件队列                 进程被移入条件队列后，应释放管程

死锁

死锁：多个进程由于竞争资源而造成的阻塞现象，若无外力作用，这些进程将无法继续推进 饥饿：等待时间过长以至于给进程推进和响应带来明显影响，“饿而不死”

死锁产生的原因：系统资源的竞争                           进程推进顺序非法

死锁产生的必要条件： 互斥条件：共享资源的排他性访问 不剥夺条件：访问时该共享资源不会被剥夺 请求并保持条件：保持当前资源时请求另一个资源 循环等待条件：存在共享资源的循环等待链

死锁的处理策略

死锁预防

破坏互斥条件：将只能互斥访问的资源改为同时共享访问              将独占锁改为共享锁            不是所有资源都能改成可共享的

破坏不剥夺/不可抢占条件：请求新资源无法满足时必须释放已有资源               由OS协助强制剥夺某进程持有的资源               实现复杂，代价高               此操作过多导致原进程任务无法推进

破坏请求并保持条件：进程开始运行时一次性申请所需资源（资源浪费、进程饥饿）                                    阶段性请求和释放资源

破坏循环等待条件：对所有资源现行排序，按序号请求资源（请求时先低再高，释放时先高再低）                        对资源的编号应相对稳定，限制了新设备增加                       进程使用资源的顺序可能与系统编号顺序不同                        限制了用户编程

死锁避免

安全性算法

系统安全状态：安全状态一定不会出现死锁                  不安全状态可能出现死锁

银行家算法：系统预判进程请求是否导致不安全状态                是则拒绝请求，否则答应请求

死锁的检测与解除

死锁检测：需要一种数据结构，保存有关资源的请求和分配信息                  提供一种算法，利用这些信息检测是否形成了死锁

资源分配图（G=(N,E)）:        两种资源        两种节点

死锁定理（死锁状态的充分条件）:          当且仅当此状态下资源分配图是不可完全简化的          简化过程类似于“拓扑排序”算法（注意数据结构考察）

死锁解除：资源剥夺：挂起死锁进程、剥夺其资源、将资源分配给其它（死锁）进程                  撤销进程                  进程回退：回退到足以避免死锁的地步、需要记录进程历史信息，设置还原点

内存管理

存储器的多层结构

寄存器 高速缓存 主存储器 硬盘缓存 固定磁盘 可移动存储介质

进程运行的基本原理

用户程序→进程：编译、链接、装入

程序的链接：静态链接、装入时动态链接、运行时动态链接

程序的装入：绝对装入、可重定位装入、动态运行时装入 两个细节：逻辑地址与物理地址、内存保护

内存扩充的两种方式：覆盖、交换

内存管理方式

内容：1.对内存的分配与回收  2.从逻辑上对内存空间进行扩充 3.用户进程中的逻辑地址和物理内存中的物理地址进行高速转换

连续分配管理方式

单一连续分配： <ul><li>优点：实现简单；无外部碎片；不一定需要内存保护 缺点：只能用于单用户、单任务OS；有内部碎片；存储器利用率低；</li></ul>

固定分区分配：            优点：实现简单；无外部碎片           缺点：1.较大用户程序时，需要采用覆盖技术，降低了性能；                      2.会产生内部碎片，利用率低

子主题

动态分区分配

动态分区分配

怎么记录内存的使用情况

选择哪个分区给新进程

首次适应算法：从低地址查找合适空间（按地址递增排列 最佳适应算法：优先使用最小空闲空间 最坏适应算法：优先使用最大连续空间 临近适应算法：从上次查找处向后查找

已使用的分区怎么回收

回收后相邻空间要合并；更新空闲分区表和/或空闲分区链记录

优点：根据进程大小动态分配内存空间，没有内部碎片 缺点：有外部碎片

非连续分配管理方式

基本分页存储管理方式： 页/页面、页框、块 页表 基本地址变换机构

将内存分为大小相等的分区: 页框/页帧/内存块/物理块；4k-2M之间 页框号/页号从0开始； OS以页框为基本单位分配内存

子主题

基本地址变换机构： 物理地址=（页号→块号）+偏移量 页号P=逻辑地址A/页面长度（大小）L 偏移量W=逻辑地址A%页面长度L P=A>>12;W=A&4095

页式管理中地址空间是一维的 每次访存都需要地址转换，必须足够快 页表不能太大，会降低内存利用率

子主题

具有快表的地址变换机构： 1.直接将页号与快表页号比较 2.匹配成功，取块号+偏移量形成地址 3.匹配失败，访问主存页表，并同步到快表（局部性原理

快表命中率在百分之90以上

两级页表： 1.页表连续存放，占用大量连续空间 2.一段时间内只需要访问部分特定页面 3.页表项分组/分页离散存储 4.建页目录表管理离散页表

最多2^20个页表项。。一个块号占4Byte，即32位。。 一个页框占2^12字节（4k=4*2的10次方）。。即一个页表需要占用4兆

两级页表

两级页表地址转换 1.将逻辑地址拆分成三部分 2.从PCB中读取页目录表始址 3.根据一级页号查出二级页表位置 4.根据二级页号查内存块号，加偏移量计算物理地址

基本分段存储管理方式

把用户进程的自然段按照逻辑划分

子主题

过程：分段、段表、地址变换机构、段的共享与保护

分页与分段方式对比：页→物理单位；段→逻辑单位                    分页→一维地址空间；分段→二维地址空间                    分段更容易信息共享和保护

子主题

段页式管理方式

1.先分段，再分页 2.1个进程→1个段表 3.1个段表项→1个页表 4.1个页表→多个物理块

子主题

地址转换 1.段表始址+段号找到段表项 2.根据页表长度检查页号越界情况 3.页表地址+页号找到页表项 4.内存块号+页内地址得到物理地址

子主题

虚拟内存管理

概念

具有请求调入和置换功能，从逻辑上对内存容量加以扩充的一种存储器系统 局部性原理：时间局部性、空间局部性 虚拟内存的特征：多次性、对换性、虚拟性

虚拟内存的实现： 请求分页存储管理 请求分段存储管理 请求段页式存储管理

所需要的硬件支持：页表/段表机制作为主要数据结构、地址变换机构、一定容量的内存和外村、中断机构

请求分页管理方式之 页表机制：状态位P          访问字段A          修改位M          外存地址 缺页中断机构 地址变换机构

基本分页与请求分页区别

请求分页管理方式之 缺页中断机构

缺页中断（内部中断，cpu产生的） 有空闲块：直接调入数据到空闲块 无空闲块：由页面置换算法选择淘汰。若修改位为1（修改过），需要对原数据进行相关覆盖

内中断（CPU内部）：陷入、故障、终止 外中断（CPU外部）：I/O中断请求、人工干预

子主题

请求分页管理方式之 地址变换机构

1.请求调页，判断是否在内存 2.可能需要页面置换 3.新增/修改页表项 4.热点表项同步到快表

子主题

页面置换算法

最佳置换算法（OPT）

保障最低缺页率：每次选择淘汰最不可能再次被使用的页面，无法实现

先进先出置换算法（FIFO）

保障顺序上的公平：每次选择淘汰最早进入内存的页面，Belady异常，性能差

最近最久置换算法（LRU）

保障时间和距离上的公平：每次选择淘汰最久最近未使用的页面，需要硬件支持，开销大

子主题

时钟置换算法（NRU）

保障性能和开销均衡：为页面设置访问为（0/1），并链接成循环队列， 进程访问页面后置为1.淘汰时为1置为0并跳过，为0时淘汰。最多需要两轮扫描

子主题

改进型时钟置换算法

额外考虑是否修改，保障最少I/O操作： 增加修改为（0/1),第一轮找（0,0），第二轮找（1,0）并修改访问为为0， 第三轮找（0，0），第四轮找（0,1）

子主题

页面分配策略

驻留集（驻留在主存中页面数）大小 驻留集包含工作集

分配空间小，进程数量多，CPU时间利用效率就高 进程在主存中页数少，错页率就高 进程在主存中页数多，错页率并无明显改善

页面分配策略

固定分配局部置换 可变分配全局置换 可变分配局部置换

调入页面的时机

预调页策略： 一次性调入若干相邻页面 多用于进程首次调入

子主题

请求调页策略： 运行时发现缺页时调入 I/O开销较大

从何处调页

系统拥有足够的对换区空间 系统缺少足够的对换区空间 UNIX方式

子主题

文件管理

文件系统基础

文件概念

定义：以计算机硬盘为载体的存储在计算机上的信息集合 属性：描述文件状态的一组信息，比如名称、标识符、类型、大小、位置、保护、时间、日期和用户标识等 基本操作：创建文件；读文件；写文件；文件重定位（寻址）；删除文件；截断文件； 打开与关闭

文件的结构

文件的逻辑结构

无结构文件（流式文件）：（文本文档，图片等）        以字节（Byte)为单位        没有具体结构        采用穷举方式搜索

有结构文件（记录式文件）：（电子表格等）关键字         顺序文件(可变长文件（无法快速定位第i个记录）/定长文件（无法快速增删记录））         索引文件（索引表是一个定长记录的顺序文件，一个索引一个记录）可以快速定位，又可以实现变长         索引顺序文件（一个索引表项对应一组记录）         直接文件或散列文件（Hash File)

文件的物理结构

文件控制块（FCB）：       基本信息       存取控制信息       使用信息

子主题

索引节点

将表瘦身。在磁盘称为为磁盘索引节点。在内存称为内存索引节点

目录结构

蓝色文件。黄色目录

有向无环图

文件共享和保护

文件共享：        硬链接（索引节点）        软链接（符号链）

硬链接：索引节点共享（配合计数器）

软链接：创建一个link型文件指向所需访问的文件，删除link对源文件无影响

文件保护（控制文件的访问权限）：           口令保护           加密保护           访问控制

子主题

文件系统实现

文件系统层次结构

用户调用接口 文件目录系统 存取控制验证模块 逻辑文件系统与文件信息缓冲区 物理文件系统 辅助分配模块 设备管理程序模块

子主题

目录实现

线性列表（链表或数组）

哈希表（避免哈希冲突）

文件实现

文件分配方式

连续分配（支持顺序和直接访问，速度快；不方便拓展，会产生磁盘碎片） 链接分配（隐式链接：支持顺序访问，方便拓展，没有碎片；不支持直接访问，效率低                  显式链接：支持顺序访问、随机访问，效率高；无外部碎片，方便拓展；占用了内存额外空间）                  隐式链接，链接信息隐藏在数据块中，读取数据后才知道下一个链接块；                  显式链接；由FAT（文件分配表）记录下一个块号，每个磁盘都有一个FAT常驻内存 索引分配：为每一个文件建立一个索引表，所有索引表占一个页块，在索引块表中记录物理块号。可设置一级索引、二级索引

一个索引占4字节，一个页块4k，则一个索引表可以存放1024个索引项。则一个由二级索引存储的文件不能大于4GB

文件存储空间管理

1.目录区：存放文件目录信息（FCB）、磁盘空间管理信息 2.文件区：存放文件数据 将物理磁盘划分成一个个文件卷，也叫逻辑卷、逻辑盘

四种管理方法

空闲表法

由空闲盘块表记录空闲块的信息。多用于连续分配，会产生外部碎片

空闲链表法

单个块想连

区域里可能有多个块

空闲块示意图

成组链接法

1.第一组连续的空闲扇区（超级块），系统启动时载入内存 2.特殊值-1表示后续无分组 3.分配过程：检查并尝试分配第一个分组的空闲块；                     修改第一个分组和超级块记录   回收过程：将新的空闲块号记录到超级块和第一个分组；                    若第一个分组已满，让新的空闲块成为新建分组

位示图法

由计算机字长决定。比如32位，64位。横向为字长，纵向为字号

输入输出管理

I/O管理概述

I/O设备的基本概念

I/O就是输入/输出，将数据输入到计算机，或接收计算机的数据输出到外部设备

分类：按使用特性：人机交互类外部设备、存储设备、网络通信设备            按传输速率：低速设备（键盘，鼠标）、中速设备（打印机）、高速设备（磁盘，内存，高速缓冲器）            按信息交换单位：块设备（磁盘）、字符设备（键盘，鼠标）

I/O设备的构成：        机械部件：比如键盘设备的按键和按钮，用来执行具体的I/O操作         电子部件：即I/O控制器、设备控制器，是CPU与硬件设备之间的桥梁

I/O控制器主要作用：接收并识别CPU命令、向CPU报告设备状态、数据交换、地址识别

I/O控制器

I/O控制器组成

CPU与控制器间的接口 I/O逻辑 控制器与设备间的接口

子主题

I/O控制方式

程序直接控制方式

CPU频繁干预 每次读/写一个字 读：设备→CPU→内存

优缺点：实现简单，读/写后轮询状态寄存器； CPU和IO设备串行，忙等

子主题

中断驱动方式

CPU将此IO进程阻塞 IO前后CPU干预 每次读/写一个字 读：设备→CPU→内存

优缺点：CPU和IO设备可以并行   频繁中断耗时

子主题

DMA方式 （Direct  Memory  Access） 直接存储器访问

传输单位是“块" 块之间传输需要CPU干预 设备<->内存

优缺点：CPU和IO设备可以并行；  每个IO指令操作一个块，离散块需要频繁中断

DR（Data   Register 数据寄存器   ）           DC（Data   Counter数据计数器）   MAR（ Memory  Address  Register  内存地址寄存器)                    CR（Control  Register  控制寄存器）

通道控制方式

（是一个硬件） 通道是专门负责I/O的处理机 每次读/写一组数据块 IO设备<->内存

优缺点：CPU和IO设备可以并行 实现复杂，需要硬件支持

子主题

I/O软件层次结构

OS内核即下面的“OS核心子系统”

用户层软件

实现用户交互接口 通过库函数实现系统调用

设备独立性软件

向上一层提供调用接口 设备保护 容错处理 设备分配与回收 数据缓冲区管理 逻辑设备与物理设备映射（逻辑设备表）

设备驱动程序

不同设备硬件特性不同，但CPU指令相同 负责控制硬件设备，将CPU指令转成设备操作 驱动程序会以独立进程的形式存在

中断处理程序

IO完成后发出中断信号 执行中断处理程序 会直接操作硬件

硬件

I/O核心子系统 I/O设备的分配与回收

I/O子系统概述

I/O调度：用算法确定一个顺序来执行I/O请求（由设备独立性软件来确定）

设备保护

SPOOLing技术（假脱机技术）

用软件模拟脱机状态，用来匹配输入输出的速率差

输入井和输出井

输入进程和输出进程

输入缓冲区和输出缓冲区

I/O设备分配与回收

设备分配应考虑的因素

固有属性 分配算法 安全性

静态分配与动态分配

进程运行前分配所有资源，还是运行中动态申请资源

设备管理中的数据结构

设备类型代表逻辑设备名。（逻辑设备表）   设备标识符代表唯一物理设备

设备分配步骤

1.根据物理设备名查SDT 2.查DCT，尝试分配给进程 3.查COCT，尝试分配给进程 4.查CHCT，尝试分配给进程

缓冲区管理

为缓解CPU和IO设备间速度不匹配的矛盾而建立的临时存储区域 1.缓和CPU和IO设备速度不匹配的矛盾 2.减少CPU中断的频率，放宽对CPU相应时间的限制 3.解决数据粒度不匹配的问题 4.提高CPU与IO设备的并行性

子主题

管理策略

单缓冲

非空不写 未满不读

处理一个块所需时间T+M或C+M（取决于T和C谁大）          T和C可以并行

双缓冲

处理一个块所需时间T或C+M（取最大结果）

循环缓冲

子主题

缓冲池

空缓冲队列 满输入缓冲队列 满输出缓冲队列

子主题

计算机组成原理

父主题

子主题

父主题

子主题

控制器的设计之微程序设计

数据结构

计算机网络

考试真题

09-14

子主题

09-17

子主题

09-18

子主题

09-20

子主题

09-22

子主题

09-34

09-35

子主题

9-36

子主题

09-39

子主题

09-04

子主题

09-05

子主题

10-04

子主题

10-05

子主题

10-07

子主题

10-08

子主题

10-09

子主题

10-10

子主题

10-24

子主题

10-28

子主题

10-29

子主题

10-30

10-32

子主题

10-34

子主题

10-35

子主题

10-36

子主题

10-39

子主题

10-40

子主题

10-12

子主题

10-13

子主题

10-14

子主题

10-15

子主题

10-16

子主题

random access memory随机访问存储器        read only memory只读存储器   

10-17

子主题

10-18

子主题

10-19

子主题

10-20

子主题

10-21

子主题

10-22

子主题

11-01

子主题

11-02

子主题

11-04

子主题

11-06

子主题

11-07

子主题

11-08

子主题

11-09

子主题

11-26

子主题

11-28

子主题

11-29

子主题

11-30

子主题

11-32

子主题

11-33

子主题

11-34

子主题

11-35

子主题

11-36

子主题

11-39

子主题

11-40

子主题

11-11

子主题

11-12

子主题

11-13

子主题

11-15

子主题

11-16

子主题

11-17

子主题

11-18

子主题

11-19

子主题

11-20

子主题

11-21

子主题

11-22

子主题

12-02

子主题

12-04

子主题

12-05

子主题

12-06

子主题

12-07

子主题

12-08

子主题

12-10

子主题

12-12

子主题

12-13

子主题

12-14

子主题

12-15

子主题

12-18

子主题

12-19

子主题

12-23

12-24

子主题

12-25

子主题

12-28

子主题

12-30

子主题

12-31

子主题

12-32

子主题

12-33

子主题

12-34

子主题

12-35

子主题

12-36

子主题

12-37

子主题

12-39

子主题

13-12

子主题

13-14

子主题

13-17

子主题

13-18

子主题

13-21

子主题

13-02

子主题

13-04

子主题

13-07

子主题

13-08

子主题

13-09

子主题

13-11

子主题

13-25

设备驱动找物理地址

13-26

一个文件只需要一个索引节点。所以与索引节点总数无关

13-27

系统缓冲区同时只能进一个数据块

13-28

子主题

13-30

子主题

13-31

A避免死锁    C说反了，后推前         D没有破坏，，，条件

13-33

子主题

13-34

子主题

13-37

HDLC发现五个1则在后面加0发送，，接收方收到后逢五个1减0

13-38

子主题

13-39

子主题

14-05

子主题

14-06

子主题

14-07

子主题

14-08

子主题

14-09

子主题

14-10

子主题

14-11

子主题

14-12

子主题

14-13

子主题

14-15

子主题

14-17

子主题

14-18

子主题

14-19

子主题

14-20

子主题

14-22

子主题

14-24

子主题

14-26

子主题

14-27

子主题

14-29

子主题

14-30

子主题

14-31

读进程只能一个，写进程可以多个      D错

14-34

子主题

14-35

子主题

14-36

子主题

14-37

子主题

14-38

子主题

14-40

子主题

考试真题大题

09-1

子主题

09-2

子主题

09-3

子主题

09-4

子主题

09-5

子主题

09-6

子主题

09-7

子主题

10-1

子主题

10-2

子主题

10-3

子主题

10-4

子主题

10-5

子主题

10-6

子主题

10-7

子主题

11-1

子主题

11-2

子主题

11-3

子主题

11-4

子主题

11-5

子主题

11-6

子主题

11-7

子主题

12-01

子主题

12-02

子主题

12-03

子主题

12-04

子主题

12-05

子主题

12-06

子主题

12-07

子主题

13-02

子主题

13-03

子主题

13-04

子主题

13-05

子主题

13-06

子主题

13-07

子主题

14-02

子主题

14-04

子主题

14-04

子主题

14-05

子主题

14-06

子主题

14-07

子主题

 收藏

立即使用

高中信息技术教资

 收藏

立即使用

考研计算机408

 收藏

立即使用

我的教育知识与能力（中学版）

小镇做题家

职业：暂无

去主页





0 条评论

下一页

为你推荐

查看更多

