第8章UNIX操作系统
UNIX操作系统从一个非常简单的操作系统发展成为性能先进、功能强大、使用广泛的操作系统,并成为事实上的多用户、多任务操作系统标准。
8.1内容辅导
8.1.1 UNIX操作系统概述
1.UNlX系统的特点
UNIX系统的特点如下：
（1）UNIX是一个多用户、多任务的操作系统,每个用户都可同时执行多个进程,系统中的进程数目在逻辑上不受限制。
（2）提供了精选的、丰富的系统功能,其中许多功能在实现思想上有其独到之处,且是高效的。
（3）该系统用高级语言编写,使系统具有易读、易懂、易修改、易移植等一系列优点,且系绕代码十分紧凑。
（4）提供了良好的用户界面。该系统提供一种命令程序设计语言SHELL作为用户界面;同时提供了系统调用作为用户程序与系统的接口。这些界面既能为用户提供各种服务,又相当简洁。
（5）在UNIX系统中使用了树型结构的文件系统,它具有良好的安全性、保密性和可维护性,在文件系统的实现方法上,也有较多创新。
（6）系统提供了多种通信机制,以满足各种进程通信的需要。
（7）在存储管理上,为提高内存利用率,提供了进程对换存储管理方式和请求调页的存储管理方式,以实现虚拟存储器。
2.UNlX系统核心体系结构整个UNIX系统可分成两大部分。第一部分是由用户程序和系统提供的服务构成的所谓核外程序,形成了良好的系统环境:第二部分是操作系统,又称为核心,其中两个最主要的部分是文件子系统和进程控制子系统。
用户程序可以通过高级语言的程序库或低级语言的直接系统调用进入核心。核心中的进程控制子系统负责进程同步、进程间通信、进程调度和存储管理。文件子系统管理文件,包括分配文件存储空间、控制对文件的存取以及为用户检索数据。文件子系统通过一个缓冲机制同设备驱动部分交互作用。设备管理、进程管理及存储管理通过硬件控制接口与硬件交互作用。
8.1.2 UNIX的进程在UNIX系统中,采用了段页式存储管理〈在UNIX中将段称为区〉方式,因此一个进程实体由若干个区组成,包括程序区、数据区、核区等。每个区又可分为若干页。
1.进程的描述在UNIX System V中,将PCB分成进程表项和U区。除进程表项和U区外,管理进程的数据结构还有本进程区表和系统区表。
（1）进程表项进程表项中的每个表目主要包含以下信息:标识进程状态的状态域；用户标识号,简称UID或用户ID；进程标识号,简称PID或进程P；存储区位置和长度；调度参数（包括优先数等）；软中断信号域；各种计时域；指向U区的指针；事件描述域。
（2）U区
U区中的各个域进一步刻画了进程的特性,U区主要包含以下信息:指向进程表项的指针；真正用户标识符(real user ID)及有效用户标识符(effective user ID)；用户文件描述符表；当前目录和当前根；计时器域；一些输入/输出参数；限制域；出错域；返回值域；信号处理数组。
（3）系统区表
UNIX System V把一个进程的虚地址空间划分为若干连续的逻辑区,有正文区、数据区、核区等。这些区是可被共享和保护的独立实体,多个进程可以共享一个区。为了对区进行管理,在核心中设置了一个系统区表(简称区表),各表项中记录了描述活动区的有关信息:区的类型和大小；区的状态（一个区具有这样几种状态:锁住、在请求中、在装入过程中、有效)；区在物理存储器中的位置；引用计数；指向文件索引节点的指针。
（4）本进程区表为了记录进程的每个区在进程中的虚地址,并通过它找到该区在物理存储器中的实地址,系统为每个进程配置了一张进程区表,表中每一项记录一个区的起始虚地址及指向系统区表中对应区表项的指针。这样,核心通过查找本进程区表和系统区表,便可将区的逻辑地址变换为物理地址。这里使用两张表来对区地址进行映像是为了便于实现区的共享。
2.进程状态及其转换在UNIX System V中,为进程设置了9种状态：
（1)创建状态：进程刚被创建时,进程已经存在,但尚未完全获得运行所必须具有的资源,因此它既不是就绪状态,也不是睡眠状态。这个状态可被认为是进程的初始状态。
（2)内存中就绪：进程己在内存中且处于就绪状态。对于新创建的进程,若系统有足够的内存,核心便将它装入内存,从而使新进程转入内存中就绪状态。
（3）就绪且换出：进程处于就绪状态,但被换出到外存中。在创建新进程时,若无足够的内存,核心便将新进程安置在外存对换区中,并赋予就绪且换出状态。此外,原已在内存中的进程,可能因内存紧张而被换出,同样也成为就绪且换出状态。
（4)核心态执行：进程在核心态下执行。
（5)用户态执行：进程在用户态下执行。
（6）内存中睡眠进程已在内存中且正处于睡眠状态。例如,进程所执行的系统调用涉及到I/O操作,而进程又须等待UO操作的完成,则进程将进入内存中睡眠。
（7)睡眠且换出当内存紧张时,在内存中睡眠的进程,首先被核心换出到外存上,以腾出内存。此时,进程将变为睡眠且换出状态。
（8）被剥夺状态当进程从核心态返回用户态时,核心剥夺了该进程的处理机,使该进程处于被剥夺状态。
（9）僵死状态进程执行了exit系统调用后,便处于僵死状态。此时,进程已不存在,但它留下一些含有状态码和一些计时统计信息的记录,供父进程收集。
3,进程上下文当一个进程在执行时,可看作是在它的进程上下文中执行。一个进程的上下文〈context〉
由三部分组成:用户级上下文、寄存器上下文和系统级上下文。
（1）用户级上下文：用户级上下文是由进程虚地址空间中的正文、数据、用户校和共享存储区组成。在采用对换和请求调页存储管理方式时,只有进程的部分虚地址空间驻留在内存。但无论它是否驻留在内存,都属于用户级上下文的组成部分。
（2）寄存器上下文：寄存器上下文主要由CPU中的一些寄存器内容构成。主要的寄存器有:程序寄存器；处理机状态寄存器；栈指针；通用寄存器。
（3）系统级上下文：系统级上下文可分为静态和动态两部分:
①静态部分：在进程的整个生命期中,系统级上下文的静态部分只有一个,其大小保持不变,它由三部分组成:进程表项、U区和本进程区表项、系统区表项和页表。
②动态部分：在进程的整个生命期中,系统级上下文动态部分的数目是可变的。它包括:核心钱和若干层寄存器上下文。
4,进程控制在UNIX System V中，进程既是一个独立拥有资源的基本单位，又是一个独立调度的基本单位。为了对进程进行控制，UNIX 提供了一系列系统功能调用，用户可以利用它们来实现"创建一个进程"或"终止一个进程的执行"等功能。
用于对进程实施控制的主要系统调用有：
（1）系统调用fork
在UNIX系统中,除了0进程外,其他所有进程都是被另一个进程利用fork创建的。0进程是一个特殊的系统进程,它在系统引导时被创建的。系统初启时,0进程又创建1进程，此后0进程就变为对换进程,而1进程就变为系统的始祖进程。UNIX利用fork为每个终端创建一个子进为用户服务，如等待用户登录、执行shell命令执行程序等。此后,每个终端子进程又可利用fork来创建它的子进程,从而可形成一棵进程树。
（2）系统调用exec
fork系统调用只是将父进程的上下文复制到新进程中,因此执行完fork时,父子进程具有完全相同的正文区、数据区及用户校区。若要使新进程执行的程序不同于父进程,可以使用exec系列系统功能调用。exec系列中的系统调用都完成同样的功能,它们把一个新的程序装入调用进程的内存空间,以改变调用进程的执行代码,从而使调用进程执行新引入的程序功能。如果exec调用成功,调用进程将被覆盖,然后从新引入程序的入口开始执行。这就产生了一个新进程,它的进程标识符与调用进程相同,但所执行的程序代码不同。这就是说,exec没有建立一个与调用进程并发执行的新进程,而是用新进程取代了老进程。这一组系统调用的主要差别在于给出参数的数目和形式不同,给出参数的形式有两种,一种是直接给出指向每个参数的指针,另一种是给出指向参数表的指针。
（3）系统调用exit
对于一般的用户进程,在其任务完成后应尽快撤消。为了及时回收进程所占用的资源并减少父进程的干预,UNIX系统利用exit来实现进程的自我终止。通常,父进程在创建子进程时,应在子进程的末尾安排一条exit,使子进程自我终止。
（4）系统调用wait
系统调用wait用于将调用进程挂起,直至其子进程因暂停或终止而发来软中断信号为止。如果在wait调用前,已有子进程暂停或终止,则调用进程作适当处理后便返回。
5.进程调度
UNIX系统是单纯的分时系统,因而未设置作业调度。对进程的调度采用多级反馈队列轮转调度方式。相应地,在系统中便为就绪进程设置了多个就绪队列。调度程序在进行调度时,总是先从最高优先级队列中取出排在队列最前面的进程。仅当最高优先级队列中没有进程时,才从次高优先级队列中找出其队首进程,令它执行一个时间片后,又剥夺该进程的执行,然后,再从优先级最高的队列中取出下一个就绪进程投入运行。
（1）进程优先级的分类在UNIX系统中,进程的优先级分为两类:核心优先级（又分为可中断和不可中断两类优先级）和用户优先级（又可分成n+1级,其中第0级为最高优先级,第n级的优先级最低）。
（2）优先级的计算
UNIX System V中的用户优先级是可变的,它随着占用CPU时间的增加而降低。核心每隔1秒钟便根据一个衰减函数来调整每个进程的最近CPU使用时间,并按下述公式对各进程重新计算其用户优先数(优先数越大,优先级越低:优先数越小,优先级越高)。
decay(CPU)=CPU/2
优先数=最近使用CPU的时间/2+基本用户优先数核心首先从处于"内存就绪"或"被剥夺"状态的进程中选择一个优先级最高的进程。若系统中同时有多个进程都具有最高优先级,则核心将选择其中处于就绪状态最久的进程,将它从所在队列中移出,恢复其上下文,使之执行。
（3）进程切换在操作系统中,凡是要进行中断处理和系统调用时,都将涉及到进程上下文的保存和恢复,此时系统所保存和恢复的是同属于一个进程的上下文。而在进程调度之后实现进程则是另一个进程的上下文,这一进程取决于调度程序所选中的是哪一个进程。
①进程上下文的保存与恢复不论发生了哪种中断(如I/0设备中断、程序中断〉,如果处理机运行级低于该中断的级别,则处理机将响应该中断,并提高处理机的运行级,以屏蔽其他中断。
②进程上下文的切换总的说来,引起进程上下文切换的原因,都是由于核心进行了进程调度而选中了一个新的进程运行。在UNIX系统中,由于采用了可剥夺的调度方式,因而引起进程调度的原因有时间片完、当前进程执行了sleep例程、进程执行完等,它们都会导致进程上下文的切换。
6.进程的同步与通信在UNIX System V中,进程的同步与通信提供了软中断信号和管道机制以及新的进程通信机构,简称IPC(Interprocess Comnmication)。它由三部分组成:消息机制、共享存储器机制和信号量机制。
（1）软中断信号：软中断信号（简称信号）是一种实现进程间简单通信的设施,用于通知对方发生了异常事件。UNIX系统V中,共有19个软中断信号。软中断是对硬件中断的一种模拟,发送软中断就是向接收进程的进程表项结构中的相应项发送一个软中断信号。如果用户进程发送的软中断信号大于19,则接收进程不予理睬,从而发送无效。接收进程在收到软中断信号后,将按照事先的规定去执行一个软中断处理程序。但是软中断处理程序不像硬件中断处理程序那样,收到中断信号后立即被启动,它必须等到接收进程执行时才能生效。另外,一个进程自己也可以向自己发送软中断信号,以便在某些意外的情况下,进程能转入规定好的处理程序。
（2）管道：用信号来处理异常事件或错误是非常合适的,但用它来处理进程之间的大量信息传送就显得非常不适宜。为此,UNIX又提供了一种称作管道的机构。所谓管道是指能连接某些读进程和写进程的、专门用于进程通信的共享文件(又称pipe文件〉。它允许读/写进程按先进先出的方式传送数据,即写进程从管道的一端向管道写入数据流,读进程从管道的另一端读出数据流。管道的类型有无名管道和有名管道，进程可利用pipe系统调用来建立一个无名管道；对无名管道的读写涉及到对pipe文件大小的限制；进程互斥；进程写管道和进程读管道。
（3）消息：消息是一个格式化的可变长的信息单元。消息机制允许由一个进程给其他任何进程发送一个消息。当一个进程收到多个消息时,可将它们排成一个消息队列。在UNIX中,消息机制向用户提供了四个系统调用,分别用于建立、发送和接收消息等。
消息有消息首部和消息队列头标，在UNIX系统中,每一个消息队列都有一个称为关键字(key)的名字,关键字是由用户指定的。此外,消息队列还有一消息队列描述符,其作用与用户文件描述符一样,也是为了方便用户和系统对消息队列的访问。进程可利用系统调用msgget来建立一消息队列,或者获取一消息队列的描述符；用msgsnd( )系统调用向指定的消息队列发送一个消息,并将发送消息链接到该消息队列的尾部；用msgrcv()系统调用从指定的消息队列中接收指定类型的消息；用户在建立了消息队列后,可利用msgctl系统调用来读取它的状态信息并进行修改,如查询消息队列描述符、修改消息队列的许可权等。
（4）共享存储区：共享存储区是UNIX系统中通信速度最高的一种通信机制。该机制可使若干进程共享主存中的某一个区域,且使该区域出现在多个进程的虚地址空间中。另一方面,一个进程的虚地址空间中又可连接多个共享存储区,每个共享存储区都有自己的名字。当进程间欲利用共享存储区进行通信时,须首先在主存中建立一共享存储区,然后将它附接到自己的虚地址空间上。此后,进程对该区的访问操作,与对其虚地址空间的其他部分的操作完全相同。进程之间以后便可通过对共享存储区中数据的读/写来进行直接通信。当用户需要使用该机制时,必须自己设置这种设施,才能保证实现正确的通信。
当进程要利用共享存储区进行通信时,应先利用系统调用shmget建立一共享存储区。如果该共享存储区已由其他进程建立,则返回其描述符shmid；进程在建立了一共享存储区并获得了其描述符后,还须利用系统调用shmat()将共享存储区附接到进程的虚地址空间上。此后,共享存储区便成为进程虚地址空间的一部分。进程可采用与其他虚地址空间一样的存取方法来存取它。当进程不再需要共享存储区时,应利用系统调用shmdt()将共享存储区与进程断接；如同消息机制一样,可以用shmctl()系统调用对共享存储区的状态信息进行读取和修改。当所有进程都与共享存储区断接时,便可删除该共享存储区。
（5）信号量
UNIX System V中采用的是信号量集机制,即由一组信号量构成的信号量集。传统的信号量机制是对信号量施加P和V操作,而System V中是利用semop()系统调用来对指定信号量进行操作。
用户可利用系统调用semget()来建立信号量集；一旦信号量集被创建成功,便可利用semop()系统调用对这组信号量进行操作。
8.1.3存储器管理在早期的UNIX系统中,为提高内存的利用率,己提供了内存与外存之间的进程对换机制。在UNIX System V中,除保留了对换功能外,还支持请求调页的存储管理方式,内存空间的分配与回收均以页为单位进行。每个页面的大小随版本不同而异,一般在512B-4KB之间。
1.请求调页管理的数据结构在UNIX系统中,为实现请求调页,核心配置了四种数据结构:
（1）页表：UNIX System V将进程的每个区分为若干页,以将它们分配到不相邻的物理块中,为此每个区设置了一张页表。为了支持请求调页,每个页表项中需包含以下字段:物理块号、年龄位、访问位、修改位、有效位、写时拷贝位和保护位。
（2）磁盘块描述表：在UNIX系统中,每个页表项对应一个磁盘块描述项,其中记录了各页面的磁盘拷贝所在的磁盘块号。一个页面的内容或在一个对换设备的特定块中,或在一个可执行文件中。如果该页在一个可执行文件中,此时磁盘块描述项中的存储器类型为File,设备块号是该页在文件中的逻辑块号。如果该页面在对换设备上,则此时的存储器类型为Disk,对换设备号和块号则用于指示该页面的拷贝所驻留的逻辑对换设备和相应的盘块号。
（3）页面数据表：每个页面数据表项描述内存中的一个物理页,每个表项包含:页状态、内存引用计数、逻辑设备和指向空闲页链表中下一个页面数据表项的指针和指向散列队列中下一个页面数据表项的指针。
在系统初启时,核心将所有的页面数据表项链接为一个空闲页链表,形成空闲页缓冲池。为给一个区分配一个物理页,核心从空闲链表之首摘下一个空闲页表项,修改其对换设备号和块号后,将它放到相应的散列队列中。
（4）对换使用表：对换设备上的每一页都占有对换使用表的一个表项,表项中含有一个引用计数,其数值表示有多少页表项指向该页。
2.偷页进程在UNIX系统的核心中,专门设置了一个偷页进程〈page stealer〉,其主要任务有二:
每隔一定时间增加内存中所有有效页的年龄:当有效页的年龄达到规定值后便将它换出。
（1）增加有效页年龄：一个页可计数的最大年龄取决于它的硬件设施。若只设置了两位作为年龄域,其有效页的年龄只能取值0、1、2和3。当该页的年龄为0、1、2时,该页处于不可换出状态;而当其年龄达到3时,便可将它换出内存。每当内存中的空闲页面数低于某规定的低限时,核心便唤醒偷页进程,由偷页进程去检查内存中的每一个活动的非上锁区,对所有有效页的年龄字段加1。对于那些年龄字段已增至3的页便不再加1,而是将它们换出。每当有进程访问了某个页面时,便将该页的年龄置0。
（2）对换出页的几种处理方法：当偷页进程从内存中的有效页中找到可被换出的页后,可采取下面三种方法对它们进行处理:
①若在对换设备上已有被换出页的拷贝,且被换出页的内容未被修改,则此时核心不必将该页重写回对换设备上,而只需将该页的页表项的有效位清零,并将页面数据表项中的引用数减1,最后将该页表项放入空闲页链表中。
②若在对换设备上没有被换出页的拷贝,则应将该页写到对换设备上。但为了提高对换效率,偷页进程并不是有一个页面换出一个页面,而是先将所有要换出的页链接到一个换出页链表上,然后再查看是否还有其他有效页要换出。当换出页面链上的页数达到某一规定值时,比如64页,核心才真正将这些页面写入对换区.
③在对换设备上已有换出页的副本,但该页内容已被修改过。此时核心将释放该页在对换设备上占有的空间,再重新将该页拷贝到对换设备上。
（3）将换出页面写到对换设备上当换出页面链上的页数达到规定值时,核心应将它们换出。为此,应首先为这些页面分配一连续的对换空间,以便将它们一起换出:但如果对换设备上没有足够大的连续空间,而其空闲存储空间的总和又大于64K时,核心可采取每次换出一页的方式将它们换出。每当核心向对换设备上写一个页面时,须首先清除该页表项的有效位,并将页面数据表项中的引用数减1。若引用计数为0,表明已无其他进程引用该页,核心便将其页面数据表项链入空闲页链表的尾部。若引用计数不为0,表明仍有进程共享该页,但如果该页长期未被访问,则也须将该页换出。最后,核心将分配给该页的对换空间地址填入相应的磁盘块描述项中,并将对换使用表中的计数加1。
3.请求调页当一个进程试图存取一个其有效位为0的页面时,将产生一有效性错。此时由核心调用有效性错处理程序加以处理。可能有下列两种情况:
一种情况是如果在磁盘块描述项中找不到所缺的页,则表明此次内存访问非法,核心将向该违例进程发出一"段违例"软中断信号；另一种情况是如果找到了所缺的页,表明此次内存访问合法:但因该页尚未调入内存,则核心为该页分配一个页面的内存,将所缺的页调入内存。
至于如何将所缺的页调入内存,则与所缺页面从何处调入有关,可分成以下三种情况:
（1）缺页在可执行文件中如果缺页对应的磁盘块描述项中的类型是File,表示该页尚未运行过,其拷贝是在可执行文件中。因此,核心应从可执行文件中将缺页调入内存。其具体的调入过程为;根据该文件所对应的系统区表项中的索引节点指针,找到该文件的索引节点,再把从磁盘块描述项中得到的该页的逻辑块号作为偏移量,查找索引节点中的磁盘块号衰,便可找到该页的磁盘块号,于是即可将该页调入内存。
（2）缺页在对换设备上如果缺页所对应的磁盘块描述项中的类型是Disk,表示该页的拷贝是在对换设备上,则核心将从对换设备上把该页调入内存。其调入过程为z核心先为缺页分配一内存页,修改该页表项使之指向内存页,并将页面数据表项放入相应的散列队列中,然后把该页从对换设备上调入内存。当I/0操作完成时,核心把请求调入该页的进程唤醒。
（3）缺页在内存页面缓冲区中在进程运行过程中,当一页被调出后又被要求访问时,需重新将它调入。但并非每次都要从对换设备上调入,因为被调出的页可能又被其他进程(共享时〉调入到另一物理页中,这时就可在页面缓冲池中找到该页。此时,只需适当地修改页表项等数据结构中的信息即可。
8.1.4 设备管理设备管理的主要任务是管理系统中的所有外部设备。UNIX系统把设备分为两类:块设备,用于存储信息,其对信息的存取是以信息块为单位的,如通常的磁盘、磁带等;字符设备,用于输入/输出,其对信息的存取是以字符为单位的,如通常的终端设备、打印机等。
1.设备缓冲管理在UNIX系统中分别为字符设备和块设备设置了缓冲池。
（1）字符设备缓冲管理在系统中设置了一组字符缓冲区,供各种字符设备使用。其中,每个缓冲区的大小为70个字节,包括以下四项:第一个字符的位置、最后一个字符的位置、指向下一个缓冲区的指针和余下的用于存放64个字符的缓冲区。所有的空闲缓冲区通过链接指针c_next链接成一个空闲缓冲队列,由队首指针cfreelist指向其第一个缓冲区。
每当设备管理程序请求一个字符缓冲区时,管理程序便从空闲缓冲区链首取得一空闲缓冲分配给相应的设备。在设备释放缓冲区时,管理程序将它链入空闲队首。可见,空闲缓冲区链实际上是一个栈,cfreelist指向栈顶。
在字符设备进行I/O时,核心可利用getcf过程从空闲缓冲区链中取得一缓冲区,来收容设备的I/O数据。当缓冲区中数据己被提取完而不再需要时,可利用putcf过程,将缓冲区归还到空闲链中。
（2）块设备缓冲队列的结构在系统中,为块设备配置了块设备数据缓冲区,供磁盘和磁带机使用。每个缓冲区的大小至少应与盘块的大小相当。至于盘块的大小则随机器而异,它们一般在512~4096字节之间。由于盘块缓冲区的容量较大,使用上也较复杂,因此UNIX系统中的盘块缓冲区的组成方式不同于字符缓冲区。
在UNIX系统中,盘块缓冲区均由两部分构成:一部分是用于存放数据的缓冲区;另一部分是缓冲控制块,也称为缓冲首都,用于存放缓冲区的管理信息,两者一一对应,但缓冲首部与缓冲区在物理上并不相连,只是在缓冲首部中用一个指向对应缓冲区的指针将两者联系起来,
缓冲首部还包括设备号和块号,以分别指出对应的文件系统和磁盘上的数据块。注意,在UNIX System V中,设备号并非物理设备号,而是逻辑设备号,核心把每一个文件系统看作是一个逻辑设备。缓冲首部中的状态字段指示对应缓冲区的当前状态,用于表示缓冲区是否空闲、缓冲区是否为延迟写、是否有进程正在等待该缓冲区变为空闲、核心是否正在读或写该缓冲区等。缓冲首部还包括两个空闲链表指针及两个散列队列指针。前者分别指向空闲链表中的上一个和下一个缓冲区首部:后者分别指向散列队列中的上一个和下一个缓冲区首部。
为了对缓冲区进行管理,在核心中设置了一个双向链接的空闲链表。系统初启时,将所有的缓冲首部都链入空闲链表中。当需要一个空闲缓冲区时,可利用getblk过程从空闲链表的首部摘下一个缓冲区:回收一个空缓冲区时,再利用brelse过程将它挂在空闲链的末尾。
为了加速对缓冲区的查找,系统把所有缓冲区按设各及块号所计算散列值的不同组织成多个散列队列,每个散列队列仍是一个双向链表,其中的缓冲区数目不断地发生变化。各块号的散列值用散列函数计算。一个空闲缓冲区可同时链入两个队列中,从而使对一空闲缓冲区的查找可通过两种方式来进行:若要求获得任意一空闲缓冲区,从空闲链上摘取第一个缓冲区即可，若要寻找一特定的空闲缓冲区,则搜索散列队列会更方便。
（3）块设备缓冲区的分配与释放核心调用getblk过程分配缓冲区。当要读磁盘数据时,核心首先检查要读入的盘块内容是否已在某个缓冲区中,若发现己在某个缓冲区中,便不必再从磁盘上读入。仅当数据未在任何缓冲区中时,核心才须从磁盘上将数据读入,这时才须为其分配一空闲缓冲区。类似地,当要把数据写入一特定盘块时,核心应先检查该块内容是否已在某缓冲区中,仅当该块内容尚不在缓冲区中时,才须分配一空闲缓冲区。获取空闲缓冲区时应提供的输入参数是文件系统号和磁盘块号。getblk过程分配缓冲区时,可分为两种情况:缓冲区在散列队列上及缓冲区不在散列队列上。
当核心用完某缓冲区时,可调用brelse过程将它释放。
2.核心与驱动程序的接口一一设备开关表在UNIX系统中,每类设备都有一个驱动程序,用它来控制该类设备。任何一个驱动程序通常都包含了用于执行不同操作的多个函数,如打开、关闭、启动设备、读和写等函数。为使核心能方便地转向各函数,系统为每类设备提供了一个设备开关表,其中含有该类设备的各函数的入口地址。
通常,字符设备和块设备的驱动程序有所不同,相应地,它们所包含的函数也不完全相同。由系统中所有字符设备的设备开关组成一张字符设备开关表,由系统中所有块设备的设备开关组成一张块设备开关表。
3.磁盘驱动程序磁盘驱动程序的主要功能是:把由逻辑设备号和盘块号组成的文件子系统地址转换为磁盘上特定的扇区号:装配磁盘控制器的各个寄存器,如磁盘地址寄存器、控制状态寄存器等:对磁盘块进行读和写。前两个功能与具体的磁盘有关,相对比较简单；而第三个功能则是驱动程序的最主要功能。
（1）磁盘的读写方式
在UNIX系统中有两种读方式:一般读方式和提前读方式。
在UNIX系统中有三种写方式:一般写方式、异步写方式和延迟写方式。。
8.1.5文件管理在文件系统中,为了能将文件存储到磁盘上,首先必须为之分配相应的存储空间;其次应考虑采用何种方式将文件存储到磁盘上;第三,为简化对文件的访问和共享。
1.文件存储空间的管理
（1）文件系统的组织在UNIX系统中,文件信息存放在磁盘或磁带上,一个物理存储器中可包含一个或多个文件卷。在UNIX中,这种文件卷又称为文件系统。一个文件系统包含许多物理块。
在文件系统中,0#块一般用于系统引导或空闲;1#块为超级块,用于存放文件系统的资源管理信息,如整个文件系统的盘块数、磁盘索引节点的盘块数、空闲盘块号表及指向下一个空闲盘块号的指针、空闲索引节点表和指向下一个空闲索引节点的指针等;从第2#块至K#块存放磁盘索引节点:第K+1#块及其后续各块存放文件数据。
（2）空闲盘块的组织
UNIX系统采用成组链接法对空闲盘块加以组织。即将若干个空闲盘块划归一个组,将每组中的所有盘块号存放在其前一组的第一个空闲盘块号指示的盘块中,而将第一组中的所有空闲盘块号放入超级块的空闲盘块号表中。
（3）空闲盘块的分配与回收
①空闲盘块的分配：当核心要从文件系统中分配一个盘块时,首先检查超级块空闲盘块表是否已上锁,若已上锁则进程睡眠等待:否则将超级块的空闲盘块表中下一个可用盘块分配出去。如果所分配的盘块号是超级块中的最后一个可用盘块号,由于在该盘块中存放了下一组的所有盘块号,于是核心在给超级块中的空闲盘块号表上锁后,先将该盘块中的内容读入超级块空闲盘块号表中；然后才将该盘块分配出去:最后将空闲盘块号表解锁,并唤醒所有等待其解锁的进程。
②空闲盘块的回收在回收空闲盘块时,如果超级块中的空闲盘块号表未满,可直接将回收盘块的编号放入空闲盘块号表中。若空闲盘块号表己满,须先将空闲盘块号表中的所有盘块号复制到新回收的盘块中,再将新回收盘块的编号放到超级块空闲盘块号表中,此块号就成了表中惟一的盘块号。
2.文件的物理结构在UNIX系统中,文件的数据存储在离散的磁盘块中,这些文件的盘块号直接或间接便可以用直接或间接的寻址方式获得指定文件的盘块号。
（1）寻址方式
①直接寻址方式：UNIX系统中的作业以中小型为主,为了提高对文件的检索速度,宜采用直接寻址方式。为此,在索引节点中建立了10个地址项,每个地址项中直接存放了该文件所在的盘块号,如图8.21所示。假定一个盘块的大小为1KB,当文件长度不大于10KB时,可直接从索引节点中得到该文件所在的全部盘块号。
②一次间接寻址方式：在UNIX系统中,可能有少数文件的长度达到了几万字节、几兆字节、甚至更长。这时,如果采用直接寻址方式,则要在索引节点中设置几百个或更多的地址项,这显然是不现实的。因此,UNIX系统中又提供了一次间接寻址方式。即在一次间接地址项中存放的不再是文件的一个物理盘块号,而是先将1~256个盘块号存放在一个磁盘块中,再将该磁盘块的块号存放在这一地址项中。这里,一个盘块为1KB,一个盘块号占32位,用一次间接地址项便可将寻址范围由lOKB扩大到266KB。
③多次间接寻址方式：为了进一步扩大寻址范围,又引入了二次间接和三次间接寻址方式。二次间接寻址可将寻址范围扩大到64MB。三次间接寻址可将寻址范围扩大到16GB。
（2）地址转换
UNIX系统利用地址转换过程bmap将文件的字节偏移量换为文件的物理块号。这一转换过程分两步实现:第一步,将字节偏移量转换为文件逻辑块号及块内偏移量;第二步,把逻辑块号转换为文件的物理块号。
3.用户文件描述符表和文件表
（1）用户文件描述符表为了方便用户和简化系统的处理过程,在UNIX System V中,每个进程的U区中设置了一张用户文件描述符表。仅在用户第一次打开指定文件时,才须给出其路径名。核心先对打开请求做仔细的检查后,便在该进程的用户文件描述符表中分配一空表工页,取该表项在用户文件描述符表中的位移量作为文件描述符返回给用户。以后,当用户再访问该文件时,只需提供该文件的描述符,系统根据描述符便可找到相应文件的内存索引节点。
（2）文件表系统为了对文件进行读/写,设置了一个确定读/写位置偏移量的读/写指针。该读/写指针应放在何处呢?是否可放在用户文件描述符表中呢?我们对此做个简单的分析。用户在读/写文件时,可采用三种方式:多个用户读/写各自的文件；多个用户共享一个文件,但彼此独立地对文件进行读/写:多个用户共享一个文件,且共享一个读/写指针。这样,若将读/写指针设置在文件描述符表项中,对前两种情况固然可行,但要实现对读/写指针的共享就很困难。为解决此问题,在UNIX系统中引入了文件表,文件表项中存放文件的读/写指针,这样对上述三种读/写要求都能很好地满足。
4.目录管理为了加速对文件目录的查找,在UNIX系统中,将文件名和文件说明分开,由文件说明形成一个称为索引节点的数据结构,而相应的文件目录项则只由文件名和对应的索引节点号构成。
（1）索引节点磁盘索引节点：索引节点是一个数据结构,其中存放文件的说明信息。索引节点以静态形式存放在磁盘上,故又称为磁盘索引节点。每个文件都有惟一的一个磁盘索引节点,它由下述各字段构成:文件所有者标识符、文件类型、文件存取权限、存放文件的物理地址、文件长度、文件联结计数、文件存取时间。
内存索引节点：为了加快文件的存取速度和减轻磁盘I/0的压力,专门在内存中建立了一个内存索引节点表,将那些要被引用的磁盘索引节点复制到内存索引节点表中,并增加了如下字段:索引节点号,内存索引节点状态、内存索引节点引用计数、设备号和内存索引节点指针。
（2）磁盘索引节点的分配与回收分配过程ialloc：每当核心创建一新文件时,都要为之分配一空闲磁盘索引节点。如果分配成功,便再分配一内存索引节点。
回收过程ifree：当要删除某文件时,应回收其所占用的盘块及相应的磁盘索引节点。过程ifree便是用于回收磁盘索引节点的。
（3）内存索引节点的分配与回收分配过程iget：主要功能是分配内存索引节点,其输入参数是文件系统号和索引节点。
回收过程iput：输入参数是指向内存i节点的指针。其主要功能是对指定的内存索引节点进行减1操作。若结果为0,则回收该内存i节点。若它已做过修改,还须将它写回磁盘后再回收,然后将它链入内存空闲i节点表中。若其磁盘i节点的联结计数也为0,便删除该文件,并回收分配给该文件的磁盘i节点和磁盘数据块。
（4）构造目录和删除目录文件系统的基本功能是实现按名存取,这是通过文件目录来实现的。UNIX系统中的每个目录项由文件名及其相应的索引节点号组成,其中文件名占14个字节,索引节点号占2个字节。通常,每个文件都在文件目录中有一个目录项,通过查找文件目录可找到该文件的目录项和对应的索引节点,进而找到文件存放的物理位置。对于可供多个用户共享的文件,则它往往会有多个目录工页。如果要将文件删除掉,其目录便也无存在的必要,因此也应将其目录项删除掉。
构造目录：每当创建一个新文件时,系统都要在其父目录文件中为之构造一个目录项。在UNIX系统中,构造目录的任务由makenode过程完成。在创建一个新文件时,由系统调用creat调用该过程来为新文件构造一个目录项。makenode过程首先调用ialloc过程来为新建的文件分配一磁盘索引节点和内存索引节点,若分配失败便返回:当分配成功时,须先设置内存索引节点的初值,然后调用写目录过程,将用户提供的文件名与分配给文件的磁盘索引节点号一起构成一新目录项,再将它记入其父目录文件中。
删除目录：当用户已不再需要某个文件时,应将它从文件系统中删除,以便及时腾出存储空间。由于UNIX系统支持文件的共享,而当文件正被多个进程共享时,不允许任何一个用户将该文件删除。这也是UNIX系统中不存在一条用于删除文件的系统调用的真正原因。当一个用户(进程〉己不再需要某文件时,只能利用系统调用unlink请求清除进程与该文件的联结。此时,系统须对该文件的联结计数执行减1操作,并相应地删除该用户(进程)的一个指定文件目录。当所有联结到该文件的用户都不再需要该文件时,其联结值为0,系统才执行删除该文件的操作。
（5）检索目录在UNIX系统中,当用户第一次访问某文件时,需要使用文件的路径名,系统按路径名去检索文件目录,得到该文件的磁盘索引节点,且返回给用户一个文件描述符。以后,用户便可利用该文件描述符来访问文件,这时系统不必再去检索文件目录。
对文件的检索是由namei过程完成的。该过程能被许多不同的系统调用所调用,如creat、open、link、chdir、chmod、chown等,但它们对namei的要求并不完全相同。可将这些系统调用分成三类:分别用f1ag=0、flag=1和flag=2来表示。Flag=O是指namei由chdir、chmod等所调用,这时若namei查找到指名文件则返回相应的内存索引节点指针。Flag=1是指由creat调用namei,此时若namei未找到指名文件便正常返回。Flag=2是指由unlink调用namei,在正常情况下应返回由路径名所指出的父目录文件的内存索引节点指针。这使得namei过程变得非常复杂。
检索目录过程namei是根据用户给出的文件路径名,从高层到低层顺序地查找各级文件目录,寻找指定文件的索引节点号。在检索路径名时,对以"/"开头的路径名须从根目录开始检索,否则从当前目录开始检索,并把与它对应的索引节点作为工作索引节点。然后用文件路径名中的第一个分量名与根或当前目录文件中的各目录项中的文件名逐一进行比较。由于一个目录文件可能占用多个盘块,因此,在检索完一个盘块中的所有目录项而未找到匹配的文件分量名时,须调用bmap和bread过程,将下一盘块中的所有目录项读入内存,再逐一检索。若检索完该目录文件的所有盘块而仍未找到匹配的目录项时,才认为无此文件分量名。
在未找到指定分量名的匹配目录项时,又分成几种情况处理：
(1)如果不是最后一个路径分量名,则出错返回。
(2〉如果是最后一个路径分量名且flag=1时,属正常情况。此时,使namei过程继续执行,去检查父目录文件是否允许写,父目录文件中是否有空目录项。若有,便分配一空目录项,然后返回NULL。
(3)如果是最后一个路径分量名,但f1ag≠1,则出错返回。
唔 如果找到相匹配的目录项,而路径名尚未检索完,则把该目录项中所指示的索引节点作为工作索引节点,并取出文件路径名中的下一个分量名,继续重复上述过程,直至路径名中的所有分量名全部查找完毕。
5.文件系统的系统调用系统调用是用户程序取得操作系统服务的惟一方式,是用户程序与操作系统之间的接口。UNIX系统中提供了丰富的系统功能调用,与文件操作相关的常用系统功能调用有：open、close、creat、link、unlink、read和write。
8.2 重点难点学习提示这一部分请周星给添上
8.3 经典问题分析和解答
1.试述UNIX的主要特点。
答,UNIX的主要特点是:
(1)UNIX系统是一个可供多用户同时操作的交互式分时操作系统;
(2)为了向用户提供交互式功能和使得用户可以利用UNIX系统的功能,UNIX系统向用户提供了两种友好的界面或接口:系统调用和命令;
(3)UNIX系统具有一个可装卸的分层树型结构文件系统,该文件系统使用方便、搜索简单；
(4)UNIX系统把所有外部设备都当成文件,并分别赋予它们对应的文件名。从而,用户可以像使用文件那样使用任一设备而不必了解该设备的内部特性,这既简化了系统设计,又方便了用户;
(5)UNIX系统核心程序的绝大部分源代码和系统上的支持软件都用C语言编写。且UNIX系统是一个开放式系统,即具有统一的用户接口,使得UNIX用户的应用程序可在不同的执行环境下运行。
正是由于UNIX具有上述这些特点,使得UNIX系统得到了广泛的应用和发展。
2,简述UNIX系统进程的概念。
答:在UNIX系统中,进程被赋予一些特定的含义和特性:
（1）一个进程是对一个程序的执行；
(2)一个进程的存在意味着在所谓的"Proc"数组(PCB的常驻内存部分)中有一个非零的结构存在,它包含着相应的进程控制信息；
(3)对于每个进程,有一个被称为U区?(userblock)或User的数据结构。这个数据结构放置该进程的私用控制信息,且在进程被创建时,才会由系统分配相应的域(field)。
(4)一个进程可以生成或删除其子进程;
(5)一个进程是获得和释放各种资源的基本单位。
3.答:在UNIX System V中引起进程调度的情况有5种:
(l)当前执行进程申请内存等系统资源未得到满足,从而自己调用sleep过程,放弃处理机而进入睡眠状态。
(2)为了与其他并发进程保持同步,调用了wait或stop过程等,从而主动放弃了处理机而进入睡眼状态。
(3)当系统在从核心态转入用户态时,发现runrun调度标志被设置（即系统中某进程的优先级已高于当前执行进程的优先级),系统调用优先级高的进程执行。
(4)时间片用完,且当前进程的优先级低于其他就绪进程。
(5)当前进程调用exit,自我终止时。
4.描述UNIX System V中消息机制的通信原理。
答:UNIX System V中消息机制使用消息队列和消息头两种基本数据结构,消息队列中每一表项由关键字、访问控制结构及操作状态信息组成,消息头描述消息的有关特征。在消息机制中,消息被格式化为类型与数据对,且允许不同的进程根据不同的消息类型接收。
消息机制提供4个系统调用msgget,msgctl,msgsnd和msgrcv。系统调用msgget返回一个消息描述字msgqid。msgqid指定一个消息队列供其它三个系统调用使用。系统调用msgctl用来设置和返回与msgqid相关联的参数选项,以及用来删除消息描述符的相关选择项。系统调用msgsnd和msgrcv分别表示发送和接收一消息。
使用消息机制的通信双方先要建立相同的消息队列。通信时先得到自身的msgqid,若要发送消息则把待发消息写入消息正文部分,并指定消息类型。最后调用msgsnd把消息发送到消息队列上。若要接收消息则调用msgrcv从消息队列中取出消息。
5.在UNIX System V中,当一个进程所访问的一页既不在内存又不在文件系统中时,该页面可能在什么地方?存储管理模块是如何把它调入内存的?
答:在UNIX System V中,一个进程所访问的页面或者在内存中,或者在文件系统中,或者在对换设备上。因此,当一个进程所访问的一页既不在内存又不在文件系统中时,该页面可能在对换设备上。此时由核心调用有效性错处理程序加以处理。
当所缺页面在对换设备上但不在内存时,则说明该页曾一度在内存中,但已被偷页进程换出。为从对换设备上调入该页面,核心从磁盘块描述项中找到存放该页面的对换设备和块号,然后为缺页分配一内存页,修改此进程的相应页表项,使之指向该内存页,并将页面数据表放入相应的散列队列中,再把该页从对换设备上调入内存。
6.UNIX 文件系统为什么有磁盘i节点和内存i节点?为什么内存i节点和磁盘i节点的内容不完全一样?
答:UNIX系统中,磁盘i节点以静态形式存放文件说明信息。引入内存i节点是为了减少设备的启动次数以及提高操作速度,把磁盘i节点复制到内存特定区域。由于进程对文件进行操作时,需要用到i节点中的逻辑结构和物理结构信息,以完成对文件信息的存取、共享和保护,故内存i节点中多了当前文件状态信息。
7.在UNIX System V中,如果一个盘块的大小为1KB,每个盘块号占4个字节,那么,一个进程要访问偏移量为263168字节处的数据时,需要经过几次间接?
答,分析：在UNIX系统中,文件的数据存储在离散的磁盘块中,这些文件的盘块号直接或间接地存放在该文件索引节点的13个地址项中。前10个地址项是直接寻址,每个地址项中直接存放了该文件所在的盘块号;第11个地址项是一次间接寻址,即先将1~256(因一个盘块的大小为1KB且每个盘块号占4个字节,所以一个盘块中最多能存放1024/4=256)个盘块号存放在一个磁盘块中,再将该磁盘块的块号存放在该地址项中;第12个地址项是二次间接寻址,其中的磁盘块号指向一个一次间接块号表;第13个地址项是三次间接寻址,其中的磁盘块号指向一个二次间接块号表。
故偏移量263168的逻辑块号为:263168/1024=257
块内偏移量为:263168.1024×257=0
因为10<257<266,所以偏移地址263168的块号在一次间接块内,故一个进程要访问偏移量为263168字节处的数据时,只需要经过一次间接。
8.在UNIX系统中,如果当前目眼录是/user/wang,那么，相对路径为../ast/xxx文件的绝对路径名是什么?
答,UNIX系统采用了树型目录结构,树根称为根目录,用"/"表示。为了使用方便,系统还设置了当前工作目录。路径名是由"/"分隔的目录名组成,以表明文件所在的目录。从根目录出发的路径称为绝对路径,从当前目录出发的路径称为相对路径。”."目录是指当前目录，”..”目录是指父目录。
在本题中,因当前目录是/usr/wang,所以相对路径为../ast/xxx的文件实际上是usr目录下的文件,故其绝对路径名时/usr/ast/XXX。
9.请为下列程序中标号处加上注释。
程序A
#denne MSGIGY 75
struct msgform{
long mtype;
char mtext[256];
}
main()
struct msgform msg;
int msgqid,pid,*pint:
msgqid=msgget(MSGKEY,0777); (1)
pid=getpid():
pint =(int*)msg.mtext; (2)
*pint=pid; (3)
msg.mtype=1; (4)
msgsnd(msgqid,&msg,sizeof(int),0); (5)
msgrcv(msgqid,&msg,256,pid,0); (6)
}
程序B
#define MSGKEY 75
struct msgform{
long mtype;
char mtext[256];
}msgl;
main()
{
int msgqid,i,pid,*pint;
msgqid=msgget(MSGKEY,0777|IPC-CREAT); (7)
msgcv(msgqid,&msg1,256,1,0); (8)
pint=(int*)msg1.mtext; (9)
pid=*pint; (10)
msg1.mtype=pid;
*pint=getpid(); (11)
msgsnd(msgqid,&msg1,sizeof(int),0); (12)
}
答,(1)获取一个消息队列标识,该消息队列的键值为MSGKEY,即75。消息队列的权限为0777,即所有用户都有读、写、执行权限。
（2）使pint指向消息块中存放消息正文的空间。
（3）在消息正文中填入本进程的进程号。
（4）设置消息类型为1。
（5）发送消息。将上述两条语句构造好的消息发送至msgqid指定的消息队列。
（6）接收消息。在接收消息时,因消息类型设置为pid,即本进程的进程号,所以该语句将读出消息类型为本进程进程号值的第一个消息。
（7)获取一个消息队列标识,该消息队列的键值为MSGIqy,即75.若给定键值尚未有对应消息队列存在,就为它建立一个消息队列。消息队列的权限为0777。
（8）接收消息。在接收消息时,因消息类型设置为1,所以该语句将读出消息类型1的第一个消息。
（9）使pint指向消息块中存放消息正文的空间。
（10）读出消息正文,放入变量pid中,即将程序A中所填入的进程号读出。
（11）在消息正文中填入本进程的进程号。
（12）发送消息。
10.一个进程在发现所要搜索的i节点位于缓冲区中,且该i节点为上锁状态时,将在iget中睡眠。在该i节点变为开锁状态并唤醒该睡眠进程之后,该进程将重新开始搜索i节点。为什么?
答：UNIX的系统内部过程iget的主要功能是分配一个内存索引节点,其输入参数是文件系统号和索引节点号。若该i节点已在索引节点的散列队列中,则只需对该i节点的引用计数加1。如果该i节点不在散列队列中,则应从空闲i节点链中摘下一空闲i节点,设置文件系统号和索引节点号,并根据i节点号计算它应在的散列队列,再将该i节点从原来的散列队列移至新的散列队列。调用bread过程将磁盘i节点的内容拷贝到内存i节点中,并对内存i节点进行初始化。其算法可形式化描述如下:
算法iget
输入:文件系统及索引节点号输出:上锁状态的索引节点
{
while (未完成)
{
if(是索引节点高速缓冲中的索引节点〉
{
if〈索引节点为上锁状态〉
{
sleep(索引节点变为开锁状态事件〉;
continue; /*循环到while */
}
if〈是空闲索引节点表上的索引节点〉
从空闲表上移出该节点;
索引节点引用计数值增1;
return (索引节点〉;
}
/*不是索引节点高速缓冲中的索引节点*/
if(空闲表上没有索引节点〉
return (错误):
从空闲表上移出一个索引节点:
重置索引节点号及文件系统:
从老的散列队列中删去该索引节点,把该索引节点放到新的散列队列中:
从磁盘上读索引节点(算法bread);
索引节点初始化〈如访问计数置为1〉:
return (索引节点〉;
}
}
当一个进程,为描述方便起见,不妨设此进程为进程B,发现所要搜索的i节点位于索引节点高速缓冲区中,且该i节点为上锁状态(不妨设进程A正使用该i节点并将该i节点上锁)时,进程B将在iget中睡眠.进程A最终将会为此i节点解锁,并唤醒睡眠在此i节点解锁事件上的所有进程,其中包括进程B.当核心再次调度到进程B时,进程B必须证实该i节点是否为上锁状态,因为可能有另一进程C也一直等待使用同一个i节点,并且核心可能先于进程B而调度到进程C运行,进程C可能正在使用该i节点,使该i节点仍为上锁状态;基于同样的竞争情况,进程B还必须证实该i节点是否还在内存索引节点高速缓冲中.
一个进程在发现所要搜索的i节点位于缓冲区中,且该i节点为上锁状态时,将在iget中睡眠。在该i节点变为开锁状态并唤醒该睡眠进程之后,为证实该i节点是否为上锁状态及该i节点中是否还在高速缓冲中,进程需要重新开始搜索i节点。
11.假定盘块的大小为1KB,每个盘块号占4个字节,文件索引节点中的磁盘地址明细表如下图所示,如何将下列文件的字节偏移量转换为物理地址?
(1〉9000;(2)14000;〈3)350000
4096
228
4542
0
3
11111
50
101
367
0
428
9156
824
1101
109
954
952
0
1
2
3
3300
333
308
428
331
452
74
9156 331
答：UNIX系统将文件的字节偏移量转换为文件物理块号的过程分两步实现:第一步,将字节偏移量转换为文件逻辑块号及块内偏移量;第二步,把逻辑块号转换为文件的物理块号。其转换方法如下:
首先,将字节偏移量转化为文件逻辑块号,即将字节偏移量除以盘块大小的字节数,其商是文件逻辑块号,余数是块内位移量。然后,把文件逻辑块号转换为物理盘块号。根据逻辑盘块号可知对应的文件地址是直接地址还是间接地址,若为直接地址,即当文件逻辑盘块号小于10时,将文件逻辑块号转换为索引节点的地址项下标,从该地址项中即可获得物理盘块号;
若为一次间接寻址,即当文件块号大于或等于10且小于266时,从索引节点的一次间接项中得到一次间接的盘块号;再计算一次间接块中的地址下标,即将文件的逻辑块号;或10,从相应下标的地址项中得到物理块号;若为多次间接寻址,即当文件的逻辑块号大于或等于266而小于65802时,应采用二次间接寻址,而当逻辑块号大于或等于65802时,应采用三次间接寻址,多次间接寻址的转换方法和一次间接寻址相类似,但要多次循环。
解:(1)字节偏移量为9000,此时逻辑块号为:9000/1024=8
块内偏移量为:9000-8×1024=808
因逻辑块号小于10,因此该块为直接块。由图可知,其物理盘块号为367,该块中的第808字节即为文件的第9000字节。
(2)字节偏移量为14000,此时逻辑块号为:14000/1024=13
块内偏移量为:14000一13×1024=688
因逻辑块号10<13<266,因此该块为一次间接块。
由图可知,一次间接的盘块号为428,从一次间接块中读出盘块号表,查得其物理盘块号为952,该块中的第688字节即为文件的第14000字节。
(3)字节偏移量为350000,此时逻辑块号为:350000/1024=341
块内偏移量为:350000-341×1024=816
因逻辑块号266<341<65802,因此该块为二次间接块。
由图可知,二次间接的盘块号为91560由于一个一次间接块中可容纳256个块号,
341-266=75
因此字节偏移量350000在二次间接块的第0个一次间接块的第75个表项中,其盘块号为3333,该块中的第816字节即为文件的第350000字节。
8.4自测题一、判断题
1.在UNIX系统中所有进程都是利用系统调用fork创建的。 （ ）
2.在早期的UNIX操作系统中,16位虚地址经地址转换后得到18位的物理地址。 ( )
3.软中断信号是一种实现进程间简单通信的设施,用于通知对方发生了异常事件。 （ ）
4.UNIX是批处理操作系统。 ( )
5.在UNIX系统V中,用户通过原语读取磁盘文件中的数据。 ( )
6.UNIX采用流式文件逻辑结构和索引文件物理结构。 （ ）
7.UNIX文件系统分为基本文件系统和扩充文件系统两部分。 （ ）
8.在UNIX中把外围设备也当作文件看待,称为设备文件。 ( )
9.在UNIX系统中,管道文件用于把一个进程的输出连接到另一个进程的输入。 （ ）
10.提供可动态装卸的文件卷是UNIX的特色之一,( )
二．单项选择题
1.UNIX是当今世界上广为使用的__________。
A.小型计算机操作系统 B.多用户多任务操作系统
C.大型计算机操作系统 D.实时多任务操作系统
2．在UNIX系统Ⅴ中,进程控制块由__________组成。
A.PROC结构和USER结构 B.用户栈和PROC结构
C.系统区表和USER结构 D.PROC结构和核心栈
3.UNIX操作系统的SHELL是负责___________的模块。
A.解释并执行来自终端的命令 B.解释并执行来自终端的内部命令
C.解释并执行来自终端的外部命令 D.进行功能调用
4.UNIX系统中把设备分为___________。
A.输入设备和输出设备 B.字符设备和块设备
C.系统设备和用户设备 D.共享设备和虚拟设备
5.在UNIX系统中,用户通过___________读取磁盘文件中的数据。
A.作业申请表 B.原语 C.系统调用 D.软中断
6.UNIX System V的调度原理基于__________。
A.先来先服务 B.短作业优先 C.时间片轮转 D.时间片+优先级
7.UNIX System V的存储管理策略基于 ____________.
A.单一连续分配 B.固定式分区分配 c.可变式分区分配 D.请求分页
8.在UNIX System V中,系统向用户提供的用于创建新进程的系统调用是__________.
A.read B.fork C.pipe D.exit
9.在UNIX系统V中,用户通过____________读取磁盘文件中的数据。
A.系统功能调用 B.作业申请表
C.原语 D.中断
10.UNIX系统V的进程调度原理是基于____________。
A.最短作业优先 B.时间片调度
C.时间片加优先级 D.先来先调度
11.当进行中断处理和系统调用时,都将涉及到进程上下文的保存和恢复,此时系统所保存和恢复的是_______________的上下文。
A.系统进程 B.同一个进程 C.不同进程 D.其他进程
12．在UNIX系统中采用的是_________对空闲磁盘块进行组织。
A.位示图 B.空白文件目录 C.链接法 D.成组链接法
13.所谓管道是指能连接某些读进程和写进程的、专门用于进程通信的共享文件。它允许读/写进程按_________的方式传送数据。
A.后进先出 B.先进先出 C.任意 D.后进后出
14.UNIX操作系统的文件系统是__________.
A.一级目录结构 B.二级目录结构 C.分级树形结构 D.链表结构
15.在UNIX中,文件的逻辑结构是__________。
A.记录式结构 B.无结构流式结构 C.串联文件结构 D.树型文件结构
16.在UNIX SystemV操作系统中,存储管理采用___________方案。
A.段式管理 B.请求分页管理
C.可变式分区管理 D.固定式分区管理
17.下列4个操作系统中,_________没有多道程序设计的特点。
A.OS/2 B.MS-DOS C.UNIX D.WIndows NT
18.下列4个操作系统中,_________具有多道程序设计的特点,但不是分时系统。
A.OS/2 B.Windows 3.1 C.UNIX D.Windows NT
19.UNIX系统中,把输入/输出设备看作是________.
A.普通文件B.特殊文件C.索引文件D.目录文件
20.在UNIX系统的多用户环境下,各个用户都是通过口令在各自的注册账号下行使自己的系统权限。系统对每个文件实行了______三级保护加强了文件的保密性和安全性。
A.文件的系统、隐含及私杳 B.文件的所有者、同组用户及其他人
C.读、写及执行 D.读、写、执行及拷贝三．填空题
1.UNIX操作系统在结构上分为_____________和_________________两部分。
2.UNIX系统为用户提供了面向操作的接口____和面向_____的接口____。
3.UNIX 系统Ⅴ中，采用的进程调度算法是_________________________。
4.在UNIX System V中,将PCB分成进程表项和U区。除进程表项和U区外,管理进程的数据结构还有________和____。
5.在UNIX中文件可分为三类:______、____和_____。
6.UNIX把执行状态分为两种:一种是_________执行,另一种是核心态执行。
7.在UNIX系统中,为实现请求调页,核心配置了四种数据结构:____、____、______和____。
8.在UNIX系统中有两种读方式:一般读方式和_______方式。
9.UNIX系统中的每个目录项由______及其相应的______组成。
10.在UNIX文件管理系统中,为了对磁盘空间的空闲块进行有效的管理,采用的方法是___________。
11.UNIX的0#进程的主要功能是创建用户进程、___________。
12.用户在第一次访问任何文件之前,都必须先使用系统调用______来打开指定文件,然后才能对该文件执行读、写和修改等操作。
答:open
13.在UNIX系统中,键盘、终端、打印机等以_____为单位组织和处理信息的设备称为____;而磁盘、磁带等以_____为单位组织和处理信息的设备称为______。
14.通往一个文件的路径数目称为此文件的________.
答:联结计数
15.缓冲区可分为______、_____、_____和_____。
16.一个进程只有在获得______、____和所需设备三者之后,才具备进行____的物质条件。
四．简答题
1.UNIX操作系统为用户提供哪些接口?试举例说明。
2.UNIX System V中,系统程序所对应的正文段未被考虑成进程上下文的一部分,为什么?
3.UNIX System V进程上下文由哪几部分组成?为什么说核心程序不是进程上下文的一部分?进程页表也在核心区,它们也不是进程上丁文的一部分吗?
4.UNIX System V的调度策略是什么?调度时应该封锁中断吗?如果不封锁,会发生什么问题?
5.试述进程0的作用。
6.在系统调用sleep和wakeup时,要提高处理机的执行级(相当于优先级)来防止中断,为什么要这样做〈提示:系统经常要从中断处理程序中唤醒睡眠进程)。
7.进程在什么时候处理它接收到的软中断信号?进程接收到软中断信号后放在什么地方?
8.UNIX System V为什么要采用交换和请求调页两种内存管理策略?交换和请求调页才式有何区别?
9.UNIX文件系统为什么有磁盘i节点和内存i节点?为什么内存i节点的内容和磁盘i节点的内容不一样?
10.为什么要有系统打开文件表?用户进程是怎样与文件系统联系的?创建一个文件时创建系统打开文件表吗?
11.UNIX采统为什么要设置延迟写和异步写?它们各有什么优缺点?
12.UNINX System v中进程管理和存储管理部分有哪些联系？
8.4.2解析题
1.试说明一个进程在其生命周期内的变化过程。
2.在UNIX系统中运行下面程序,最多可产生多少个进程?画出进程家族树。
main( )
{
fork();
fork();
fork();
}
3.UNIX采用一般写、异步写和延迟写三种方式将缓冲区中的内容写回磁盘。试述这三种方式的特点。
4.UNIX的i节点是文件内容的一部分,对吗?请说明理由。
5.是否当每次进行磁盘读/写时,核心都要为之分配缓冲区?当需要分配缓冲区时,应从何处获得?
6.编写一个程序,使用系统调用fork生成三个子进程,并使用系统调用pipe创建一管道,使得这三个子进程和父进程共用同一管道进行通信。
7.一个UNIX文件F的存取权限为,rwxr-x---,该文件的文件主uid=12,gid=1。另一个用户的uid=6,gid=1,是否允许该用户执行文件F?
8.下列程序执行时,"parent:child exited"可能在"child leaving"前面打印吗?为什么?程序执行结果中a=?为什么?
{…
a=55;
pid=fork():
if(pid==0)
{
sleep(5);
a=99;
sleep(5);
printf("child leavingh");
exit(0);
}
else
{
sleep(7):
pdntf(“a=%d\n",a);
wait(0):
printf(“parent:child exited\n");
}
}
为了便于读者理解本程序,将程序注释如下:
{
a=55;
pid=fork(); /*创建子进程*/
if(pid==0) /*子进程执行*/
sleep(5):/*睡眠5秒*/
a=99;
sleep(5);
printf("child leaving\n");
exit(O);
}
else /*父进程执行*/
{
sleep(7);/*睡眠7秒*/
printf("a=%d\n”,a);
wait(O); /*等待子进程终止*/
printf("parent:child exitedh");
}
}
9.在UNIX系统中有卷资源表如下所示:
(1)现有个进程要释放四个物理块,其块号为
150#,156#,172#,177#,画出卷资源表的变化。
(2)在(1)的基础上假定一进程要求分配5个空闲块,画出分配后的卷资源表。
10.描述UNIX System V的i节点释放过程ifree,并说明为什么在文件系统中会含有其索引节点号比"铭记"索引节点号小的空闲索引节点。
11.试述下面程序的运行结果。
#include 〈fcntl.h〉
int fdrd,fdwt;
char c;
main(arse,argv)
int argc;
char *argv[];
{
if(argv!=3)
exit(l);
if(fdrd=open(argv[1],O_RDONLY))==一1)
exit(1):
if(fdwt=creat(argv[2],0666))==-1)
exit(1):
fork():
rdwrt():
exit(0):
}
rdwrt()
{
for〈;;)
{
if(read(fdrd,&c,1)!=1)
return;
write(fdwt,&c,1);
}
}
12.假定一个索引节点为128字节,指针为4字节长,而状态信息占用了68个字节。假定每块的大小为8K。问在索引节点中有多大的空间给指针?使用直接指针、间接指针、二次间接指针、三次间接指针分别可以表示多大的文件?
8.4 答案一．判断题
1.Χ 2.√ 3,√ 4,Χ 5,Χ 6,√ 7,Χ 8,√ 9.√ 10.√
二．选择题：
1.B 2.A 3.A 4.B 5.C 6.D 7.D 8.B 9.A 10.C 11.B 12.D 13.B 14.C 15.B 16.B 17.B 18.B 19.B 20.B
三．填空题
1.
2.Shell ②程序 ③系统调用
3.
4,本进程区表 系统区表
5,普通文件 目录文件 特殊文件
6.用户态
7.页表 磁盘块描述表 页面数据表 对换使用表
8.提前读
9.文件名 索引节点号
10.成组链接法
11.对换
12.open
13.字符 字符设备 块 块设备
14.联结计数
15.单缓冲区 双缓冲区 多缓冲区 缓冲池
16.通道 控制器 I/O操作四．简答题
1.答:UNIX系统为用户提供两个接口,即面向操作命令的接口Shell和面向编程用户的接口:系统调用。常见的Shell命令:login,logout,vi,emacs,cp,rm,ls,cc,link,adduser,date等；常见的系统调用如:ioct1,read,write,open,close,creah，exec1,flock,stah mount,fork,wait,exit,socket等。
2.答:因为系统程序的代码被用户程序所共享,因此如果每个进程在保存进程上下文时,都将系统程序代码放到其进程上下文中,则大大浪费了资源。因此系统程序的代码不放在进程上下文中,而是统一放在核心程序所处的内存中。
3.答:UNIX System V进程上下文由以下几部分组成：
Proc结构,User结构,用户找和核心梭的内容,用户地址空间的正文段和数据段,硬件寄存器的内容,区表,页表。
核心页表被所有进程共享,所以不是进程上下文的一部分。
而进程页表是进程上下文的一部分。
4.答:UNIX System V采用基于优先级的多级轮转反馈调度策略。在调度时应封锁中断,否则在调度过程中由于中断会使进程上下文的切换出现错误。
5.答:当UNIX操作系统装入内存后,系统的控制权便由自举程序转到核心程序,即操作系统程序上来。核心首先生成系统进程0,然后由0号进程创建一个1号进程(即init进程),进程1负责初始化所有新的用户进程。实际上,1号进程是除了0号进程之外所有用户进程的祖先。UNIX系统的调度与交换都是0进程的两部分,它们分别由swtch过程和sched过程实现。sched过程把处于外存就绪态的进程换入内存,swtch则从就绪队列中寻找一优先级最高的进程。
因此,进程0的作用是:创建进程1,进行进程的调度和交换。
6.答:系统调用sleep和wakeup时经常要做进程上下文切换,而系统又经常要从中断处理程序中唤醒睡眠进程,为了保证进程上下文切换的正确进行,防止在切换过程中响应中断,需要提高处理机的执行级。
7.答:进程在再次被调度执行时先检查是否收到软中断,若进程接收到了软中断信号则优先处理软中断。进程把接收到软中断信号存放在proc结构的相应项中。
8.答:交换是UNIX System早期版本引入的扩充内存技术,但交换不能实现虚拟存储,故UNIX System V引入请求调页内存管理策略以实现虚拟存储且保留了交换技术。
交换技术在交换时换入换出的是整个进程(除Proc外),即使实现部分交换也不是按进程执行的需要进行交换。交换根据程序和数据在内存或外存中驻留时间长短进行换入换出。交换不能实现虚拟存储。
请求调页只是把经常执行或正在执行的页调入内存,当执行到当前页不在内存时,系统调入此页。请求调页内存管理技术可以实现虚拟存储。
9.答:UNIX系统中,磁盘i节点以静态形式存放文件说明信息。引入内存i节点是为了减少设备的启动次数以及提高操作速度,把磁盘i节点复制到内存特定区域。由于进程需用i节点中的逻辑结构和物理结构信息完成对文件信息的保护和共享,故i节点中多了当前文件状态信息。
10.答:用户打开文件表记录一个进程可以同时打开的文件数,UNIX System V最多可达到20。用户打开表的描述符返回给用户进程后成为文件描述符。与此相对应,用户对文件进行操作时,在系统内部需有相应数据结构来记录和控制打开文件的用户进程,以及记录和控制那些共享同一文件的用户进程。这个数据结构就是系统打开表。用户进程通过系统调用来完成与文件系统联系。创建文件时,需要在系统打开文件表的相应表项中生成相应数据,但不需要创建系统打开表。
11.答:异步写的目的是提高写盘速度,延迟写的目的是为了让数据块在内存中待尽量多的时间,以减少不必要的I/0操作。优点:把一个缓冲区的数据往磁盘写时,如同步,进程因为等待写操作完成而进入睡眠,而且要在写操作完成后才释放缓冲区。如延迟写或异步写时,系统启动传输,不等写完成而返回,都加快了写盘速度,但延迟写还减少了不必要的I/O操作。缺点:延迟写没有立即把数据写入磁盘,当系统发生瘫痪时将产生磁盘数据错误。异步写是启动传输后,不等传输完成而返回,也可能发生数据错,但可能性小。
12.答:进程管理包括进程创建、进程调度、进程执行和进程撤消。进程创建、调度和执行需要存储管理部分为进程分配或释放内存空间,进程的撤消需要存储管理部分回收分配给撒消进程的内存空间。存储管理系统必须决定哪个进程的哪个部分应该放在内存,并管理那些不在内存又属于同一进程虚空间的部分。
解析题8
1.答:一个进程从被创建开始到被释放为止，状态之间的转换有些是通过系统原语或核心函数完成,有些则由外部事件的发生而导致状态转换。下面我们讨论一个进程可能的状态变迁过程,其中的事件说明了各种可能的转换原因,但进程并不一定总是要经历这些事件。
首先,当父进程执行系统调用fork时,被创建进程进入创建状态。当被创建进程处于该状态时,核心为该进程分配U区以及必要的内存工作集。内存管理分配程序如果能为该进程分配足够的内存,则进程状态发生变化,由创建状态变为内存中就绪状态。此时,由于该进程已分得存放U区、各种页表和堆钱以及部分正文段和数据段等的内存空间,因此,该进程可以经调度选中后占有CPU。
如果内存分配程序不能为该进程分配足够的内存,则该进程的进程上下文被存放到外存交换区中,进程由创建状态变为就绪且换出状态。如果进程处于就绪且换出状态,则只有在交换程序将进程上下文换入内存成为状态之后,才有可能被调度执行。
当进程进入内存中就绪状态后,进程调度程序将会在适当时机选择该进程去执行。这时,该进程在核心态下执行,以装配该进程的进程上下文。在这个状态下,该进程完成它的fork部分的工作。
当该进程完成fork系统调用后,它可能返回用户态下执行用户程序,这时该进程进入用户态执行状态。
另外,UNIX System V的调度策略规定,在进程完成系统调用后返回用户态之前,若此时有优先级高于当前进程的进程存在,则系统将调度优先级高的进程去占据处理机,从而使当前运行进程进入状态被剥夺状态。进程进入被剥夺状态之后,所处的地位与内存中就绪状态相同,即要等到再一次进程调度时才能返回用户态执行。
当进程处于用户态执行时,用户程序中由于使用系统调用或输入/输出数据等而发生陷入与中断。这样,进程又进入核心态执行。
进程在核心态执行时,因为等待某事件发生,如等待输入/输出完成等,调用sleep原语进入内存中睡眠状态。处于内存中睡眠状态的进程因为内存的限制,将在睡眠一段时间后被交换程序换出内存而进入睡眠且换出状态,直到事件发生后被唤醒原语唤醒而进入就绪且换出状态。
当进程完成时,将使用系统调用exit,从而使得进程进入僵死状态。
2.答：分析：系统调用fork的功能是创建一个新进程,新浙主运行与其创建者一样的程序,新创建的进程称为子进程,调用fork的进程称为父进程,父子进程都从fork调用后的那条语句开始执行。
当程序执行时,若所有进程都能成功地执行系统调用fork,则会产生最多数目的进程。为了描述方便起见,将开始执行时的进程称为A进程,此时程序计数器PC 指向第一个fork调用。
main( )
{
fork(); /*←PC,进程A*/
fork();
fork();
}
当进程A成功地执行完第一个fork调用时,它创建了一个子进程,将此子进程称为进程B。此时,进程A、B的程序计数器PC指向第二个fork调用,进程A派生了1个子孙进程。
main()
{
fork();
fork(); /*←PC,进程A*/
fork();
}
当进程A、B成功地执行完第二个fork调用时,它们分别创建了一个子进程,将这些子进程分别称为进程C、D.此时,进程A、B、C、D的程序计数器PC指向第三个fork调用,进程A派生了3个子孙进程。
Main()
{
fork();
fork();
fork(); /* ←pc,进程A */
}
main()
{
fork();
fork();
fork(); /*←PC,进程B*/
}
main()
{
fork();
fork();
fork(); /*←PC,进程C*/
}
main()
{
fork();
fork();
fork(); /*←PC,进程D*/
}
当进程A、B、C、D成功地执行完第三个fork调用时,它们分别创建了一个子进程,将这些子进程分别称为进程E、F、G、H.此时,进程A、B、C、D、E、F、G、H的程序计数器PC指向程序结束处,进程A派生了7个子孙进程。
main()
{
fork();
fork();
fork();
} /*←PC,进程A*/
main()
{
fork();
fork();
fork();
} /*←PC,进程B*/
main()
{
fork();
fork();
fork();
} /*←PC,进程C*/
main()
{
fork();
fork();
fork();
} /*←PC,进程D/
main( )
{
fork();
fork();
fork();
} /* ←PC,进程E/
main()
{
fork();
fork();
fork();
} /*←PC,进程F*/
main()
{
fork();
fork();
fork();
} /*←PC,进程G*/
main()
{
fork();
fork();
fork();
} /* ←PC,进程H*/
进程家族树是一棵有向树,有向树的节点代表进程,由进程P指向进程Q的边表示由进程P创建了进程Q。我们称进程P走进程Q的父进程,进程Q走进程P的子进程,这样便形成了进程树。
答:从上面的分析过程可以看出,执行第一个fork调用时,进程A创建了进程B；执行第二个fork调用时,进程A创建了进程C,进程B创建了进程D；执行第三个fork调用时,进程A创建了进程E,进程B创建了进程F,进程C创建了进程G,进程D创建了进程H。因此,在UNIX系统中运行题目中的程序,最多可产生7个进程,其进程家族树如下图所示。
3.答:(1)一般写。启动设备写时,进程使自己睡眠,等待写操作完成后唤醒等待进程。
(2)异步写过程。启动设备写后,进程不等待写操作完成即返回。
(3)延迟写过程。进行延迟写时,只是将数据写到内存缓冲区中,等到该缓冲区分配给其他磁盘块使用时再将该块内容写入磁盘,从而增加了数据在内存的驻留时间。
4.答：在UNIX系统中,文件名与文件说明是分开存放的。由文件说明形成的一个数据结构称为索引节点(index node ),而相应的文件目录项则只由文件名和其索引节点号构成。
索引节点又称i节点,其中存放文件的说明信息。索引节点以静态形式存放在磁盘上,故又称为磁盘索引节点。每个文件都有惟一的一个磁盘索引节点,它由下述字段构成:
文件所有者标识符、文件类型、文件存取权限、存放文件的物理地址、文件长度、文件联结计数和文件存取时间。
为了加快文件的存取速度和减轻磁盘I/0的压力,系统又专门在内存中建立了一个内存索引节点表,将那些要被引用的磁盘索引节点复制到内存索引节点表中,并增加了如下字段:
索引节点号、内存索引节点状态、内存索引节点引用计数、设备号、内存索引节点指针从上面的分析可以看出,UNIX系统中的i节点不是文件内容的一部分,而是用于文件管理的数据结构。
5.答：每当进行磁盘读/写操作时,核心调用getblk过程分配缓冲区.当要读磁盘数据时,核心首先检查委读入的盘块内容是否已在某个缓冲区中,若发现已在某个缓冲区中,便不必再从磁盘上读入。仅当数据未在任何缓冲区中时,核心才需从磁盘上将数据读入,这时才需为其分自己一空闲缓冲区。类似地,当要把数据写入一特定盘块时,核心应先检查该决内容是否已在某缓冲区中,仅当该块内容尚不在缓冲区中时,才需分配一空闲缓冲区。获取空闲缓冲区时应提供的输入参数是文件系统号和磁盘块号。getblk过程分自己缓冲区时,可分为两种情况:
(1)缓冲区在散列队列上。进入getblk过程后,首先根据文件系统号和盘块号去查找散列队列,若找到与文件系统号和块号相匹自己的缓冲区,便可进一步检查该缓冲区是否空闲。若空闲,则应先上锁,以防止其他进程对它进行访问,然后把它从空闲链上摘下;若忙,则表明缓冲区已被其他进程上锁,因此暂时不能对它进行访问而进入睡眠,直至该缓冲区变为空闲时再将它唤醒。
(2)缓冲区不在散列队列上。若在散列队列中找不到与文件系统号及块号相匹配的缓冲区,使只有从空闲链表中找一个缓冲区.若空闲链表已空,则无法进行分配,进程睡眠,直到空闲链表中出现缓冲区为止;若空闲链表不空,这时可从链首摘下一缓冲区,若此缓冲区标记有"延迟写",此时应将该缓冲区内容异步地写到磁盘上,再从空闲链表中摘下一个缓冲区,并调整该缓冲区所在的散列队列,即将该散列队列从原来的散列队列调整到新的散列队列中.因为当该缓冲区重新分自己后,缓冲区对应的盘块号发生了变化,从而也相应地改变了其所在的散列队列.
由上面的叙述可以看出,当每次进行磁盘读/写时,核心都要检查读/写操作对应的磁盘块是否在缓冲池中。如果在缓冲池中,则直接引用缓冲池中的数据:如果不在,则分配一个空闲缓冲区。当需要空闲缓冲区时,应从空闲队列首部摘下缓冲区。
6.答:因pipe系统调用建立的是无名管道,而父子进程之间又需要通过无名管道进行通信,因此应先建立管道,再创建进程。
main( )
int r,p1,p2,,p3,fd[2] /*fd[2]用于存放管道文件描述符*/
char buf[50],s[5];
pipe(fd); /*创建管道,fd[0]、fd[1]分别为读、写描述符*/
while((p1= fork())==1); /*创建子进程1*/
if(pl==0) /*在子进程1中执行*/
{
lockf(fd[1],1,0); /*锁定写,参数1、0分别表示锁定、锁定范围*/
sprintf(buf,"child process P1 is sending message!\n");
printf("child process pl!\n");
write(fd[1],buf,50); /*将buf中的数据写入管道*/
sleep(5); /*睡眠等待*/
lockf(fd[1],0,0); /*解锁,第一个参数0表示解锁*/
exit(0);
else /*F父进程执行*/
{
while((p2=fork())=-1); /*创建子进程*/
if(p2===0) /*在子进程2中执行*/
{
lock(fd[1],1,0); /*锁定写*/
sprintf(buf,"child process P2 is sending message!\n);
printf("child process P2!＼n");
write(fd[1],buf,50); /*将buf中的数据写入管道*/
sleep(5); /*睡眠等待*/
lockkfd[1],0,0):/*解锁串/
exit(0);
}
else /*P父进程执行*/
{
while((p3=fork())==1); /*创建子进程3*/
if (p3==0) /*在子进程3中执行*/
lockf(fd[1],1,0); /*锁定写*/
sprintf(buf,"child process P3 is sending message!＼n");
printf(“child process P3!\n");
write(fd[ll,buf,50); /*将buf中的数据写入管道*/
sleep(5); /*睡眠等待*/
lockf(fd[1],0,0); /*解锁*/
exit(0);
}
wait(O); /*等待子进程执行*/
if(r=(read(fd[0],s,50)==-1) /*读管道内容到s*/
printf("can't read pipe\n");
else
printf(“%s\n",s);
wait(0); /*等待另一子进程执行*/
if(r=(read(fd[0],s,50)==-1) /*读管道内容到s*/
printf("can't read pipe\n");
else
printf("%s\n",s);
wait(O); /*等待最后一子进程执行*/
if(r=(read(fd[o],s,50)==-1) /*读管道内容到s*/
printf("can't read pipe\n");
else
printf("%s\n",s);
exit(0);
}
}
}
7．答：在UNIX操作系统中,一个文件应属于某个用户所有,我们将这个用户称为该文件的文件主。一般情况下,文件主就是建立文件的用户。在系统中,使用用户标识符(uid)来记录文件主.UNIX将使用文件的用户分成三类,即文件主、同组用户和其他用户。同组用户是相互之间有某种关系的用户,如同一课题组的人,用户所在的用户纽用纽标识符(gid)来表示.其他用户一般是和文件主元关的用户,但他们也是系统中的用户。
每一类用户对文件的操作都有三种不同的存取权限,即读、写和执行。由于有三类用户,每类用户有三种存取权限,故每个文件都有9种存取权限。在系统内部,文件的存取权限用9位二进制数描述,文件主权限对应最高三位,同组用户权限对应中间三位,其他用户权限对应低三位。例如,111101001(也可以用八进制数表示,如0751),表示文件主可以对该文件进行读、写、执行操作;同组用户可以对该文件进行读和执行操作;其他用户只能对该文件进行执行操作。
当系统用ls命令列目录时,文件权限以标准的符号形式表示。这种表示法使用9个字符,分为3组,每组3个字符.第一纽表示文件主的权限,第二纽表示同组用户的权限,第三组表示其他用户的权限.在每组的三个字符中,如果允许这类用户读,则第一个字符直为"r",如果允许进行写,则第二个字符直为"w",如果允许执行,则第三个字符置为"x"。如果不允许某个权限,则相应的字符置为"一".
由上述介绍可知,文件F的存取权限rwxr-x- - - 表示文件主可以对F进行读、写及执行操作,同组用户可以对F进行读及执行操作,其他用户不能对F进行操作。因为另一用户与文件主的组标识符相同(gid均为1),由此可知他们是同组用户,所以允许该用户执行文件F。
8.答:由于UNIX输出时采用缓冲区缓冲数据,尽管本程序中通过sleep来让进程睡眠,以达到同步控制的目的,但缓冲区中的数据"parent:child exited"仍有可能在"childleaving"前面打印输出。
在进程创建之前,变量a的值设置为55,进程创建之后,父子进程具有各自私有的数据区。因在父进程中,没有重新对变量a赋值且打印输出语句在父进程中,所以,程序执行结果中,输出的是"a=55"。
9.答：（1）画出的卷资源表如下:
将这块内容填入172#中,则卷资源表变成如下形式:
(2)先根据卷资源表取出172块的内容:取走177,172两块,然后将取出的内容置为卷资源表内容,取走其中的156,150,210,则卷资源表变为:
10.答：在UNIX System V中,文件系统包含一个索引节点线性表.如果索引节点的类型字段为0,则说明这个索引节点是空闲的。从理论上说核心能搜索磁盘索引节点表,以寻找一个空闲节点。然而像这样的技索太费时间,至少对每个索引节点都需要一个读操作(可能从磁盘读)。为了改善性能,在UNIX的文件系统超级块中包含一个空闲索引节点表,以便把文件系统中空闲的索引节点号缓存起来。当系统分配一个索引节点时,核心首先验证超级块是否上锁。在超级块未上锁时,若超级块中的空闲索引节点号表非空,则核心分配下一个索引节点号;若超级决空闲索引节点表为空,则核心搜索磁盘,并把尽可能多的空闲索引节点号放到超级块中。核心一块接一块地读磁盘上的索引节点表,并将空闲索引节点号填入超级块空闲索引节点表中,直至表满为止。同时,核心记住它所找到的最高序号的索引节点,称之为铭记索引节点,这是保存在超级块中的最后一个索引节点。下次核心搜索磁盘上的空闲索引节点时,就从铭记索引节点开始,这样能确保核心不浪费时间去读那些已不含空闲索引节点的磁盘块。
UNIX System V中的i节点释放过程ifree用于回收磁盘索引节点。其算法可形式化带述如下:
算法ifree
输入:文件系统索引节点号输出:无
{
文件系统空闲索引节点计数值增1:
if(超级块被锁住)
return:
if(索引节点表满〉
{
if(索引节点号小于用于搜索的铭记索引节点号〉
置用于搜索的铭记索引节点号=输入索引节点号:
}
else
把输入索引节点号存储到空闲索引节点表中:
retunu
}
在ifree算法中,当核心发现超级块上锁时,为了避免竞争,该算法立即返回。这时,系统既没有将释放的索引节点放入超级块的空闲索引节点表中,也没有修改铭记索引节点,而此时释放的索引节点号可能小于当前超级块中的铭记索引节点号,因此,在文件系统中可能会含有其索引节点号比"铭记"索引节点号小的空闲索引节点。
11.答：在本题程序中,调用该程序应有两个参数,一个是已有的文件名,另一个是要创建的新文件名。该程序打开已有的文件,创建一个新文件,若上述两个系统调用成功,则再利用fork创建一个子进程。父进程和子进程在不同的地址空间上运行相同的程序代码,每个进程都存取私有的全局变量fdrd,fdwt和c及私有的找变量argc和argv,但每个进程都不能存取另一进程的这些私有变量。父进程和子进程分别独立地调用rdwrt函数,并执行函数中的循环,即从源文件中读一个字节,然后写一个字节到目标文件中。当系统调用遇到文件尾时,函数rdwrt立即返回。
由于在fork调用前,相应的文件己打开或创建,因此父进程和子进程通过相同的文件表项共享对文件的存取,即两个进程的文件描述符fdrd都指向源文件的文件表项,fdwt都指向目标文件的文件表项。这两个进程永远不会读或写到相同的文件偏移量,因为核心在每次read和write调用之后,都要增加文件的偏移量。两个进程合作完成了一次从源文件到目标文件的复制工作,每个进程完成了其中的一部分文件复制任务,因此目标文件的内容依赖于核心调度两个进程的次序。如果核心只在每个进程执行完一对read和write系统调用后才进行切换,即在每个进程从源文件中读出的一个字节写入目标文件后才进行切换,则目标文件的内容与源、文件完全一致;否则,源文件的内容与目标文件不同。考虑、下述情况,两个进程正要读源文件中的两个连续的字符"ab",假定父进程读了字符"a",这时,核心在父进程做写之前,进行上下文切换并调度子进程运行;如果子进程读到字符"b"并在父进程被调度到之前将它写入目标文件,那么,目标文件将不再正确地含有字符串"ab",而是含有"ba”。
本程序完成的功能是将源文件复制到目标文件,父子进程合作完成此任务,但因核心并不保证进程执行的先后顺序,源文件与目标文件字符个数及字符内容相同,但次序不一定相同,如源文件为"aba",目标文件可能为"aab"。
12.答:由于索引节点为128字节,状态信息存用68个字节,用于指针的空间大小为:
128-68=60(字节〉
一次间接指针、二次间接指针和三次间接指针将占用索引节点中的三个指针项,因此直接指针项数为:
60/4-3=12(个)
使用直接指针时:
12×8196=98304(字节〉
大小不超过98304字节的文件使用直接指针即可表示。
使用一次间接指针时:
8196/4=2048(即一个磁盘块中可以装入2048个指针项)
2048×8196=16M〈字节〉
一次间接指针提供了对附加16M字节信息的寻址能力。
使用二次间接指针时:
2048×2048=4M(即二次间接可以提供4M个指针项)
4M×8196=32G(字节〉
二次间接指针提供了附加32G字节信息寻址能力。
使用三次间接指针时:
2048×2048×2048=8G(即三次间接可以提供8G个指针项〉
8G×8196=16T〈字节〉〈1T=1024GE240〉
三次间接指针提供了对附加16T字节信息的寻址能力。
UNIX操作系统从一个非常简单的操作系统发展成为性能先进、功能强大、使用广泛的操作系统,并成为事实上的多用户、多任务操作系统标准。
8.1内容辅导
8.1.1 UNIX操作系统概述
1.UNlX系统的特点
UNIX系统的特点如下：
（1）UNIX是一个多用户、多任务的操作系统,每个用户都可同时执行多个进程,系统中的进程数目在逻辑上不受限制。
（2）提供了精选的、丰富的系统功能,其中许多功能在实现思想上有其独到之处,且是高效的。
（3）该系统用高级语言编写,使系统具有易读、易懂、易修改、易移植等一系列优点,且系绕代码十分紧凑。
（4）提供了良好的用户界面。该系统提供一种命令程序设计语言SHELL作为用户界面;同时提供了系统调用作为用户程序与系统的接口。这些界面既能为用户提供各种服务,又相当简洁。
（5）在UNIX系统中使用了树型结构的文件系统,它具有良好的安全性、保密性和可维护性,在文件系统的实现方法上,也有较多创新。
（6）系统提供了多种通信机制,以满足各种进程通信的需要。
（7）在存储管理上,为提高内存利用率,提供了进程对换存储管理方式和请求调页的存储管理方式,以实现虚拟存储器。
2.UNlX系统核心体系结构整个UNIX系统可分成两大部分。第一部分是由用户程序和系统提供的服务构成的所谓核外程序,形成了良好的系统环境:第二部分是操作系统,又称为核心,其中两个最主要的部分是文件子系统和进程控制子系统。
用户程序可以通过高级语言的程序库或低级语言的直接系统调用进入核心。核心中的进程控制子系统负责进程同步、进程间通信、进程调度和存储管理。文件子系统管理文件,包括分配文件存储空间、控制对文件的存取以及为用户检索数据。文件子系统通过一个缓冲机制同设备驱动部分交互作用。设备管理、进程管理及存储管理通过硬件控制接口与硬件交互作用。
8.1.2 UNIX的进程在UNIX系统中,采用了段页式存储管理〈在UNIX中将段称为区〉方式,因此一个进程实体由若干个区组成,包括程序区、数据区、核区等。每个区又可分为若干页。
1.进程的描述在UNIX System V中,将PCB分成进程表项和U区。除进程表项和U区外,管理进程的数据结构还有本进程区表和系统区表。
（1）进程表项进程表项中的每个表目主要包含以下信息:标识进程状态的状态域；用户标识号,简称UID或用户ID；进程标识号,简称PID或进程P；存储区位置和长度；调度参数（包括优先数等）；软中断信号域；各种计时域；指向U区的指针；事件描述域。
（2）U区
U区中的各个域进一步刻画了进程的特性,U区主要包含以下信息:指向进程表项的指针；真正用户标识符(real user ID)及有效用户标识符(effective user ID)；用户文件描述符表；当前目录和当前根；计时器域；一些输入/输出参数；限制域；出错域；返回值域；信号处理数组。
（3）系统区表
UNIX System V把一个进程的虚地址空间划分为若干连续的逻辑区,有正文区、数据区、核区等。这些区是可被共享和保护的独立实体,多个进程可以共享一个区。为了对区进行管理,在核心中设置了一个系统区表(简称区表),各表项中记录了描述活动区的有关信息:区的类型和大小；区的状态（一个区具有这样几种状态:锁住、在请求中、在装入过程中、有效)；区在物理存储器中的位置；引用计数；指向文件索引节点的指针。
（4）本进程区表为了记录进程的每个区在进程中的虚地址,并通过它找到该区在物理存储器中的实地址,系统为每个进程配置了一张进程区表,表中每一项记录一个区的起始虚地址及指向系统区表中对应区表项的指针。这样,核心通过查找本进程区表和系统区表,便可将区的逻辑地址变换为物理地址。这里使用两张表来对区地址进行映像是为了便于实现区的共享。
2.进程状态及其转换在UNIX System V中,为进程设置了9种状态：
（1)创建状态：进程刚被创建时,进程已经存在,但尚未完全获得运行所必须具有的资源,因此它既不是就绪状态,也不是睡眠状态。这个状态可被认为是进程的初始状态。
（2)内存中就绪：进程己在内存中且处于就绪状态。对于新创建的进程,若系统有足够的内存,核心便将它装入内存,从而使新进程转入内存中就绪状态。
（3）就绪且换出：进程处于就绪状态,但被换出到外存中。在创建新进程时,若无足够的内存,核心便将新进程安置在外存对换区中,并赋予就绪且换出状态。此外,原已在内存中的进程,可能因内存紧张而被换出,同样也成为就绪且换出状态。
（4)核心态执行：进程在核心态下执行。
（5)用户态执行：进程在用户态下执行。
（6）内存中睡眠进程已在内存中且正处于睡眠状态。例如,进程所执行的系统调用涉及到I/O操作,而进程又须等待UO操作的完成,则进程将进入内存中睡眠。
（7)睡眠且换出当内存紧张时,在内存中睡眠的进程,首先被核心换出到外存上,以腾出内存。此时,进程将变为睡眠且换出状态。
（8）被剥夺状态当进程从核心态返回用户态时,核心剥夺了该进程的处理机,使该进程处于被剥夺状态。
（9）僵死状态进程执行了exit系统调用后,便处于僵死状态。此时,进程已不存在,但它留下一些含有状态码和一些计时统计信息的记录,供父进程收集。
3,进程上下文当一个进程在执行时,可看作是在它的进程上下文中执行。一个进程的上下文〈context〉
由三部分组成:用户级上下文、寄存器上下文和系统级上下文。
（1）用户级上下文：用户级上下文是由进程虚地址空间中的正文、数据、用户校和共享存储区组成。在采用对换和请求调页存储管理方式时,只有进程的部分虚地址空间驻留在内存。但无论它是否驻留在内存,都属于用户级上下文的组成部分。
（2）寄存器上下文：寄存器上下文主要由CPU中的一些寄存器内容构成。主要的寄存器有:程序寄存器；处理机状态寄存器；栈指针；通用寄存器。
（3）系统级上下文：系统级上下文可分为静态和动态两部分:
①静态部分：在进程的整个生命期中,系统级上下文的静态部分只有一个,其大小保持不变,它由三部分组成:进程表项、U区和本进程区表项、系统区表项和页表。
②动态部分：在进程的整个生命期中,系统级上下文动态部分的数目是可变的。它包括:核心钱和若干层寄存器上下文。
4,进程控制在UNIX System V中，进程既是一个独立拥有资源的基本单位，又是一个独立调度的基本单位。为了对进程进行控制，UNIX 提供了一系列系统功能调用，用户可以利用它们来实现"创建一个进程"或"终止一个进程的执行"等功能。
用于对进程实施控制的主要系统调用有：
（1）系统调用fork
在UNIX系统中,除了0进程外,其他所有进程都是被另一个进程利用fork创建的。0进程是一个特殊的系统进程,它在系统引导时被创建的。系统初启时,0进程又创建1进程，此后0进程就变为对换进程,而1进程就变为系统的始祖进程。UNIX利用fork为每个终端创建一个子进为用户服务，如等待用户登录、执行shell命令执行程序等。此后,每个终端子进程又可利用fork来创建它的子进程,从而可形成一棵进程树。
（2）系统调用exec
fork系统调用只是将父进程的上下文复制到新进程中,因此执行完fork时,父子进程具有完全相同的正文区、数据区及用户校区。若要使新进程执行的程序不同于父进程,可以使用exec系列系统功能调用。exec系列中的系统调用都完成同样的功能,它们把一个新的程序装入调用进程的内存空间,以改变调用进程的执行代码,从而使调用进程执行新引入的程序功能。如果exec调用成功,调用进程将被覆盖,然后从新引入程序的入口开始执行。这就产生了一个新进程,它的进程标识符与调用进程相同,但所执行的程序代码不同。这就是说,exec没有建立一个与调用进程并发执行的新进程,而是用新进程取代了老进程。这一组系统调用的主要差别在于给出参数的数目和形式不同,给出参数的形式有两种,一种是直接给出指向每个参数的指针,另一种是给出指向参数表的指针。
（3）系统调用exit
对于一般的用户进程,在其任务完成后应尽快撤消。为了及时回收进程所占用的资源并减少父进程的干预,UNIX系统利用exit来实现进程的自我终止。通常,父进程在创建子进程时,应在子进程的末尾安排一条exit,使子进程自我终止。
（4）系统调用wait
系统调用wait用于将调用进程挂起,直至其子进程因暂停或终止而发来软中断信号为止。如果在wait调用前,已有子进程暂停或终止,则调用进程作适当处理后便返回。
5.进程调度
UNIX系统是单纯的分时系统,因而未设置作业调度。对进程的调度采用多级反馈队列轮转调度方式。相应地,在系统中便为就绪进程设置了多个就绪队列。调度程序在进行调度时,总是先从最高优先级队列中取出排在队列最前面的进程。仅当最高优先级队列中没有进程时,才从次高优先级队列中找出其队首进程,令它执行一个时间片后,又剥夺该进程的执行,然后,再从优先级最高的队列中取出下一个就绪进程投入运行。
（1）进程优先级的分类在UNIX系统中,进程的优先级分为两类:核心优先级（又分为可中断和不可中断两类优先级）和用户优先级（又可分成n+1级,其中第0级为最高优先级,第n级的优先级最低）。
（2）优先级的计算
UNIX System V中的用户优先级是可变的,它随着占用CPU时间的增加而降低。核心每隔1秒钟便根据一个衰减函数来调整每个进程的最近CPU使用时间,并按下述公式对各进程重新计算其用户优先数(优先数越大,优先级越低:优先数越小,优先级越高)。
decay(CPU)=CPU/2
优先数=最近使用CPU的时间/2+基本用户优先数核心首先从处于"内存就绪"或"被剥夺"状态的进程中选择一个优先级最高的进程。若系统中同时有多个进程都具有最高优先级,则核心将选择其中处于就绪状态最久的进程,将它从所在队列中移出,恢复其上下文,使之执行。
（3）进程切换在操作系统中,凡是要进行中断处理和系统调用时,都将涉及到进程上下文的保存和恢复,此时系统所保存和恢复的是同属于一个进程的上下文。而在进程调度之后实现进程则是另一个进程的上下文,这一进程取决于调度程序所选中的是哪一个进程。
①进程上下文的保存与恢复不论发生了哪种中断(如I/0设备中断、程序中断〉,如果处理机运行级低于该中断的级别,则处理机将响应该中断,并提高处理机的运行级,以屏蔽其他中断。
②进程上下文的切换总的说来,引起进程上下文切换的原因,都是由于核心进行了进程调度而选中了一个新的进程运行。在UNIX系统中,由于采用了可剥夺的调度方式,因而引起进程调度的原因有时间片完、当前进程执行了sleep例程、进程执行完等,它们都会导致进程上下文的切换。
6.进程的同步与通信在UNIX System V中,进程的同步与通信提供了软中断信号和管道机制以及新的进程通信机构,简称IPC(Interprocess Comnmication)。它由三部分组成:消息机制、共享存储器机制和信号量机制。
（1）软中断信号：软中断信号（简称信号）是一种实现进程间简单通信的设施,用于通知对方发生了异常事件。UNIX系统V中,共有19个软中断信号。软中断是对硬件中断的一种模拟,发送软中断就是向接收进程的进程表项结构中的相应项发送一个软中断信号。如果用户进程发送的软中断信号大于19,则接收进程不予理睬,从而发送无效。接收进程在收到软中断信号后,将按照事先的规定去执行一个软中断处理程序。但是软中断处理程序不像硬件中断处理程序那样,收到中断信号后立即被启动,它必须等到接收进程执行时才能生效。另外,一个进程自己也可以向自己发送软中断信号,以便在某些意外的情况下,进程能转入规定好的处理程序。
（2）管道：用信号来处理异常事件或错误是非常合适的,但用它来处理进程之间的大量信息传送就显得非常不适宜。为此,UNIX又提供了一种称作管道的机构。所谓管道是指能连接某些读进程和写进程的、专门用于进程通信的共享文件(又称pipe文件〉。它允许读/写进程按先进先出的方式传送数据,即写进程从管道的一端向管道写入数据流,读进程从管道的另一端读出数据流。管道的类型有无名管道和有名管道，进程可利用pipe系统调用来建立一个无名管道；对无名管道的读写涉及到对pipe文件大小的限制；进程互斥；进程写管道和进程读管道。
（3）消息：消息是一个格式化的可变长的信息单元。消息机制允许由一个进程给其他任何进程发送一个消息。当一个进程收到多个消息时,可将它们排成一个消息队列。在UNIX中,消息机制向用户提供了四个系统调用,分别用于建立、发送和接收消息等。
消息有消息首部和消息队列头标，在UNIX系统中,每一个消息队列都有一个称为关键字(key)的名字,关键字是由用户指定的。此外,消息队列还有一消息队列描述符,其作用与用户文件描述符一样,也是为了方便用户和系统对消息队列的访问。进程可利用系统调用msgget来建立一消息队列,或者获取一消息队列的描述符；用msgsnd( )系统调用向指定的消息队列发送一个消息,并将发送消息链接到该消息队列的尾部；用msgrcv()系统调用从指定的消息队列中接收指定类型的消息；用户在建立了消息队列后,可利用msgctl系统调用来读取它的状态信息并进行修改,如查询消息队列描述符、修改消息队列的许可权等。
（4）共享存储区：共享存储区是UNIX系统中通信速度最高的一种通信机制。该机制可使若干进程共享主存中的某一个区域,且使该区域出现在多个进程的虚地址空间中。另一方面,一个进程的虚地址空间中又可连接多个共享存储区,每个共享存储区都有自己的名字。当进程间欲利用共享存储区进行通信时,须首先在主存中建立一共享存储区,然后将它附接到自己的虚地址空间上。此后,进程对该区的访问操作,与对其虚地址空间的其他部分的操作完全相同。进程之间以后便可通过对共享存储区中数据的读/写来进行直接通信。当用户需要使用该机制时,必须自己设置这种设施,才能保证实现正确的通信。
当进程要利用共享存储区进行通信时,应先利用系统调用shmget建立一共享存储区。如果该共享存储区已由其他进程建立,则返回其描述符shmid；进程在建立了一共享存储区并获得了其描述符后,还须利用系统调用shmat()将共享存储区附接到进程的虚地址空间上。此后,共享存储区便成为进程虚地址空间的一部分。进程可采用与其他虚地址空间一样的存取方法来存取它。当进程不再需要共享存储区时,应利用系统调用shmdt()将共享存储区与进程断接；如同消息机制一样,可以用shmctl()系统调用对共享存储区的状态信息进行读取和修改。当所有进程都与共享存储区断接时,便可删除该共享存储区。
（5）信号量
UNIX System V中采用的是信号量集机制,即由一组信号量构成的信号量集。传统的信号量机制是对信号量施加P和V操作,而System V中是利用semop()系统调用来对指定信号量进行操作。
用户可利用系统调用semget()来建立信号量集；一旦信号量集被创建成功,便可利用semop()系统调用对这组信号量进行操作。
8.1.3存储器管理在早期的UNIX系统中,为提高内存的利用率,己提供了内存与外存之间的进程对换机制。在UNIX System V中,除保留了对换功能外,还支持请求调页的存储管理方式,内存空间的分配与回收均以页为单位进行。每个页面的大小随版本不同而异,一般在512B-4KB之间。
1.请求调页管理的数据结构在UNIX系统中,为实现请求调页,核心配置了四种数据结构:
（1）页表：UNIX System V将进程的每个区分为若干页,以将它们分配到不相邻的物理块中,为此每个区设置了一张页表。为了支持请求调页,每个页表项中需包含以下字段:物理块号、年龄位、访问位、修改位、有效位、写时拷贝位和保护位。
（2）磁盘块描述表：在UNIX系统中,每个页表项对应一个磁盘块描述项,其中记录了各页面的磁盘拷贝所在的磁盘块号。一个页面的内容或在一个对换设备的特定块中,或在一个可执行文件中。如果该页在一个可执行文件中,此时磁盘块描述项中的存储器类型为File,设备块号是该页在文件中的逻辑块号。如果该页面在对换设备上,则此时的存储器类型为Disk,对换设备号和块号则用于指示该页面的拷贝所驻留的逻辑对换设备和相应的盘块号。
（3）页面数据表：每个页面数据表项描述内存中的一个物理页,每个表项包含:页状态、内存引用计数、逻辑设备和指向空闲页链表中下一个页面数据表项的指针和指向散列队列中下一个页面数据表项的指针。
在系统初启时,核心将所有的页面数据表项链接为一个空闲页链表,形成空闲页缓冲池。为给一个区分配一个物理页,核心从空闲链表之首摘下一个空闲页表项,修改其对换设备号和块号后,将它放到相应的散列队列中。
（4）对换使用表：对换设备上的每一页都占有对换使用表的一个表项,表项中含有一个引用计数,其数值表示有多少页表项指向该页。
2.偷页进程在UNIX系统的核心中,专门设置了一个偷页进程〈page stealer〉,其主要任务有二:
每隔一定时间增加内存中所有有效页的年龄:当有效页的年龄达到规定值后便将它换出。
（1）增加有效页年龄：一个页可计数的最大年龄取决于它的硬件设施。若只设置了两位作为年龄域,其有效页的年龄只能取值0、1、2和3。当该页的年龄为0、1、2时,该页处于不可换出状态;而当其年龄达到3时,便可将它换出内存。每当内存中的空闲页面数低于某规定的低限时,核心便唤醒偷页进程,由偷页进程去检查内存中的每一个活动的非上锁区,对所有有效页的年龄字段加1。对于那些年龄字段已增至3的页便不再加1,而是将它们换出。每当有进程访问了某个页面时,便将该页的年龄置0。
（2）对换出页的几种处理方法：当偷页进程从内存中的有效页中找到可被换出的页后,可采取下面三种方法对它们进行处理:
①若在对换设备上已有被换出页的拷贝,且被换出页的内容未被修改,则此时核心不必将该页重写回对换设备上,而只需将该页的页表项的有效位清零,并将页面数据表项中的引用数减1,最后将该页表项放入空闲页链表中。
②若在对换设备上没有被换出页的拷贝,则应将该页写到对换设备上。但为了提高对换效率,偷页进程并不是有一个页面换出一个页面,而是先将所有要换出的页链接到一个换出页链表上,然后再查看是否还有其他有效页要换出。当换出页面链上的页数达到某一规定值时,比如64页,核心才真正将这些页面写入对换区.
③在对换设备上已有换出页的副本,但该页内容已被修改过。此时核心将释放该页在对换设备上占有的空间,再重新将该页拷贝到对换设备上。
（3）将换出页面写到对换设备上当换出页面链上的页数达到规定值时,核心应将它们换出。为此,应首先为这些页面分配一连续的对换空间,以便将它们一起换出:但如果对换设备上没有足够大的连续空间,而其空闲存储空间的总和又大于64K时,核心可采取每次换出一页的方式将它们换出。每当核心向对换设备上写一个页面时,须首先清除该页表项的有效位,并将页面数据表项中的引用数减1。若引用计数为0,表明已无其他进程引用该页,核心便将其页面数据表项链入空闲页链表的尾部。若引用计数不为0,表明仍有进程共享该页,但如果该页长期未被访问,则也须将该页换出。最后,核心将分配给该页的对换空间地址填入相应的磁盘块描述项中,并将对换使用表中的计数加1。
3.请求调页当一个进程试图存取一个其有效位为0的页面时,将产生一有效性错。此时由核心调用有效性错处理程序加以处理。可能有下列两种情况:
一种情况是如果在磁盘块描述项中找不到所缺的页,则表明此次内存访问非法,核心将向该违例进程发出一"段违例"软中断信号；另一种情况是如果找到了所缺的页,表明此次内存访问合法:但因该页尚未调入内存,则核心为该页分配一个页面的内存,将所缺的页调入内存。
至于如何将所缺的页调入内存,则与所缺页面从何处调入有关,可分成以下三种情况:
（1）缺页在可执行文件中如果缺页对应的磁盘块描述项中的类型是File,表示该页尚未运行过,其拷贝是在可执行文件中。因此,核心应从可执行文件中将缺页调入内存。其具体的调入过程为;根据该文件所对应的系统区表项中的索引节点指针,找到该文件的索引节点,再把从磁盘块描述项中得到的该页的逻辑块号作为偏移量,查找索引节点中的磁盘块号衰,便可找到该页的磁盘块号,于是即可将该页调入内存。
（2）缺页在对换设备上如果缺页所对应的磁盘块描述项中的类型是Disk,表示该页的拷贝是在对换设备上,则核心将从对换设备上把该页调入内存。其调入过程为z核心先为缺页分配一内存页,修改该页表项使之指向内存页,并将页面数据表项放入相应的散列队列中,然后把该页从对换设备上调入内存。当I/0操作完成时,核心把请求调入该页的进程唤醒。
（3）缺页在内存页面缓冲区中在进程运行过程中,当一页被调出后又被要求访问时,需重新将它调入。但并非每次都要从对换设备上调入,因为被调出的页可能又被其他进程(共享时〉调入到另一物理页中,这时就可在页面缓冲池中找到该页。此时,只需适当地修改页表项等数据结构中的信息即可。
8.1.4 设备管理设备管理的主要任务是管理系统中的所有外部设备。UNIX系统把设备分为两类:块设备,用于存储信息,其对信息的存取是以信息块为单位的,如通常的磁盘、磁带等;字符设备,用于输入/输出,其对信息的存取是以字符为单位的,如通常的终端设备、打印机等。
1.设备缓冲管理在UNIX系统中分别为字符设备和块设备设置了缓冲池。
（1）字符设备缓冲管理在系统中设置了一组字符缓冲区,供各种字符设备使用。其中,每个缓冲区的大小为70个字节,包括以下四项:第一个字符的位置、最后一个字符的位置、指向下一个缓冲区的指针和余下的用于存放64个字符的缓冲区。所有的空闲缓冲区通过链接指针c_next链接成一个空闲缓冲队列,由队首指针cfreelist指向其第一个缓冲区。
每当设备管理程序请求一个字符缓冲区时,管理程序便从空闲缓冲区链首取得一空闲缓冲分配给相应的设备。在设备释放缓冲区时,管理程序将它链入空闲队首。可见,空闲缓冲区链实际上是一个栈,cfreelist指向栈顶。
在字符设备进行I/O时,核心可利用getcf过程从空闲缓冲区链中取得一缓冲区,来收容设备的I/O数据。当缓冲区中数据己被提取完而不再需要时,可利用putcf过程,将缓冲区归还到空闲链中。
（2）块设备缓冲队列的结构在系统中,为块设备配置了块设备数据缓冲区,供磁盘和磁带机使用。每个缓冲区的大小至少应与盘块的大小相当。至于盘块的大小则随机器而异,它们一般在512~4096字节之间。由于盘块缓冲区的容量较大,使用上也较复杂,因此UNIX系统中的盘块缓冲区的组成方式不同于字符缓冲区。
在UNIX系统中,盘块缓冲区均由两部分构成:一部分是用于存放数据的缓冲区;另一部分是缓冲控制块,也称为缓冲首都,用于存放缓冲区的管理信息,两者一一对应,但缓冲首部与缓冲区在物理上并不相连,只是在缓冲首部中用一个指向对应缓冲区的指针将两者联系起来,
缓冲首部还包括设备号和块号,以分别指出对应的文件系统和磁盘上的数据块。注意,在UNIX System V中,设备号并非物理设备号,而是逻辑设备号,核心把每一个文件系统看作是一个逻辑设备。缓冲首部中的状态字段指示对应缓冲区的当前状态,用于表示缓冲区是否空闲、缓冲区是否为延迟写、是否有进程正在等待该缓冲区变为空闲、核心是否正在读或写该缓冲区等。缓冲首部还包括两个空闲链表指针及两个散列队列指针。前者分别指向空闲链表中的上一个和下一个缓冲区首部:后者分别指向散列队列中的上一个和下一个缓冲区首部。
为了对缓冲区进行管理,在核心中设置了一个双向链接的空闲链表。系统初启时,将所有的缓冲首部都链入空闲链表中。当需要一个空闲缓冲区时,可利用getblk过程从空闲链表的首部摘下一个缓冲区:回收一个空缓冲区时,再利用brelse过程将它挂在空闲链的末尾。
为了加速对缓冲区的查找,系统把所有缓冲区按设各及块号所计算散列值的不同组织成多个散列队列,每个散列队列仍是一个双向链表,其中的缓冲区数目不断地发生变化。各块号的散列值用散列函数计算。一个空闲缓冲区可同时链入两个队列中,从而使对一空闲缓冲区的查找可通过两种方式来进行:若要求获得任意一空闲缓冲区,从空闲链上摘取第一个缓冲区即可，若要寻找一特定的空闲缓冲区,则搜索散列队列会更方便。
（3）块设备缓冲区的分配与释放核心调用getblk过程分配缓冲区。当要读磁盘数据时,核心首先检查要读入的盘块内容是否已在某个缓冲区中,若发现己在某个缓冲区中,便不必再从磁盘上读入。仅当数据未在任何缓冲区中时,核心才须从磁盘上将数据读入,这时才须为其分配一空闲缓冲区。类似地,当要把数据写入一特定盘块时,核心应先检查该块内容是否已在某缓冲区中,仅当该块内容尚不在缓冲区中时,才须分配一空闲缓冲区。获取空闲缓冲区时应提供的输入参数是文件系统号和磁盘块号。getblk过程分配缓冲区时,可分为两种情况:缓冲区在散列队列上及缓冲区不在散列队列上。
当核心用完某缓冲区时,可调用brelse过程将它释放。
2.核心与驱动程序的接口一一设备开关表在UNIX系统中,每类设备都有一个驱动程序,用它来控制该类设备。任何一个驱动程序通常都包含了用于执行不同操作的多个函数,如打开、关闭、启动设备、读和写等函数。为使核心能方便地转向各函数,系统为每类设备提供了一个设备开关表,其中含有该类设备的各函数的入口地址。
通常,字符设备和块设备的驱动程序有所不同,相应地,它们所包含的函数也不完全相同。由系统中所有字符设备的设备开关组成一张字符设备开关表,由系统中所有块设备的设备开关组成一张块设备开关表。
3.磁盘驱动程序磁盘驱动程序的主要功能是:把由逻辑设备号和盘块号组成的文件子系统地址转换为磁盘上特定的扇区号:装配磁盘控制器的各个寄存器,如磁盘地址寄存器、控制状态寄存器等:对磁盘块进行读和写。前两个功能与具体的磁盘有关,相对比较简单；而第三个功能则是驱动程序的最主要功能。
（1）磁盘的读写方式
在UNIX系统中有两种读方式:一般读方式和提前读方式。
在UNIX系统中有三种写方式:一般写方式、异步写方式和延迟写方式。。
8.1.5文件管理在文件系统中,为了能将文件存储到磁盘上,首先必须为之分配相应的存储空间;其次应考虑采用何种方式将文件存储到磁盘上;第三,为简化对文件的访问和共享。
1.文件存储空间的管理
（1）文件系统的组织在UNIX系统中,文件信息存放在磁盘或磁带上,一个物理存储器中可包含一个或多个文件卷。在UNIX中,这种文件卷又称为文件系统。一个文件系统包含许多物理块。
在文件系统中,0#块一般用于系统引导或空闲;1#块为超级块,用于存放文件系统的资源管理信息,如整个文件系统的盘块数、磁盘索引节点的盘块数、空闲盘块号表及指向下一个空闲盘块号的指针、空闲索引节点表和指向下一个空闲索引节点的指针等;从第2#块至K#块存放磁盘索引节点:第K+1#块及其后续各块存放文件数据。
（2）空闲盘块的组织
UNIX系统采用成组链接法对空闲盘块加以组织。即将若干个空闲盘块划归一个组,将每组中的所有盘块号存放在其前一组的第一个空闲盘块号指示的盘块中,而将第一组中的所有空闲盘块号放入超级块的空闲盘块号表中。
（3）空闲盘块的分配与回收
①空闲盘块的分配：当核心要从文件系统中分配一个盘块时,首先检查超级块空闲盘块表是否已上锁,若已上锁则进程睡眠等待:否则将超级块的空闲盘块表中下一个可用盘块分配出去。如果所分配的盘块号是超级块中的最后一个可用盘块号,由于在该盘块中存放了下一组的所有盘块号,于是核心在给超级块中的空闲盘块号表上锁后,先将该盘块中的内容读入超级块空闲盘块号表中；然后才将该盘块分配出去:最后将空闲盘块号表解锁,并唤醒所有等待其解锁的进程。
②空闲盘块的回收在回收空闲盘块时,如果超级块中的空闲盘块号表未满,可直接将回收盘块的编号放入空闲盘块号表中。若空闲盘块号表己满,须先将空闲盘块号表中的所有盘块号复制到新回收的盘块中,再将新回收盘块的编号放到超级块空闲盘块号表中,此块号就成了表中惟一的盘块号。
2.文件的物理结构在UNIX系统中,文件的数据存储在离散的磁盘块中,这些文件的盘块号直接或间接便可以用直接或间接的寻址方式获得指定文件的盘块号。
（1）寻址方式
①直接寻址方式：UNIX系统中的作业以中小型为主,为了提高对文件的检索速度,宜采用直接寻址方式。为此,在索引节点中建立了10个地址项,每个地址项中直接存放了该文件所在的盘块号,如图8.21所示。假定一个盘块的大小为1KB,当文件长度不大于10KB时,可直接从索引节点中得到该文件所在的全部盘块号。
②一次间接寻址方式：在UNIX系统中,可能有少数文件的长度达到了几万字节、几兆字节、甚至更长。这时,如果采用直接寻址方式,则要在索引节点中设置几百个或更多的地址项,这显然是不现实的。因此,UNIX系统中又提供了一次间接寻址方式。即在一次间接地址项中存放的不再是文件的一个物理盘块号,而是先将1~256个盘块号存放在一个磁盘块中,再将该磁盘块的块号存放在这一地址项中。这里,一个盘块为1KB,一个盘块号占32位,用一次间接地址项便可将寻址范围由lOKB扩大到266KB。
③多次间接寻址方式：为了进一步扩大寻址范围,又引入了二次间接和三次间接寻址方式。二次间接寻址可将寻址范围扩大到64MB。三次间接寻址可将寻址范围扩大到16GB。
（2）地址转换
UNIX系统利用地址转换过程bmap将文件的字节偏移量换为文件的物理块号。这一转换过程分两步实现:第一步,将字节偏移量转换为文件逻辑块号及块内偏移量;第二步,把逻辑块号转换为文件的物理块号。
3.用户文件描述符表和文件表
（1）用户文件描述符表为了方便用户和简化系统的处理过程,在UNIX System V中,每个进程的U区中设置了一张用户文件描述符表。仅在用户第一次打开指定文件时,才须给出其路径名。核心先对打开请求做仔细的检查后,便在该进程的用户文件描述符表中分配一空表工页,取该表项在用户文件描述符表中的位移量作为文件描述符返回给用户。以后,当用户再访问该文件时,只需提供该文件的描述符,系统根据描述符便可找到相应文件的内存索引节点。
（2）文件表系统为了对文件进行读/写,设置了一个确定读/写位置偏移量的读/写指针。该读/写指针应放在何处呢?是否可放在用户文件描述符表中呢?我们对此做个简单的分析。用户在读/写文件时,可采用三种方式:多个用户读/写各自的文件；多个用户共享一个文件,但彼此独立地对文件进行读/写:多个用户共享一个文件,且共享一个读/写指针。这样,若将读/写指针设置在文件描述符表项中,对前两种情况固然可行,但要实现对读/写指针的共享就很困难。为解决此问题,在UNIX系统中引入了文件表,文件表项中存放文件的读/写指针,这样对上述三种读/写要求都能很好地满足。
4.目录管理为了加速对文件目录的查找,在UNIX系统中,将文件名和文件说明分开,由文件说明形成一个称为索引节点的数据结构,而相应的文件目录项则只由文件名和对应的索引节点号构成。
（1）索引节点磁盘索引节点：索引节点是一个数据结构,其中存放文件的说明信息。索引节点以静态形式存放在磁盘上,故又称为磁盘索引节点。每个文件都有惟一的一个磁盘索引节点,它由下述各字段构成:文件所有者标识符、文件类型、文件存取权限、存放文件的物理地址、文件长度、文件联结计数、文件存取时间。
内存索引节点：为了加快文件的存取速度和减轻磁盘I/0的压力,专门在内存中建立了一个内存索引节点表,将那些要被引用的磁盘索引节点复制到内存索引节点表中,并增加了如下字段:索引节点号,内存索引节点状态、内存索引节点引用计数、设备号和内存索引节点指针。
（2）磁盘索引节点的分配与回收分配过程ialloc：每当核心创建一新文件时,都要为之分配一空闲磁盘索引节点。如果分配成功,便再分配一内存索引节点。
回收过程ifree：当要删除某文件时,应回收其所占用的盘块及相应的磁盘索引节点。过程ifree便是用于回收磁盘索引节点的。
（3）内存索引节点的分配与回收分配过程iget：主要功能是分配内存索引节点,其输入参数是文件系统号和索引节点。
回收过程iput：输入参数是指向内存i节点的指针。其主要功能是对指定的内存索引节点进行减1操作。若结果为0,则回收该内存i节点。若它已做过修改,还须将它写回磁盘后再回收,然后将它链入内存空闲i节点表中。若其磁盘i节点的联结计数也为0,便删除该文件,并回收分配给该文件的磁盘i节点和磁盘数据块。
（4）构造目录和删除目录文件系统的基本功能是实现按名存取,这是通过文件目录来实现的。UNIX系统中的每个目录项由文件名及其相应的索引节点号组成,其中文件名占14个字节,索引节点号占2个字节。通常,每个文件都在文件目录中有一个目录项,通过查找文件目录可找到该文件的目录项和对应的索引节点,进而找到文件存放的物理位置。对于可供多个用户共享的文件,则它往往会有多个目录工页。如果要将文件删除掉,其目录便也无存在的必要,因此也应将其目录项删除掉。
构造目录：每当创建一个新文件时,系统都要在其父目录文件中为之构造一个目录项。在UNIX系统中,构造目录的任务由makenode过程完成。在创建一个新文件时,由系统调用creat调用该过程来为新文件构造一个目录项。makenode过程首先调用ialloc过程来为新建的文件分配一磁盘索引节点和内存索引节点,若分配失败便返回:当分配成功时,须先设置内存索引节点的初值,然后调用写目录过程,将用户提供的文件名与分配给文件的磁盘索引节点号一起构成一新目录项,再将它记入其父目录文件中。
删除目录：当用户已不再需要某个文件时,应将它从文件系统中删除,以便及时腾出存储空间。由于UNIX系统支持文件的共享,而当文件正被多个进程共享时,不允许任何一个用户将该文件删除。这也是UNIX系统中不存在一条用于删除文件的系统调用的真正原因。当一个用户(进程〉己不再需要某文件时,只能利用系统调用unlink请求清除进程与该文件的联结。此时,系统须对该文件的联结计数执行减1操作,并相应地删除该用户(进程)的一个指定文件目录。当所有联结到该文件的用户都不再需要该文件时,其联结值为0,系统才执行删除该文件的操作。
（5）检索目录在UNIX系统中,当用户第一次访问某文件时,需要使用文件的路径名,系统按路径名去检索文件目录,得到该文件的磁盘索引节点,且返回给用户一个文件描述符。以后,用户便可利用该文件描述符来访问文件,这时系统不必再去检索文件目录。
对文件的检索是由namei过程完成的。该过程能被许多不同的系统调用所调用,如creat、open、link、chdir、chmod、chown等,但它们对namei的要求并不完全相同。可将这些系统调用分成三类:分别用f1ag=0、flag=1和flag=2来表示。Flag=O是指namei由chdir、chmod等所调用,这时若namei查找到指名文件则返回相应的内存索引节点指针。Flag=1是指由creat调用namei,此时若namei未找到指名文件便正常返回。Flag=2是指由unlink调用namei,在正常情况下应返回由路径名所指出的父目录文件的内存索引节点指针。这使得namei过程变得非常复杂。
检索目录过程namei是根据用户给出的文件路径名,从高层到低层顺序地查找各级文件目录,寻找指定文件的索引节点号。在检索路径名时,对以"/"开头的路径名须从根目录开始检索,否则从当前目录开始检索,并把与它对应的索引节点作为工作索引节点。然后用文件路径名中的第一个分量名与根或当前目录文件中的各目录项中的文件名逐一进行比较。由于一个目录文件可能占用多个盘块,因此,在检索完一个盘块中的所有目录项而未找到匹配的文件分量名时,须调用bmap和bread过程,将下一盘块中的所有目录项读入内存,再逐一检索。若检索完该目录文件的所有盘块而仍未找到匹配的目录项时,才认为无此文件分量名。
在未找到指定分量名的匹配目录项时,又分成几种情况处理：
(1)如果不是最后一个路径分量名,则出错返回。
(2〉如果是最后一个路径分量名且flag=1时,属正常情况。此时,使namei过程继续执行,去检查父目录文件是否允许写,父目录文件中是否有空目录项。若有,便分配一空目录项,然后返回NULL。
(3)如果是最后一个路径分量名,但f1ag≠1,则出错返回。
唔 如果找到相匹配的目录项,而路径名尚未检索完,则把该目录项中所指示的索引节点作为工作索引节点,并取出文件路径名中的下一个分量名,继续重复上述过程,直至路径名中的所有分量名全部查找完毕。
5.文件系统的系统调用系统调用是用户程序取得操作系统服务的惟一方式,是用户程序与操作系统之间的接口。UNIX系统中提供了丰富的系统功能调用,与文件操作相关的常用系统功能调用有：open、close、creat、link、unlink、read和write。
8.2 重点难点学习提示这一部分请周星给添上
8.3 经典问题分析和解答
1.试述UNIX的主要特点。
答,UNIX的主要特点是:
(1)UNIX系统是一个可供多用户同时操作的交互式分时操作系统;
(2)为了向用户提供交互式功能和使得用户可以利用UNIX系统的功能,UNIX系统向用户提供了两种友好的界面或接口:系统调用和命令;
(3)UNIX系统具有一个可装卸的分层树型结构文件系统,该文件系统使用方便、搜索简单；
(4)UNIX系统把所有外部设备都当成文件,并分别赋予它们对应的文件名。从而,用户可以像使用文件那样使用任一设备而不必了解该设备的内部特性,这既简化了系统设计,又方便了用户;
(5)UNIX系统核心程序的绝大部分源代码和系统上的支持软件都用C语言编写。且UNIX系统是一个开放式系统,即具有统一的用户接口,使得UNIX用户的应用程序可在不同的执行环境下运行。
正是由于UNIX具有上述这些特点,使得UNIX系统得到了广泛的应用和发展。
2,简述UNIX系统进程的概念。
答:在UNIX系统中,进程被赋予一些特定的含义和特性:
（1）一个进程是对一个程序的执行；
(2)一个进程的存在意味着在所谓的"Proc"数组(PCB的常驻内存部分)中有一个非零的结构存在,它包含着相应的进程控制信息；
(3)对于每个进程,有一个被称为U区?(userblock)或User的数据结构。这个数据结构放置该进程的私用控制信息,且在进程被创建时,才会由系统分配相应的域(field)。
(4)一个进程可以生成或删除其子进程;
(5)一个进程是获得和释放各种资源的基本单位。
3.答:在UNIX System V中引起进程调度的情况有5种:
(l)当前执行进程申请内存等系统资源未得到满足,从而自己调用sleep过程,放弃处理机而进入睡眠状态。
(2)为了与其他并发进程保持同步,调用了wait或stop过程等,从而主动放弃了处理机而进入睡眼状态。
(3)当系统在从核心态转入用户态时,发现runrun调度标志被设置（即系统中某进程的优先级已高于当前执行进程的优先级),系统调用优先级高的进程执行。
(4)时间片用完,且当前进程的优先级低于其他就绪进程。
(5)当前进程调用exit,自我终止时。
4.描述UNIX System V中消息机制的通信原理。
答:UNIX System V中消息机制使用消息队列和消息头两种基本数据结构,消息队列中每一表项由关键字、访问控制结构及操作状态信息组成,消息头描述消息的有关特征。在消息机制中,消息被格式化为类型与数据对,且允许不同的进程根据不同的消息类型接收。
消息机制提供4个系统调用msgget,msgctl,msgsnd和msgrcv。系统调用msgget返回一个消息描述字msgqid。msgqid指定一个消息队列供其它三个系统调用使用。系统调用msgctl用来设置和返回与msgqid相关联的参数选项,以及用来删除消息描述符的相关选择项。系统调用msgsnd和msgrcv分别表示发送和接收一消息。
使用消息机制的通信双方先要建立相同的消息队列。通信时先得到自身的msgqid,若要发送消息则把待发消息写入消息正文部分,并指定消息类型。最后调用msgsnd把消息发送到消息队列上。若要接收消息则调用msgrcv从消息队列中取出消息。
5.在UNIX System V中,当一个进程所访问的一页既不在内存又不在文件系统中时,该页面可能在什么地方?存储管理模块是如何把它调入内存的?
答:在UNIX System V中,一个进程所访问的页面或者在内存中,或者在文件系统中,或者在对换设备上。因此,当一个进程所访问的一页既不在内存又不在文件系统中时,该页面可能在对换设备上。此时由核心调用有效性错处理程序加以处理。
当所缺页面在对换设备上但不在内存时,则说明该页曾一度在内存中,但已被偷页进程换出。为从对换设备上调入该页面,核心从磁盘块描述项中找到存放该页面的对换设备和块号,然后为缺页分配一内存页,修改此进程的相应页表项,使之指向该内存页,并将页面数据表放入相应的散列队列中,再把该页从对换设备上调入内存。
6.UNIX 文件系统为什么有磁盘i节点和内存i节点?为什么内存i节点和磁盘i节点的内容不完全一样?
答:UNIX系统中,磁盘i节点以静态形式存放文件说明信息。引入内存i节点是为了减少设备的启动次数以及提高操作速度,把磁盘i节点复制到内存特定区域。由于进程对文件进行操作时,需要用到i节点中的逻辑结构和物理结构信息,以完成对文件信息的存取、共享和保护,故内存i节点中多了当前文件状态信息。
7.在UNIX System V中,如果一个盘块的大小为1KB,每个盘块号占4个字节,那么,一个进程要访问偏移量为263168字节处的数据时,需要经过几次间接?
答,分析：在UNIX系统中,文件的数据存储在离散的磁盘块中,这些文件的盘块号直接或间接地存放在该文件索引节点的13个地址项中。前10个地址项是直接寻址,每个地址项中直接存放了该文件所在的盘块号;第11个地址项是一次间接寻址,即先将1~256(因一个盘块的大小为1KB且每个盘块号占4个字节,所以一个盘块中最多能存放1024/4=256)个盘块号存放在一个磁盘块中,再将该磁盘块的块号存放在该地址项中;第12个地址项是二次间接寻址,其中的磁盘块号指向一个一次间接块号表;第13个地址项是三次间接寻址,其中的磁盘块号指向一个二次间接块号表。
故偏移量263168的逻辑块号为:263168/1024=257
块内偏移量为:263168.1024×257=0
因为10<257<266,所以偏移地址263168的块号在一次间接块内,故一个进程要访问偏移量为263168字节处的数据时,只需要经过一次间接。
8.在UNIX系统中,如果当前目眼录是/user/wang,那么，相对路径为../ast/xxx文件的绝对路径名是什么?
答,UNIX系统采用了树型目录结构,树根称为根目录,用"/"表示。为了使用方便,系统还设置了当前工作目录。路径名是由"/"分隔的目录名组成,以表明文件所在的目录。从根目录出发的路径称为绝对路径,从当前目录出发的路径称为相对路径。”."目录是指当前目录，”..”目录是指父目录。
在本题中,因当前目录是/usr/wang,所以相对路径为../ast/xxx的文件实际上是usr目录下的文件,故其绝对路径名时/usr/ast/XXX。
9.请为下列程序中标号处加上注释。
程序A
#denne MSGIGY 75
struct msgform{
long mtype;
char mtext[256];
}
main()
struct msgform msg;
int msgqid,pid,*pint:
msgqid=msgget(MSGKEY,0777); (1)
pid=getpid():
pint =(int*)msg.mtext; (2)
*pint=pid; (3)
msg.mtype=1; (4)
msgsnd(msgqid,&msg,sizeof(int),0); (5)
msgrcv(msgqid,&msg,256,pid,0); (6)
}
程序B
#define MSGKEY 75
struct msgform{
long mtype;
char mtext[256];
}msgl;
main()
{
int msgqid,i,pid,*pint;
msgqid=msgget(MSGKEY,0777|IPC-CREAT); (7)
msgcv(msgqid,&msg1,256,1,0); (8)
pint=(int*)msg1.mtext; (9)
pid=*pint; (10)
msg1.mtype=pid;
*pint=getpid(); (11)
msgsnd(msgqid,&msg1,sizeof(int),0); (12)
}
答,(1)获取一个消息队列标识,该消息队列的键值为MSGKEY,即75。消息队列的权限为0777,即所有用户都有读、写、执行权限。
（2）使pint指向消息块中存放消息正文的空间。
（3）在消息正文中填入本进程的进程号。
（4）设置消息类型为1。
（5）发送消息。将上述两条语句构造好的消息发送至msgqid指定的消息队列。
（6）接收消息。在接收消息时,因消息类型设置为pid,即本进程的进程号,所以该语句将读出消息类型为本进程进程号值的第一个消息。
（7)获取一个消息队列标识,该消息队列的键值为MSGIqy,即75.若给定键值尚未有对应消息队列存在,就为它建立一个消息队列。消息队列的权限为0777。
（8）接收消息。在接收消息时,因消息类型设置为1,所以该语句将读出消息类型1的第一个消息。
（9）使pint指向消息块中存放消息正文的空间。
（10）读出消息正文,放入变量pid中,即将程序A中所填入的进程号读出。
（11）在消息正文中填入本进程的进程号。
（12）发送消息。
10.一个进程在发现所要搜索的i节点位于缓冲区中,且该i节点为上锁状态时,将在iget中睡眠。在该i节点变为开锁状态并唤醒该睡眠进程之后,该进程将重新开始搜索i节点。为什么?
答：UNIX的系统内部过程iget的主要功能是分配一个内存索引节点,其输入参数是文件系统号和索引节点号。若该i节点已在索引节点的散列队列中,则只需对该i节点的引用计数加1。如果该i节点不在散列队列中,则应从空闲i节点链中摘下一空闲i节点,设置文件系统号和索引节点号,并根据i节点号计算它应在的散列队列,再将该i节点从原来的散列队列移至新的散列队列。调用bread过程将磁盘i节点的内容拷贝到内存i节点中,并对内存i节点进行初始化。其算法可形式化描述如下:
算法iget
输入:文件系统及索引节点号输出:上锁状态的索引节点
{
while (未完成)
{
if(是索引节点高速缓冲中的索引节点〉
{
if〈索引节点为上锁状态〉
{
sleep(索引节点变为开锁状态事件〉;
continue; /*循环到while */
}
if〈是空闲索引节点表上的索引节点〉
从空闲表上移出该节点;
索引节点引用计数值增1;
return (索引节点〉;
}
/*不是索引节点高速缓冲中的索引节点*/
if(空闲表上没有索引节点〉
return (错误):
从空闲表上移出一个索引节点:
重置索引节点号及文件系统:
从老的散列队列中删去该索引节点,把该索引节点放到新的散列队列中:
从磁盘上读索引节点(算法bread);
索引节点初始化〈如访问计数置为1〉:
return (索引节点〉;
}
}
当一个进程,为描述方便起见,不妨设此进程为进程B,发现所要搜索的i节点位于索引节点高速缓冲区中,且该i节点为上锁状态(不妨设进程A正使用该i节点并将该i节点上锁)时,进程B将在iget中睡眠.进程A最终将会为此i节点解锁,并唤醒睡眠在此i节点解锁事件上的所有进程,其中包括进程B.当核心再次调度到进程B时,进程B必须证实该i节点是否为上锁状态,因为可能有另一进程C也一直等待使用同一个i节点,并且核心可能先于进程B而调度到进程C运行,进程C可能正在使用该i节点,使该i节点仍为上锁状态;基于同样的竞争情况,进程B还必须证实该i节点是否还在内存索引节点高速缓冲中.
一个进程在发现所要搜索的i节点位于缓冲区中,且该i节点为上锁状态时,将在iget中睡眠。在该i节点变为开锁状态并唤醒该睡眠进程之后,为证实该i节点是否为上锁状态及该i节点中是否还在高速缓冲中,进程需要重新开始搜索i节点。
11.假定盘块的大小为1KB,每个盘块号占4个字节,文件索引节点中的磁盘地址明细表如下图所示,如何将下列文件的字节偏移量转换为物理地址?
(1〉9000;(2)14000;〈3)350000
4096
228
4542
0
3
11111
50
101
367
0
428
9156
824
1101
109
954
952
0
1
2
3
3300
333
308
428
331
452
74
9156 331
答：UNIX系统将文件的字节偏移量转换为文件物理块号的过程分两步实现:第一步,将字节偏移量转换为文件逻辑块号及块内偏移量;第二步,把逻辑块号转换为文件的物理块号。其转换方法如下:
首先,将字节偏移量转化为文件逻辑块号,即将字节偏移量除以盘块大小的字节数,其商是文件逻辑块号,余数是块内位移量。然后,把文件逻辑块号转换为物理盘块号。根据逻辑盘块号可知对应的文件地址是直接地址还是间接地址,若为直接地址,即当文件逻辑盘块号小于10时,将文件逻辑块号转换为索引节点的地址项下标,从该地址项中即可获得物理盘块号;
若为一次间接寻址,即当文件块号大于或等于10且小于266时,从索引节点的一次间接项中得到一次间接的盘块号;再计算一次间接块中的地址下标,即将文件的逻辑块号;或10,从相应下标的地址项中得到物理块号;若为多次间接寻址,即当文件的逻辑块号大于或等于266而小于65802时,应采用二次间接寻址,而当逻辑块号大于或等于65802时,应采用三次间接寻址,多次间接寻址的转换方法和一次间接寻址相类似,但要多次循环。
解:(1)字节偏移量为9000,此时逻辑块号为:9000/1024=8
块内偏移量为:9000-8×1024=808
因逻辑块号小于10,因此该块为直接块。由图可知,其物理盘块号为367,该块中的第808字节即为文件的第9000字节。
(2)字节偏移量为14000,此时逻辑块号为:14000/1024=13
块内偏移量为:14000一13×1024=688
因逻辑块号10<13<266,因此该块为一次间接块。
由图可知,一次间接的盘块号为428,从一次间接块中读出盘块号表,查得其物理盘块号为952,该块中的第688字节即为文件的第14000字节。
(3)字节偏移量为350000,此时逻辑块号为:350000/1024=341
块内偏移量为:350000-341×1024=816
因逻辑块号266<341<65802,因此该块为二次间接块。
由图可知,二次间接的盘块号为91560由于一个一次间接块中可容纳256个块号,
341-266=75
因此字节偏移量350000在二次间接块的第0个一次间接块的第75个表项中,其盘块号为3333,该块中的第816字节即为文件的第350000字节。
8.4自测题一、判断题
1.在UNIX系统中所有进程都是利用系统调用fork创建的。 （ ）
2.在早期的UNIX操作系统中,16位虚地址经地址转换后得到18位的物理地址。 ( )
3.软中断信号是一种实现进程间简单通信的设施,用于通知对方发生了异常事件。 （ ）
4.UNIX是批处理操作系统。 ( )
5.在UNIX系统V中,用户通过原语读取磁盘文件中的数据。 ( )
6.UNIX采用流式文件逻辑结构和索引文件物理结构。 （ ）
7.UNIX文件系统分为基本文件系统和扩充文件系统两部分。 （ ）
8.在UNIX中把外围设备也当作文件看待,称为设备文件。 ( )
9.在UNIX系统中,管道文件用于把一个进程的输出连接到另一个进程的输入。 （ ）
10.提供可动态装卸的文件卷是UNIX的特色之一,( )
二．单项选择题
1.UNIX是当今世界上广为使用的__________。
A.小型计算机操作系统 B.多用户多任务操作系统
C.大型计算机操作系统 D.实时多任务操作系统
2．在UNIX系统Ⅴ中,进程控制块由__________组成。
A.PROC结构和USER结构 B.用户栈和PROC结构
C.系统区表和USER结构 D.PROC结构和核心栈
3.UNIX操作系统的SHELL是负责___________的模块。
A.解释并执行来自终端的命令 B.解释并执行来自终端的内部命令
C.解释并执行来自终端的外部命令 D.进行功能调用
4.UNIX系统中把设备分为___________。
A.输入设备和输出设备 B.字符设备和块设备
C.系统设备和用户设备 D.共享设备和虚拟设备
5.在UNIX系统中,用户通过___________读取磁盘文件中的数据。
A.作业申请表 B.原语 C.系统调用 D.软中断
6.UNIX System V的调度原理基于__________。
A.先来先服务 B.短作业优先 C.时间片轮转 D.时间片+优先级
7.UNIX System V的存储管理策略基于 ____________.
A.单一连续分配 B.固定式分区分配 c.可变式分区分配 D.请求分页
8.在UNIX System V中,系统向用户提供的用于创建新进程的系统调用是__________.
A.read B.fork C.pipe D.exit
9.在UNIX系统V中,用户通过____________读取磁盘文件中的数据。
A.系统功能调用 B.作业申请表
C.原语 D.中断
10.UNIX系统V的进程调度原理是基于____________。
A.最短作业优先 B.时间片调度
C.时间片加优先级 D.先来先调度
11.当进行中断处理和系统调用时,都将涉及到进程上下文的保存和恢复,此时系统所保存和恢复的是_______________的上下文。
A.系统进程 B.同一个进程 C.不同进程 D.其他进程
12．在UNIX系统中采用的是_________对空闲磁盘块进行组织。
A.位示图 B.空白文件目录 C.链接法 D.成组链接法
13.所谓管道是指能连接某些读进程和写进程的、专门用于进程通信的共享文件。它允许读/写进程按_________的方式传送数据。
A.后进先出 B.先进先出 C.任意 D.后进后出
14.UNIX操作系统的文件系统是__________.
A.一级目录结构 B.二级目录结构 C.分级树形结构 D.链表结构
15.在UNIX中,文件的逻辑结构是__________。
A.记录式结构 B.无结构流式结构 C.串联文件结构 D.树型文件结构
16.在UNIX SystemV操作系统中,存储管理采用___________方案。
A.段式管理 B.请求分页管理
C.可变式分区管理 D.固定式分区管理
17.下列4个操作系统中,_________没有多道程序设计的特点。
A.OS/2 B.MS-DOS C.UNIX D.WIndows NT
18.下列4个操作系统中,_________具有多道程序设计的特点,但不是分时系统。
A.OS/2 B.Windows 3.1 C.UNIX D.Windows NT
19.UNIX系统中,把输入/输出设备看作是________.
A.普通文件B.特殊文件C.索引文件D.目录文件
20.在UNIX系统的多用户环境下,各个用户都是通过口令在各自的注册账号下行使自己的系统权限。系统对每个文件实行了______三级保护加强了文件的保密性和安全性。
A.文件的系统、隐含及私杳 B.文件的所有者、同组用户及其他人
C.读、写及执行 D.读、写、执行及拷贝三．填空题
1.UNIX操作系统在结构上分为_____________和_________________两部分。
2.UNIX系统为用户提供了面向操作的接口____和面向_____的接口____。
3.UNIX 系统Ⅴ中，采用的进程调度算法是_________________________。
4.在UNIX System V中,将PCB分成进程表项和U区。除进程表项和U区外,管理进程的数据结构还有________和____。
5.在UNIX中文件可分为三类:______、____和_____。
6.UNIX把执行状态分为两种:一种是_________执行,另一种是核心态执行。
7.在UNIX系统中,为实现请求调页,核心配置了四种数据结构:____、____、______和____。
8.在UNIX系统中有两种读方式:一般读方式和_______方式。
9.UNIX系统中的每个目录项由______及其相应的______组成。
10.在UNIX文件管理系统中,为了对磁盘空间的空闲块进行有效的管理,采用的方法是___________。
11.UNIX的0#进程的主要功能是创建用户进程、___________。
12.用户在第一次访问任何文件之前,都必须先使用系统调用______来打开指定文件,然后才能对该文件执行读、写和修改等操作。
答:open
13.在UNIX系统中,键盘、终端、打印机等以_____为单位组织和处理信息的设备称为____;而磁盘、磁带等以_____为单位组织和处理信息的设备称为______。
14.通往一个文件的路径数目称为此文件的________.
答:联结计数
15.缓冲区可分为______、_____、_____和_____。
16.一个进程只有在获得______、____和所需设备三者之后,才具备进行____的物质条件。
四．简答题
1.UNIX操作系统为用户提供哪些接口?试举例说明。
2.UNIX System V中,系统程序所对应的正文段未被考虑成进程上下文的一部分,为什么?
3.UNIX System V进程上下文由哪几部分组成?为什么说核心程序不是进程上下文的一部分?进程页表也在核心区,它们也不是进程上丁文的一部分吗?
4.UNIX System V的调度策略是什么?调度时应该封锁中断吗?如果不封锁,会发生什么问题?
5.试述进程0的作用。
6.在系统调用sleep和wakeup时,要提高处理机的执行级(相当于优先级)来防止中断,为什么要这样做〈提示:系统经常要从中断处理程序中唤醒睡眠进程)。
7.进程在什么时候处理它接收到的软中断信号?进程接收到软中断信号后放在什么地方?
8.UNIX System V为什么要采用交换和请求调页两种内存管理策略?交换和请求调页才式有何区别?
9.UNIX文件系统为什么有磁盘i节点和内存i节点?为什么内存i节点的内容和磁盘i节点的内容不一样?
10.为什么要有系统打开文件表?用户进程是怎样与文件系统联系的?创建一个文件时创建系统打开文件表吗?
11.UNIX采统为什么要设置延迟写和异步写?它们各有什么优缺点?
12.UNINX System v中进程管理和存储管理部分有哪些联系？
8.4.2解析题
1.试说明一个进程在其生命周期内的变化过程。
2.在UNIX系统中运行下面程序,最多可产生多少个进程?画出进程家族树。
main( )
{
fork();
fork();
fork();
}
3.UNIX采用一般写、异步写和延迟写三种方式将缓冲区中的内容写回磁盘。试述这三种方式的特点。
4.UNIX的i节点是文件内容的一部分,对吗?请说明理由。
5.是否当每次进行磁盘读/写时,核心都要为之分配缓冲区?当需要分配缓冲区时,应从何处获得?
6.编写一个程序,使用系统调用fork生成三个子进程,并使用系统调用pipe创建一管道,使得这三个子进程和父进程共用同一管道进行通信。
7.一个UNIX文件F的存取权限为,rwxr-x---,该文件的文件主uid=12,gid=1。另一个用户的uid=6,gid=1,是否允许该用户执行文件F?
8.下列程序执行时,"parent:child exited"可能在"child leaving"前面打印吗?为什么?程序执行结果中a=?为什么?
{…
a=55;
pid=fork():
if(pid==0)
{
sleep(5);
a=99;
sleep(5);
printf("child leavingh");
exit(0);
}
else
{
sleep(7):
pdntf(“a=%d\n",a);
wait(0):
printf(“parent:child exited\n");
}
}
为了便于读者理解本程序,将程序注释如下:
{
a=55;
pid=fork(); /*创建子进程*/
if(pid==0) /*子进程执行*/
sleep(5):/*睡眠5秒*/
a=99;
sleep(5);
printf("child leaving\n");
exit(O);
}
else /*父进程执行*/
{
sleep(7);/*睡眠7秒*/
printf("a=%d\n”,a);
wait(O); /*等待子进程终止*/
printf("parent:child exitedh");
}
}
9.在UNIX系统中有卷资源表如下所示:
(1)现有个进程要释放四个物理块,其块号为
150#,156#,172#,177#,画出卷资源表的变化。
(2)在(1)的基础上假定一进程要求分配5个空闲块,画出分配后的卷资源表。
10.描述UNIX System V的i节点释放过程ifree,并说明为什么在文件系统中会含有其索引节点号比"铭记"索引节点号小的空闲索引节点。
11.试述下面程序的运行结果。
#include 〈fcntl.h〉
int fdrd,fdwt;
char c;
main(arse,argv)
int argc;
char *argv[];
{
if(argv!=3)
exit(l);
if(fdrd=open(argv[1],O_RDONLY))==一1)
exit(1):
if(fdwt=creat(argv[2],0666))==-1)
exit(1):
fork():
rdwrt():
exit(0):
}
rdwrt()
{
for〈;;)
{
if(read(fdrd,&c,1)!=1)
return;
write(fdwt,&c,1);
}
}
12.假定一个索引节点为128字节,指针为4字节长,而状态信息占用了68个字节。假定每块的大小为8K。问在索引节点中有多大的空间给指针?使用直接指针、间接指针、二次间接指针、三次间接指针分别可以表示多大的文件?
8.4 答案一．判断题
1.Χ 2.√ 3,√ 4,Χ 5,Χ 6,√ 7,Χ 8,√ 9.√ 10.√
二．选择题：
1.B 2.A 3.A 4.B 5.C 6.D 7.D 8.B 9.A 10.C 11.B 12.D 13.B 14.C 15.B 16.B 17.B 18.B 19.B 20.B
三．填空题
1.
2.Shell ②程序 ③系统调用
3.
4,本进程区表 系统区表
5,普通文件 目录文件 特殊文件
6.用户态
7.页表 磁盘块描述表 页面数据表 对换使用表
8.提前读
9.文件名 索引节点号
10.成组链接法
11.对换
12.open
13.字符 字符设备 块 块设备
14.联结计数
15.单缓冲区 双缓冲区 多缓冲区 缓冲池
16.通道 控制器 I/O操作四．简答题
1.答:UNIX系统为用户提供两个接口,即面向操作命令的接口Shell和面向编程用户的接口:系统调用。常见的Shell命令:login,logout,vi,emacs,cp,rm,ls,cc,link,adduser,date等；常见的系统调用如:ioct1,read,write,open,close,creah，exec1,flock,stah mount,fork,wait,exit,socket等。
2.答:因为系统程序的代码被用户程序所共享,因此如果每个进程在保存进程上下文时,都将系统程序代码放到其进程上下文中,则大大浪费了资源。因此系统程序的代码不放在进程上下文中,而是统一放在核心程序所处的内存中。
3.答:UNIX System V进程上下文由以下几部分组成：
Proc结构,User结构,用户找和核心梭的内容,用户地址空间的正文段和数据段,硬件寄存器的内容,区表,页表。
核心页表被所有进程共享,所以不是进程上下文的一部分。
而进程页表是进程上下文的一部分。
4.答:UNIX System V采用基于优先级的多级轮转反馈调度策略。在调度时应封锁中断,否则在调度过程中由于中断会使进程上下文的切换出现错误。
5.答:当UNIX操作系统装入内存后,系统的控制权便由自举程序转到核心程序,即操作系统程序上来。核心首先生成系统进程0,然后由0号进程创建一个1号进程(即init进程),进程1负责初始化所有新的用户进程。实际上,1号进程是除了0号进程之外所有用户进程的祖先。UNIX系统的调度与交换都是0进程的两部分,它们分别由swtch过程和sched过程实现。sched过程把处于外存就绪态的进程换入内存,swtch则从就绪队列中寻找一优先级最高的进程。
因此,进程0的作用是:创建进程1,进行进程的调度和交换。
6.答:系统调用sleep和wakeup时经常要做进程上下文切换,而系统又经常要从中断处理程序中唤醒睡眠进程,为了保证进程上下文切换的正确进行,防止在切换过程中响应中断,需要提高处理机的执行级。
7.答:进程在再次被调度执行时先检查是否收到软中断,若进程接收到了软中断信号则优先处理软中断。进程把接收到软中断信号存放在proc结构的相应项中。
8.答:交换是UNIX System早期版本引入的扩充内存技术,但交换不能实现虚拟存储,故UNIX System V引入请求调页内存管理策略以实现虚拟存储且保留了交换技术。
交换技术在交换时换入换出的是整个进程(除Proc外),即使实现部分交换也不是按进程执行的需要进行交换。交换根据程序和数据在内存或外存中驻留时间长短进行换入换出。交换不能实现虚拟存储。
请求调页只是把经常执行或正在执行的页调入内存,当执行到当前页不在内存时,系统调入此页。请求调页内存管理技术可以实现虚拟存储。
9.答:UNIX系统中,磁盘i节点以静态形式存放文件说明信息。引入内存i节点是为了减少设备的启动次数以及提高操作速度,把磁盘i节点复制到内存特定区域。由于进程需用i节点中的逻辑结构和物理结构信息完成对文件信息的保护和共享,故i节点中多了当前文件状态信息。
10.答:用户打开文件表记录一个进程可以同时打开的文件数,UNIX System V最多可达到20。用户打开表的描述符返回给用户进程后成为文件描述符。与此相对应,用户对文件进行操作时,在系统内部需有相应数据结构来记录和控制打开文件的用户进程,以及记录和控制那些共享同一文件的用户进程。这个数据结构就是系统打开表。用户进程通过系统调用来完成与文件系统联系。创建文件时,需要在系统打开文件表的相应表项中生成相应数据,但不需要创建系统打开表。
11.答:异步写的目的是提高写盘速度,延迟写的目的是为了让数据块在内存中待尽量多的时间,以减少不必要的I/0操作。优点:把一个缓冲区的数据往磁盘写时,如同步,进程因为等待写操作完成而进入睡眠,而且要在写操作完成后才释放缓冲区。如延迟写或异步写时,系统启动传输,不等写完成而返回,都加快了写盘速度,但延迟写还减少了不必要的I/O操作。缺点:延迟写没有立即把数据写入磁盘,当系统发生瘫痪时将产生磁盘数据错误。异步写是启动传输后,不等传输完成而返回,也可能发生数据错,但可能性小。
12.答:进程管理包括进程创建、进程调度、进程执行和进程撤消。进程创建、调度和执行需要存储管理部分为进程分配或释放内存空间,进程的撤消需要存储管理部分回收分配给撒消进程的内存空间。存储管理系统必须决定哪个进程的哪个部分应该放在内存,并管理那些不在内存又属于同一进程虚空间的部分。
解析题8
1.答:一个进程从被创建开始到被释放为止，状态之间的转换有些是通过系统原语或核心函数完成,有些则由外部事件的发生而导致状态转换。下面我们讨论一个进程可能的状态变迁过程,其中的事件说明了各种可能的转换原因,但进程并不一定总是要经历这些事件。
首先,当父进程执行系统调用fork时,被创建进程进入创建状态。当被创建进程处于该状态时,核心为该进程分配U区以及必要的内存工作集。内存管理分配程序如果能为该进程分配足够的内存,则进程状态发生变化,由创建状态变为内存中就绪状态。此时,由于该进程已分得存放U区、各种页表和堆钱以及部分正文段和数据段等的内存空间,因此,该进程可以经调度选中后占有CPU。
如果内存分配程序不能为该进程分配足够的内存,则该进程的进程上下文被存放到外存交换区中,进程由创建状态变为就绪且换出状态。如果进程处于就绪且换出状态,则只有在交换程序将进程上下文换入内存成为状态之后,才有可能被调度执行。
当进程进入内存中就绪状态后,进程调度程序将会在适当时机选择该进程去执行。这时,该进程在核心态下执行,以装配该进程的进程上下文。在这个状态下,该进程完成它的fork部分的工作。
当该进程完成fork系统调用后,它可能返回用户态下执行用户程序,这时该进程进入用户态执行状态。
另外,UNIX System V的调度策略规定,在进程完成系统调用后返回用户态之前,若此时有优先级高于当前进程的进程存在,则系统将调度优先级高的进程去占据处理机,从而使当前运行进程进入状态被剥夺状态。进程进入被剥夺状态之后,所处的地位与内存中就绪状态相同,即要等到再一次进程调度时才能返回用户态执行。
当进程处于用户态执行时,用户程序中由于使用系统调用或输入/输出数据等而发生陷入与中断。这样,进程又进入核心态执行。
进程在核心态执行时,因为等待某事件发生,如等待输入/输出完成等,调用sleep原语进入内存中睡眠状态。处于内存中睡眠状态的进程因为内存的限制,将在睡眠一段时间后被交换程序换出内存而进入睡眠且换出状态,直到事件发生后被唤醒原语唤醒而进入就绪且换出状态。
当进程完成时,将使用系统调用exit,从而使得进程进入僵死状态。
2.答：分析：系统调用fork的功能是创建一个新进程,新浙主运行与其创建者一样的程序,新创建的进程称为子进程,调用fork的进程称为父进程,父子进程都从fork调用后的那条语句开始执行。
当程序执行时,若所有进程都能成功地执行系统调用fork,则会产生最多数目的进程。为了描述方便起见,将开始执行时的进程称为A进程,此时程序计数器PC 指向第一个fork调用。
main( )
{
fork(); /*←PC,进程A*/
fork();
fork();
}
当进程A成功地执行完第一个fork调用时,它创建了一个子进程,将此子进程称为进程B。此时,进程A、B的程序计数器PC指向第二个fork调用,进程A派生了1个子孙进程。
main()
{
fork();
fork(); /*←PC,进程A*/
fork();
}
当进程A、B成功地执行完第二个fork调用时,它们分别创建了一个子进程,将这些子进程分别称为进程C、D.此时,进程A、B、C、D的程序计数器PC指向第三个fork调用,进程A派生了3个子孙进程。
Main()
{
fork();
fork();
fork(); /* ←pc,进程A */
}
main()
{
fork();
fork();
fork(); /*←PC,进程B*/
}
main()
{
fork();
fork();
fork(); /*←PC,进程C*/
}
main()
{
fork();
fork();
fork(); /*←PC,进程D*/
}
当进程A、B、C、D成功地执行完第三个fork调用时,它们分别创建了一个子进程,将这些子进程分别称为进程E、F、G、H.此时,进程A、B、C、D、E、F、G、H的程序计数器PC指向程序结束处,进程A派生了7个子孙进程。
main()
{
fork();
fork();
fork();
} /*←PC,进程A*/
main()
{
fork();
fork();
fork();
} /*←PC,进程B*/
main()
{
fork();
fork();
fork();
} /*←PC,进程C*/
main()
{
fork();
fork();
fork();
} /*←PC,进程D/
main( )
{
fork();
fork();
fork();
} /* ←PC,进程E/
main()
{
fork();
fork();
fork();
} /*←PC,进程F*/
main()
{
fork();
fork();
fork();
} /*←PC,进程G*/
main()
{
fork();
fork();
fork();
} /* ←PC,进程H*/
进程家族树是一棵有向树,有向树的节点代表进程,由进程P指向进程Q的边表示由进程P创建了进程Q。我们称进程P走进程Q的父进程,进程Q走进程P的子进程,这样便形成了进程树。
答:从上面的分析过程可以看出,执行第一个fork调用时,进程A创建了进程B；执行第二个fork调用时,进程A创建了进程C,进程B创建了进程D；执行第三个fork调用时,进程A创建了进程E,进程B创建了进程F,进程C创建了进程G,进程D创建了进程H。因此,在UNIX系统中运行题目中的程序,最多可产生7个进程,其进程家族树如下图所示。
3.答:(1)一般写。启动设备写时,进程使自己睡眠,等待写操作完成后唤醒等待进程。
(2)异步写过程。启动设备写后,进程不等待写操作完成即返回。
(3)延迟写过程。进行延迟写时,只是将数据写到内存缓冲区中,等到该缓冲区分配给其他磁盘块使用时再将该块内容写入磁盘,从而增加了数据在内存的驻留时间。
4.答：在UNIX系统中,文件名与文件说明是分开存放的。由文件说明形成的一个数据结构称为索引节点(index node ),而相应的文件目录项则只由文件名和其索引节点号构成。
索引节点又称i节点,其中存放文件的说明信息。索引节点以静态形式存放在磁盘上,故又称为磁盘索引节点。每个文件都有惟一的一个磁盘索引节点,它由下述字段构成:
文件所有者标识符、文件类型、文件存取权限、存放文件的物理地址、文件长度、文件联结计数和文件存取时间。
为了加快文件的存取速度和减轻磁盘I/0的压力,系统又专门在内存中建立了一个内存索引节点表,将那些要被引用的磁盘索引节点复制到内存索引节点表中,并增加了如下字段:
索引节点号、内存索引节点状态、内存索引节点引用计数、设备号、内存索引节点指针从上面的分析可以看出,UNIX系统中的i节点不是文件内容的一部分,而是用于文件管理的数据结构。
5.答：每当进行磁盘读/写操作时,核心调用getblk过程分配缓冲区.当要读磁盘数据时,核心首先检查委读入的盘块内容是否已在某个缓冲区中,若发现已在某个缓冲区中,便不必再从磁盘上读入。仅当数据未在任何缓冲区中时,核心才需从磁盘上将数据读入,这时才需为其分自己一空闲缓冲区。类似地,当要把数据写入一特定盘块时,核心应先检查该决内容是否已在某缓冲区中,仅当该块内容尚不在缓冲区中时,才需分配一空闲缓冲区。获取空闲缓冲区时应提供的输入参数是文件系统号和磁盘块号。getblk过程分自己缓冲区时,可分为两种情况:
(1)缓冲区在散列队列上。进入getblk过程后,首先根据文件系统号和盘块号去查找散列队列,若找到与文件系统号和块号相匹自己的缓冲区,便可进一步检查该缓冲区是否空闲。若空闲,则应先上锁,以防止其他进程对它进行访问,然后把它从空闲链上摘下;若忙,则表明缓冲区已被其他进程上锁,因此暂时不能对它进行访问而进入睡眠,直至该缓冲区变为空闲时再将它唤醒。
(2)缓冲区不在散列队列上。若在散列队列中找不到与文件系统号及块号相匹配的缓冲区,使只有从空闲链表中找一个缓冲区.若空闲链表已空,则无法进行分配,进程睡眠,直到空闲链表中出现缓冲区为止;若空闲链表不空,这时可从链首摘下一缓冲区,若此缓冲区标记有"延迟写",此时应将该缓冲区内容异步地写到磁盘上,再从空闲链表中摘下一个缓冲区,并调整该缓冲区所在的散列队列,即将该散列队列从原来的散列队列调整到新的散列队列中.因为当该缓冲区重新分自己后,缓冲区对应的盘块号发生了变化,从而也相应地改变了其所在的散列队列.
由上面的叙述可以看出,当每次进行磁盘读/写时,核心都要检查读/写操作对应的磁盘块是否在缓冲池中。如果在缓冲池中,则直接引用缓冲池中的数据:如果不在,则分配一个空闲缓冲区。当需要空闲缓冲区时,应从空闲队列首部摘下缓冲区。
6.答:因pipe系统调用建立的是无名管道,而父子进程之间又需要通过无名管道进行通信,因此应先建立管道,再创建进程。
main( )
int r,p1,p2,,p3,fd[2] /*fd[2]用于存放管道文件描述符*/
char buf[50],s[5];
pipe(fd); /*创建管道,fd[0]、fd[1]分别为读、写描述符*/
while((p1= fork())==1); /*创建子进程1*/
if(pl==0) /*在子进程1中执行*/
{
lockf(fd[1],1,0); /*锁定写,参数1、0分别表示锁定、锁定范围*/
sprintf(buf,"child process P1 is sending message!\n");
printf("child process pl!\n");
write(fd[1],buf,50); /*将buf中的数据写入管道*/
sleep(5); /*睡眠等待*/
lockf(fd[1],0,0); /*解锁,第一个参数0表示解锁*/
exit(0);
else /*F父进程执行*/
{
while((p2=fork())=-1); /*创建子进程*/
if(p2===0) /*在子进程2中执行*/
{
lock(fd[1],1,0); /*锁定写*/
sprintf(buf,"child process P2 is sending message!\n);
printf("child process P2!＼n");
write(fd[1],buf,50); /*将buf中的数据写入管道*/
sleep(5); /*睡眠等待*/
lockkfd[1],0,0):/*解锁串/
exit(0);
}
else /*P父进程执行*/
{
while((p3=fork())==1); /*创建子进程3*/
if (p3==0) /*在子进程3中执行*/
lockf(fd[1],1,0); /*锁定写*/
sprintf(buf,"child process P3 is sending message!＼n");
printf(“child process P3!\n");
write(fd[ll,buf,50); /*将buf中的数据写入管道*/
sleep(5); /*睡眠等待*/
lockf(fd[1],0,0); /*解锁*/
exit(0);
}
wait(O); /*等待子进程执行*/
if(r=(read(fd[0],s,50)==-1) /*读管道内容到s*/
printf("can't read pipe\n");
else
printf(“%s\n",s);
wait(0); /*等待另一子进程执行*/
if(r=(read(fd[0],s,50)==-1) /*读管道内容到s*/
printf("can't read pipe\n");
else
printf("%s\n",s);
wait(O); /*等待最后一子进程执行*/
if(r=(read(fd[o],s,50)==-1) /*读管道内容到s*/
printf("can't read pipe\n");
else
printf("%s\n",s);
exit(0);
}
}
}
7．答：在UNIX操作系统中,一个文件应属于某个用户所有,我们将这个用户称为该文件的文件主。一般情况下,文件主就是建立文件的用户。在系统中,使用用户标识符(uid)来记录文件主.UNIX将使用文件的用户分成三类,即文件主、同组用户和其他用户。同组用户是相互之间有某种关系的用户,如同一课题组的人,用户所在的用户纽用纽标识符(gid)来表示.其他用户一般是和文件主元关的用户,但他们也是系统中的用户。
每一类用户对文件的操作都有三种不同的存取权限,即读、写和执行。由于有三类用户,每类用户有三种存取权限,故每个文件都有9种存取权限。在系统内部,文件的存取权限用9位二进制数描述,文件主权限对应最高三位,同组用户权限对应中间三位,其他用户权限对应低三位。例如,111101001(也可以用八进制数表示,如0751),表示文件主可以对该文件进行读、写、执行操作;同组用户可以对该文件进行读和执行操作;其他用户只能对该文件进行执行操作。
当系统用ls命令列目录时,文件权限以标准的符号形式表示。这种表示法使用9个字符,分为3组,每组3个字符.第一纽表示文件主的权限,第二纽表示同组用户的权限,第三组表示其他用户的权限.在每组的三个字符中,如果允许这类用户读,则第一个字符直为"r",如果允许进行写,则第二个字符直为"w",如果允许执行,则第三个字符置为"x"。如果不允许某个权限,则相应的字符置为"一".
由上述介绍可知,文件F的存取权限rwxr-x- - - 表示文件主可以对F进行读、写及执行操作,同组用户可以对F进行读及执行操作,其他用户不能对F进行操作。因为另一用户与文件主的组标识符相同(gid均为1),由此可知他们是同组用户,所以允许该用户执行文件F。
8.答:由于UNIX输出时采用缓冲区缓冲数据,尽管本程序中通过sleep来让进程睡眠,以达到同步控制的目的,但缓冲区中的数据"parent:child exited"仍有可能在"childleaving"前面打印输出。
在进程创建之前,变量a的值设置为55,进程创建之后,父子进程具有各自私有的数据区。因在父进程中,没有重新对变量a赋值且打印输出语句在父进程中,所以,程序执行结果中,输出的是"a=55"。
9.答：（1）画出的卷资源表如下:
将这块内容填入172#中,则卷资源表变成如下形式:
(2)先根据卷资源表取出172块的内容:取走177,172两块,然后将取出的内容置为卷资源表内容,取走其中的156,150,210,则卷资源表变为:
10.答：在UNIX System V中,文件系统包含一个索引节点线性表.如果索引节点的类型字段为0,则说明这个索引节点是空闲的。从理论上说核心能搜索磁盘索引节点表,以寻找一个空闲节点。然而像这样的技索太费时间,至少对每个索引节点都需要一个读操作(可能从磁盘读)。为了改善性能,在UNIX的文件系统超级块中包含一个空闲索引节点表,以便把文件系统中空闲的索引节点号缓存起来。当系统分配一个索引节点时,核心首先验证超级块是否上锁。在超级块未上锁时,若超级块中的空闲索引节点号表非空,则核心分配下一个索引节点号;若超级决空闲索引节点表为空,则核心搜索磁盘,并把尽可能多的空闲索引节点号放到超级块中。核心一块接一块地读磁盘上的索引节点表,并将空闲索引节点号填入超级块空闲索引节点表中,直至表满为止。同时,核心记住它所找到的最高序号的索引节点,称之为铭记索引节点,这是保存在超级块中的最后一个索引节点。下次核心搜索磁盘上的空闲索引节点时,就从铭记索引节点开始,这样能确保核心不浪费时间去读那些已不含空闲索引节点的磁盘块。
UNIX System V中的i节点释放过程ifree用于回收磁盘索引节点。其算法可形式化带述如下:
算法ifree
输入:文件系统索引节点号输出:无
{
文件系统空闲索引节点计数值增1:
if(超级块被锁住)
return:
if(索引节点表满〉
{
if(索引节点号小于用于搜索的铭记索引节点号〉
置用于搜索的铭记索引节点号=输入索引节点号:
}
else
把输入索引节点号存储到空闲索引节点表中:
retunu
}
在ifree算法中,当核心发现超级块上锁时,为了避免竞争,该算法立即返回。这时,系统既没有将释放的索引节点放入超级块的空闲索引节点表中,也没有修改铭记索引节点,而此时释放的索引节点号可能小于当前超级块中的铭记索引节点号,因此,在文件系统中可能会含有其索引节点号比"铭记"索引节点号小的空闲索引节点。
11.答：在本题程序中,调用该程序应有两个参数,一个是已有的文件名,另一个是要创建的新文件名。该程序打开已有的文件,创建一个新文件,若上述两个系统调用成功,则再利用fork创建一个子进程。父进程和子进程在不同的地址空间上运行相同的程序代码,每个进程都存取私有的全局变量fdrd,fdwt和c及私有的找变量argc和argv,但每个进程都不能存取另一进程的这些私有变量。父进程和子进程分别独立地调用rdwrt函数,并执行函数中的循环,即从源文件中读一个字节,然后写一个字节到目标文件中。当系统调用遇到文件尾时,函数rdwrt立即返回。
由于在fork调用前,相应的文件己打开或创建,因此父进程和子进程通过相同的文件表项共享对文件的存取,即两个进程的文件描述符fdrd都指向源文件的文件表项,fdwt都指向目标文件的文件表项。这两个进程永远不会读或写到相同的文件偏移量,因为核心在每次read和write调用之后,都要增加文件的偏移量。两个进程合作完成了一次从源文件到目标文件的复制工作,每个进程完成了其中的一部分文件复制任务,因此目标文件的内容依赖于核心调度两个进程的次序。如果核心只在每个进程执行完一对read和write系统调用后才进行切换,即在每个进程从源文件中读出的一个字节写入目标文件后才进行切换,则目标文件的内容与源、文件完全一致;否则,源文件的内容与目标文件不同。考虑、下述情况,两个进程正要读源文件中的两个连续的字符"ab",假定父进程读了字符"a",这时,核心在父进程做写之前,进行上下文切换并调度子进程运行;如果子进程读到字符"b"并在父进程被调度到之前将它写入目标文件,那么,目标文件将不再正确地含有字符串"ab",而是含有"ba”。
本程序完成的功能是将源文件复制到目标文件,父子进程合作完成此任务,但因核心并不保证进程执行的先后顺序,源文件与目标文件字符个数及字符内容相同,但次序不一定相同,如源文件为"aba",目标文件可能为"aab"。
12.答:由于索引节点为128字节,状态信息存用68个字节,用于指针的空间大小为:
128-68=60(字节〉
一次间接指针、二次间接指针和三次间接指针将占用索引节点中的三个指针项,因此直接指针项数为:
60/4-3=12(个)
使用直接指针时:
12×8196=98304(字节〉
大小不超过98304字节的文件使用直接指针即可表示。
使用一次间接指针时:
8196/4=2048(即一个磁盘块中可以装入2048个指针项)
2048×8196=16M〈字节〉
一次间接指针提供了对附加16M字节信息的寻址能力。
使用二次间接指针时:
2048×2048=4M(即二次间接可以提供4M个指针项)
4M×8196=32G(字节〉
二次间接指针提供了附加32G字节信息寻址能力。
使用三次间接指针时:
2048×2048×2048=8G(即三次间接可以提供8G个指针项〉
8G×8196=16T〈字节〉〈1T=1024GE240〉
三次间接指针提供了对附加16T字节信息的寻址能力。
