期末复习

第一章•操作系统基本概念•操作系统的目标•操作系统的作用•实时操作系统•操作系统的基本特性•*操作系统的主要功能•前趋图•程序的并发执行及特征•进程的特征与状态•如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？•OS如何进行进程切换？•请结合进程状态图说说何时会发生进程切换？•有没有这样的状态转换，为什么？等待—运行；就绪—等待•请设想一下进程在什么情况下会变为阻塞状态？•阻塞进程在什么情况下会被唤醒？谁来唤醒它？第二章•请说说PCB的定义，包含哪些方面信息，有什么作用。•为什么要引入线程？•任何两个线程切换的开销是大致相当的吗？第二章例1：T0时刻P1请求资源•P1发出请求Request(1,0,2)，执行银行家算法执行安全性算法•可以找到一个安全序列{p1,p3,p4,p0,p2}.系统是安全的，可以将P1的请求分配给它。P4请求资源•P4发出请求Request(3,3,0),执行银行家算法•Available=230•不能通过算法第2步（Request[i]≤Available），所以P4等待。P0请求资源•Request（0，2，0），执行银行家算法进行安全性检查•Available{2,1,0}已不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配•练习：有三类资源A(17)、B(5)、C(20)。有5个进程P1—P5。T0时刻系统状态如下：问(1)、T0时刻是否为安全状态，给出安全系列。(2)、T0时刻，P2:Request(0,3,4)，能否分配，为什么？(3)、在(2)的基础上P4：Request(2,0,1)，能否分配，为什么？(4)、在(3)的基础上P1：Request(0,2,0)，能否分配，为什么？最大需求已分配P1559212P2536402P34011405P4425204P5424314解：(1)T0时刻的出安全系列最大需求已分配NeedP1559212347P2536402134P34011405006P4425204221P5424314110A(17)、B(5)、C(20)Work=233先求出Need和WorkWorkAllocationNeedW+AFinishP5233314110547TP45472042217411TP3741140500611416TP21141640213415418TP11541821234717520TWork=233(2)P2:Request(0,3,4)•因（Available=233）Request(0,3,4)所以不能分配(3)P4：Request(2,0,1)WorkAllocationNeedW+AFinishP4032405020437TP54373141107411TP3741140500611416TP21141640213415418TP11541821234717520TAvailable=233AllocationNeedAvailableP1212347032P2402134P3405006P4405020P5314110有安全序列P4P5P3P2P1可以分配(4)P1：Request(0,2,0)AllocationNeedAvailableP1232327012P2402134P3405006P4405020P5314110012已不能满足任何进程的需要，不能分配司机进程：while(1){启动车辆正常驾驶到站停车}…售票员进程：while(1){关门售票开门}…用P.V操作解决司机与售票员的问题解•设有两个信号量S1，S2，初值均为0。司机进程：while(1){P(S1)启动车辆正常驾驶到站停车V(S2)}…售票员进程：while(1){关门V(S1)售票P(S2)开门}…共享缓冲区的进程的同步•设某计算进程ＣＰ和打印进程ＩＯＰ共用一个单缓冲区，ＣＰ进程负责不断地计算数据并送入缓冲区Ｔ中，ＩＯＰ进程负责不断地从缓冲区Ｔ中取出数据去打印。分析通过分析可知，ＣＰ、ＩＯＰ必须遵守以下同步规则：•当ＣＰ进程把计算结果送入缓冲区时，IOP进程才能从缓冲区中取出结果去打印;•当IOP进程把缓冲区中的数据取出打印后，ＣＰ进程才能把下一个计算结果送入缓冲区解•为此设有两个信号量Sa=0，Sb=1，Sa表示缓冲区中有无数据，Sb表示缓冲区中有无空位置。•两个进程的同步可以描述如下：【思考题】1.用P.V操作解决下图之同步问题提示：分别考虑对缓冲区S和T的同步，再合并考虑getcopyputst解•设置四个信号量Sin=1，Sout=0，Tin=1，Tout=0；get：while（1）{P(Sin）;将数放入S;V(Sout);}copy：while（1）{P(Sout）;P(Tin）;将数从S取出放入T;V(Tout);V(Sin);}put：while（1）{P(Tout）;将数从T取走;V(Tin);}【思考题】•桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。试用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。提示：设置一个信号量表示可否向盘中放水果，一个信号量表示可否取桔子，一个信号量表示可否取苹果。解设置三个信号量S,So,Sa，初值分别为1，0，0。分别表示可否向盘中放水果，可否取桔子，可否取苹果。Father(){while(1){p(S);将水果放入盘中;if(是桔子)v(So);elsev(Sa);}}Son(){while(1){p(So)取桔子v(S);吃桔子;}}Daughter(){while(1){p(Sa)取苹果v(S);吃苹果;}}【思考题】有一个仓库，可以存放A和B两种产品，但要求：（1）每次只能存入一种产品（A或B）（2）－N＜A产品数量－B产品数量＜M。其中，N和M是正整数。试用P、V操作描述产品A与B的入库过程。提示：设两个信号量Sa、SbSa表示允许A产品比B产品多入库的数量Sb表示允许B产品比A产品多入库的数量解设两个信号量Sa、Sb，初值分别为M-1，N-1Sa表示允许A产品比B产品多入库的数量Sb表示允许B产品比A产品多入库的数量设互斥信号量mutex，初值为1。B产品入库进程：j=0;while(1){P(Sb);P(mutex);B产品入库V(mutex);V(Sa);消费产品;};A产品入库进程：i=0;while(1){生产产品;P(Sa);P(mutex);A产品入库V(mutex);V(Sb);};存储管理•2.何谓静态链接及装入时动态链接和运行时的动态链接?–a.静态链接是指事先进行链接形成一个完整的装入模块，以后不再拆开的链接方---式；–b.装入时动态链接是指目标模块在装入内存时，边装入边链接的链接方式；–c.运行时的动态链接是将某些目标模块的链接推迟到执行时才进行.•3.在进行程序链接时，应完成哪些工作?–a.对相对地址进行修改；–b.变换外部调用符号.存储管理•试用类C语言来描述首次适应算法进行内存分配的过程.•在采用首次适应算法回收内存时，可能出现哪几种情况?应怎样处理这些情况?–a.回收区与插入点的前一个分区相邻接，此时可将回收区与插入点的前一分区合并，不再为回收分区分配新表项，而只修改前邻接分区的大小；–b.回收分区与插入点的后一分区相邻接，此时合并两区，然后用回收区的首址作为新空闲区的首址，大小为两者之和；–c.回收区同时与插入点的前后两个分区邻接，此时将三个分区合并，使用前邻接分区的首址，大小为三区之和，取消后邻接分区的表项；–d.回收区没有邻接空闲分区，则应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址，插入到空闲链中的适当位置.•在具有快表的段页式存储管理方式中，如何实现地址变换?存储管理•分页和分段有何区别?•解释页面置换算法。比较最佳置换算法和最近最久未使用置换算法。•一个计算机系统的虚拟存储器，其最大容量和实际容量分别由什么决定?•1．试画出微机和主机中常采用的I/O系统结构图。•2．试说明设备控制器的构成。8．试说明DMA的工作流程。