一、概要

1、操作系统的内核。

2、操作系统的五大管理功能:进程管理、存储管理、设备管理、文件管理、作业管理。

3、网络操作系统和嵌入式操作系统基础知识。

4、操作系统的配置。

                                  二、进程管理

进程管理也称为处理机管理,该部分内容是整个操作系统部分的重点,主要知识点有:进程状态转换图、信号量与PV操作、死锁问题、银行家算法。

1.进程状态转换图

        进程状态转换图用于展现进程的状态,以及各种状态之间的转换。最为常见的有:三态模型和五态模型,其后又提出了七态模型。要求考生掌握三态模型与五态模型。五态模型是对三态模型的扩展(即五态模型已经包含了三态模型)。标准的五态模型如图2-2所示。

从该图可以看出,五态模型中的五态为:执行状态(运行状态)、活跃就绪状态、活跃阻塞状态、挂起就绪状态、挂起阻塞状态。其中前三种状态组成了三态模型。

执行状态:指进程占有处理机正在CPU上执行的状态。在单CPU系统中,每一时刻只有一个进程处于执行状态。

活跃就绪状态:指进程分配到除处理机以外的必需的资源(已经具备了执行的条件)的状态。进程被创建后处于就绪状态,处于就绪状态的进程可以有多个。

活跃阻塞状态:指进程因等待某个事件的发生而放弃处理机进入等待状态。系统中处于这种状态的进程可以有多个。

        在三态模型中,总是假设所有的进程都在内存中。事实上,可能出现这样一些情况,例如由于进程的不断创建,系统的资源已经不能满足进程运行的要求,这个时候就必须把某些进程挂起,对换到磁盘镜像区中,暂时不参与进程调度,起到平滑系统操作负荷的目的。这就形成了挂起就绪状态和挂起阻塞状态。

挂起就绪状态:指进程被移至磁盘镜像区中,此时进程只缺处理机资源。

挂起阻塞状态:指进程被移至磁盘镜像区中,此时进程除了缺处理机资源,还缺其它资源。

2.信号量与PV操作

在操作系统中,进程之间经常会存在互斥(都需要共享独占性资源时)和同步(完成异步的两个进程的协作)两种关系。为了有效地处理这两种情况,W. Dijkstra在 1965年提出信号量和PV操作。

信号量是一种特殊的变量,表现形式是一个整型S和一个队列。

P操作:也称为down()、wait()操作,使S=S-1,若S<0,进程暂停执行,放入信号量的等待队列。

V操作:也称为up()、signal()操作,使S=S+1,若S≤0,唤醒等待队列中的一个进程。

(1)完成互斥控制

也就是为了保护共享资源,不让多个进程同时访问这个共享资源,换句话说,就是阻止多个进程同时进入访问这些资源的代码段,这个代码段称为临界区(也称为管程),而这种一次只允许一个进程访问的资源称为临界资源。为了实现进程互斥地进入自己的临界区,代码可以如下所示:

P(信号量)

临界区

V(信号量)

由于只允许一个进程进入,因此信号量中整型值的初始应该为1.该值表示可以允许多少个进程进入,当该值<0时,其绝对值就是等待使用的进程数,也就是等待队列中的进程数。而当一个进程从临界区出来时,就会将整型值加1,如果等待队列中还有进程,则调入一个新的进程进入(唤醒)。

(2)完成同步控制

最简单的同步形式是:进程A在另一个进程B到达L2以前,不应前进到超过点L1,这样就可以使用程序,如下所示:

进程A 进程B

... ...

L1:P(信号量)L2:V(信号量)

... ...

因此要确保进程B执行V操作之前,不让进程A的运行超过L1,因此信号量的初值就应该为0.这样,如果进程A先执行到L1,那么执行P操作后,信号量的整型值就会小于1,也就停止执行。直到进程B执行到L2时,将信号量的整型值加1,并唤醒它以继续执行。

例如,某工厂仓库有一名保管员,该仓库可存放n箱零件。该工厂生产车间有m名工人,只要仓库空闲,工人将生产好的整箱零件放入仓库,并由保管员登记入库数量;该工厂销售部有k名销售员,只要仓库库存数能满足客户要求,便可提货,并由保管员登记出库数量。规定工人和销售员不能同时进入仓库,但是工人和工人,销售员和销售员可以同时进入仓库,其工作流程如图2-3所示。

          为了利用PV操作正确地协调工人和销售员进程之间的工作,设置了信号量S1,S2和S3,它们的初值分别为n、0和1.则图2-3中的a~h应分别填写什么操作呢?

         根据问题给出的条件,我们可以判断出,信号量S1表示仓库空闲位置个数,初值为n;S2表示仓库中零件箱数,初值为0;S3用于实现对保管员的互斥访问,初值为1.

         对于工人进程,首先应执行P(S1),看仓库中是否有空闲位置,若有,则将零件送入仓库,然后执行V(S2),表明仓库中已有一箱零件,通知销售员可以提货。然后执行P(S3),看保管员是否空闲,若空闲,登记入库数,然后V(S3),使保管员处于空闲状态。

         对于销售员进程,首先执行P(S2),看仓库中是否有货物,若有,可以提货,然后执行V(S1),表明已经提走一箱零件,空闲出一个位置,工人进程可以放置货物;然后执行P(S3),看保管员是否空闲,若空闲,登记出库数,然后V(S3),使保管员处于空闲状态。

3.死锁问题

        死锁是指各并发进程彼此互相等待对方所拥有的资源,且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成大家都想得到资源而又都得不到资源,各并发进程不能继续向前推进的状态。

       产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。产生死锁有四个必要条件:

(1)互斥条件:即一个资源每次只能被一个进程使用,在操作系统中这是真实存在的情况。

(2)保持和等待条件:有一个进程已获得了一些资源,但因请求其他资源被阻塞时,对已获得的资源保持不放。

(3)不剥夺条件:有些系统资源是不可剥夺的,当某个进程已获得这种资源后,系统不能强行收回,只能由进程使用完时自己释放。

(4)环路等待条件:若干个进程形成环形链,每个都占用对方要申请的下一个资源。

对待死锁的策略主要有:

(1)死锁的预防。不让任一产生死锁的必要条件发生就可以预防死锁。

(2)死锁的避免。这种策略不对用户进程的推进顺序加以限制,在进程申请资源时先判断这次分配安全否,只有安全才实施分配,典型的算法是银行家算法。

(3)死锁的检测。这种策略采用资源请求分配图的化简方法来判断是否发生了不安全状态。资源请求分配图是一种有向图,表示进程与资源之间的关系。死锁的检测是在需要的时刻执行的,当发现系统处于不安全状态时,即执行死锁的解除策略。

(4)死锁的解除。解除死锁的基本方法是剥夺。一种方法是把资源从一些进程处剥夺分给别的进程,被剥夺资源的进程则需回退到请求资源处重新等待执行;另一种方法是终止一个进程,剥夺其全部资源,以后再重新运行被终止的进程。

4.银行家算法

银行家算法是一种经典的死锁避免方法。银行家算法的基本思想是:当某个进程提出申请时,必须判断将资源分配给该进程后,会不会引起死锁。若不会,则进行分配;否则就不分配。这样做能保证在任何时刻至少有一个进程可以得到所需的全部资源而执行结束,并将归还资源加入到系统的剩余资源中,这些资源又至少可以满足一个进程的最大需求,于是保证所有进程都能在有限的时间内得到需求的全部资源。

按照银行家算法的思想,当进程请求资源时,系统将按如下原则分配资源:

(1)当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程。

(2)进程可以分期请求资源,但请求的总数不能超过最大需求量。

(3)当系统现有的资源不能满足进程尚需资源数时,对进程的请求可以推迟分配,但总能使进程在有限的时间里得到资源。

(4)当系统现有的资源能满足进程尚需资源数时,必须测试系统现存的资源能否满足该进程尚需的最大资源数,若能满足则按当前的申请量分配资源,否则也要推迟分配。

                                三、磁盘管理

磁盘是最常见的一种外部存储器,它是由1至多个圆形磁盘组成的,其结构如图2-4所示。

1、概念  

磁道:磁道是一组记录密度不同的同心圆。在一个磁盘中,从外到内,磁盘记录密度不断增加。同时,值得注意的是,0磁道是磁盘最外圈的磁道。 

 扇区:磁盘上的每个磁道被等分为若干个弧段,这些弧段便是磁盘的扇区。  

柱面:一个磁盘中,多个记录面相同磁道组成柱面。如磁盘有9个记录面,则这9个记录面的0磁道可组成一个柱面。

2、公式

计算磁道数=(外半径-内半径)×道密度×记录面数。 

 注意:硬盘的第一面与最后一面是保护用的,要减掉。如3个双面的盘片的记录面数是3×2-2=4。

非格式化容量=位密度×π×最内圈直径×总磁道数。  

注意:位密度是每道不同的,但每道的容量是相同的。0道是最外面的磁道,其位密度最小。

格式化容量 = 每道扇区数×扇区容量×总磁道数。

平均数据传输速率 = 每道扇区数×扇区容量×盘片转数。

 存取时间=寻道时间+等待时间,寻道时间是指磁头移动到磁道所需的时间;等待时间为等待读写的扇区转到磁头下方所用的时间。

3、数据存取过程

        根据硬盘存放数据的规则,在向磁盘记录一个文件时,应将文件尽可能记录在同一柱面上,当一个柱面记录不下时,再记录到相邻柱面上。因此,当一个文件超出一个磁道容量时,剩下的部分应存于其他盘面的同一编号的磁道上,即同一柱面的其他磁道上。

         为存取磁盘上的一个物理记录,必须给出3个参数:柱面号,磁头号(盘面号),扇区号。磁盘机根据柱面号控制移动臂作径向运动,带动读写头到达所需的柱面;从磁头号可确定哪一个磁头来读写数据,然后便等待访问的信息块旋转到读写头下时进行存取。磁盘机实现这些功能的操作是:查找(将读写头定位到指定柱面并选择指定磁头)、搜索(指定磁头寻找访问的记录块)、读、写和控制等。

      平均存取时间(Average Access Time)是反映磁盘数据操作速度的指标,单位是毫秒(ms)。它包括三个时间段,分别是平均寻道时间(Seek Time),平均定位时间(SettingTime)和转动延迟(Rotational Latency),其中后两个又统称为等待时间。

         寻道时间也称为查找时间,为磁头移动到目标磁道所需的时间。对于固定磁头磁盘而言,无需移动磁头,只需选择目标磁道对应的磁头即可。等待时间为等待读写的扇区旋转到磁头下方所用的时间。一般选用磁道旋转一周所用时间的一半作为平均等待时间。寻道时间由磁盘机的性能决定,目前主流硬盘典型的平均寻道时间(Average Seek Time,AST)一般在4ms左右,而转速则有5400rpm、7200rpm、15000rpm等。在考试当中,这些参数通常是由试题指定。

4、磁盘调度算法

        先来先服务(FCFS):该算法根据进程请求访问磁盘的先后次序进行调度。其优点是公平、简单,且每个进程的请求都能依次得到处理,不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化,致使平均寻道时间可能较长。

      最短寻道时间优先(SSTF):该算法选择这样的进程,其要求访问的磁道与当前磁头所在的磁道距离最近,以使每次的寻道时间最短,但这种调度算法却不能保证平均寻道时间最短。

         扫描算法(SCAN):SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离,更优先考虑的是磁头的当前移动方向。例如,当磁头正在自里向外移动时,SCAN算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外,又是距离最近的。这样自里向外地访问,直到再无更外的磁道需要访问才将磁臂换向,自外向里移动。由于这种算法中磁头移动的规律颇似电梯的运行,故又称为电梯调度算法。

        循环扫描(CSCAN)算法:该算法规定磁头单向移动。例如,只自里向外移动,当磁头移到最外的被访问磁道时,磁头立即返回到最里的欲访磁道,即将最小磁道号紧接着最大磁道号构成循环,进行扫描。

                                     四、设备管理 

          在计算机系统中,除了处理器和内存之外,其他的大部分硬设备称为外部设备。它包括输入/输出设备,辅存设备及终端设备等。

1.数据传输控制方式

输入输出系统主要有五种方式与主机交换数据:程序控制方式、程序中断方式、DMA方式、通道方式、I/O处理机。

(1)程序控制方式:CPU直接利用I/O指令编程,实现数据的I/O.CPU发出I/O命令,命令中包含了外设的地址信息和所要执行的操作,相应的I/O系统执行该命令并设置状态寄存器;CPU不停地(定期地)查询I/O系统以确定该操作是否完成。由程序主动查询外设,完成主机与外设间的数据传送,方法简单,硬件开销小。

(2)程序中断方式:CPU利用中断方式完成数据的I/O,当I/O系统与外设交换数据时,CPU无需等待也不必去查询I/O的状态,当I/O系统完成了数据传输后则以中断信号通知CPU.CPU然后保存正在执行程序的现场,转入I/O中断服务程序完成与I/O系统的数据交换。然后返回原主程序继续执行。与程序控制方式相比,中断方式因为CPU无需等待而提高了效率。在系统中具有多个中断源的情况下,常用的处理方法有:多中断信号线法、中断软件查询法、雏菊链法、总线仲裁法和中断向量表法。

(3)DMA方式:使用DMA控制器(DMAC)来控制和管理数据传输。DMAC和CPU共享系统总线,并且具有独立访问存储器的能力。在进行DMA时,CPU放弃对系统总线的控制而由DMAC控制总线;由DMAC提供存储器地址及必须的读写控制信号,实现外设与存储器之间进行数据交换。DMAC获取总线方式主要有三种,分别是暂停方式、周期窃取方式和共享方式。

(4)通道:通道是一种通过执行通道程序管理I/O操作的控制器,它使主机与I/O操作之间达到更高的并行程度。在具有通道处理机的系统中,当用户进程请求启动外设时,由操作系统根据I/O要求构造通道程序和通道状态字,将通道程序保存在主存中,并将通道程序的首地址放到通道地址字中,然后执行"启动I/O"指令。按照所采取的传送方式,可将通道分为字节多路通道、选择通道和数组多路通道三种。

(5)输入输出处理机(IOP):也称为外围处理机(PPU),它是一个专用处理机,也可以是一个通用的处理机,具有丰富的指令系统和完善的中断系统。专用于大型、高效的计算机系统处理外围设备的I/O,并利用共享存储器或其他共享手段与主机交换信息。从而使大型、高效的计算机系统更加高效地工作。与通道相比,IOP具有比较丰富的指令系统,结构接近于一般的处理机,有自己的局部存储器。

2.虚设备与SPOOLING技术

SPOOLING(Simultaneous Peripheral Operation On Line)的意思是外部设备同时联机操作,又称为假脱机输入输出操作,采用一组程序或进程模拟一台I/O处理器。SPOOLING系统的组成如图2-5所示。

          该技术利用了专门的外围控制机将低速I/O设备上的数据传送到高速设备上,或者相反。但是当引入多道程序后,完全可以利用其中的一道程序来模拟脱机输入时的外围控制机的功能,把低速的I/O设备上的数据传送到高速磁盘上;再利用另一道程序来模拟脱机输出时的外围控制机的功能,把高速磁盘上的数据传送到低速的I/O设备上。这样便可以在主机的控制下实现脱机输入、输出的功能。此时的外围操作与CPU对数据的处理同时进行,我们将这种在联机情况下实现的同时外围操作称为SPOOLING,或称为假脱机操作。

         采用假脱机技术,可以将低速的独占设备改造成一种可共享的设备,而且一台物理设备可以对应若干台虚拟的同类设备。SPOOLING系统必须有高速、大容量并且可随机存取的外存(如磁盘或磁鼓)支持。

                                         五、文件管理

文件管理部分主要集中于位示图、树型目录结构以及索引文件结构。

1. 树型目录结构

       在计算机的文件系统中,一般采用树型目录结构。在树型目录结构中,树的根结点为根目录,数据文件作为树叶,其他所有目录均作为树的结点。

      根目录隐含于一个硬盘的一个分区中,根目录在最顶层。它包含的子目录是一级子目录。每一个一级子目录又可以包含若干二级子目录,...,这样的组织结构就叫做目录树。

        当前盘和当前目录是系统默认的操作对象。如果用户没有指明操作对象,系统就将用户命令指向当前盘和当前目录。 路径是指从根目录或者当前目录开始到访问对象(目录或者文件),在目录树中路经过的所有目录的序列。例如"c:\dos\lmouse\mouse"就是Windows系统中的一条路径。在树型目录结构中,从根目录到任何数据文件之间,只有一条惟一的通路,从树根开始,把全部目录文件名与数据文件名,依次用"/"(UNIX/Linux系统)或"\"(Windows系统)连接起来,构成该数据文件的路径名,且每个数据文件的路径名是惟一的。这样,可以解决文件重名问题。

         从树根开始的路径为绝对路径,如果文件系统有很多级时,使用不是很方便,所以引入相对路径,即是从当前目录开始,再逐级通过中间的目录文件,最后到达所要访问的数据文件。

      绝对路径给出文件或目录位置的完全的描述,通常由层次结构的顶端开始(根目录),通常第一个字符是"/"(UNIX/Linux系统)或者是盘符(Windows系统)。相对路径通常由目录结构中的当前的位置开始,一般都比绝对路径要短。

     父目录是指当前路径的上一层目录。每个目录下都有代表当前目录的"."文件和代表当前目录父目录的""文件,相对路径名一般就是从""开始的。

2. 位示图

位示图法是为管理磁盘空闲存储空间而提出的一种方法。该方法是在外存上建立一张位示图(Bitmap),记录文件存储器的使用情况。每一位仅对应文件存储器上的一个物理块,取值0和1分别表示空闲和占用。文件存储器上的物理块依次编号为:0、1、2、...假如系统中字长为32位,有4096个物理块,那么在位示图中的第1个字对应文件存储器上的0、1、2...31号物理块;第2个字对应文件存储器上的32、33、34、...、63号物理块;第32字对应文件存储器上的4064、4065、...、4095号物理块。这样位示图的大小为32字。

        位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况,如图2-6所示。当其值为"0"时,表示对应的盘块空闲;为"1"时表示已分配。由所有盘块对应的位构成一个集合,称为位示图。位示图也可描述为一个二维数组map:Var map:array[1...m,1...n]of bit;

3. 索引文件

     索引文件是一种对文件存储不连续分配的方法。为每个文件建立一张索引表,索引表中的每一表项指出文件信息所在的逻辑块号和与之对应的物理块号。

      索引文件既可以满足文件动态增长的要求,又可以方便而迅速地实现随机存取。对一些大的文件,当索引表的大小超过一个物理块时,会发生索引表的分配问题。一般采用多级(间接索引)技术,这时在由索引表指出的物理块中存放的不是文件存放处而是存放文件信息的物理块地址。这样,如果一个物理块能存储n个地址,则一级间接索引将使可寻址的文件长度变成n2块,对于更大的文件可以采用二级甚至三级间接索引(例如,Unix操作系统采用三级索引结构,如图2-7所示)。

          索引文件的优点是既适用于顺序存取,又适用于随机存取。缺点是索引表增加了存储空间的开销。另外,在存取文件时需要访问两次磁盘,一次是访问索引表,另一次是根据索引表提供的物理块号访问文件信息。为了提高效率,一种改进的方法是,在对某个文件进行操作之前,预先把索引表调入内存。这样,文件的存取就能直接从在内存的索引表中确定相应的物理块号,从而只需要访问一次磁盘。