考研计算机408
2023-08-22 12:18:47 0 举报AI智能生成
往年真题练习。易错较难题
作者其他创作
大纲/内容
计算机系统的构成：用户、应用程序、操作系统、硬件（裸机）
1.与硬件交互2.对资源共享进行调度管理3.解决并发操作处理中存在的协调问题4.数据结构复杂，外部接口多样化，便于用户反复使用
（是一种）系统软件：
管理与配置内存
决定系统资源供需的优先次序
控制输入设备与输出设备
操作网络与管理文件系统等基本事务
提供一个让用户与系统交互的操作界面
主要作用
什么是操作系统
有效性（提高系统资源利用率、提高系统的吞吐量）—管理系统资源
方便性—方便用户使用
可扩充性、开放性—作为扩充机器
目标
进程控制进程同步进程通信调度
处理机管理
内存分配内存保护地址映射内存扩充
存储器管理
缓冲管理设备分配设备处理
I/O设备管理
文件存储空间的管理目录管理文件的读/写管理和保护
文件管理
os作为计算机系统资源的管理者
程序接口
命令接口
os作为用户与计算机“硬件系统”之间的接口
将具体的计算机硬件资源抽象成软件资源，方便用户使用
开放了简单的访问方式，隐藏了实现细节
os实现了对计算机资源的抽象
功能
并发：同一时间间隔（时间段）发生的事件数量并行：同一时刻（时间点）发生的事件数量
同一时间间隔内执行和调度多个程序的能力
特点：宏观上，处理机同时执行多道程序微观上，处理机在多道程序间高速切换（分时交替执行）关注单个处理机同一时间段内处理任务数量的能力
并发性（concurrence）
即资源共享，系统中的资源供多个并发执行的应用程序共同使用
同时访问方式：同一时段允许多个程序同时访问共享资源互斥共享方式：也叫独占式，允许多个程序在同一个共享资源上独立而互不干扰的工作（共享打印机、音频设备、视频设备）
并发和共享互为存在条件：共享性要求OS中同时运行着多道程序（若只有单道程序正在运行，则不存在共享的可能）并发性难以避免的导致多道程序同时访问同一个资源（若多道程序无法共享部分资源，则无法并发）
共享性（Sharing）
使用某种技术把一个物理实体变成多个逻辑上的对应物
时分复用技术（TDM，Time Division Multiplexing） 虚拟处理机技术：四核八线程 虚拟设备技术：虚拟打印机空分复用技术（SDM，Space Division Multiplexing） 虚拟磁盘技术：将一块硬盘虚拟出若干个卷 虚拟存储器技术
虚拟（Virtual）
多道程序环境下，允许多个程序并发执行单处理机环境下，多个程序分时交替执行
程序执行的不可预知性（获得运行的时机、因何暂停、每道程序需要多少时间、不同程序的性能，比如计算多少，I/O多少）宏观上“一气呵成”，微观上“走走停停 ”
异步（Asynchronism）
特征
手工操作阶段(此阶段无操作系统) 人工操作方式（用户独占全机、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
传统的操作系统结构
概念：1.足够小的内核，只实现OS核心功能 与硬件处理紧密相关的部分，比如硬件处理、客户与服务器通信和其他基本功能 一些较基本的功能 客户和服务器之间通信（2.客户/服务器模式） 3.应用“机制与策略分离”原理 4.采用面向对象技术
优点：提高OS的可扩展性、可靠性、可移植性；支持分布式系统；融入了面向对象技术缺点：相较早期OS，降低了一定的效率
第四代：微内核OS结构
结构设计
操作系统引论
要点：1.进程是程序的一次执行，an instance of a computer program that is being executed2.进程是一个程序及其数据在处理机上顺序执行时所发生的的活动3.进程是程序在一个数据集合上运行的过程4.进程是系统进行资源分配和调度的一个独立单位（或基本单位）
进程的结构：控制块、数据段、程序段
动态性：由创建而生，由撤销而亡并发性：多个进程同时运行独立性：独立资源分配异步性：相互独立、互不干扰
进程的特征
引入线程的原因：提高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.处理机回收：从进程收回处理机
调度过程
调度算法指标
算法内容：调度作业/就绪队列中最先入队者，等待操作完成或阻塞算法原则：按作业/进程到达顺序服务（执行）调度方式：非抢占式调度适用场景：作业/进程调度优缺点：有利于CPU繁忙型作业，充分利用CPU资源 不利于I/O繁忙型作业，操作耗时，其它饥饿
算法内容：所需服务时间最短的作业/进程优先服务（执行）算法原则：追求最少的平均（带权）周转时间调度方式：SJF/SPF非抢占式适用场景：作业/进程调度优缺点：平均等待/周转时间最少 长作业周转时间会增加或饥饿 估计时间不准确，不能保证紧迫任务及时处理
短作业优先（SJF，Shortest Job First）
算法内容：结合FCFS和SJF，综合考虑等待时间和服务时间计算响应比，高的优先调度算法原则：综合考虑作业/进程的等待时间和服务时间调度方式：非抢占式适用场景：作业/进程调度响应比计算： 响应比=（等待时间+服务时间）/服务时间，≥1 只有当前进程放弃执行权（完成/阻塞）时，重新计算所有进程响应比 长作业等待越久响应比越高，更容易获得处理机
高响应比优先调度（HRRN，Highest Response Ratio Next）
算法内容：又叫优先权调度，按作业/进程的优先级（紧迫程度）进行调度算法原则：优先级最高（最紧迫）的作业/进程先调度调度方式：抢占/非抢占式（并不能获得及时执行适用场景：作业/进程调度优先级设置原则： 静态/动态优先级 系统>用户；交互型>非交互型；I/O型>计算型 低优先级进程可能会产生饥饿
优先级调度（PSA，Priority-Scheduling Algorithm）
算法内容：按进程到达就绪队列的顺序，轮流分配一个时间片去执行，时间用完则剥夺算法原则：公平、轮流为每个进程服务，进程在一定时间内都能得到响应调度方式：抢占式，由时钟中断确定时间到适用场景：进程调度优缺点： 公平，响应快，适用于分时系统 时间片决定因素：系统响应时间、就绪队列进程数量、系统处理能力 时间片太大，相当于FCFS;太小，处理机切换频繁，开销增大
时间片轮转调度（RR，Round-Robin）
算法内容：设置多个按优先级顺序的就绪队列 优先级从高到低，时间片从小到大 新进程采用队列降级法 进入第一级队列，按FCFS分时间片 没有执行完，移到第二级，第三级…… 前面队列不为空，不执行后续队列进程算法原则：集前几种算法优点，相当于PSA+RR调度方式：抢占式适用场景：进程调度优缺点： 对各类型相对公平；快速响应 终端型作业用户：短作业优先 批处理作业用户：周转时间短 长批处理作业用户：在前几个队列部分执行
多级反馈队列调度（MFQ，Multileveled Feedback Queue）
调度算法
进程调度（处理机调度）
运行机制
概念：进程通信即进程间的信息交换 进程是资源分配的基本单位，各进程内存空间彼此独立 一个进程不能随意访问其他进程的地址空间
基于共享数据结构的通信方式 多个进程共用某个数据结构（OS提供并控制） 由用户（程序员）负责同步处理 低级通信：可以传递少量数据，效率低
基于共享存储区的通信方式 多个进程共用内存中的一块存储区域 由进程控制数据的形式和方式 高级通信：可以传递大量数据，效率高
缺点：数据收发双方不可见，存在安全隐患
共享存储Shared-Memory
直接通信：点到点发送 发送和接收时指明双方进程的ID 每个进程维护一个消息缓冲队列
多处理机系统、分布式系统、计算机网络系统等。应用多
间接通信：广播信箱 以信箱为媒介，作为中间实体 发进程将消息发送到信箱，收进程从信箱读取 可以广播，容易建立双向通信链
消息传递Message-Passing
管道 用于连接读/写进程的共享文件，pipe文件 本质是内存中固定大小的缓冲区
半双工通信 同一时段只能单向通信，双工通信需要两个管道 以先进先出（FIFO）方式组织数据传输 通过系统调用read() /write()函数进行读写操作
管道通信Pipe
特点
进程通信
概念：协调进程间的相互制约关系，使它们按照预期的方式执行的过程前提： 进程是并发执行的，进程间存在着相互制约关系 并发的进程对系统共享资源进行竞争 进程通信，过程中相互发送的信号称为消息或事件两种相互制约形式 间接相互制约关系（互斥）：进程排他性地访问共享资源 直接相互制约关系（同步）：进程间的合作，比如管道通信
访问过程：1.进入区：尝试进入临界区，成功则加锁（lock） 2.临界区：访问共享资源 3.退出区：font color=\"#ff0000\
访问原则：空闲让进：临界区空闲，允许一个进程进入 忙则等待：临界区已有进程，其它进程等待（阻塞状态） 有限等待：处于等待的进程，等待时间有限 让权等待：等待时应让出CPU执行权，防止“忙等待”
单标志法：违背“空闲让进”
双标志法先检查：违背“忙则等待”
双标志法后检查：违背“空闲让进”、“有限等待”
皮特森算法（Peterson's Algorithm）：违背“让权等待”，会发生“忙等”
软件实现方法：
禁止一切中断，CPU执行完临界区之前不会切换关中断可能会被滥用关中断时间长影响效率不适用于多处理机，无法防止其它处理机调度其它进程访问临界区只适用于内核进程（该指令运行在内核态）
中断屏蔽方法：关中断/开中断
读出标志并设置为true，返回旧值，原子操作也被称作TSL指令（Test-And-Set-Lock）违背“让权等待”，会发生忙等
Test-And-Set(TS指令/TSL指令
交换两个变量的值，原子操作违背“让权等待”
Swap指令（EXCHANGE、XCHG）指令
硬件实现方法
PV操作 P操作：wait原语，进程等待 V操作：signal原语，唤醒等待进程
整型信号量：违背“让权等待”，会发生忙等
子主题
记录型型号量：进程进入阻塞状态，不会忙等
信号量（Semaphore)机制
互斥的访问临界资源
概念：“管理进程”，即用于实现进程同步的工具。是由代表共享资源的数据结构和一组过程（进行PV操作的函数）组成的管理程序（封装）。
组成： 管程名称 局部于管程内部的共享数据结构 对该数据结构操作的一组过程（函数） 管程内共享数据的初始化语句
管程的基本特性：是一个模块化的基本程序单位，可以单独编译 是一种抽象数据类型，包含数据和操作 信息掩蔽，共享数据只能被管程内的过程访问
条件变量/条件对象：进入管程的进程可能由于条件不满足而阻塞 此时进程应释放管程以便其他进程调用管程 进程被阻塞的条件（原因）有多个，移入不同的条件队列 进程被移入条件队列后，应释放管程
管程（Monitor，监视器）
进程同步
进程间协作
死锁：多个进程由于竞争资源而造成的阻塞现象，若无外力作用，这些进程将无法继续推进饥饿：等待时间过长以至于给进程推进和响应带来明显影响，“饿而不死”
死锁产生的原因：系统资源的竞争 进程推进顺序非法
死锁产生的必要条件：互斥条件：共享资源的排他性访问不剥夺条件：访问时该共享资源不会被剥夺请求并保持条件：保持当前资源时请求另一个资源循环等待条件：存在共享资源的循环等待链
破坏互斥条件：将只能互斥访问的资源改为同时共享访问 将独占锁改为共享锁 不是所有资源都能改成可共享的
破坏不剥夺/不可抢占条件：请求新资源无法满足时必须释放已有资源 由OS协助强制剥夺某进程持有的资源 实现复杂，代价高 此操作过多导致原进程任务无法推进
破坏请求并保持条件：进程开始运行时一次性申请所需资源（资源浪费、进程饥饿） 阶段性请求和释放资源
破坏循环等待条件：对所有资源现行排序，按序号请求资源（请求时先低再高，释放时先高再低） 对资源的编号应相对稳定，限制了新设备增加 进程使用资源的顺序可能与系统编号顺序不同 限制了用户编程
死锁预防
系统安全状态：安全状态一定不会出现死锁 不安全状态可能出现死锁
银行家算法：系统预判进程请求是否导致不安全状态 是则拒绝请求，否则答应请求
安全性算法
死锁避免
死锁定理（死锁状态的充分条件）: 当且仅当此状态下资源分配图是不可完全简化的 简化过程类似于“拓扑排序”算法（注意数据结构考察）
死锁检测：需要一种数据结构，保存有关资源的请求和分配信息 提供一种算法，利用这些信息检测是否形成了死锁
死锁解除：资源剥夺：挂起死锁进程、剥夺其资源、将资源分配给其它（死锁）进程 撤销进程 进程回退：回退到足以避免死锁的地步、需要记录进程历史信息，设置还原点
死锁的检测与解除
死锁的处理策略
死锁
进程管理
寄存器高速缓存主存储器硬盘缓存固定磁盘可移动存储介质
存储器的多层结构
用户程序→进程：编译、链接、装入
程序的链接：静态链接、装入时动态链接、运行时动态链接
程序的装入：绝对装入、可重定位装入、动态运行时装入两个细节：逻辑地址与物理地址、内存保护
内存扩充的两种方式：覆盖、交换
进程运行的基本原理
内容：1.对内存的分配与回收 2.从逻辑上对内存空间进行扩充3.用户进程中的逻辑地址和物理内存中的物理地址进行高速转换
单一连续分配：优点：实现简单；无外部碎片；不一定需要内存保护缺点：只能用于单用户、单任务OS；有内部碎片；存储器利用率低；
固定分区分配： 优点：实现简单；无外部碎片 缺点：1.较大用户程序时，需要采用覆盖技术，降低了性能； 2.会产生内部碎片，利用率低
怎么记录内存的使用情况
首次适应算法：从低地址查找合适空间（按地址递增排列最佳适应算法：优先使用最小空闲空间最坏适应算法：优先使用最大连续空间临近适应算法：从上次查找处向后查找
选择哪个分区给新进程
回收后相邻空间要合并；更新空闲分区表和/或空闲分区链记录
已使用的分区怎么回收
动态分区分配
优点：根据进程大小动态分配内存空间，没有内部碎片缺点：有外部碎片
连续分配管理方式
将内存分为大小相等的分区:页框/页帧/内存块/物理块；4k-2M之间页框号/页号从0开始；OS以页框为基本单位分配内存
页式管理中地址空间是一维的每次访存都需要地址转换，必须足够快页表不能太大，会降低内存利用率
基本地址变换机构：物理地址=（页号→块号）+偏移量页号P=逻辑地址A/页面长度（大小）L偏移量W=逻辑地址A%页面长度LP=A>>12;W=A&4095
快表命中率在百分之90以上
具有快表的地址变换机构：1.直接将页号与快表页号比较2.匹配成功，取块号+偏移量形成地址3.匹配失败，访问主存页表，并同步到快表（局部性原理
两级页表地址转换1.将逻辑地址拆分成三部分2.从PCB中读取页目录表始址3.根据一级页号查出二级页表位置4.根据二级页号查内存块号，加偏移量计算物理地址
两级页表
最多2^20个页表项。。一个块号占4Byte，即32位。。一个页框占2^12字节（4k=4*2的10次方）。。即一个页表需要占用4兆
两级页表：1.页表连续存放，占用大量连续空间2.一段时间内只需要访问部分特定页面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）
保障顺序上的公平：每次选择淘汰最早进入内存的页面，Belady异常，性能差
先进先出置换算法（FIFO）
保障时间和距离上的公平：每次选择淘汰最久最近未使用的页面，需要硬件支持，开销大
最近最久置换算法（LRU）
保障性能和开销均衡：为页面设置访问为（0/1），并链接成循环队列，进程访问页面后置为1.淘汰时为1置为0并跳过，为0时淘汰。最多需要两轮扫描
时钟置换算法（NRU）
改进型时钟置换算法
页面置换算法
分配空间小，进程数量多，CPU时间利用效率就高进程在主存中页数少，错页率就高进程在主存中页数多，错页率并无明显改善
驻留集（驻留在主存中页面数）大小驻留集包含工作集
固定分配局部置换可变分配全局置换可变分配局部置换
预调页策略：一次性调入若干相邻页面多用于进程首次调入
请求调页策略：运行时发现缺页时调入I/O开销较大
调入页面的时机
系统拥有足够的对换区空间系统缺少足够的对换区空间UNIX方式
从何处调页
页面分配策略
虚拟内存管理
内存管理
定义：以计算机硬盘为载体的存储在计算机上的信息集合属性：描述文件状态的一组信息，比如名称、标识符、类型、大小、位置、保护、时间、日期和用户标识等基本操作：创建文件；读文件；写文件；文件重定位（寻址）；删除文件；截断文件；打开与关闭
文件概念
无结构文件（流式文件）：（文本文档，图片等） 以字节（Byte)为单位 没有具体结构 采用穷举方式搜索
有结构文件（记录式文件）：（电子表格等）关键字 顺序文件(可变长文件（无法快速定位第i个记录）/定长文件（无法快速增删记录）） 索引文件（索引表是一个定长记录的顺序文件，一个索引一个记录）可以快速定位，又可以实现变长 索引顺序文件（一个索引表项对应一组记录） 直接文件或散列文件（Hash File)
文件的逻辑结构
文件控制块（FCB）： 基本信息 存取控制信息 使用信息
将表瘦身。在磁盘称为为磁盘索引节点。在内存称为内存索引节点
索引节点
有向无环图
蓝色文件。黄色目录
目录结构
文件的物理结构
文件的结构
软链接：创建一个link型文件指向所需访问的文件，删除link对源文件无影响
硬链接：索引节点共享（配合计数器）
文件共享： 硬链接（索引节点） 软链接（符号链）
文件保护（控制文件的访问权限）： 口令保护 加密保护 访问控制
文件共享和保护
文件系统基础
用户调用接口文件目录系统存取控制验证模块逻辑文件系统与文件信息缓冲区物理文件系统辅助分配模块设备管理程序模块
文件系统层次结构
线性列表（链表或数组）
哈希表（避免哈希冲突）
目录实现
一个索引占4字节，一个页块4k，则一个索引表可以存放1024个索引项。则一个由二级索引存储的文件不能大于4GB
连续分配（支持顺序和直接访问，速度快；不方便拓展，会产生磁盘碎片）链接分配（隐式链接：支持顺序访问，方便拓展，没有碎片；不支持直接访问，效率低 显式链接：支持顺序访问、随机访问，效率高；无外部碎片，方便拓展；占用了内存额外空间） 隐式链接，链接信息隐藏在数据块中，读取数据后才知道下一个链接块； 显式链接；由FAT（文件分配表）记录下一个块号，每个磁盘都有一个FAT常驻内存索引分配：为每一个文件建立一个索引表，所有索引表占一个页块，在索引块表中记录物理块号。可设置一级索引、二级索引
文件分配方式
1.目录区：存放文件目录信息（FCB）、磁盘空间管理信息2.文件区：存放文件数据将物理磁盘划分成一个个文件卷，也叫逻辑卷、逻辑盘
由空闲盘块表记录空闲块的信息。多用于连续分配，会产生外部碎片
空闲表法
单个块想连
空闲块示意图
区域里可能有多个块
空闲链表法
1.第一组连续的空闲扇区（超级块），系统启动时载入内存2.特殊值-1表示后续无分组3.分配过程：检查并尝试分配第一个分组的空闲块； 修改第一个分组和超级块记录 回收过程：将新的空闲块号记录到超级块和第一个分组； 若第一个分组已满，让新的空闲块成为新建分组
成组链接法
由计算机字长决定。比如32位，64位。 横向为字长，纵向为字号
位示图法
四种管理方法
文件存储空间管理
文件实现
文件系统实现
I/O就是输入/输出，将数据输入到计算机，或接收计算机的数据输出到外部设备
分类：按使用特性：人机交互类外部设备、存储设备、网络通信设备 按传输速率：低速设备（键盘，鼠标）、中速设备（打印机）、高速设备（磁盘，内存，高速缓冲器） 按信息交换单位：块设备（磁盘）、字符设备（键盘，鼠标）
I/O设备的构成： 机械部件：比如键盘设备的按键和按钮，用来执行具体的I/O操作 电子部件：即I/O控制器、设备控制器，是CPU与硬件设备之间的桥梁
I/O控制器主要作用：接收并识别CPU命令、向CPU报告设备状态、数据交换、地址识别
I/O设备的基本概念
CPU与控制器间的接口I/O逻辑控制器与设备间的接口
I/O控制器组成
优缺点：实现简单，读/写后轮询状态寄存器；CPU和IO设备串行，忙等
CPU频繁干预每次读/写一个字读：设备→CPU→内存
程序直接控制方式
优缺点：CPU和IO设备可以并行 频繁中断耗时
CPU将此IO进程阻塞IO前后CPU干预每次读/写一个字读：设备→CPU→内存
中断驱动方式
DR（Data Register 数据寄存器 ） DC（Data Counter数据计数器） MAR（ Memory Address Register 内存地址寄存器) CR（Control Register 控制寄存器）
优缺点：CPU和IO设备可以并行； 每个IO指令操作一个块，离散块需要频繁中断
传输单位是“块\"块之间传输需要CPU干预设备<->内存
DMA方式（Direct Memory Access）直接存储器访问
优缺点：CPU和IO设备可以并行实现复杂，需要硬件支持
（是一个硬件）通道是专门负责I/O的处理机每次读/写一组数据块IO设备<->内存
通道控制方式
I/O控制方式
I/O控制器
实现用户交互接口通过库函数实现系统调用
用户层软件
向上一层提供调用接口设备保护容错处理设备分配与回收数据缓冲区管理逻辑设备与物理设备映射（逻辑设备表）
设备独立性软件
不同设备硬件特性不同，但CPU指令相同负责控制硬件设备，将CPU指令转成设备操作驱动程序会以独立进程的形式存在
设备驱动程序
IO完成后发出中断信号执行中断处理程序会直接操作硬件
中断处理程序
硬件
OS内核即下面的“OS核心子系统”
I/O软件层次结构
I/O管理概述
I/O调度：用算法确定一个顺序来执行I/O请求（由设备独立性软件来确定）
设备保护
I/O子系统概述
输入井和输出井
输入进程和输出进程
输入缓冲区和输出缓冲区
用软件模拟脱机状态，用来匹配输入输出的速率差
SPOOLing技术（假脱机技术）
固有属性分配算法安全性
设备分配应考虑的因素
进程运行前分配所有资源，还是运行中动态申请资源
静态分配与动态分配
设备类型代表逻辑设备名。（逻辑设备表） 设备标识符代表唯一物理设备
设备管理中的数据结构
1.根据物理设备名查SDT2.查DCT，尝试分配给进程3.查COCT，尝试分配给进程4.查CHCT，尝试分配给进程
设备分配步骤
I/O设备分配与回收
为缓解CPU和IO设备间速度不匹配的矛盾而建立的临时存储区域1.缓和CPU和IO设备速度不匹配的矛盾2.减少CPU中断的频率，放宽对CPU相应时间的限制3.解决数据粒度不匹配的问题4.提高CPU与IO设备的并行性
处理一个块所需时间T+M或C+M（取决于T和C谁大） T和C可以并行
非空不写未满不读
单缓冲
处理一个块所需时间T或C+M（取最大结果）
双缓冲
循环缓冲
空缓冲队列满输入缓冲队列满输出缓冲队列
缓冲池
管理策略
缓冲区管理
I/O核心子系统I/O设备的分配与回收
输入输出管理
操作系统
父主题
控制器的设计之微程序设计
计算机组成原理
数据结构
计算机网络
09-14
09-17
09-18
09-20
09-22
09-34
09-35
9-36
09-39
09-04
09-05
09
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
random access memory随机访问存储器 read only memory只读存储器
10-16
10-17
10-18
10-19
10-20
10-21
10-22
10
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
11
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
C
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
12
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
A避免死锁 C说反了，后推前 D没有破坏，，，条件
13-31
13-33
13-34
HDLC发现五个1则在后面加0发送，，接收方收到后逢五个1减0
13-37
13-38
13-39
13
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
读进程只能一个，写进程可以多个 D错
14-31
14-34
14-35
14-36
14-37
14-38
14-40
14
考试真题
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-03
13-03
13-05
13-06
14-02
14-04
考试真题大题
考研计算机408
0 条评论
下一页
