操作系统

标识符:进程唯一ID

状态:运行/阻塞/挂起…

优先级:相对执行优先顺序

程序计数器:程序要执行的下一条指令的地址

内存指针:程序代码和进程相关数据的指针,以及其他进程共享内存的指针

上下文:执行时处理器寄存器中数据

IO状态信息:与IO有关信息

记账信息:处理器时间总和,使用时钟数总和,时间限制,记帐号等

总结: 进程=程序代码+相关数据+进程控制块

阻塞态必须先变为就绪态(👇就绪队列的限制)才能运行

转换:

• 空->新建
• 新建->就绪
• 就绪->运行
• 运行->退出
• 运行->就绪
• 运行->阻塞
• 阻塞->就绪
• 就绪->退出

转换: 除了内存中的就绪和阻塞,还产生了就绪/挂起和阻塞/挂起

用户数据

用户可修改区域

用户程序

待执行程序

栈

每个进程有一个LIFO栈,保存参数,过程调用地址和系统调用地址

进程控制块

进程表示

标识符

处理器状态

用户可见寄存器

控制和状态寄存器：程序计数器、条件码、状态信息

栈指针

进程控制信息

调度和状态信息、数据结构、进程间通信、进程特权、存储、资源所有权和使用情况

执行模式

大多处理器至少支持两种执行模式,某些指令只能在特权模式下执行,且某些区域仅能在特权模式下访问

非特权模式

• 用户模式: 通常用户程序在该模式下运行

特权模式

• 系统模式
• 控制模式
• 内核模式(kernel mode)

无进程内核(a)

传统,古老
在所有进程外执行系统内核,当进程中断或产生系统调用,保存其上下文,把控制权交给OS内核执行系统相关功能后,再恢复进程上下文

用户进程内运行(b)

小型PC,工作站中
在用户进程的上下文中执行操作系统软件

基于进程的OS(c)

把OS当作一组系统进程实现

进程

线程

关联属性

• 存放映像的虚拟地址空间
• 对处理器,其他进程,文件和IO资源的受保护访问

• 线程执行状态
• 未运行线程的上下文
• 执行栈
• 存放局部变量的静态存储空间
• 与其他进程内线程共享的内存和资源访问

进程管理

• 进程只有一个相关的控制块和地址空间
• 进程运行时,CPU寄存器被进程控制
• 未运行时,保存寄存器中内容

• 每个线程有单独的栈和控制块,其中包含寄存器值,优先级等线程相关属性
• 进程中所有线程共享进程的状态和资源

内核级线程(Kernel-Level Thread, KLT)

管理线程的所有工作都由应用程序完成,内核意识不到线程的存在

管理线程的工作由内核完成,

ULT优点

• 线程的管理切换无需特权
• 调度算法可根据程序调整
• ULT可在任何OS运行,依靠应用层级的线程库,无需底层内核支持

ULT缺点

• ULT在执行系统调用时,除了阻塞线程,还会阻塞进程中所有线程
• 纯ULT中,无法使用多处理技术,内核一次只能给一个进程分配一个处理器

把信号量视为int变量,在其上定义了三个操作:

• initialize: 信号量初始化为非负数(通常为1)
• semWait: 信号量-1,当s<0,阻塞执行semWait的进程
• semSignal: 信号量+1,若s>=0,被semWait阻塞的进程解除阻塞

问题描述

生产者/消费者问题是互斥的典型问题:有一个或多个producer将数据放入buffer,有一个consumer从中取数据,每次取一项,在任何时候:

• 只能有一个P或C访问buffer
• buffer满时P不会再放数据,buffer空时C不会取数据

解决思路

数据结构：给定缓冲区数组

• produce()->元素in
• consume()->元素out

给定以下变量和信号量:

• n=(in-out),即缓冲区中数据个数
• s, 互斥信号量
• delay, 数据信号量,强迫consumer在数据空时等待

原始算法

分析

修正

该算法不能保证任何情况下的正确：

正确前提:

Producer总能在Consumer之前工作,即消费时,n总为1

错误情况:

• consumer刚出临界区还未执行consume(),n=0
• producer抢占,n++ ->1且delay->1,表示有数据
• consumer恢复,消费后不满足n==0,delay保持1
• consumer连续执行,n-- ->0,消费后满足n==0,此时delay==1,semWait(1)表示进程继续,产生矛盾:n==0,缓冲区无数据,却还能继续take()

产生错误的直接原因: n变化-->delay的更新失败-->consumer第二次先于producer执行

consumer本身满足n==0,准备在此处阻塞,delay置为0,但被抢占后,n++,delay保持1,使得consumer恢复后delay未能阻塞连续消费的发生

使用一般信号量时:
n本身替代了delay作为数据信号量,判断当前缓冲区数据

交换producer中两语句--无影响:

• 图中顺序,当producer出临界区后立刻被抢占,consumer的semWait(n)也会阻塞消费
• 交换,全在临界区进行,更不会抢占

交换consumer中两语句--产生死锁:

• 系统偶然错误,在n==0时,consumer进入临界区执行semWait(n),此时producer无法进入临界区,无法改变n,死锁

消息传递

进程交互需要满足同步和通信.为了实时互斥,进程需要同步,为了合作,需要通信.消息传递可以提供以上功能,且可在分布式系统,共享内存的多处理器系统和单处理器系统实现

基本实现

两个重要原语:

• send(destination, message)
• receive(source, message)

• 进程以message的形式给目标进程destination发送消息;
• 进程通过receive接收消息,当中指明了源进程source和消息message

send阻塞/receive阻塞

发送进程和接收进程都阻塞,直到完成投递

send无阻塞/receive阻塞

接收者阻塞,直到接收到消息(最自然的方式)

send无阻塞/receive无阻塞

双方都不等待

两个进程两个信箱:

• 初始化:mayproduce填满空消息
• 生产:mayproduce中始终放空消息,生产前从mayproduce中接收空消息,当没有空消息,说明缓冲区没有空间,阻塞直到消费后产生空间
• 消费:消费前从maycosume中接收消息,当没有消息,说明缓冲区中无数据,阻塞,直到产生消息

读者/写者问题

一个共享的数据区,一些进程(reader)只读取数据,一些进程(writer)只写数据,且满足

• 读者可多个同时读取
• 同时只能一个人写
• 写的时候不能读

即读进程不排除其余读进程,写进程排除所有进程

对比P/C问题

主要在于对共享空间的访问

• R/W问题中,读者不会写数据,写者不会读数据,
• P/C问题中P可能读取队列指针确定写的位置以及是否已满,c也会调整缓冲区表示其消费了数据

问题分类

读者优先:只要有一个读进程执行,就为读进程保留数据区控制权,其余读进程可同时进行,写进程可能饥饿

写者优先:当一个写进程要执行,假设此时一个读进程正执行,暂时阻塞写进程,但其余读进程也被阻塞不能再执行,且优先恢复写进程

死锁

一组相互竞争系统资源或通信的进程发生"永久阻塞"

系统资源

可重用 

reusable

一次仅供一个进程安全使用且不会因为使用而耗尽,数量有限

死锁情况:两个进程分别占有一个资源,但都请求对方占有的资源,产生死锁

可消耗

consumable

可被生产/消耗的资源,数量通常无限
死锁情况:参考: Ch5 4.2交换consumer中两语句--产生死锁 ,很多事件组合都会导致死锁

死锁的必要条件

• 互斥:一次只有一个进程可以使用一个资源

• 占有且等待: 一个进程等待其他进程时,继续占有已分配资源
• 不可抢占: 不能抢占其余进程已占有资源

额外条件,组成充要条件

• 循环等待:形成闭合链,阻塞的进程间互相等待其他进程释放资源

①互斥

操作系统普遍实现,不具备禁止条件

②占有且等待

一次性请求所需资源,确保后续无等待
👹问题:低效,可能长时间阻塞以等待资源

③不可抢占

👹问题:第二种额外抢占需要满足优先级不同,且两种实现都需要系统可以容易保存与恢复进程状态

④循环等待

若AB死锁,可能是A占有Ri,请求Rj,B占有Rj请求Ri,因此杜绝B的请求就能防止死锁
👹问题:低效,产生长时间阻塞或者无必要的拒绝

资源向量化

进程启动拒绝
(死锁避免策略)

资源分配拒绝
(银行家算法)⭐

参考: 银行家算法例题

进程启动拒绝和资源分配拒绝的区别:

进程启动拒绝是基于假设:新旧进程一起以最大请求访问资源,安全但产生不必要的拒绝;
资源分配拒绝是基于动态判断:当前进程中是否有能够运行结束,当其结束后释放资源能否满足其他进程结束,循环,最终保证所有进程都执行结束

死锁检测和死锁预防的区别:
预防策略很保守,属于"未雨绸缪"但检测算法属于不限制系统的资源分配,但定期执行算法检测当前是否有死锁,并在有死锁后恢复系统,属于"亡羊补牢"

算法

参考: 死锁检测算法

银行家算法和死锁检测算法本质相同,只是在系统的使用时间在分配资源前后与否

P1

0

0

0

0

P2

0

7

5

0

P3

6

6

2

2

P4

2

0

0

2

P5

0

3

2

0

1. 没有分配资源都为0的进程,不标记
2. 初始化W=(2 1 0 0)
3. 进程p1需求可满足,标记P1

W = W+(0 0 1 2)=(2 1 1 2)

4. 重复,最终所有进程都接受了标记
5. 则没有死锁

银行家算法和检测算法:

银行家算法和死锁检测是同一种算法,但前者专门指资源分配前通过算法得出的安全状态而决定是否分配资源给某个线程;后者则是判断当前状态下是否有进程无法执行完毕

多队列法

将每个进程放到能容纳它的最小分区, 每个队列负责维护该分区换出的进程,对单个分区,该方法最优,内部碎片少,但整体看,当分区有挂起进程,但此时别的分区本可以容纳,却由于非对应队列而无法执行,增加阻塞

单队列法

当没有可用分区后,进行交换,优先换出可容纳该进程的最小分区

定义

分区的长度和数量可变,进程装入内存时,系统分配给它一块与其容量完全相等的内存空间

外部碎片

动态分区时,内存中会出现"空洞",无法满足任何进程的空间需求,只能换出其余进程,

• 这种碎片是对内存整体来说的
• 压缩: 运用动态重定位的方法,将进程位置移动,整理碎片成一个足够大的空间

加载模块被加载到内存时,全部使用相对地址,只有真正执行才使用绝对地址

假设某进程占据了内存中一段完整的相邻分区:

程序装入的实际起点(Base值)为1024,假设x装入后Bounds为2688,此时统一相对化地址:开始执行x的语句

jump 400,400+1024=1424 < 2688,读取400处指令

load 1200,1200+1024=2224 < 2688,加载1200处数据

例题:使用16位寻址,页大小1k,已知相对地址1502,和部分页表,求逻辑地址与物理地址

解:1502化为二进制0000,0101,1101,1110,1K=210,16-10=6,则6位用于片选

page:000001,offset:0111011110=478

⭐则相对地址1502的逻辑地址:对于page1(000001)的偏移量为478(0111011110)二者产生的16位数一样,但含义不一样

page:000001->frame:000110

则物理地址:0001100111011110

逻辑地址

物理地址

例题:使用16位寻址,段号占4位,已知逻辑地址0001,0010,1111,0000和部分段表,求逻辑地址与物理地址

解:片选4位

segment:0001,offset:0010,1111,0000

段表中Length代表该段分区长度,起始地址Base=0010,0000,0010,0000

则offset+Base=0010,0011,0001,0000即物理地址

注意点:

• 虚拟地址即逻辑地址
• 页表指针寄存器位于"进程控制块"中
• 由于页表长度基于进程长度而变化,因此页表不能在寄存器中保存,须在内存中且可访问
• 一般每个进程都一个页表,页表可能占据巨大的空间：某系统中,一个进程可有虚存2GB=231,页大小29 ,则一个进程就需要222页
• 解决:在虚存中保存页表--页表本身也使用分页机制

👉

在32位机器中,当页大小为4KB,虚拟空间4GB:

2³²/4k=2²⁰,分为2²⁰页,当每页都使用一个4B的页表项映射,构成一张二级页表,需要内存空间4*2²⁰=4MB

页目录表(Directory)/一级页表/根页表

页表地址(Table)/二级页表/用户页表

👈

把4GB空间分为1024个可被页目录索引的页组(二级页表),每个页组长4MB.包含1024个项,每项对应大小4KB的页.

此时实存中只保存了2¹⁰个一级页表项

4B页表项即32b地址,符合32位机

2²²/4k=2¹⁰,需要2¹⁰个页目录,则1级是包含1024个项的页目录表/一级页表

页表大小与虚拟空间大小成正比

倒排

使用散列函数将n位页号映射到散列表得到m位帧号,表中有指向倒排表的指针,倒排表中有页表项.这种结构下,散列表和倒排表各有一项对应一个实存页:

• 散列指针->页表项
• 链->页表项/物理地址

由于多个虚拟地址可能映射到一个散列表项中,需要使用链接技术管理溢出,因此无论有多少进程,支持多少虚拟页,页表只需要实存中的一个固定部分

(类比数据结构散列表有限,但通过散列函数和二次散列等方式保证了散列值的不同)

• 称为"倒排"的原因:使用帧号而非虚拟页号索引页表

• 由a,开始页尺寸加大,缺页率升高,然后又成反比,最终,当页和进程大小一样,没有缺页出现(分段)
• 由b,当分配的页框数越充裕,缺页率越低
   

基于分段的虚拟内存中,每个进程有唯一的段表

• 存在位:由于一个进程可能只有一部分段在内存中,因此段表有一位表示段是否存在
• 修改位:表明上次被装入内存到目前位置其内容是否改变

段页式结构中,每个进程使用一个段表和一些页表. 段表项:包含段长和Base,无需存在位和修改位,留在页级处理

• 页表项:类似纯粹的分页,需要P,M位
• 程序员角度:逻辑地址=段号+段偏移
• 系统角度:段偏移即指定的页号+页偏移
  

策略意义

决定某页何时取如内存

方式

• 请求分页式(Demand paging):访问到某页时才取入

• 问题:开始可能遇到大量缺页中断

• 预约分页式(Preparing):事先读取多于当前需要的页

• 问题:当大多数页没有用到时,效率低

策略意义

决定进程块驻留在实存的什么位置

方式

• 对分段系统和NUMA(nonuniform memory access非一致存储器访问)系统

• 放置策略影响较大

• 对分页或段页式系统

• 放置位置无影响,地址转换和内存访问对不同位置页框执行效率一致

策略意义

决定读取新页时应该置换出内存中哪一页

方式

• OPT:最佳策略,选择换出下次访问距当前时间间隔最长的页

• 问题:不可能实现,需要预测未来的进程

• LRU:最近最少使用,换出上次访问距今时间最长的页

• 问题:性能接近OPT,实现开销巨大

• FIFO:先进先出队列

• 问题:实现简单,但隐含替换留存时间最久的页,不一定符合局部性原理,中断多

• Clock Policy:时钟策略

• 👇时钟置换策略 ,以较小的开销实现LRU性能

例子: 要换入页727,初始指针在页框2
① 页框2处使用位为1,置为0,指针后移
② 页框3处使用位为1,置为0,指针后移
③ 页框4处使用位为0,换出,将727置入,指针后移

策略意义

决定给进程分配多少空间,允许其中多少页驻留在内存中

分配方式

• 固定分配策略:分配固定的页框
• 可变分配策略:根据缺页率,可动态调整页框分配

置换范围

• 局部置换:只换出分配该进程内存页框中的页
• 全局置换:可换出内存所有可用页框中的页

组合方式

• 固定+局部：缺页时,从该进程驻留页中选择一页换出
• 可变+局部：评估后,为进程分配不一定等大的页框,缺页时,从当前进程驻留页中换出,但系统不时重新评估,动态调整
• 可变+全局：最易于实现,所有进程页框数一样,但系统维护一个空闲页框列表,当缺页发生,空闲页框可加入进程驻留集,从而改变驻留集大小

策略意义

确定何时将已经修改的一页写回辅存

方式

• 请求式(demand cleaning):当一页被置换时才写回

• 问题:中断解除阻塞前要经过旧页写回和新页读入两次

• 预约式(precleaning):将修改的多页在置换前成批写回

• 问题:可能浪费资源,毕竟大部分页在写回后又会修改

策略意义

影响系统并发度:驻留在内存中的进程数量

影响

• 进程太少:进程运行处于阻塞态的概率较大
• 进程太多:平均到每个进程的驻留集空间不够,频繁缺页中断,发生系统抖动

一块晶片上有大量芯片,每个芯片上有无数的门电路用于处理数据,位元用于存储数据

半导体存储器的基本结构是位元,可被多种技术实现,但都具有以下性质:

• 可稳定保持两种状态
• 可读/可写

位元普遍有三个功能端口:

• Select,用来选择位元
• Control,用来确定读写
• Data-In,接收1,0电信号
• Sense,输出当前状态

图示为一个储存1位信息的DRAM结构: 电容具有漏电的自然趋势,因此需要周期性充电保持存储状态--"动态"的来历

• 写操作:位线输入高低电压代表1和0,利用晶体管的特性,施加电压到地址线导通,电荷传输到电容器保存
• 读操作:施加电压到地址线,电容器放电,电荷被位线接收,经过放大器放大,对比参考值,确定位值是1还是0

当阵列中位宽16bits(极端)

1M×16b,1M个16位字

当阵列中位宽1bit(极端)

16M×1b,16M个1位字

当采用4M×4(常见)

4M×4b,4M个4位字

逻辑上: 

DRAM组织成4个2048×2048的方阵,阵列元素使用行和列控制线连接,行控制线连接行内每个位元的Select端口,列控制线连接Data-In/Sence端口

log2(4M)得到22,需要22根地址线,各取11位控制行与列,最终确定4位位元参与读/写:

• 写:每根位线的位驱动器根据对应数据线的值激活为1/0
• 读:每根位线的值经过放大器,传递到数据线

• 1M×8=4×(256K×2)×4
• 共需要16块RAM芯片组成存储器,其中4个芯片组成一个bank;

• log2(256k)=18,行列控制位各9位
• 还需要2位进行组选择

总线宽度

• 数据总线宽度对系统性能影响:数据总线越宽,一次传送的位数越多
• 地址总线宽度对系统容量影响:地址总线越宽,可访问单元越多

CPU位宽

32位CPU和64位CPU的两大区别体现在此

• 数据总线:32位下,CPU在处理指令时只能处理最多32位,但64位下能够翻倍,大幅提升了对指令的执行能力,即前面得到字的位宽决定半导体存储器一次读/写数据的位数,在真实的计算机中,位宽由CPU决定
• 地址总线:32位下,最大寻址空间最大也只有2^32=4Gb,但64位下能有2^64b,更大的物理存储空间也提升了系统性能

• 32位二级页表结构(字节寻址): 假设页大小4k,虚存空间4G 则232/4k=220,页表个数为220,需要页表项也为220个
• 当每页都使用一个4bytes的页表项,则需要内存空间4*220=4M
• 对所有一级页表项占据的空间分页
• 222/4k=210,则需要210页,因为给定每页一个页表项
• 此时实存中保存了210个页表项,每个页表项4bytes,实际占用内存4k

虚拟内存使用2入口TLB,2路组关联cache,一个页表,假设cache块大小8个字,页大小16个字,RAM如如分块,两个块为一个页框

1. 进程p的虚拟地址位数
2. 物理地址位数
3. 求出虚拟地址(18)10的格式,解释转换为物理地址的过程
4. 已知虚拟地址610转换为物理地址(54)10,给出物理地址形式,确定主存cache块位置,给出过程
5. 已知虚拟地址(25)10在page1,偏移量9处,给出物理地址,以及访问数据全过程

Consider the following page reference string:  7,2,3,7,2,5,1,4,6,5,7,1,0,5,4,0,2,3,0,5 Assuming demand paging with 4 frames, please show the frame contents of the pages after each page reference for the following page-replacement algorithms and count the page interrupt times for every replacement algorithm.

a) LRU replacement  (3分)

b) Optimal replacement (3分)

c) FIFO replacement  (3分)

d) Clock replacement (4分)

LRU

OPT

Clock

类型

解释

理解⭐

长程

决定加入待执行进程池

将批作业/程序加载到系统,最少使用

中程

决定加入部分或全部位于内存中的进程集合

一定涉及到交换(swapping),即挂起态到其他态的转换,稍频繁

短程/分派器

决定处理器执行哪个可运行进程

决定下次执行哪个进程,最频繁,以下事件都属于短程调度:时钟中断、I/O中断、操作系统调用、信号量

I/O

决定可用I/O设备处理哪个挂起的I/O请求

与I/O请求有关

对象

性能

用户

相关

周转时间

(Turnaround time)

周转时间=等待时间+执行时间

对批处理作业适用

响应时间

进程从提交请求到接收响应时间间隔,

对用户需要接收响应的进程更适用

最后期限

在DDL接近时,规则会降低其余目标

其他

可预测性(predictability)

无论负载大小,用户不希望出现大范围波动

系统

相关

吞吐量 (Throughput)

单位时间完成最大进程数

处理器利用率

(Processor efficiency)

处理器忙状态占比

对共享系统重要,但单用户/实时系统不重要

其他

公平性

没有额外限定时,每个进程应该平等对待

强制优先级

优先执行高优先度的

平衡资源

当资源都忙,优先调用较少使用紧缺资源的进程

决策模式

非抢占

调度时间

当前进程完毕,执行下一进程

进程选择

设置就绪队列,当前进程结束后,执行队列中存在最久的进程

缺点

• 一个短进程可能会等待很久
• 不利于I/O密集型进程:cpu进程执行时,I/O设备可能空闲,当I/O进程通过就绪队列后阻塞,cpu又空闲

优点

• 适用长进程
• 有利于处理器密集型进程

决策模式

抢占

调度时间

按基于时钟中断的时间片(time slicing)执行

进程选择

基于FCFS选择下一时间片执行的进程

缺点

• 时间片短虽然利于短作业,但耗费资源,最好让时间片长度略大于典型交互时间,当时间片大于最初进程运行时间后,退化为FCFS
• 在兼具处理器密集进程和I/O密集进程时:I/O进程使用处理器如果阻塞,这段时间占据时间片,实际上处理器没能执行

优点

• 适用通用的分时系统和事务处理系统

决策模式

抢占

调度时间

同上RR

进程选择

见👇与RR对比

对比

区别:
I/O进程阻塞接触后没有回到就绪队列,而是进入辅助队列,直接面向处理器,且辅助队列中进程优先于就绪队列,弥补了I/O阻塞带来的执行缺失

决策模式

非抢占

调度时间

当前进程完毕,执行下一进程

进程选择

预期处理时间最短的进程下一个执行

缺点

• 长进程的可预测度降低
• 长进程可能饥饿

优点

• 适用短作业

决策模式

抢占

调度时间

新进程抵达后决定

进程选择

新进程抵达后选取剩余时间最短者

缺点

• 记录过去的服务时间,增加开销

优点

• 不像FCFS偏向长进程,也不像SPN偏向短进程

决策模式

非抢占

调度时间

当前进程完毕,执行下一进程

进程选择

计算最大响应比的进程作为下一个

响应比

• R:响应比
• w:等待时间
• s:预计服务时间

R最小值为1.0,只有第一个进入系统的进程才可能达到

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

A

B

C

D

E

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

A

B

C

D

E

• 规律:阶梯状
• 易错:以5-6-7为例的就绪队列状况,新线程进入先于当前进程重新入队

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

A

B

C

D

E

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

A

B

C

D

E

0

1

2

R

3

4

5

6

7

8

R

9

10

11

12

R

13

14

15

16

17

18

19

A

B

7/6

C

9/4

D

8/5

12/5

E

3/2

7/2

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

A

1

2

3

结束

B

1

2

2

2

3

3

3

3

3

3

4

4

4

5

5

5

6

结束

C

1

2

2

2

3

3

3

3

3

4

4

结束

D

1

2

2

2

3

3

3

3

4

4

4

5

结束

E

1

2

结束

人可读

• 打印机
• 终端:显示器,键盘,鼠标等

机器可读

磁盘,usb密钥,传感器

通信

调制解调器

程序控制I/O

处理器代表进程给IO模块发送IO指令,进程进入忙等待直到IO操作完成

中断驱动I/O

处理器代表进程给IO模块发送IO指令:分为两种情况:

• 进程非阻塞:处理器执行后续指令
• 阻塞进程:处理器被中断并执行操作系统的指令,将当前的进程设为阻塞态,调度其余进程

DMA

专门的DMA模块控制内存和IO模块间的数据交换.为传输数据,处理器给DMA模块发送请求后执行后续指令,只有整个数据库传输结束后,处理器才被中断

无中断

有中断

处理器实现IO和内存间传输

程序控制IO

中断驱动IO

IO和内存直接传输

DMA

总结:

1. 处理器直接控制外设
2. IO模块控制外设,处理器非中断式处理IO
3. 处理器可中断处理IO
4. DMA模块

5. IO配置专门处理器

6. IO的存储器独立
总结: IO去处理器化

IO设备

面向流

设备以字节流输入/输出数据,没有快结构

单缓冲

系统为操作分配一个内存中系统部分的缓冲区

优点

• 用户进程可在下一块读取时处理当前块

• 缓冲区在系统内存中非用户进程内存中,故系统可换出它

缺点

• 系统必须记录给用户进程分配缓冲区的情况

• 交换逻辑有漏洞:当IO和换出磁盘是一块时,若执行IO,再换出可能出问题

面向流

• 一次传送一字节--系统和用户的交互以p/c模型进行
• 一次传送一行--适于哑终端

面向块

无明显提升

双缓冲

面向流

• 一次传送一字节--用户进程无需再为IO挂起,提高性能
• 一次传送一行--对比两倍长单循环无明显提升

面向块

提高复杂性,提升性能

循环缓冲

支持大量IO

当进程需求远大于IO模块处理请求时,即使再多的缓冲也会被填满；

但在多道环境中,当有多种IO和进程,缓冲能够提高系统效率,提升单个进程性能

寻道时间

磁头定位到某磁道

旋转延迟

抵达磁道后,适当扇区旋转到磁头下

传输时间

数据传输时间

存取时间

寻道时间+旋转延迟

总平均存取时间

寻道时间+旋转延迟+传输时间

T:传输时间,b:字节数, N:一个磁道字节数, r:旋转速度(r/s)

顺序组织下,只有第一次需要寻道:
第一个磁道中:

• 寻道时间:4ms

• 旋转延迟=1/2*1r/7500rpm=30000ms/7500=4ms

• 读500扇区(全读):1/7500rpm=8ms

合计:16ms

其余每个磁道:

• 旋转延迟:4ms
• 读取时间:8ms

合计4*12=48ms

因此读取完5个磁道共需:64ms

随机组织：文件随机分布在不同磁道的扇区

随机组织下,每个扇区都需要重新寻道:

• 寻道时间:4ms
• 旋转延迟:4ms
• 读取一个扇区:8ms/500=0.016ms

因此读取完2500个扇区共需:2500*8.016=20040ms

结论:完全随机的存取时性能非常差

文件组织

数据结构

堆 Pile

优点

最简单,按照达到顺序被收集,记录的组成域可以不同,没有规范

缺点

堆文件没有结构,访问记录是需要穷举查找

顺序文件

优点

最常见,每条记录长度相同,且组成记录的域也是数量相同,长度固定

缺点

记录有规范,域的位置大小都已知,只需要保存域的值,访问记录还是需要使用顺序查找

索引顺序文件

优点

保持了顺序文件的特点,增加了索引和溢出文件

缺点

基于文件的域进行处理,无法使用其他属性查找记录

索引文件

• 完全索引类似索引顺序方式
• 部分索引运行使用定义的属性进行查找

直接/散列文件

允许直接访问磁盘中任何一个地址已知块

记录组块

如上图所示,记录是访问结构化文件的逻辑单元,而内存中的块是与辅存IO交互的基本单位,因此记录必须组织成块

定长

记录定长,且若干完整记录在一块,因此块内会产生内部碎片

变长跨越式

使用变长记录,使得块中无剩余空间,但有些记录会跨块,使用指针连接