操作系统-=《操作系统整理.docx

该【操作系统-=《操作系统整理 】是由【guoxiachuanyue015】上传分享，文档一共【15】页，该文档可以免费在线阅读，需要了解更多关于【操作系统-=《操作系统整理 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第一章操作系统概述
识记:
(目标?)和OS的定义:
操作系统是一组计算机程序的集合
1)控制和管理计算机的硬件和软件资源,
2)合理地组织计算机的工作流程,使之可以得到更加合理的共享及保护,以及尽量好的性能。
3)向应用程序和用户提供方便、快捷、友好的使用接口。
OS有哪3种基本类型及其目标:
1)批处理操作系统:提高系统资源利用率和作业吞吐率
2)分时操作系统:满足用户交互的及时响应
3)实时操作系统:提高系统的及时性和可靠性(?)
OS有哪4个特征:并发性、共享性、虚拟性、异步性(随机性)
OS有哪5大功能:(6?)
进程管理、存储管理、文件管理和设备管理是操作系统的基本功能,网络通信与服务、安全与保护是现在主流操作系统的衍生功能。
第二章进程管理
识记:
进程的定义:可并发执行的程序在某个数据集合上的一次执行过程,是操作系统资源分配、保护和调度的一个基本单位进程的基本状态:就绪状态,运行状态,阻塞状态(等待状态)
进程的组成:进程控制块(PCB)+程序块+数据块+堆栈
进程控制块的组织方式:线性方式(有?)
链接方式:单向,或双向
索引方式:对具有相同状态的进程,分别设置各自的PCB索引表,表明PCB在PCB表中的地址
原语的定义:由若干条指令所组成,用来实现某个特定功能,在执行过程中不可被中断的程序段
进程互斥的定义:若干进程因相互争夺独占型资源而产生的竞争制约关系
(若干个进程要访问同一共享资源时,任何时刻最多允许一个进程访问,其他进程必须等待,直到占有资源的进程释放该资源)
临界资源和临界区的定义;
临界资源:某段时间内只能允许一个进程使用的共享资源
临界区:访问临界资源的代码段
进程同步的定义:为完成共同任务的并发进程基于某个条件来协调其运行进度、执行次序
而等待、传递信号或消息而产生的协作制约关系
理解:
;锁、信号量、管程、消息传递
进程互斥与进程同步的异同点;(?)
异:进程同步是为完成共同任务的并发进程基于某个条件来协调其运行进度、执行次序而等待、传递信号或消息
而产生的协作制约关系,而进程互斥是若干进程因相互争夺独占型资源而产生的竞争制约关系。同:互斥是一种特殊的同步关系一一以一定次序协调地使用共享资源
(S)操作与V(S)操作及其处理的物理意义。(P39)
P(s):将信号量s的值减1,若结果小于0则调用P(s)的进程被阻塞,并进入信号量s的阻塞队列中;若结果大于等于0则调用P(s)的进程继续运行
物理意义:P(s)操作表示进程申请一个资源,求而不得则阻塞进程
voidP(semaphore&s){
--;if()block();〃阻塞本进程并进入S信号量队列
}
V(s):将信号量s的值加1,若结果不大于0则调用V(s)的进程从该信号量阻塞队列中释放,唤醒一个处于等待状态的进程,将其转换为就绪状态,调用V(s)的进程继续运行;若结果大于0,则调用V(s)的进程继续运行。物理意义:V(s)操作表示释放一个资源,若此时还有进程在等待获取该资源,则被唤醒
voidV(semaphore&s){
++;
if(<=0)wakeup();〃唤醒s信号量队列中的一个进程入就绪队列
}
简单应用:利用信号量解前趋图问题。(?)
利用信号量描述程序和语句之间的前驱关系
如果进程p1中有语句s1,p2中有语句s2,为实现s1执行后再执行s2,只需让p1,p2进程共享一个公共信号量S,且init(S)=0
Pl
例题:在公共汽车上,司机和售票员的工作流程如下图所示。为保证乘客的安全,司机和售票员应协调工作:
停车后才能开门,关车门后才能行车。用PV操作来实现他们之间的协调
分析:司机启动车辆的动作必须于售票员关车门的动作取得同步,售票员开车门的动作也必须与司机停车取得同步
itemB[k];〃缓冲区,长度k
解:设信号量:
S1:是否允许司机启动汽车,初值为0
S2:是否允许售票员开门,初值为0
driverO
{wbik(1)
{
P(S1);启动汽车;正常行车匸到站停车匸
V(S2);}
bi]snianO{
while(1){
关车门;
V(S1);
售票
P(S2)f开车门匸上下乘客;}
int*1=0;
ints2=0;
main{cobegindikerO;busnianO;coend
itemB[k];〃缓冲区,长度k
itemB[k];〃缓冲区,长度k
综合应用:.
能写和理解计算、打印问题程序,生产者/消费者问题程序;(P43)
取出第果
打印
(生产者进程可以是计算、发送进程,消费者进程可以是打印、接受进程)计算、打印问题程序
计算
条件=bnf^
设信号量bufempty=l(表示缓冲区数)buffull=0(表示运算结果数)processC(){processP(){
while(true){P(buffull);
取出buf中的数据置空标记,打印
V(bufempty);
}
}
while(true){P(bufempty);
计算;buf计算结果
V(buffull);
}
}
生产者/消费者问题:
m个生产者和n个消费者共享k件产品缓冲区,只要缓冲区未满,生产者就可送入缓冲区;只要缓冲区不空,消费者就可从缓冲区取走并消耗产品
解:互斥信号量mutex:限制生产者和消费者互斥地对缓冲区进行存取,初值为1
同步信号量empty:保证生产者不向已满地缓冲区中放入产品,初值为k
同步信号量fuH:保证消费者有产品消费,初值为0
in和out:放入缓冲区指针和取出缓冲区指针
itemB[k];〃缓冲区,长度k
semaphoreempty=k;〃可用的空缓冲区数semaphorefull=0;〃缓冲区内可用的产品数
semaphoremutex=1;〃互斥信号量intin=0;〃缓冲区放入位置
intout=0;〃缓冲区取出位置
processconsumer」。{while(true){
P(full);
P(mutex);take()fromB[out];out=(out+1)%k;V(mutex);V(empty);consume。;
}
}
cobeginprocessproducer_i(){while(true){produce。;〃生产一个产品
P(empty);〃申请空缓冲区P(mutex);〃申请互斥使用缓冲区appendtoB[in];〃产品放入缓冲in=(in+1)%k;〃更新缓冲区指针
V(mutex);
V(full);
}
}
coend
;(P46)
有五个哲学家围坐在一圆桌旁,桌子中央有一盘通心面,每人面前有一只空盘子,每两人之间放一个筷子。每个哲学家思考、饥饿,然后想吃通心面。为了吃面,每个哲学家必须获得两个筷子,规定每人只能直接从其左边或右边去取筷子
解:筷子是共享资源,需要互斥访问(信号量解决互斥问题)。引入五个互斥信号量。
给所有哲学家编号,奇数号的哲学家必须首先拿左边的筷子,偶数号的哲学家则反之
semaphorechopsticks[5];
for(inti=0;i<5;i++)chopsticks[i]=1;
cobegin
processphilmac_i(){〃i=0,l,2,3,4
think();
if(i%2==0){
P(chopsticks[i]);
P(chopsticks[(i+1)%5]);
}
else{
P(chopsticks[(i+l)%5]);
P(chopsticks[i]);
}
eat();
V(chopsticks[i]);
V(chopsticks([i+1]%5);
}
coend
。(P45)
有两组并发进程,读进程与写进程,共享一个文件,为防止出错,要求:
1)允许多个读进程同时读文件;
2)只允许一个写进程写文件;
3)写进程在没有写完成之前不允许其他读写;
4)写之前应该让所有已经在读或写的进程操作完成。
解:引入一个计数器和两个信号量解决此问题:
信号量:ws:允许写信号量,初值为1
mutex:互斥访问rc计数器信号量,初值为1
计数量:readcount:读进程计数器
intreadcount=0;
〃读进程计数器
processwriter_j(){P(ws);
写文件;
V(ws);
}
semaphorews=1,mutex:=1;cobegin
processreader_i(){
P(mutex);readcount++;
if(readcount==1)P(ws);V(mutex);
读文件;
P(mutex);readcount--;
if(readcount==0)V(ws);V(mutex);
}
coend
处理器调度
识记:
作业调度的定义;
按一定的算法对外存输入井上的大量后备作业进行选择调入内存,并为它们创建进程、分配必要的资源,再将新创建的进程排在就绪队列上,准备执行(or:按照某种调度算法从后备作业队列中选取作业,使其进入内存运行)
进程调度的定义;
用来决定就绪队列中的哪个进程应获得处理机,再由分派程序执行把处理机分配给该进程的具体操作
中级调度的定义;
为了提高内存的利用率和系统吞吐量,根据存储资源量和进程的当前状态来决定辅存和主存中进程的对换
进程调度的两种方式;非抢占方式,抢占方式
作业平均周转时间的公式T;T=(工Ti)/n
作业平均带权周转时间的公式W;W=(工Wi)/n
综合应用:
作业采用先来先服务、短作业优先、优先级高优先的调度算法时计算一批作业的T和Wo(P55)
(一)先来先服务算法(FCFS)
■【例】系统中现有5个作业A、B、C、D、E同时提交(到达顺序也为ABCDE),其预计运行时间分别10、1、
2、1、5个时间单位,如表所示,计算FCFS调度下作业的平均周转时间和平均带权周转时间
作业:TD
预计需运行时间
A
10
&
1
C
2
b
1
E
5
解:设作业到达时刻为0,根据定义计算,系统运行情况
业DTI
运行时间
开始时间
完戚时间
同转时间
周转时间
A
10
0
0
.10
10
t
BJ
1
10
10
11
11
11
C
2
11
11
13
13
65
b
1
13
13
14
14
14
E\
5
14
14
19
19
P38
▽J埴法17间平均带杈周转时
IV
T=:10*11+13+14+19)/5==1+11+-141-'/5=
■【例】在单道环境下,某批处理系统有四道作业,已知它们的进入系统的时刻、估计运算时间如下:

进入时刻(h>
运行时间g
i


冷


3

斗


用FCFS算法计算作业的运行情况、平均周转时间和平均带权周转时间
解:1)调度次序:1234
2)完成时间图:
3)T=2+2++)F4=(h)
W=(2/2+2/++=(h)
(二)短作业优先算法(SJF)
■【例】设有5道作业
作业名
提交时间
运行时
P1
mi时

P2
】0一3时
0占小时
P*

P4
]山6时
山环时
P5


P1
P2
P5
P3
解:根据SJF原则,调度次序为:P1-P2-P5-P4-P3°"。花丨1"
T=(++++)—5=(h)W=(++++)—5=(h)
(三)优先级高优先算法(HPF)
【例】系统的进程调度采用抢占式优先权调度算法,优先数越小优先级越高,其参数如表所示,
求平均周转时间和平均等待时间
作业:CD
提交(到达}时间
预计需运行时闫
优先数
A
0
7
3
B
2
4
2
C
斗
1
4
D
5
4
1
4
D
色
|C|
31
11
1i
a
9a
解:作业进程综合调度示例:
作0D
提交(到达}时间
运行结束时间
A
0
15
B
2
10
C
4
16
D
5
9
平均周转时间T=(15+8+12+4)/4==(8+4+11+0)/4=
W
死锁
理解:
死锁检测;(P66)
对资源的分配不加任何限制,也不采取死锁避免措施,但系统定时地运行一个“死锁检测”程序,判断系统内是否已出现死锁,如果检测到系统已发生了死锁,再采取措施解除它。关键难点:确定何时运行死锁检测算法
死锁解除;(P66)重启、撤销、剥夺、回滚
死锁预防;(P62)
主要方法:(都会造成系统资源利用率和吞吐率降低)
(1)破坏互斥条件:使资源可同时访问而不是互斥使用,受资源本身特性限制,可行性较差
(2)破坏占有并请求(等待):静态分配(进程必须获得所需要的所有资源才能运行),严重降低资源利用效率
(3)允许剥夺:剥夺式调度算法,只适用于CPU和内存
(4)阻止环路等待:层次分配策略,低效,限制新设备类型的增加,使执行速度变慢,并可能在无必要的情况下拒绝资源访问
死锁避免。(P63)常见的方法:银行家算法
不是通过对进程随意强加一些规则,而是通过对每一次资源申请进行认真的分析来判断它是否能够完全的分配,在确定不会发生死锁的情况下,才把资源真正分配给进程,从而避免死锁的发生
综合应用:银行家算法的具体应用。(必考)(P63-65)
多种资源的银行家算法的具体过程:
请求的K1〉申请量超过最大需求量吋出错”否则转步骤(2);
官签性](2)当申请超过当前系统所拥有的可分配量时,挂起进程,程翦处于等待态,否则转步骤〔3),
<3)垂统对円进程谙求瓷瀕进行试探性分配,执行
预分配]
Possession[i.*]=Possession[i,*]+Request[*]
Available[*]^Available[*]-Request[*]
执行安全性测试算法(5),进程円等待;
【例】设有五个进程{P0,片,P2,P3,P4},三类资源{A,B,C},各拥有资源数{10,5,7},
(1)在T0时刻系统的资源分配情况如下:当前状态为:Available={3,3,2}
进程
A
Chiiu
Possession
5hortage=Cki-Pki
B
C
A
BC
A
B
C
P0
7
5
3
0
in
7
4
3
P1
7
■
2
2nn
1
7
■
■
P2
9
(J
2
302
6
0
i)
P3
222
211
0
1
1
P4
4
3
3
0
2
4
3
1
则目前系统处于安全状态,因为存在安全序列:{P1,P3,P0,P2,P4},满足安全性条件
假定进程P1又要申请1个A类资源和2个C类资源,判断此申请能否获得批准?
首先检查Request的有效性:Request1(1,0,2)v=S1(1,2,2),Request1(1,0,2)v=Avaliable(3,3,2)尝试分配后的状态是:Available=(2,3,0)
进程
CurrentAvl
S=Cm-Pw
POSseSSiO
n
Currentavil+possession
Possible
A
B
C
A
B
C
A
B
c
A
B
C
7
4
3
7
4
3
0
1
0
7
5
3
T
Fi
3
3
2
1
2
2
2
0
0
5
3
2
T
內
7
5
3
6
D
0
3
0
2
10
5
5
T
f3
5
3
2
0
1
pl
2
1
1
\
$
T
Pa
10
5
5
4
3
1
0
0
2
10
5
1
T
Resource=(10,5,7)
仍存在一个执行序列{P1,P3,P4,P0,P2},满足安全性条件,因此方案可行
如果进程P4再发出资源请求:Request4(3,3,0)能否分配?
系统剩余资源向量Available(2,3,0)小于该请求向量,故无法通过有效性检查,P4进程阻塞
进程P0请求资源Request0(0,2,0),能否满足分配?
虽可通过有效性检查,但试分配后,系统的剩余资源不能满足任何进程的需求缺口,
因而无法找到一个执行序列,将导致系统进入不安全状态,所以不能按P0的请求进行资源分配
第三章存储管理
识记:
3级存储器在容量、速度和价格方面的比较;
更快的访问速度
逻辑地址和物理地址的定义;
逻辑地址:目标程序使用的地址
物理地址:程序在物理内存中的实际存储位置
地址重定位及静态重定位和动态重定位;
地址重定位:把程序和数据的逻辑地址转换为物理地址,使程序正确运行的过程
静态重定位:在用户作业装入内存时由装入程序(装配程序)实现从逻辑地址到物理地址的转换,地址转换在作业执行前一次完成
动态重定位:程序执行过程中,CPU在访问程序和数据之前才实现地址转换
存储管理的4大功能;
1)内存的分配和回收:
2)提高内存的利用率:
3)通过虚拟存储技术“扩充”内存容量。
4)内存信息保护
虚存的定义;具有请求调入功能和置换功能,能够从逻辑上对内存空间进行扩展,
允许用户的逻辑地址空间大于物理内存地址空间的存储器系统
提取页面的两种策略;(P103)请求页调入、预先页调入
页式、段式虚存段表表目各个表项的作用;
1)页式:(P99)
♦状态位:用于标志一页是否已装入内存
♦夕卜存地址:页在外存中的地址
修改位:页在内存中是否被修改过的标志,用来确定如果该页被换出内存时,是否需要再回写入外存
访问字段:标志页在内存时是否被访问过,用于进行页面置换时考虑是否将该页换出内存。
如果该页被访问过,在进行页面置换时,系统会考虑该页可能以后会被再次访问而不将其换出
2)段式:(P109)(?)
♦段号,段长
主存始址(在内存中的起始地址),辅存始址(在外存中的起始地址)
♦特征位:该段是否在内存。0(不在主存);1(在主存);
存取权限:00(可执行);01(可读);11(可写);
♦扩充位:该段是否可扩充。0(固定长);1(可扩充);
标志位:该段是否被修改过,是否移动。00(未修改);01(已修改);11(不可移动)
共享标志:该段能否共享。
段页式虚存管理的基本思想。
1)虚地址以程序的逻辑结构划分成段(段页式存储管理的段式特征)
2)实地址划分成位置固定、大小相等的页框(段页式存储管理的页式特征)
3)将每一段的线性地址空间划分成与页框大小相等的页面,于是形成了段页式存储管理的特征。
段内页号9)
贰内低移(cl)
理解:
实现虚存的基本方法;
请求分页虚拟存储管理、请求分段虚拟存储管理、请求段页虚拟存储管理
分页存储管理的基本方法;(P87)
页式存储管理采用了对进程的逻辑地址空间分页,对内存的物理空间分块,页的大小等于块大小等基本思想,通过页表和地址转换机构实现逻辑地址到物理地址的变换,能够有效地利用内存空间。
页式虚存的页表结构;
除了要完成从逻辑地址到物理地址的转换外,还需要提供页面置换的相关信息。
因此,页表中除了有页号和物理块号等信息外,还增加了页的状态位、外存地址、修改位、访问字段等信息
頁号
辆理块号
恼位
外存地址
修改位
访问字段
段式虚存管理方法;
把作业的所有分段的副本都存放在辅助存储器中,当作业被调度投入运行时,首先把当前需要的一段或几段装入主存,在执行过程中访问到不在主存的段时再把它们装入。
动态地址转换过程。(P78)(?)(地址转换有静态重定位和动态重定位两种方式)
程序执行过程中,CPU在访问程序和数据之前才实现地址转换,称为动态重定位。
动态重定位必须借助于硬件地址转换机构来实现,硬件系统中设置了一个定位寄存器,当操作系统为某程序分配了一块内存区域后,装入程序把程序装入到所分配的区域中,然后把该内存区域的起始地址置入定位寄存器中。在程序执行过程中需要进行地址转换时,只需将逻辑地址与定位寄存器中的值相加就可得到物理地址。
简单应用:页式虚存的动态地址的转换过程。(P101)