计算机操作系统ppt课件第10章

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第十章 UNIX系统内核结构,第十章 UNIX系统内核结构,10.1 UNIX系统概述,10.2 进程的描述和控制,10.3 进程的同步与通信,10.4 存储器管理,10.5 设备管理,10.6 文件管理,第十章 UNIX系统内核结构 10.1 UNIX系统概述,1,10.1 UNIX系统概述,10.1.1 UNIX系统的发展史,1. UNIX系统的发展,2. 两大集团对峙,3. 网络操作系统UNIX,10.1 UNIX系统概述 10.1.1 UNIX系统的发展,2,10.1.2 UNIX系统的特征,开放性,2) 多用户、 多任务环境,3) 功能强大， 实现高效,4) 提供了丰富的网络功能,5) 支持多处理器功能,10.1.2 UNIX系统的特征 开放性,3,10.1.3 UNIX系统的内核结构,图 10-1 UNIX核心的框图,10.1.3 UNIX系统的内核结构 图 10-1 UNIX,4,1. 进程控制子系统,进程控制。,(2) 进程通信。,(3) 存储器管理。,(4) 进程调度。,1. 进程控制子系统 进程控制。,5,2. 文件子系统,文件管理。,(2) 高速缓冲机制。,(3) 设备驱动程序。,2. 文件子系统 文件管理。,6,10.2 进程的描述和控制,10.2.1 进程控制块PCB,在UNIX系统中， 把进程控制块分为四部分：,(1) 进程表项。,(2) U区。 ,(3) 进程区表。 ,(4) 系统区表。,10.2 进程的描述和控制 10.2.1 进程控制块PCB,7,1. 进程表项(Process Table Entry),进程标识符(PID)。,(2) 用户标识符(UID)。,(3) 进程状态。,(4) 事件描述符。,(5) 进程和U区在内存或外存的地址。,(6) 软中断信息。,(7) 计时域。,(8) 进程的大小。,(9) 偏置值nice。,(10) P-Link指针。,(11) 指向U区进程正文、 数据及栈在内存区域的指针。,1. 进程表项(Process Table Entry),8,2. U区(U Area),进程表项指针。,(2) 真正用户标识符u-ruid(real user ID)。,(3) 有效用户标识符u-euid(effective user ID)。,(4) 用户文件描述符表。,(5) 当前目录和当前根。,(6) 计时器。,(7) 内部I/O参数。,(8) 限制字段。,(9) 差错字段。,(10) 返回值。,(11) 信号处理数组。,2. U区(U Area) 进程表项指针。,9,3. 系统区表(System Region Table),区的类型和大小。,(2) 区的状态。,(3) 区在物理存储器中的位置。,(4) 引用计数。,(5) 指向文件索引结点的指针。,3. 系统区表(System Region Table) 区,10,4. 本进程区表(Per Process Region Table),图 10-2 进程区表项、系统区表项和区的关系,4. 本进程区表(Per Process Region Ta,11,图 10-3 进程的数据结构,图 10-3 进程的数据结构,12,10.2.2 进程状态与进程映像,1. 进程状态,图 10-4 进程的状态转换,10.2.2 进程状态与进程映像 1. 进程状态 图 10-,13,2. 进程映像,用户级上下文,2) 寄存器上下文,程序寄存器。,(2) 处理机状态寄存器(PSR)。,(3) 栈指针。,(4) 通用寄存器。,3) 系统级上下文,静态部分。,(2) 动态部分。,2. 进程映像 用户级上下文,14,10.2.3 进程控制,1. fork系统调用,为新进程分配一个进程表项和进程标识符。,(2) 检查同时运行的进程数目。,(3) 拷贝进程表项中的数据。,(4) 子进程继承父进程的所有文件。,(5) 为子进程创建进程上下文。,(6) 子进程执行。,10.2.3 进程控制 1. fork系统调用 为新进程分配,15,2. exec系统调用,图 10-5 exec 的参数组织方式,2. exec系统调用 图 10-5 exec 的参数组织,16,3. exit系统调用,通常，父进程在创建子进程时，应在进程的末尾安排一条exit，使子进程能自我终止。内核须为exit完成以下操作：,(1) 关闭软中断。,(2) 回收资源。,(3) 写记账信息。,(4) 置进程为“僵死”状态。,3. exit系统调用 通常，父进程在创建子,17,4. wait系统调用,wait系统调用用于将调用进程挂起， 直至其子进程因暂停或终止而发来软中断信号为止。如果在wait调用前，已有子进程暂停或终止，则调用进程做适当处理后便返回。核心对wait调用做以下处理：核心查找调用进程是否还有子进程， 若无，便返回出错码；如果找到一个处于“僵死”状态的子进程，便将子进程的执行时间加到其父进程的执行时间上， 并释放该子进程的进程表项； 如果未找到处于“僵死”状态的子进程，则调用进程便在可被中断的优先级上睡眠，等待其子进程发来软中断信号时被唤醒。,4. wait系统调用 wait系统调用用于,18,10.2.4 进程调度与切换,1. 引起进程调度的原因,首先，由于UNIX系统是分时系统，因而其时钟中断处理程序须每隔一定时间，便对要求进程调度程序进行调度的标志runrun予以置位，以引起调度程序重新调度。其次，当进程执行了wait、exit及sleep等系统调用后要放弃处理机时， 也会引起调度程序重新进行调度。此外，当进程执行完系统调用功能而从核心态返回到用户态时，如果系统中又出现了更高优先级的进程在等待处理机时，内核应抢占当前进程的处理机， 这也会引起调度。,10.2.4 进程调度与切换 1. 引起进,19,2. 调度算法,进程调度，在此是采用动态优先数轮转调度算法。 调度程序在进行调度时，首先从处于“内存就绪”或“被抢占”状态的进程中，选择一个其优先数最小(优先级最高)的进程。若此时系统中(同时)有多个进程都具有相同的最高优先级，则内核将选择其中处于就绪状态或被抢占状态最久的进程，将它从其所在队列中移出，并进行进程上下文的切换， 恢复其运行。,2. 调度算法,20,3. 进程优先级的分类,UNIX系统把进程的优先级分成两类，第一类是核心优先级，又可进一步把它分为可中断和不可中断两种。当一个软中断信号到达时，若有进程正在可中断优先级上睡眠，该进程将立即被唤醒；若有进程处于不可中断优先级上， 则该进程继续睡眠。对诸如“对换”、“等待磁盘I/O”、“等待缓冲区”等几个优先级，都属于不可中断优先级；而“等待输入”、“等待终端输出”、“等待子进程退出”的几个优先级， 都是可中断优先级。另一类是用户优先级，它又被分成n+1级， 其中第0级为最高优先级，第n级的优先级最低。,3. 进程优先级的分类,21,4. 进程优先数的计算,其中，基本用户优先数即proc结构中的偏移值nice，可由用户将它设置成040中的任一个数。一旦设定后， 用户仅能使其值增加， 特权用户才有权减小nice的值。而最近使用CPU的时间，则是指当前占有处理机的进程本次使用CPU的时间。内核每隔16.667 ms，便对该时间做加1操作，这样，占有CPU的进程其优先数将会随着它占有CPU时间的增加而加大，相应地，其优先级便随之降低。,4. 进程优先数的计算 其中，基本用户优先数,22,5. 进程切换,在OS中， 凡要进行中断处理和执行系统调用时， 都将涉及到进程上下文的保存和恢复问题， 此时系统所保存或恢复的上下文都是属于同一个进程的。而在进程调度之后， 内核所应执行的是进程上下文的切换，即内核是把当前进程的上下文保存起来，而所恢复的则是进程调度程序所选中的进程的上下文，以使该进程能恢复执行。,5. 进程切换 在OS中， 凡要进行中断处理,23,10.3 进程的同步与通信,10.3.1 sleep与wakeup同步机制,1. sleep过程,进入sleep过程后，核心首先保存进入睡眠时的处理机运行级， 再提高处理机的运行优先级，来屏蔽所有的中断，接着将该进程置为“睡眠”状态，将睡眠地址保存在进程表项中，并将该进程放入睡眠队列中。如果进程的睡眠是不可中断的，做了进程上下文的切换后，进程便可安稳地睡眠。 当进程被唤醒并被调度执行时，将恢复处理机的运行级为进入睡眠时的值， 此时允许中断处理机。,10.3 进程的同步与通信 10.3.1 sleep与wak,24,2. wakeup过程,该过程的主要功能，是唤醒在指定事件队列上睡眠的所有进程，并将它们放入可被调度的进程队列中。 如果进程尚未被装入内存，应唤醒对换进程； 如果被唤醒进程的优先级高于当前进程的优先级，则应重置调度标志。最后， 在恢复处理机的运行级后返回。,2. wakeup过程,25,10.3.2 信号(signal)机制,1. 信号机制的基本概念,信号机制主要是作为在同一用户的诸进程之间通信的简单工具。 信号本身是一个119中的某个整数，用来代表某一种事先约定好的简单消息。信号机制是对硬中断的一种模拟。,10.3.2 信号(signal)机制 1.,26,信号机制与中断机制之间的相似之处表现为： 信号和中断都同样采用异步通信方式，在检测出有信号或有中断请求时，两者都是暂停正在执行的程序而转去执行相应的处理程序，处理完后都再返回到原来的断点；再有是两者对信号或中断都可加以屏蔽。,信号与中断两机制之间的差异是：中断有优先级，而信号机制则没有，即所有的信号都是平等的；再者是信号处理程序是在用户态下运行的，而中断处理程序则是在核心态下运行；还有，中断响应是及时的，而对信号的响应通常都有较长的时间延迟。,信号机制与中断机制之间的相似之处表现为： 信,27,2. 信号机制的功能,1）发送信号,2) 设置对信号的处理方式,(1) func=1时， 进程对sig类信号不予理睬， 亦即屏蔽了该信号。,(2) func=0， 即为缺省值时， 进程在收到sig信号后应自我终止。,(3) func为非0、 非1类整数时， 就把func的值作为指向某信号处理程序的指针。,3) 对信号的处理 ,2. 信号机制的功能 1）发送信,28,10.3.3 管道机制,管道的类型,无名管道(Unnamed Pipes),2) 有名管道(Named Pipes),10.3.3 管道机制 管道的类型,29,2. 对无名管道的读写,对pipe文件大小的限制,2) 进程互斥,3) 进程写管道,4) 进程读管道,2. 对无名管道的读写 对pipe文件大小的限制,30,10.3.4 消息机制,1. 消息和消息队列,1) 消息(message),图 10-6 消息机制中的数据结构,10.3.4 消息机制 1. 消息和消息队列图 10-6,31,2) 消息队列,当一个进程收到由其它多个进程发来的消息时， 可将这些消息排成一个消息队列， 每个消息队列有一个称为关键字key的名称， 它是由用户指定的。 每个消息队列还有一个消息队列描述符， 其作用与用户文件描述符一样， 以方便用户和系统对消息队列的访问。 在一个系统中可能有若干个消息队列， 由所有的消息队列的头标组成一个头标数组。,2) 消息队列 当一个进程收到由其它多个进程,32,2. 消息队列的建立与操作,1) 消息队列的建立,在一个进程要利用消息机制与其它进程通信之前， 应利用系统调用msgget( )先建立一个指名的消息队列。对于该系统调用，核心将搜索消息队列头标表， 确定是否有指定名字的消息队列。若无，核心将分配一个新的消息队列头标， 并对它进行初始化，然后给用户返回一个消息队列描述符； 否则，它只是检查该消息队列的许可权后便返回。,2. 消息队列的建立与操作 1) 消息队列的,33,2) 消息队列的操纵,(1) 用于查询有关消息队列的情况， 如队列中的消息数目、 队列中的最大字节数、 最后一个发送消息的进程的标识符、 发送时间等。,(2) 用于设置和改变有关消息队列的属性， 如改变消息队列的用户标识符、 或用户组标识符、 消息队列的许可权等。,(3) 消除消息队列的标识符。,2) 消息队列的操纵 (1) 用于查询有关消息,34,3. 消息的发送和接收,1) 消息的发送,当进程要与其它进程通信时，可利用msgsnd( )系统调用来发送消息。 对于msgsnd( )系统调用， 核心检查消息队列描述符和许可权是否合法、消息长度是否超过系统规定的长度。通过检查后，核心为消息分配消息数据区，并将消息从用户消息缓冲区拷贝到消息数据区。 分配消息首部，将它链入消息队列的末尾；在消息首部中填写消息的类型、 大小以及指向消息数据区的指针等；还要修改消息队列头标中的数据(如消息队列中的消息数、字节数等。然后，唤醒在等待消息到来的睡眠进程。,3. 消息的发送和接收,35,2) 消息的接收,进程可利用msgrcv( )系统调用， 从指定消息队列中读一个消息。对于msgrcv( )系统调用， 是先由核心检查消息队列标识符和许可权， 继而根据用户指定的消息类型做相应的处理。消息类型msgtyp的参数可能有三种情况：当msgtyp=0时，核心寻找消息队列中的第一个消息，并将它返回给调用进程；当msgtyp为正整数时，核心返回指定类型的第一个消息；当msgtyp为负整数时，核心应在其类型值小于或等于msgtyp绝对值的所有消息中，选出类型值最低的第一个消息返回。 如果所返回消息的大小等于或小于用户的请求，核心便将消息正文拷贝到用户区，再从队列中删除该消息，并唤醒睡眠的发送进程；如果消息长度比用户要求的大， 则系统返回出错信息。,2) 消息的接收,36,10.3.5 共享存储区机制,1. 共享存储区,图 10-7 利用共享存储区进行通信,10.3.5 共享存储区机制 1. 共享存储区 图 10-7,37,2. 共享存储区的建立与操纵,1) 共享存储区的建立,当进程要利用共享存储区与另一进程进行通信时， 须先利用系统调用shmget( )建立一块共享存储区，并提供该共享存储区的名字key和共享存储区以字节为单位的长度size等参数。 若系统中已经建立了指名的共享存储区，则该系统调用将返回该共享存储区的描述符shmid；若尚未建立，便为进程建立一个指定大小的共享存储区。,2. 共享存储区的建立与操纵 1) 共享存,38,2) 共享存储区的操纵,如同消息机制一样，可以用shmctl( )系统调用对共享存储区的状态信息进行查询，如其长度、所连接的进程数、创建者标识符等； 也可设置或修改其属性， 如共享存储区的许可权、当前连接的进程计数等；还可用来对共享存储区加锁或解锁，以及修改共享存储区标识符等。,2) 共享存储区的操纵,39,3. 共享存储区的附接与断开,在进程已经建立了共享存储区或已获得了其描述符后， 还须利用系统调用shmat( )将该共享存储区附接到用户给定的某个进程的虚地址shmaddr上，并指定该存储区的访问属性即指明该区是只读，还是可读可写。此后，此共享存储区便成为该进程虚地址空间的一部分。进程可采取与对其它虚地址空间一样的存取方法来访问。当进程不再需要该共享存储区时，再利用系统调用shmdt( )把该区与进程断开。,3. 共享存储区的附接与断开,40,10.3.6 信号量集机制,1. 信号量与信号量集,1) 信号量,在UNIX系统中规定，每个信号量有一个可用来表示某类资源数目的信号量值和一个操作值，该操作值可为正整数、零或负整数三种情况之一。传统的信号量机构是对信号量施加wait及signal操作。而在UNIX系统中则并未采用wait及signal， 而是利用semop( )系统调用对指定的信号量施加操作。此外，还可利用semget( )来建立信号量及利用semctl( )系统调用对信号量进行操纵。,10.3.6 信号量集机制 1. 信号量与信号量集,41,2) 信号量集,在一个信号量集中，通常都包含有若干个信号量。对这组信号量的操作方式应当是原子操作方式， 此即，把对这组信号量视为一个整体，要么全做，要么全不做。如果核心不能完成对这组所有信号量的操作，则核心应将已经操作过的信号量恢复到操作前的状态，这样便可实现要么全做、 要么全不做的原子操作方式。,2) 信号量集,42,2. 信号量集的数据结构,1) 信号量表,信号量表是信号量的结构数组。在系统中，每个信号量用一个信号量结构表示。其中，包括信号量值semval及最近一次对信号量进行操作的进程标识符sempid、等待该信号量值增加的进程数等。,2. 信号量集的数据结构 1) 信号量表,43,2) 信号量集表,图 10-8 信号量集表与信号量表,2) 信号量集表 图 10-8 信号量集表与信号量表,44,3. 系统调用,在信号量机制中，同样也提供了若干条系统调用， 分别用于对信号量执行各种操作。,1) semget( )系统调用,用户可利用该系统调用来建立信号量集。用户应提供信号量的名字、信号量集中信号量的数目等。若信号量集的建立成功，将返回信号量集的描述符semid。,3. 系统调用,45,2) semop( )系统调用,该系统调用可用来对信号量集进行操作。用户需提供信号量集的描述符、信号量的编号，即信号量在信号量集中的序号，以及所要施加操作的操作数semop。 内核根据semop来改变信号量的值。当semop为正值时，便将该正值加到信号量的值上。当semop为负值时，若信号量的值大于semop的绝对值，应将该负值加到信号量值上； 否则， 操作失败，内核将已经操作过的信号量恢复到该系统调用开始执行时的值。,2) semop( )系统调用,46,10.4 存 储 器 管 理,10.4.1 请求调页管理的数据结构,1. 页表和磁盘描述表,1) 页表,图 10-9 页表项和磁盘描述表项,物理页号,年龄,写时拷贝,修改位,访问位,有效位,保护,（,a,）页表项,对换设备号,设备块号,存储器类型,（,b,）盘块说明,10.4 存 储 器 管 理 10.4.1 请求调页管理的,47,2. 页框数据表和对换使用表,1) 页框数据表,页状态： 指示该页的拷贝是在对换设备上， 还是在可执行文件中。,内存引用计数： 指出引用该页面的进程数目。,逻辑设备： 指含有此拷贝的逻辑设备， 它可以是对换设备， 也可以是文件系统。,块号： 当逻辑设备为对换设备时， 这是盘块号； 而当逻辑设备为文件系统时，这是指文件的逻辑块号。,指针1： 指向空闲页链表中的下一个页框数据表的指针。,指针2： 指向散列队列中下一个页框数据表的指针。,2. 页框数据表和对换使用表 1) 页框数据表,48,图 10-10 页框数据表项及其散列队列,图 10-10 页框数据表项及其散列队列,49,2) 对换使用表,图 10-11 四种数据结构之间的关系,2) 对换使用表 图 10-11 四种数据结构之间的关系,50,10.4.2 换页进程,1. 增加有效页的年龄,一个页可计数的最大年龄，取决于它的硬件设施。对于只设置两位作为年龄域的页，其有效页的年龄只能取值为0、1、2和3。当该页的年龄为0、 1、 2时，该页处于不可换出状态；而当其年龄达到3时，该页便为换出状态。 每当内存中的空闲页面数低于某规定的低限时，核心便唤醒换页进程，由换页进程去检查内存中的每一个活动的、 非上锁的区，对所有有效页的年龄字段加1。对于那些其年龄已增至3的页，便不再加1，而是将它们换出。如果这种页已被进程访问过，便将其年龄域中的年龄降为0。,10.4.2 换页进程 1. 增加有效页的年,51,2. 对换出页的几种处理方式,(1) 若在对换设备上已有被换出页的拷贝，且该页的内容未被修改，此时，核心只须将该页页表项中的有效位清零，并将页框数据表项中的引用计数减1，最后将该页表项放入空闲页链表中。,(2) 若在对换设备上没有被换出页的拷贝，则换出进程应将该页写到对换设备上。 ,(3) 虽然在对换设备上已有换出页的副本，但该页的内容已被修改过，此时核心应将该页在对换设备上原来占有的空间释放， 再重新将该页拷贝到对换设备上，使在对换设备上的拷贝内容总是最新的。,2. 对换出页的几种处理方式 (1) 若在对换,52,3. 将换出页面写到对换设备上,当在换出页面链表中的页面数已达到规定值时， 核心应将它们换出。为此，应首先为它们分配一个连续的对换空间，以便一起将它们换出； 但如果在对换设备上没有足够大的连续空间，而其空闲存储空间的总和又大于64 KB时，核心可采取每次换出一页的方式将它们换出。 每当核心向对换设备上写一个页时， 须首先清除该页页表项的有效位，并将页框数据表项中的引用计数减1。若引用计数为0，表明已无其它进程再引用该页，核心便将其页框数据表项链入空闲页链表的尾部。 若虽引用计数不为0，表明仍有进程共享该页，但如果该页已长期未被访问过，则也须将该页换出。最后，核心将分配给该页的对换空间的地址填入相应的磁盘描述表项中， 并将对换使用表中的计数加1。,3. 将换出页面写到对换设备上 当在换出页面,53,10.4.3 请求调页,缺页在可执行文件上,2. 缺页在对换设备上,3. 缺页在内存页面缓冲区中 ,10.4.3 请求调页 缺页在可执行文件上,54,10.5 设 备 管 理,10.5.1 字符设备缓冲区管理,1. 空闲字符缓冲区队列,图 10-12 空闲字符缓冲区队列,10.5 设 备 管 理10.5.1 字符设备缓冲区管理 1,55,2. 空闲字符缓冲区的分配与回收,在字符设备进行I/O时，内核可利用getcf过程从空闲字符缓冲区队列中取得一个空闲缓冲区，若队列空，表明已无空闲缓冲区可提供，便返回；否则，从队首取得一个空闲缓冲区， 并把指向该缓冲区的指针bp返回给调用者。由于空闲缓冲区队列属于临界资源，故还须采取互斥访问措施， 即，在过程开始处，将处理机的优先级提升为6，在取得空缓冲区之后，再恢复处理机的优先级。,2. 空闲字符缓冲区的分配与回收,56,3. 设备的字符缓冲区队列,(1) getc过程。,该过程用于从一个clist结构的队首指针所指示的字符缓冲队列中，取出为首的字符，然后修改该队列的可用字符计数和队首指针。当取完一个缓冲区中的所有字符时，将释放该缓冲区。该过程的返回值是取出的字符。,(2) putc过程。,该过程用于将一个字符C放入设备的指定字符缓冲区队列的末尾。若此时该队列空、或队列的最后一个缓冲区已满，且空闲字符缓冲区队列也空，该过程无法将字符放入队列中， 则返回“-1”。,3. 设备的字符缓冲区队列 (1) getc过,57,(3) getcb过程。,该过程用于从指定的设备字符缓冲区队列中， 取出第一个缓冲区，并将该队列的可用字符计数减去第一个缓冲区中的字符数，然后返回指向该缓冲区的指针bp。若该缓冲区已是该队列中惟一的缓冲区， 则置队尾指针为空。,(4) putcb过程。,该过程用于将由bp所指向的缓冲区放入指定的设备字符缓冲区队列的末尾，然后将该队列的可用字符计数加上bp缓冲区中的字符数后返回。,(3) getcb过程。,58,10.5.2 块设备缓冲区管理,1. 盘块缓冲区及其首部,图 10-13 缓冲首部,设备号,块号,状态,缓冲区指针,散列队列的前向指针,散列队列的后向指针,空闲表上的前向指针,空闲表上的后向指针,10.5.2 块设备缓冲区管理1. 盘块缓冲区及其首部 图,59,2. 盘块缓冲池结构,图 10-14 空闲队列(链)及散列队列,2. 盘块缓冲池结构 图 10-14 空闲队列(链)及散列队,60,3. 盘块缓冲区的分配,(1) getblk( )过程。,该过程用于从空闲缓冲区队列中获得任一空闲缓冲区。 该过程首先检查空闲块缓冲队列是否为空，若空，便调用sleep过程睡眠等待， 直至在空闲块缓冲队列中出现空闲缓冲区为止； 否则，从空闲块缓冲队列中摘下第一个缓冲区。若在其缓冲首部中还有延迟写标志，则还须调用bdwrite过程，将此缓冲区中的数据写回到磁盘中，再从空闲队列中取得一个空缓冲区；否则，便将b-flag中的bCD*2busy标志置为1， 并返回指向该缓冲区的指针bp。,3. 盘块缓冲区的分配 (1) getblk,61,(2) getblk(dev, blkno)过程。,该过程用于为指定设备dev和盘块号为blkno的盘块申请一个缓冲区。核心首先检查要读入的盘块内容是否已在某个缓冲区中，若发现已在某缓冲区中，便不再从磁盘上读； 否则，核心须从磁盘上将数据读入，这时才需为其分配一个空缓冲区。类似地，当要把数据写入一特定盘块时， 核心先检查该盘块的内容是否已在某缓冲区，仅当该块的内容尚不在缓冲区中时，才需调用getblk( )过程，分配一个空缓冲区。,(2) getblk(dev, blkno),62,4,. 盘块缓冲区的回收,当核心用完某缓冲区时，可调用brelse过程将之收回。 此前，可能有些进程因等待使用该缓冲区而睡眠，此时，释放者进程应将睡眠队列的队首进程唤醒。此外，还有可能有进程因空闲链表空而处于等待状态，同样也应将之唤醒。如果在所释放的缓冲区中的数据是有效的，为使以后在某进程需要它时，也能直接从缓冲区中读出而不必启动磁盘的I/O操作， 可将该缓冲区链入空闲链表的末尾；否则(缓冲区中数据无效)，应将它链入空闲队列的头部。空闲链表属于临界资源， 为了保证对它操作的互斥性，UNIX系统通过提高处理机的运行级对中断加以屏蔽的方法来实现。,4. 盘块缓冲区的回收,63,10.5.3 内核与驱动程序接口,1. 设备开关表的作用,图 10-15 设备开关表及系统调用和驱动程序间的接口,10.5.3 内核与驱动程序接口1. 设备开关表的作用 图,64,2. 块设备开关表,函数,表项,open,close,strategy,0,1,gdopen,gtopen,gdclose,gtclose,gdstrategy,gtstrategy,图 10-16 块设备开关表,2. 块设备开关表 函数 open c,65,3. 字符设备开关表,函数 ,表项,open,close,read,write,Ioctl,0,Conopen,Conclose,Conrdad,Conwrite,Conioctl,1,Dzbopen,Dzbclose,Dzbread,Dzbwrite,Dzbioctl,2,Syopen,nulldev,syread,sywrite,syioctl,图 10-17 字符设备开关表,3. 字符设备开关表 函数 opencl,66,10.5.4 磁盘驱动程序,1. 打开磁盘驱动器的过程gdopen,在UNIX系统中，设备被看作是一种特殊类型的文件， 因而在使用该文件之前，也须先将它打开。gdopen便是用于打开磁盘驱动器的过程，该过程的输入参数是设备号，无输出参数。进入该过程后，首先检查系统中是否有由输入参数dev所指定类型的磁盘驱动器，若有，再检查它是否已被打开， 如果尚未打开，便将此驱动器打开，亦即，将该磁盘控制器表中的标志b-flag设置为B-ONCE; 再调用gdtimer过程启动对应的控制器和设备短期时钟闹钟，用于控制磁盘驱动器的执行时间。若系统中无指定类型的磁盘驱动器，则置相应的出错信息后返回。,10.5.4 磁盘驱动程序 1. 打开磁盘驱动器的过程gdo,67,2. 启动磁盘控制器的过程,该过程的输入参数是控制器号ctl，无输出参数。进入该过程后，先从磁盘设备控制表中找到I/O队列的队首指针，若它为0，表示I/O队列空，无I/O缓冲区可取，于是返回；否则， 将控制器表中的忙闲标志b-active置“1”。设置磁盘控制器中的各寄存器，如磁盘地址寄存器、内存总线地址寄存器、控制状态寄存器、字计数器等，最后启动磁盘控制器读(或写)后返回。而gdstartegy过程的主要功能，则是把指定的缓冲首部排在磁盘控制器I/O队列的末尾，并启动磁盘控制器。,2. 启动磁盘控制器的过程,68,3. 磁盘中断处理过程gdintr,当磁盘I/O传送完成并发出中断请求信号时，CPU响应后将通过中断总控程序进入磁盘中断处理过程gdintr。该过程的输入参数是控制器号ctl。进入该过程后，先检查磁盘是否已经启动，若尚未启动，程序便不予理睬即返回； 若已启动， 则还须先通过对状态寄存器的检查，来了解本次传送是否出错。 若已出错，便在控制终端上显示出错信息。由于磁盘的出错率较高，因而并不采取一旦出错便停止传送的策略，而是做好重新执行的准备，然后再传送。仅当重试多次都失败、且超过规定的执行时间时，才设置出错标志。如未出错，则继续传送下一个缓冲区中的数据。,3. 磁盘中断处理过程gdintr,69,10.5.5 磁盘读、写程序,1) 读方式,在UNIX系统中有两种读方式：一般读方式：只把盘块中的信息读入缓冲区，由bread过程完成。提前读方式：当一个进程要顺序地读一个文件所在的各个盘块时，会预见到所要读的下一个盘块，因而在读出指定盘块(作为当前块)的同时，可要求提前将下一个盘块(提前块)中的信息读入缓冲区。这样，当以后需要该盘块的数据时，由于它已在内存， 故而可缩短读这块数据的时间，从而改善了系统性能。 提前读功能由breada过程完成。,10.5.5 磁盘读、写程序 1) 读方式,70,2) 写方式,一般写方式：这是真正把缓冲区中的数据写到磁盘上， 且进程须等待写操作完成，由bwrite过程完成。,异步写方式：进程无须等待写操作完成便可返回， 异步写过程是bawrite。,延迟写方式：该方式并不真正启动磁盘，而只是在缓冲首部设置延迟写标志，然后便释放该缓冲区，并将之链入空闲链表的末尾。以后，当有进程申请到该缓冲区时，才将其内容写入磁盘。引入延迟写的目的是为了减少不必要的磁盘I/O， 因为只要没有进程申请到此缓冲区，其中的数据便不会被写入磁盘，倘若再有进程需要访问其中的数据时，便可直接从空闲链表中摘下该缓冲区，而不必从磁盘读入。延迟写方式由过程bdwrite完成。,2) 写方式,71,2. 读过程bread和breada,一般读过程bread,2) 提前读过程breada,2. 读过程bread和breada 一般读过程bread,72,3. 写过程bwrite、 bawrite和bdwrite,1) 一般写过程bwrite,该过程的输入参数是缓冲区指针bp。进入该过程后，根据bp指针找到缓冲区首部，设置缓冲区首部的初值，通过设备开关表转入策略过程，启动磁盘。如是一般写， 应等待I/O完成，为此， 须调用sleep过程使自己睡眠。 I/O完成后才被唤醒，再调用brelse过程释放该缓冲区。如是异步写、且有延迟写标志，则在给缓冲区打上标志后，将之放入空闲链表的首部。,3. 写过程bwrite、 bawrite和bdwrite,73,2) 异步写过程bawrite,它与一般写过程很相似，但不须等待I/O完成即可返回。 进入bawrite过程后，设置异步写标志，再调用bwrite过程实现之。,3) 延迟写过程bdwrite,延迟写过程也很简单。这里只须设置延迟写标志及数据有效标志， 再调用brelse过程，将该缓冲区释放，并链入空闲链表的尾部。以后，当某进程调用getblk获得该缓冲区时，再用异步写方式将缓冲区内容写入磁盘。,2) 异步写过程bawrite,74,10.6 文 件 管 理,10.6.1 UNIX文件系统概述,1. UNIX文件系统的特点,文件系统的组织是分级树形结构。,(2) 文件的物理结构为混合索引式文件结构。,(3) 采用了成组链接法管理空闲盘块。,10.6 文 件 管 理 10.6.1 UNIX文件系统概,75,2. 文件系统的结构,图 10-18 UNIX文件系统的结构,2. 文件系统的结构图 10-18 UNIX文件系统的结构,76,3. 文件系统的资源管理,当文件处于“未打开”状态时， 文件需占用三种资源： ,一个目录项。,(2) 一个磁盘索引结点项。,(3) 若干个盘块。,当文件被引用或“打开”时， 须再增加三种资源：,(1) 一个内存索引结点项。 它驻留在内存中。,(2) 文件表中的一个登记项。,(3) 用户文件描述符表中的一个登记项。,3. 文件系统的资源管理 当文件处于“未打开”状态时， 文,77,由于对文件的读写管理，必须涉及到上述各种资源， 因而使对文件的读写管理，又在很大程度上依赖于对这些资源的管理， 故可从资源管理观点上来介绍文件系统。这样，对文件的管理就必然包括： 对索引结点的管理； 对空闲盘块的管理； 对目录文件的管理； 对文件表和描述符表的管理； 对文件的使用。,由于对文件的读写管理，必须涉及到上述各种资源,78,10.6.2 文件的物理结构,1. 寻址方式,(1) 直接寻址。,(2) 一次间接寻址方式。,(3) 多次间接寻址。,10.6.2 文件的物理结构 1. 寻址方式,79,图 10-19 直接寻址和间接寻址,图 10-19 直接寻址和间接寻址,80,2. 地址转换,将字节偏移量转换为文件逻辑块号,2) 把文件逻辑块号转换为物理盘块号,直接寻址。,(2) 一次间址。,(3) 多次间址。,2. 地址转换 将字节偏移量转换为文件逻辑块号,81,图 10-20 文件的地址映射示例,图 10-20 文件的地址映射示例,82,10.6.3 索引结点的管理,1. 超级块(Superblock),(1) 文件系统的盘块数目。,(2) 空闲盘块号栈。,(3) 当前空闲盘块号数目。,(4) 空闲磁盘i结点号栈。,(5) 空闲磁盘i结点数目。,(6) 空闲盘块编号栈的锁字段。,(7) 空闲磁盘i结点栈的锁字段。,(8) 超级块修改标志。,(9) 修改时间。,10.6.3 索引结点的管理 1. 超级块(Superblo,83,2. 磁盘索引结点的分配与回收,分配过程ialloc,检查超级块上锁否。,(2) 检索i结点栈空否。,(3) 从空闲i结点编号栈中分配一个i结点， 并且加以初始化， 填写有关文件的属性。,(4) 分配内存i结点。,(5) 将磁盘i结点总数减1， 并在置超级块的修改标志后返回。,2. 磁盘索引结点的分配与回收 分配过程ialloc,84,2) 回收过程ifree,检查超级块上锁否。,(2) 检查i结点编号栈满否。,(3) 若i结点编号栈未满， 便将回收的i结点的编号进栈， 并使当前空闲i结点数加1。,(4) 置超级块修改标志后返回。,2) 回收过程ifree 检查超级块上锁否。,85,3. 内存索引结点的分配与回收,1) 分配过程iget,该过程的主要功能，是在打开文件时， 为之分配内存i结点。 由于允许文件被共享，因此，如果一文件早已被其他用户打开并有了内存i结点，此时便只须将该i结点中的引用计数加1； 如果文件尚未被其他用户打开，则由iget过程为该文件分配一个内存i结点，并调用bread过程将其磁盘i结点的内容拷贝到内存i结点中，同时进行初始化。,3. 内存索引结点的分配与回收 1) 分配过,86,2) 回收过程iput,每当进程要关闭某文件时，须调用iput过程，先对该文件的内存i结点中的引用计数做减1操作。若结果为0，便回收该内存i结点， 再对该文件的磁盘i结点中的连接计数减1；若其结果也为0，便删除此文件， 并回收分配给该文件的盘块和磁盘i结点。,2) 回收过程iput,87,10.6.4 空闲磁盘空间的管理,图 10-21 文件卷的组织,10.6.4 空闲磁盘空间的管理 图 10-21 文件卷的组,88,2. 空闲盘块的组织,图 10-22 空闲盘块的组织,2. 空闲盘块的组织 图 10-22 空闲盘块的组织,89,3. 空闲盘块的分配与回收,1) 空闲盘块的分配,空闲盘块的分配是由alloc过程完成的，该过程的主要功能，是从空闲盘块号栈中获得一空闲盘块号。当核心要从文件系统中分配一个盘块时，首先检查超级块中的盘块号栈是否已经上锁。若已锁上，便调用sleep过程睡眠； 否则，将超级块的空闲盘块号栈顶的盘块号(如95号)分配出去。如果所分配的空闲盘块号是在栈底(如109号)，由于在该号盘块中又包含了第二组盘块的所有盘块号(如211、 208等)，于是核心在给超级块上锁后，应先调用bread过程将该栈底盘块号对应盘块中的内容读出，作为新栈的内容进栈；然后，再将原有栈底所对应的盘块作为空闲盘块分配出去(即109号盘块)；最后，将超级块解锁，唤醒等待超级块解锁的进程。,3. 空闲盘块的分配与回收 1) 空闲盘块,90,2) 空闲盘块的回收,空闲盘块的回收是由free过程完成的。在回收空闲盘块时，首先检查超级块中的盘块号栈是否已经上锁， 若已上锁，便调用sleep睡眠；否则， 再检查空闲盘块号栈是否已满。如果空闲盘块号栈未满，可直接将回收盘块的编号记入空闲盘块号栈中；若栈已满，须调用betblk过程申请一个缓冲区， 将栈中的所有空闲盘块号复制到新回收的盘块中，再将新回收盘块的编号作为新栈的栈底块号进栈。,2) 空闲盘块的回收,91,10.6.5 文件表的管理,用户文件描述符表的管理,(1) 用户文件描述符表。,为了方便用户和简化系统的处理过程，在UNIX系统中， 在每个进程的U区中都设置了一张用户文件描述符表。核心先对其打开请求做仔细检查后，便在该进程的用户文件描述符表中， 分配一个空项，取其在该表中的位移量作为文件描述符fd(file discriptor)返回给用户。以后，当用户再访问该文件时， 只需提供该文件描述符fd，系统根据fd便可找到相应文件的内存索引结点。,10.6.5 文件表的管理 用户文件描述符表的管理,92,(2) ufalloc过程。,用户文件描述符表项的分配，是由ufalloc过程完成的。该过程首先是从用户文件描述符表中查找一个空项， 若找到，便将该表项的序号fd作为文件描述符写入进程的U区，然后返回； 否则， 置出错标志后返回“NULL”。,(2) ufalloc过程。,93,2. 文件表的管理,(1) 文件表。,图 10-23 对文件的三种读/写方式,2. 文件表的管理 (1) 文件表。 图 10-23 对文件,94,(2) falloc过程。,该过程的功能是分配文件表项。进入falloc过程后，调用ufalloc过程分配用户文件描述表项。若未分配成功，便返回NULL； 否则，继续从文件表中查找一个空闲文件表项若找到空闲文件表项，便将该项的始址置入用户文件描述符表项中。在设置文件描述表表项的初始值后便返回(fp)。 若未找到空闲文件表表项， 则返回NULL。,(2) falloc过程。,95,10.6.6 目录管理,构造目录,2. 删除目录,3. 检索目录,10.6.6 目录管理 构造目录,96,