网站优化的代码,大连网站建设解决方案,广东百度seo关键词排名,百度推广价格概念
接口
操作系统为用户提供两类接口#xff1a;操作一级的接口和程序控制一级的接口。操作一级的接口包括操作控制命令、菜单命令等#xff1b;程序控制一级的接口包括系统调用。
UMA和NUMA
UMA#xff0c;统一内存访问#xff0c;Uniform Memory Access#xff0c…概念
接口
操作系统为用户提供两类接口操作一级的接口和程序控制一级的接口。操作一级的接口包括操作控制命令、菜单命令等程序控制一级的接口包括系统调用。
UMA和NUMA
UMA统一内存访问Uniform Memory Access指所有的物理存储器被均匀共享即处理器访问它们的时间是一样的。UMA亦称作统一寻址技术或统一内存存取架构。这种系统因为高度的资源共享也被称为紧耦合系统Tightly Coupled System。
NUMA非统一内存访问架构Non-Uniform Memory Access是一种为多处理器的电脑设计的内存架构内存访问时间取决于内存相对于处理器的位置。在NUMA下处理器访问它自己的本地内存的速度比非本地内存内存位于另一个处理器或者是处理器之间共享的内存快一些。
进程
组成进程控制块PCB唯一标志、程序描述进程要做什么、数据存放进程是所需要的数据
临界资源各进程间需要以互斥方式访问的资源
临界区进程中对临界资源操作的那段程序
互斥信号量初值为1
同步信号量初值为共享资源的数量
PCB
进程控制块其组织方式有
线性表方式不论进程的状态如何将所有的PCB连续地存放在内存的系统区。适用于系统中进程数目不多的情况索引表方式该方式是线性表方式的改进系统按照进程的状态分别建立就绪索引表、阻塞索引表等链接表方式系统按照进程的状态将进程的PCB组成队列从而形成就绪队列、阻塞队列、运行队列等。
状态切换
参考进程、线程和协程的区别与联系
PV操作
信号量
在并发系统中信号量是用于控制公共资源访问权限的变量。信号量用于解决临界区问题使得多任务环境下进程能同步运行。此概念是由荷兰计算机科学家Dijkstra在1962年左右提出的。信号量仅仅跟踪还剩多少资源可用不会跟踪哪些资源是可用的。
信号量机制处理进程同步和互斥的问题。信号量的一大特征就是它的值不能通过PV操作以外的方式更改只能被两个标准的原语wait(s)和signal(s)访问也可记为P(s)和V(s)。信号量数值为负时表明有进程在等资源。
信号量提供一种很方便的方法来确保对共享变量的互斥访问。基本思想是将每个共享变量与一个信号量s初值为1联系起来然后用P(s)和V(s)操作将相应的临界区包围起来。以这种方式来保护共享变量的信号量叫做二元信号量因为它的值总是0和1。一个被用作一组可用资源的计数器的信号量被称为计数信号量。
PV操作
计数信号量Counting Semaphores通常有两种操作记做P和VP操作减少信号量SV操作增加信号量S
P操作P(s)wait申请资源信号量数值减一并且立即返回S - 1。S0此进程执行S0此进程置为阻塞等待、挂起状态直到s变为非0将其插入阻塞队列。进入临界区时执行P操作V操作V(s)signal释放资源信号量数值加一S 1。S0此进程继续执行S0从阻塞队列唤醒一个并插入就绪队列。退出临界区时执行V操作
P、V都来源自荷兰语V通常解释为verhogen、increase。P则有多种解释proberen、to test、to try、passeren、pass、pakken、grab。
在Dijkstra最早的论文中P表示passeringpassingV表示vrijgaverelease。
应用场景
生产者-消费者问题哲学家就餐问题
实战
信号量
假设系统中有n个进程共享3台打印机任一进程在任一时刻最多只能使用1台打印机。若用PV操作控制n个进程使用打印机则相应信号量S的取值范围为若信号量S的值为-3则系统中有个进程等待使用打印机。
解析 假设系统中有n个进程共享3台打印机 意味着每次只允许3个进程进入互斥段则信号量的初值应为3最小值为-(n-3)因此取值范围3, 2, 1, 0, -1, ..., -(n-3)。
信号量S的值为-3则系统中有3个进程等待使用打印机。
信号量S的物理意义为当S0时表示资源的可用数当S0时其绝对值表示等待资源的进程数。
PV操作
进程P1、P2、P3、P4和P5的前趋图如下 若用PV操作控制进程P1〜P5并发执行的过程则需要设置5个信号S1、S2、S3、S4和S5进程间同步所使用的信号量标注在上图中的边上且信号量S1〜S5的初值都等于零初始状态下进程P1开始执行。下图中a、b和c处应分别填写d和e处应分别填写f和g处应分别填写。 解析 因为P1是P2和P3的前驱当P1执行完应通知P2和P3应采用V(S1)V(S2)操作分别通知P2和P3故a处应填写V(S1)V(S2)又因为P2是P1的后继当P2执行前应测试P1是否执行完应采用P(S1)操作测试P1是否执行完故b处应填写P(S1)P2是P4和P5的前驱当P2执行完应通知P4和P5应使用V(S3)V(S4)操作分别通知P4和P5故c处应填写V(S3)V(S4)。
因为P3是P1的后继当P3执行前应测试P1是否执行完应采用P(S2)操作测试P1是否执行完故d应填写P(S2)P3是P5的前驱当P3执行完应通知P5应采用V(S5)操作通知P5故e处应填写V(S5)。
P4是P2的后继当P4执行前应测试P2是否执行完应采用P(S3)操作分别测试P2是否执行完故f处应填写P(S3)又因为P5是P2和P3的前驱当P5执行前应测试P2和P3是否执行完应采用P(S4)P(S5)操作分别测试P2和P3是否执行完故g处应填写P(S4)P(S5)。
机票
某航空公司机票销售系统有n个售票点该系统为每个售票点创建一个进程 P i ( i 1 , 2 , … , n ) P_i(i1,2,…,n) Pi(i1,2,…,n)管理机票销售。假设 T j ( j 1 , 2 , … , m ) T_j(j1,2,…,m) Tj(j1,2,…,m)单元存放某日某航班的机票剩余票数Temp为 P i P_i Pi进程的临时工作单元x为某用户的订票张数。初始化时系统应将信号量S赋值为。 P i P_i Pi进程的工作流程如下图所示若用P操作和V操作实现进程间的同步与互斥则图中空abc处应分别填入。 解析 公共数据单元是一个临界资源最多允许1个终端进程使用因此需要设置一个互斥信号量S初值等于1。
进入临界区时执行P操作退出临界区时执行V操作。答案应该是P(S),V(S)和V(S)。
死锁
进程死锁的四个必要条件
资源互斥每个进程占用资源并等待其他资源系统不能剥夺进程资源进程资源图是一个环路
死锁进程计算 n个进程、每个进程都需要R资源 发生死锁的最大资源数n *(R - 1) 不发生死锁的最小资源数n *(R - 1) 1
存储
存取方式
存储器中数据常用的存取方式
顺序存取存储器的数据以记录的形式进行组织。对数据的访问必须按特定的线性顺序进行。磁带存储器采用顺序存取的方式。直接存取与顺序存取相似直接存取也使用一个共享的读写装置对所有的数据进行访问。但是每个数据块都拥有唯一的地址标识读写装置可以直接移动到目的数据块的所在位置进行访问。存取时间也是可变的。磁盘存储器采用直接存取的方式。随机存取存储器的每一个可寻址单元都具有自己唯一的地址和读写装置系统可以在相同的时间内对任意一个存储单元的数据进行访问与先前的访问序列无关。主存储器采用随机存取的方式。相联存取相联存取也是一种随机存取的形式但是选择某一单元进行读写是取决于其内容而不是其地址。与普通的随机存取方式一样每个单元都有自己的读写装置读写时间也是一个常数。使用相联存取方式可以对所有的存储单元的特定位进行比较选择符合条件的单元进行访问。为了提高地址映射的速度Cache采取相联存取的方式。
LRU算法最近最少使用理论依据是局部性原理。要求较多硬件支持成本高。 CLOCK算法LRU近似算法。 简单CLOCK算法循环队列每页有访问位淘汰访问位为0的页。 改进型CLOCK算法同时考虑访问位与修改位。 时间局部性刚被访问的内容立即又被访问。 空间局部性刚被访问的内容临近的空间很快被访问。
程序访问具有时间局部性即最近将要用的信息很可能是正在使用的信息 程序访问具有空间局部性即最近将要用的信息很可能与正在使用的信息在存储空间上是相邻的 程序访问局部性是构成层次结构的存储系统的主要依据
分页存储管理
逻辑页分为页号和页内地址页内地址就是物理偏移地址页号通过查询页表得知页号对应的物理块号块号 偏移地址得出真正的物理地址如果该页尚未调入内存则产生缺页中断以装入所需的页
分区存储组织页式存储段式存储段页式存储
页面淘汰算法
最优OptimalOPT算法随机RAND算法先进先出FIFO算法有可能产生抖动与Belady奇异现象。
抖动
如果分配给进程的存储块数量小于进程所需要的最小值进程的运行将很频繁地产生缺页中断这种频率非常高的页面置换现象称为抖动。Thrashing又叫颠簸。 产生原因进程的内存量不足。因而分配页面太少总是缺页。 在请求分页存储管理中可能出现这种情况即对刚被替换出去的页立即又要被访问。需要将它调入因无空闲内存又要替换另一页而后者又是即将被访问的页于是造成了系统需花费大量的时间忙于进行这种频繁的页面交换致使系统的实际效率很低严重导致系统瘫痪这种现象称为抖动现象。
解决办法
使用更好的页替换算法减少运行的进程数增大内存
Belady奇异现象
指采用页面置换FIFO算法时如果对一个进程未分配它所要求的全部页面有时就会出现分配的页面数增多但缺页率反而提高的异常现象这是一个违反直觉的现象。
原因所使用的FIFO算法不够好。
文件管理
记录文件有顺序文件、索引顺序文件、索引文件和直接文件。
位示图法
某文件管理系统在磁盘上建立位示图bitmap记录磁盘的使用情况。 若磁盘上物理块的编号依次为0、1、2、…系统中的字长为32位字的编号依次为0、1、2、…字中的一位对应文件存储器上的一个物理块取值0和1分别表示空闲和占用。假设操作系统将2053号物理块分配给某文件那么该物理块的使用情况在位示图中编号为64系统应该将该字的位号5的位置“1 2053号物理块对应字的编号是64号前面的0-2047位已经占满因此第64号字的第0位是2048第1位是2049第2位是2050第3位2051第4位2052第5位2053。
索引文件
结构示意图 索引文件结构的扩展机制能够极大扩充现有容量是操作系统中比较特殊的文件结构。
一般的索引文件结构由13个结点组成其中0 - 9个结点为直接的物理盘块直接索引第10个结点是一级间接索引第11个结点是二级间接索引第12个结点是三级间接索引 如果一个存储结构不使用索引其存储量就是物理块数 * 单位大小。如果每个物理块的单位大小为4K则总空间为52K。
如果引入一级间接索引索引指向具体的物理块号
如果一个地址占用 4 个字节一个物理盘块有 4KB 容量则在第 10 个物理块中就可以存放 1024 份地址则10 号物理块可存储 1024 份容量即1024 X 4KB 4MB容量。
如果引入二级间接索引即索引指向中间索引中间索引再指向具体的物理块号 如果一个地址占用 4 个字节一个物理盘块有 4KB 容量则在第 11 个物理块中就可以存放 1024 份地址每份子地址可以再存储 1024 份二级地址则11 号物理块可存储 1024 * 1024 份容量就是 1024 X 1024 X 4KB 4GB 的容量。 三级间接索引依次类推。
实战
某⽂件系统采⽤多级索引结构若磁盘块的⼤⼩为4K字节每个块号需占4字节采⽤⼆级索引结构时的⽂件最⼤长度可占⽤ 个物理块。 答案1024*1024 解析每个索引表可以存4K/41024个块号所以⼆级索引可对应1024*1024个物理块。
现有一个文件系统采用索引结点管理模式物理块大小为1KB。每个索引结点有32KB的存储空间每个地址项占4字节磁盘索引块和磁盘数据块大小均为1KB。其中0-4用直接地址索引5-6用一级间接地址索引7用二级间接地址索引逻辑块号为5和261的物理块号在哪里 答案6、7的第一个字块。
解析 逻辑块号从0开始编码物理块号从一开始编码所以逻辑块号5就代表第六块。 每个地址项占4字节磁盘索引块大小均为1KB所以一个物理块可以存放256份地址。 1KB1024字节1024字节/(4字节/块)256块。 第261个逻辑块号的物理块号位置
磁盘
基本概念 盘面号磁头号0 ~ M-1由于一个盘面上只有一个磁头所以盘面号也叫作磁头号 柱面号磁道号0 ~ L-1磁道编号通常是从外沿向内进行编号 扇区号1 ~ N对于同一条磁道可以分为若干扇区对于扇区分成三个字段
标识符字段存放扇区的标识信息 校验字段检验磁盘读写操作的正确性 数据字段存放数据信息
存储容量计算公式 存储容量 磁头数 × 磁道柱面数 × 每道扇区数 × 每扇区字节数
扇区编址方式
CHS方式柱面/磁头/扇区××磁道柱面××磁头××扇区DOS中称为绝对扇区表示法。LBA方式相对扇区号以磁盘第一个扇区0柱面、0磁头、1扇区作为LBA的0扇区后面的扇区依次编号
LBA扇区号与CHS间的转换
CHS转换为LBA若L、M、N分别表示一个磁盘的柱面数磁道数、盘面数磁头数、扇区数则第i柱面j磁头k扇区所对应的LBA扇区号为 L B A ( i ∗ M ∗ N ) ( j ∗ N ) k − 1 LBA(i*M*N)(j*N)k-1 LBA(i∗M∗N)(j∗N)k−1LBA转换为CHS若知道LBA扇区号则对应的柱面号、磁头号、扇区号分别是 柱面号 i i n t ( L B A / ( M ∗ N ) ) iint(LBA/(M*N)) iint(LBA/(M∗N))磁头号 j [ L B A m o d ( M ∗ N ) ] / N j[LBAmod(M*N)]/N j[LBAmod(M∗N)]/N扇区号 k [ L B A m o d ( M ∗ N ) ] m o d N 1 k[LBAmod(M*N)]modN1 k[LBAmod(M∗N)]modN1
磁盘类型
按照磁头是否需要移动进行分类
固定头磁盘对于同一盘面上的不同磁道都有相应位置固定的磁头进行读写如上图中的黑色磁头和蓝色磁头分别读取一个磁道对多条磁道进行读写的时候磁头不需要移动位置。所以对于一个盘面上的多条磁道可以并行进行读取访问速度较快。同样价格也较高 移动头磁盘对于移动头磁盘它的磁头是可以沿着径向臂进行径向移动所以只需要使用一个磁头就可以访问所有的磁道。但是同一时间只能访问一个磁道只能实现顺序读写读写速度较慢造价较低。计算机中使用的磁盘大多数都是移动头磁盘
磁盘访问时间
以移动头磁盘为例
寻道时间Ts把磁头移动到指定磁道上所经历的时间。 T s m ∗ n s T_sm*ns Tsm∗ns m一般磁盘0.20.3高速磁盘m≤0.1 s磁臂启动时间约为2ms3ms
磁盘读写操作中绝大部分时间都是寻道时间所以对寻道时间进行优化可以有效的大幅减少访问时间。
旋转延迟时间Tr指定扇区移动到磁头下面所经历的时间。 也就是要读取的蓝色扇区移动到黑色磁头下面所要经历的时间。旋转延迟时间最长为 1 r \frac{1}{r} r1最短为0。平均旋转延迟时间为 T r 1 2 r T_r\frac{1}{2r} Tr2r1r表示转速。
传输时间Tt把数据从磁盘读出或向磁盘写入数据所经历的时间。 T t b r N T_t\frac{b}{rN} TtrNb b表示要读写的字节数N表示一条磁道上总的字节数
因此可将磁盘访问时间 T a T_a Ta表示为 T a T s 1 2 r b r N T_aT_s\frac{1}{2r}\frac{b}{rN} TaTs2r1rNb
磁盘调度
当有大量磁盘I/O请求时恰当选择调度顺序以降低完成这些I/O服务的总时间。
磁盘调度方式主要有以下两种
移臂调度当同时有多条磁道访问请求时确定磁道访问顺序以减少平均寻道时间旋转调度当一条磁道上有多个扇区访问请求时确定扇区访问顺序以减少旋转延迟时间。按照扇区距离磁头的位置的偏差来进行调度。
旋转调度算法较为简单只是按照扇区距离磁头的位置的偏差来进行调度。
磁盘调度算法
主要有两类
移臂调度在满足一个磁盘请求时总是选取与当前移动臂前进方向上最近的那个请求使移臂距离最短旋转调度在满足一个磁盘请求时总是选取与当前读写头旋转方向上最近的那个请求是旋转圈数最少
移臂调度算法
FCFS
先来先服务First-Come First Served
假设当前磁道在100号磁道磁头正向磁道号增加的方向由外向里移动。现依次有如下磁盘请求队列23, 376, 205, 132, 61, 190, 29, 4, 40
则磁盘调度顺序为23, 376, 205, 132, 61, 190, 29, 4, 40
寻道距离Ts (100-23) (376-23) (376-205) (205-132) ... (40-4)
平均寻道距离 Ts / 9。
由于先来新服务算法并没有对磁盘访问进行优化所以它可能会得到比较长的寻道距离。
SSTF
最短寻道时间优先算法在选择下一条磁道的时候总是访问与当前磁盘距离最近的磁盘进行访问。
对于上例其磁盘调度顺序为132, 190, 205, 61, 40, 29, 23, 4, 376
寻道距离Ts (132-100) (190-132) (205-190) ... (23-4) (376-4)
最短寻道距离优先可以保障每一次的寻道距离最短但是不能够保障最后系统得到的平均寻道距离最短。
存在的问题
不能保证平均寻道距离最短会产生饥饿现象 如果系统不断的出现在100号磁道附近的磁道访问请求则原先较远的磁道请求如205 376 就会处于很长时间的等待中影响磁盘的机械寿命不考虑磁头的移动方向可能会造成磁盘频繁的改变其磁头运动方向。从而影响磁盘的机械寿命
SCAN
扫描算法又称为电梯算法是目前操作系统中用的比较广泛的一种磁盘移臂调度算法。其在对下一条磁道进行选择时需要判断
欲访问磁道与当前磁道的距离磁头当前的移动方向即保持处于磁道号增加或减少状态
同样对于上例其磁盘调度顺序为132, 190, 205, 376, 61, 40, 29, 23, 4
寻道距离Ts (132-100) (190-132) (205-190) (376-205) (376-61) (61-40) ... (23-4)
N-Step-SCAN
N步扫描算法为了克服扫描算法和最短寻道时间有限算法的磁臂粘着现象而引入的。
磁臂粘着现象就是指当系统不断的提出对当前磁道的访问那么磁头会一直处于该磁道上进行磁道访问请求导致其它磁道的访问被推迟的现象。
N步扫描算法的算法思想将磁盘请求队列分成若干个长度为N的子队列磁盘调度将按FCFS算法依次处理这些子队列 而每处理一个子队列时又采用SCAN算法。
如对于上例若其子队列的长度为4则可以分为3个队列 它就会首先处理第一个队列中的四个磁道请求再处理第二个队列和最后的第三个队列。其对于每一个队列的处理都是按照扫描算法来进行处理。
FSCAN
该算法实质上是N步SCAN算法的简化 它只将磁盘请求队列分成两个子队列
由当前所有请求磁盘形成的队列由磁盘调度按SCAN算法进行处理在扫描期间将新出现的所有磁盘I/O请求 放入另一个等待处理的请求队列
如上例先把所有的磁盘请求放在第一个队列中对其应用扫描算法进行磁盘调度。若访问过程中出现的新的磁盘请求就放在下面的新队列中当第一个队列全部访问完再处理第二个队列。
旋转调度算法
当同一磁道柱面上有多个扇区请求时总是选取与当前读写头最近的那个I/O请求使旋转圈数最少。
例对磁盘访问的5个请求若磁头在1号柱面先按SCAN算法做移臂调度柱面号排序再进行旋转调度块号排序则调度顺序如下
实战
在磁盘调度管理中应先进行移臂调度再进行旋转调度。假设磁盘移动臂位于21号柱面上进程的请求序列如下表所示。如果采用最短移臂调度算法那么系统的响应序列应为。
4个备选项为 ②⑧③⑤⑦①④⑥⑨ ②③⑧④⑥⑨①⑤⑦ ②⑧③④⑤①⑦⑥⑨ ①②③④⑤⑥⑦⑧⑨
请求序列柱面号磁头号扇区号①1789②2363③2396④32105⑤1784⑥32310⑦1779⑧23104⑨38108
解析 应先进行移臂对应柱面调度再进行旋转对应磁头、扇区调度。由表可知 ①⑤⑦在17柱面21-174 ②③⑧在23柱面23-212 ④⑥在32柱面32-219 因此按最短移臂算法应该是23柱面、17柱面、32柱面、38柱面。应该是②⑧③⑤⑦①④⑥⑨。
任务调度
前驱图
实战
某计算机系统中有一个CPU、一台扫描仪和一台打印机。现有三个图像处理任务每个任务有三个程序段扫描 S i S_i Si图像处理 C i C_i Ci和打印 P i P_i Pi i 1 , 2 , 3 i1, 2, 3 i1,2,3。下图为三个任务各程序段并发执行的前驱图其中可并行执行的直接制约的间接制约。 解析 前趋图是一个有向无循环图图由结点和结点间的有向边组成结点代表各程序段的操作而结点间的有向边表示两程序段操作之间存在的前趋关系-。两程序段 P i P_i Pi和 P j P_j Pj的前趋关系表示成 P i − P j P_i -P_j Pi−Pj其中 P i P_i Pi是 P j P_j Pj的前趋 P j P_j Pj是 P i P_i Pi的后继其含义是 P i P_i Pi执行完毕才能由 P j P_j Pj执行。
可见S1执行完毕后计算C1与扫描S2可并行执行C1与S2执行完毕后打印P1、计算C2与扫描S3可并行执行P1、C2与S3执行完毕后打印P2与计算C3可并行执行。
直接制约 间接制约
可见 直接制约C1和P1受到S1、C2和P2受到S2、C3和P3受到S3 间接制约S2和S3受到S1、C2和C3受到C1、P2和P3受到P1
参考
操作系统-文件系统-磁盘管理
