操作系统-精髓与设计原理
操作系统利用一个或多个处理器的硬件资源,为系统用户提供一组服务,它还代表用户来管理辅助存储器和输入输出(
Input/Output, IO
)设备。因此,从最顶层看,一台计算机由处理器、存储器和输入/输出部件组成,每类部件都有一个或者多个模块。这些部件以某种方式互联,以实现计算机执行程序的主要功能。
主要探讨了操作系统中关于memory
管理、淘汰算法及虚拟内存机制、线程和进程内容(并发控制):
一、进程管理
2021.下列操作中,操作系统在创建新进程时,必须完成的是(a,b)。a.申请空白的进程控制块 b.初始化进程控制块 c.设置金策红状态为执行态。
Note: 进程的创建步骤为:申请一个空白的
PCB
(进程控制块)、为新进程分配资源(程序、数据及用户栈分配必要的内存)、初始化PCB
块以及将新进程插入到就绪队列。
2021.对于"中断处理结束"、"进程阻塞"、"进程执行结束"和"进程时间片用完"的操作,会引起进程调度程序的执行。此外,常考察进程状态的转换,分时系统CPU
时间片用完或主动出让CPU
,线程会由执行态转换为就绪态。用户级线程完全由用户管理,多线程模型的多对一模式,当一个线程使用内核服务时被阻塞,则整个进程都会被阻塞。
死锁产生的必要条件有:a.互斥条件、b.不剥夺条件、c.请求保持条件、d.循环等待条件,死锁的处理策略有死锁预防、避免死锁和死锁的检测及解除。对于死锁避免,常会考察安全序列和银行家算法。
2020.系统中有A
、B
类资源各6
个,t
时刻资源分配及需求情况如表所示。计算安全序列时,会涉及资源相关矩阵如Need
=Max
-Allocated
,Need
矩阵结果为:{(4, 4), (3, 1), (3, 4)} - {(2, 3), (2, 1), (1, 2)} = {(2 1), (1, 0), (2,2)}。
进程 | A已分配数量 | B已分配数量 | A需求总量 | B需求总量 |
---|---|---|---|---|
P1 | 2 | 3 | 4 | 4 |
P2 | 2 | 1 | 3 | 1 |
P3 | 1 | 2 | 3 | 4 |
A
、B
各类资源各6
个,除去3
个进程已分配的资源,还剩A
、B
为(1, 0),故只有P2
满足条件,分配给P2
其执行完成后,A
、B
的资源为(3, 1)。此时满足P1
的要求,分配给P1
。等其执行完成后,最后将所有资源分配给P3
,最后构成安全序列为(P1,P2,P3)。
进程调度的指标,周转时间:指作业从提交到作业完成所经历的时间,包含作业等待、在就绪队列中排队、在处理机上运行等操作花费时间的总和,周转时间=作业完成时间 - 作业提交时间。平均周转时间指多个作业周转时间的平均数值,平均周转时间=(作业1周转时间 + .... + 作业n周转时间)/n,带权周转时间指作业周转时间与作业实际运行时间的比值,带权周转时间=作业周转时间/作业实际运行时间。
2019.系统采用二级反馈队列调度,队列Q1采用时间片轮转算法,时间片为10
ms;就绪队列Q2采用短进程优先调度算法,系统优先调度Q1队列的进程,当Q1为空时才会调度Q2的进程,系统依次创建P1,P2后即开始进行调度,P1、P2需要的CPU
时间分别为30
ms和20
ms,则其平均等待时间为(15ms)
Note: 多级反馈队列调度,Q1通常为时间片轮询调度,若进程在
1
个时间片执行不完,则会将其放入Q2中进行调度。P1执行时间为 = Q1执行10ms + Q2等待10ms + Q2中等待P2执行10ms(SJF) + 自己执行20ms = 50ms,P2执行时间为 = Q1等待P1执行10ms + Q1自己执行10ms + Q2自己执行10ms = 30ms。平均等待时间为 = (10ms+10ms+10ms) / 2 = 15ms。
信号量同步P
操作和V
操作,wait(S)
和signal(S)
访问。利用信号量实现进程间资源同步,P1
和P2
执行具有依赖关系,则P1
中处理完后调用V(S)
、P2
在执行过程中用P(S)
等待执行。用P
和V
操作实现进程间互斥,对于临界资源可分别用P
和V
操作保护。
semaphore S=0; // 初始化信号量
// (同步)实现P1、P2间的同步,只有x执行完后,y语句才可继续执行
P1() { x语句执行; V(s); ... } P2() { z语句执行; P(S); y语句; }
// 实现进程P1、P2资源访问互斥特点,在访问临界资源前,都需加锁,仅有一个进程可进入临界区。
P1() { ... P(S); 进程P1的临界区; V(S); }
P2() { ... P(S); 进程P1的临界区; V(S); }
利用信号量实现前驱关系,对依赖关系S1->S3,S1->S2,S2->S5,S3->S5设置变量为a, b, c, d,用信号量实现的逻辑如下:
semaphore a=b=c=d=0; // 信号量a, b, c, d分别表示进程间依赖关系
S1() { ...; V(a); V(b); } // S1的逻辑执行完后,通过信号量a, b 通知S2、S3可继续执行
S2() { ...; P(b); V(c); } // S2处于阻塞状态,直到S1执行完成调用signal(a)变量
S3() { ...; V(a); V(d); } // S3、S4的逻辑也是同理
S5() { ...; P(c); P(d); ..; }
二、内存管理
编译后的程序需经过链接才能装载,而链接后形成的目标程序中的地址也就是逻辑地址:
- 静态重定位特点,要求必须给作业分配全部内存空间,若无法分配则不能装入改作业,此外,作业一旦进入内存,整个运行期间就不能在内存中移动,也不能再申请内存空间。
- 动态重定位,只有在程序真正执行时,才会将逻辑地址转换为绝对地址,这种转换需要一个重定位寄存器的支持。程序运行之前可以只装入它的部分代码,然后在运行期间动态申请分配内存。
基本分页存储管理方式(含二级分页):
固定分区会产生内部碎片,动态分区会产生外部碎片,都会产生内存碎片。分页的**,将主存空间划分大小相等且固定的块,块相对较小,作为主存的基本单位。引入二级分页,主要是为了避免页表项太多,占用过多内存空间。
分页存储的几个基本概念,页、地址结构、页表,系统中通常设置一个页表寄存器(PTR),存放页表在内存的起始地址和页表长度,地址转换均是由硬件自动完成:
- 进程中的块称为页(Page),内存中的块称为页框(Page Frame),外存也以同样的单位进行划分,直接称为块(Block)。
- 地址结构包含两部分,前一部分为页号P,后一部分为页内偏移量W,地址长度为32位,地址结构决定了虚拟内存的寻址空间有多大。
- 系统为每个进程建立一张页表,它记录页面在内存中对应的物理块号,页表一般存放在内存中。页表由两部分组成,页号和块号。
若页面大小L
为1KB
,页号2
对应的物理块为b=8
,计算逻辑地址A=2500
的对应的物理地址E
?计算页表页号P = 2500/1k = 2,计算页内偏移W = 2500 % 1k = 452。然后查页表项,页号2对应的物理块为8,起始地址从0开始时,E = 8*1024 + 452 = 8644。
基本分段存储管理方式及段页式:
分页管理方式是从计算机的角度考虑设计,目的是提高内存利用率,分段管理方式的提出则考虑了用户和程序员,以满足编程、信息共享保护。分段内存管理的基本概念:
- 段式管理按用户进程中的自然段划分逻辑空间(主程序、子程序、栈和一段数据等),段内要求连续,段间不要求连续,其逻辑上由段号
S
与段内偏移量W
两部分组成。 - 逻辑空间与内存空间映射的段表,段表项包括“段号”、“段长”和“本段在主存的始址”。
- 地址变换机构,实现进程从逻辑地址到物理地址变换的功能,在系统中设置段表寄存器,存放段表始址
F
和段表长度M
。
2021.在采用二级页表的分页系统中,CPU
页表基址寄存器中的内容是当前进程的一级页表的起始物理地址(页表在内存中的首地址)。对于动态分区分配算法,最容易产生内存碎片的是最佳适应算法。
段的共享与保护,段的共享是通过两个段表中相应表项指向相同段来实现的,当一个作业正从共享段中读数据时,必须防止另一个作业修改此共享段的数据。页式存储管理可有效提高内存利用率,而分段存储管理能反映程序的逻辑结构、有利于段的共享,段页式的管理方式是将两种分配方式的优点结合起来。
8.(计算) 在某页式管理系统中,假定主存为64KB
,分成16块,块号为0,1,2,...,15,设某进程有4
页,其页号为0,1,2,3,被分别装入主存的第9,0,1,14块。问题:1)该进程的总长度是多大?2)写出该进程每页在主存的始址。3)若给出逻辑地址(0,0)(1,72)(2, 1023)(3,99),请计算出相应的内存地址。
Note:页面大小为(64 / 16)= 4KB,该进程共有
4
页,所以该进程的总长度为4 * 4 = 16KB。页面大小为4KB,因此低12
位为页内偏移地址;主存分为16
块,因此内存物理地址的高4
位为主存块号。在页表中,页号0
对应第9
块,因此内存中的始址为:1001 0000 0000 0000(此处为针对页表的计算,不涉及页内偏移);逻辑地址(1,72)实际对应内存地址(0, 72)= 0000 0000 0100 1000B。
虚拟内存管理基于局部性原理,时间局部性、空间局部性。解释:某数据被访问过,不久后该指令可能再次执行,虚拟存储器具有三个特征:多次性(作业被允许分多次调入)、对换性(作业运行时可换出、换进)、虚拟性(从逻辑上扩充内存的容量),虚拟内存的实现需建立在离散分配的内存管理方式的基础上。
当进程访问的页面不在主存中,且主存中没有可用的空闲帧时,正确的处理顺序为:缺页中断 -> 决定淘汰页 -> 页面调出 -> 页面调入。在页面置换策略中,所有的置换算法都可能产生抖动。FIFO
算法存在Belady
现象,虚拟存储器的最大容量由计算机的地址结构决定。
2015.系统为某进程分配了4
个页框,该进程已访问的页号序列为 2, 0, 2, 9, 3, 4, 2, 8, 2, 4, 8, 4, 5,若进程要访问的下一页页号为7
,依据LRU
算法,应淘汰的页号是(2)。可采用便捷法,对页序号从后往前计数,直到数到4
个不同的数字为止(要淘汰的页)。
2022.下列选项中,不会影响系统缺页率的是(D.页缓冲队列的长度),其中A.页面置换算法、B.工作集的大小、C.进程的数量都是影响因素,算法局部性具有较好的命中率。工作集越大,命中率越高,进程的数量越多,缺页率越高。
三、文件管理
软、硬链接文件共享的区别:建立符号链接时,引用计数值直接复制;建立硬链接时,引用计数值加1
。删除文件时,删除操作对于符号链接是不可见的,当以后再通过符号链接访问时,发现文件不存在,直接删除符号链接;但对于硬链接则不可直接删除,引用计数值减1
,若值不为0
,则不能删除此文件,因为还有其它硬链接指向此文件。
2017.若文件f1
的硬链接为f2
,两个进程分别打开f1
和f2
,获得对应的文件描述符号为fd1
和fd2
,则下列叙述中正确的是:a. f1和f2共享同一个内存索引节点 b. fd1和fd2分别指向各自的用户打开文件表中的一项。
文件保护通过口令保护、加密保护和访问控制等方式实现。2014. 在一个文件被用户进程首次打开的过程中,操作系统需做的是将文件控制块(FCB
)读到内存中。2013. 用户在删除某文件的过程中,操作系统不可能执行的操作是:a.删除此文件所在的目录,此文件所在的目录存在其它文件时,是不能进行删除的。
文件分配对应于文件的物理结构,是指如何为文件分配磁盘块,常见的磁盘空间分配方法有三种:连续分配、链接分配和索引分配:
- 连续分配要求每个文件在磁盘上占有一组连续的块,连续分配可用第一块的磁盘地址和连续块的数量来定义,一个文件的目录条目包括开始块的地址和此区域的长度。
- 链接分配采取离散分配的方式,消除了外部碎片,显著提高了磁盘空间的利用率,链接分配又可以分配隐式链接和显式链接两种形式。
- 索引分配解决了链接分配不能有效支持直接访问的问题,它将每个文件的所有的磁盘块号集中放在一起构成索引块(表),索引块的第
i
个条目指向文件的第i
个块。同时,支持多层索引和混合索引。
文件存储空间管理-位示图法,磁盘上所有的盘块都有一个二进制位与之对应。当其值为0
时,表示对应的盘块空闲。当其值为1
时,表示对应的盘块已分配,盘块号转换成位示图中的行号和列号:
i = (b-1) DIV n + 1
j = (b-1) MOD n + 1
磁盘调度算法,一次磁盘读写操作由寻找(寻道)时间、延迟时间和传输时间决定,常用的磁盘调度算法有以下几种:
- 先来先服务算法(FCFS),此算法的优点是具有公平性,不足之处是平均寻道距离大,仅应用在磁盘I/O较少的场合。
- 最短寻找路径优先算法(SSTF),选择调度处理与当前磁头所在磁道距离最近的磁道,以便使每次的寻找时间最短。其性能好于FCFS,但不能保证平均寻道时间最短,可能出现“饥饿”现象;
- SCAN算法(电梯调度算法),在SSTF的基础上规定了磁头的运动方向,可避免“饥饿”现象,但不利于远离磁头一端的访问请求;
- 循环扫描算法(C-SCAN)消除了对两端磁道请求的不公平,识别到电梯顶后,再重新从底部开始;
2017.磁盘逻辑格式化程序所做的工作是:a.建立文件系统的根目录 b.确定磁盘扇区校验码所占位数,新磁盘是空白的,必须分为各个扇区以便磁盘控制器能读和写,这个过程称为低级格式化。第二步是逻辑格式化(创建文件系统),操作系统会将初始的文件系统数据结构存储到磁盘上。
四、输入、输出(I/O)管理
Spooling
假脱机由以下三部分组成:输入井和输出井、输入进程和输出进程、输入缓冲区和输出缓冲区,其主要特点有:提高了I/O
的速度,将独占设备改造为共享设备,实现了虚拟设备功能。Spooling
技术是一种以空间换时间的技术,它开辟了磁盘上的空间作为输入井和输出井。
系统启动过程中程序的执行顺序为:ROM
中的引导程序、磁盘引导程序、分区引导程序、操作系统的初始化程序;将硬盘制作为启动盘时,执行这4
个操作的正确顺序为:磁盘的物理格式化、对磁盘进行分区、逻辑格式化、OS
安装;磁盘扇区的划分是在磁盘的物理格式化操作中完成的,文件系统根目录的建立是在逻辑格式化操作中完成的。
信号量同步相关,如下信号量同步的问题在于wait(S)
方法,当S
<=0
时,关中断后,其它进程无法修改S
的值,while
会陷入一直循环的逻辑。对信号量S
执行互斥访问,是因为其可以被多个进程共享,存在县城安全问题。
Semaphore S;
wait(S) {
关中断; while (S<=0); S=S-1; 开中断;
}
signal(S) {
关中断; S=S+1; 开中断;
}
在用户态下无法使用开/关中断指令实现临界区互斥,因为开中断和关中断指令都是特权指令,在"用户态
"下无法直接执行。
另一种信号量同步问题,有5
个操作A
,B
,C
,D
和E
,操作C
必须在A
和B
完成后执行,操作E
必须在C
和D
完成后执行。请使用信号量wait()
,signal()
操作(P,V操作)描述上述操作之间的同步关系,并说明所用信号量及其初始值。
Semaphore sac = 0; // 控制操作a与c的执行顺序
Semaphore sbc = 0; // 控制操作b与c的执行顺序
Semaphore sce = 0; // 控制操作c与e的执行顺序
Semaphore sde = 0; // 控制操作d与e的执行顺序
Cobegin
Begin操作A:Signal(sac); end
Begin操作B:Signal(sbc); end
Begin wait(sac); wait(sbc); 操作C;
Signal(sce); end
Begin 操作D: Signal(sde); end
Begin wait(sce); wait(sde); 操作E; end
Coend
虚拟地址计算问题,某C
程序中数组a[1024][1024]
的启始虚拟地址为1080 0000H
,数组元素占4
字节,该程序运行时,其进程的页目录项启始地址为0200 1000H
,计算数组元素a[1][2]
的虚拟地址?对应的页目录号和页号分别是什么?对应的页目录项的物理地址是什么?
a[1][2]的虚拟地址为 1080 0000H + (1024*1 + 2) * 4 = 1080 1008H,将
16
进制拍平为二进制,按页目录号、页号、页内偏移量按位数可得对应的页目录号
、页号
信息。
2022.假设某磁盘驱动器有4
个双面盘片,每个盘面有20000
个磁道,每个磁道有500
个扇区,每个扇区可记录512
字节的数据,盘片转速为7200 r/min
(转/分),平均寻道时间为5ms
,请回答下列问题:
1)每个扇区包含数据及其地址信息,地址信息分为3
个字段,这3
个字段的名称分别为:"柱面号"、"盘面号"、"扇区号",由于每个盘面有2000
个磁道,因此该磁盘共有2000
个柱面,因此柱面号字段分别占log2^2000=15
位,由于该磁盘共有4
个盘片,且每个盘有2
个盘面,因此磁头号字段至少有log2^(4*2)=3
位。由于每个磁道有500
个扇区,因此扇区字段至少是log2^500=9
位。
2)一个扇区的平均访问时间包含:寻道时间、旋转延迟(半圈)和读写延迟,该磁盘旋转一周的时间为60*10^3/7200 = 8.33ms
,那么旋转延迟是转半圈的时间8.33/2ms
。每个磁道有500
个扇区,所以读写时间是1/500
*转一圈的时间,那么一个扇区的平均访问时间为:5
+ 8.33/2
+ 8.33/500
= 9.18ms
。
3)当采用周期挪用DMA
方式进行磁盘与主机之间的数据传送,磁盘控制器中的数据缓冲区大小为64
位,则在一个扇区读写过程中,DMA
控制器向CPU
发送了512B/64bit = 64
次总线请求,由于采用周期挪用DMA
方式,因此当CPU
和DMA
控制器都需要访问主存时,DMA
控制器可以优先获得总线使用权。因为一旦磁盘开始读写,就必须按时完成数据传送,否则数据缓存区的数据会发生丢失。
2022.某文件系统的磁盘块大小为4
KB,目录项由文件名和索引节点号构成,每个索引节点占256
字节,其中包含直接地址项10
个,一集、二级和三级间接地址项各1
个,每个地址占4
个字节,该文件系统中子目录stu
包含子目录couurse
和文件doc
,各文件的文件名、索引节点、占用磁盘块如下所示,请回答下列问题:
1)在文件系统中,目录项由文件名和索引结点号构成。目录文件stu
中每个目录项下有两个文件,分别是course
和doc
,因此目录文件stu
中两个目录项的内容分别是:course/2
、doc/10
;
2)文件doc
和文件course1
对应的索引结点号都是10
,说明doc
和course1
对应的索引结点号都为10
,说明doc
和course1
两个目录项共享同一个索引结点,本质上对应同一个文件,而文件course1
存储在30
号磁盘块,因此文件doc
占用的磁盘块的块号x
为30
;
3)需要读取整个磁盘块,先读course1
的索引结点所在磁盘块,再度course1
的内容所在磁盘块。目录文件course
的内容已在磁盘中,即course1
、course2
对应的目录项已在内存中,根据course1
对应的目录项可以知道其索引结点号,即可读入course1
的索引结点所在的磁盘块30
就可以;
4)存取course2
需要使用索引结点的一级和二级间接地址,6MB
大小的文件需要占用6MB/4KB = 1536
个磁盘块,直接地址项可以记录10
个磁盘块号,一级间接地址可以记录4KB/4B=1024
个磁盘块号,二级间接地址块可以记录4KB/4B=1024
个磁盘块号,而1536
刚处于范围之间,因而需要两级间接地址项。