《操作系统》课件-8.ppt

《《操作系统》课件-8.ppt》由会员分享，可在线阅读，更多相关《《操作系统》课件-8.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第8章 实例分析：Linux操作系统1.2.3.本章讲述内容：本章讲述内容：4.Linux的三种进程调度策略及消息队列；的三种进程调度策略及消息队列；Linux的多级页表地址转换机制的多级页表地址转换机制；Linux的文件系统的文件系统Ext2和虚拟文件系统和虚拟文件系统VFS；Linux对字符设备和块设备的管理对字符设备和块设备的管理。8.1 Linux的处理机管理的处理机管理o8.1.1 Linux的进程的进程Linux进程的两种运行模式进程的两种运行模式1.Linux里，当进程运行用户程序时，称为“用户模式用户模式”；当进程运行中出现系统调用或中断事件，转去执行操作系统内核程序时，称为“

2、核心模式核心模式”。进程在核心模式时，从事资源管理及各种控制活动；在用户模式时，在操作系统管理和控制下做自己的工作。.在Linux里处理机有两种运行状态：在核心态，CPU执行操作系统的程序；在用户态，CPU执行用户程序。这两种运行状态，会在一定时机按需要进行转换。.Linux把进程定义为是“程序运行的一个实例程序运行的一个实例”。进程竞争并占用系统资源，向系统提出各种请求服务；进程也是调度单位，任何时刻只有一个进程在CPU上运行。Linux进程实体的组成进程实体的组成2.Linux中，每个进程是一个任务(task)，有四个部分：进程描述符进程描述符，即进程控制块；进程专用的系统堆栈空间堆栈空间

3、；正文段正文段，即供进程执行的程序段；进程专用的数据段和用户数据段和用户堆栈空间堆栈空间。Linux进程的四个部分.在Linux中，进程描述符是一个结构类型的数据结构：task_struct，主要有以下信息：接收的信号 进程队列指针CPU的现场保护区与文件系统有关的信息 产生一个新进程时，系统就分配总量为8KB的空间(即两个连续的内存块)，用于存放进程描述符和组成系统堆栈。进程因系统调用进入Linux内核时(这时CPU被切换成核心态)，就使用系统堆栈。.进程描述符和核心栈 两个连续的物理块(8KB)堆栈进程描述符进程的核心栈(7KB)(1KB)Linux对进程描述符的管理 Linux在内核存储

4、区里开辟一个指针数组task，长度为NR_TASKS，每个数组元素里存放一个已创建进程的进程描述符地址。即每个数组元素都指向一个已创建进程的进程描述符，通过它，就可以找到当前系统中所有进程的进程描述符。一个进程描述符一个进程描述符一个进程描述符NR_TASKS个元素指针数组taskLinux进程描述符的内容进程描述符的内容3.进程标识.进程状态.进程调度信息 进程家族关系 暂停状态暂停状态：运行进程由于接收到一个信号，执行被暂时停止。处于该状态的进程，只能由来自另一个进程发来的信号改变成就绪状态。不可中断状态不可中断状态：这是另外一种阻塞状态。处于这种状态的进程，表示进程不能被信号中断，而是在

5、等待硬件条件的到来。可中断状态可中断状态：进程由于等待某些条件，而处于这种阻塞状态，直到那些条件出现将其唤醒。4.Linux的进程状态的进程状态 可运行状态可运行状态：进程已做好了运行的准备。该状态实际上包含两个状态，要么在CPU上运行（为执行状态），要么已经做好准备，随时可以投入运行（为就绪状态）。暂停状态可中断状态不可中断状态僵死状态可运行状态就绪执行调度被抢先创建事件信号终止信号或事件信号.僵死状态僵死状态：进程已经被终止，正在结束中。5.Linux的进程族系的进程族系 Linux系统初启时，自动建立系统的第一个进程：初始化进程。之后，所有的进程都由它以及它的子孙创建。因此，Linux系

6、统中的各个进程，相互之间构成了一个树型的进程族系。o8.1.2 Linux的进程调度的进程调度1.SCHED_FIFO实时进程的先进先出调度策略实时进程的先进先出调度策略 SCHED_FIFO是一种抢占式的调度策略。原则上，把CPU分给进程后，该进程就占用CPU直到释放为止。但若在此期间另有更高优先级的FIFO进程就绪，那就会把CPU抢夺过来。若有多个进程都有最高优先级，那就选择等待时间最长的投入运行。该调度策略适合实时进程，它们对时间性要求较强，每次运行所需的时间较短。SCHED_RR实时进程的轮转调度实时进程的轮转调度 SCHED_RR是一种抢占式的调度策略。分配给进程一个时间片后，若在此

7、期间有另一个更高优先级的RR进程就绪，那么就允许它抢夺过CPU投入运行。若有多个进程都具有最高优先级，那就选择其中等待时间最长的投入运行。可见，SCHED_RR调度策略适合于每次运行需要时间较长的实时进程。SCHED_OTHER非实时进程的轮转调度非实时进程的轮转调度 SCHED_OTHER是基于动态优先级的轮转调度策略，它适合于交互式的分时应用。在这种调度策略里，进程的动态优先级用所谓的优先数来表示：优先数越小，相应的优先级越高。操作系统对核心态进程和对用户态进程，采取不同的方法来改变其优先数，从而改变优先级。Linux的三种调度策略的三种调度策略.消息队列是进程间的一种异步通信方法。所谓“

8、异步”，即发送消息的进程在消息发出之后，不必等待接收进程做出反应，就可以去做其他的事情了。Linux为进程间的通信提供多种机制，如有消息队列、信号、信号量、管道以及共享内存储区等。信号用于一个进程向另一个进程发通知，有某个事件发生；信号量用于进程间取得同步；消息队列、管道、共享存储区，都用于在进程之间传递数据。处理各种等待时，Linux把等待队列和等待的事件联系在一起。需要等待事件的进程，根据等待的事件进入不同的等待队列。.2.Linux的等待队列的等待队列因某事件等待的队列头指针nexttasknexttaskNULLtask进程描述符进程描述符进程描述符o8.1.3 Linux进程间的通信

9、进程间的通信消息队列消息队列.在进程间通信前，先要建立消息队列。有了消息队列，进程就可以向（或从）消息队列发送（或接收）消息了。消息在消息队列里，按照到达的先后顺序排成队。类型相同的消息，先进入队列的先被接收。Linux对消息的长度没有限制。消息队列使用完毕后，应该予以释放（即删除）。进程都有自己的正文段，数据段，堆栈段等。Linux按这种逻辑单位，把虚拟空间划分成若干分区，然后进行分页。这样，进程每一个分区段位于一个连续的虚拟空间里，那里的内容有相同的特性，有利于对它们分别实行存储保护和共享。另外，虚拟空间在各个分区之间可以不连续。即进程所用的虚拟地址并不一定是连成一片的，可以有空洞存在。o

10、8.2.1 Linux的虚拟存储空间的虚拟存储空间1.Linux的虚拟存储空间的虚拟存储空间 在Linux中，虚拟地址用32个二进制位表示。这意味系统向每个进程提供的虚存空间，最多可以高达232 字节=4GB。8.2 Linux的存储管理的存储管理.Linux把4GB的虚拟空间划分为两部分：最高的1GB用于内核本身，称为“系统系统空间空间”，为所有的进程共享；较低的3GB供进程使用，称为“用户空间用户空间”。.进程A的用户空间(3GB)进程B的用户空间(3GB)进程N的用户空间(3GB)共享的系统空间(1GB)4GB的虚拟空间2.多级页表的地址变换多级页表的地址变换 Linux向用户提供的最大

11、虚拟空间为4GB。由于内存块长度是4KB，因此一个虚拟地址空间最多可有220(4GB/4KB=1M)个页面。即用户虚拟地址空间的页表，最多要用一百万个表项来记录页面与物理块的对应关系，不利于存储空间的利用。.Linux在对虚拟地址空间进行分页时，采用两级页表的机制：先是对虚拟地址空间进行分页，形成页表；再对页表进行分页，形成页表的页表。页面索引号p1页号p2位移量d32位虚拟地址：10位10位12位一个页面一个页面用户虚拟地址空间1M个页面1M个表项(1024个页面)1024个表项页表页表索引3.二级页表的地址转换过程二级页表的地址转换过程 在知道一个虚拟地址后，就可根据地址的前10位，先去查

12、页表索引，以便得到该索引所对应的页表放在哪一个内存块。.再由地址中间的10位，去查这个页表，得到该页所对应的内存块的起始地址。.最后，与位移量d相加后，就得到最终所需要的物理地址。p1p2d索引项页表索引p11页1页表项页表p2d内存物理地址1块1块 Linux进程的各个分区可以是不连续的，因此形成了若干个离散的虚拟区间。为了对它们加以管理，定义了vm_area_struct型及mm_struct型数据结构。o8.2.2 管理虚拟存储空间的数据结构管理虚拟存储空间的数据结构.vm_area_struct用于管理进程的每一个虚拟区间，mm_struct用于管理进程的整个虚拟空间、页表索引和页表。

13、因此，一个进程可以有多个vm_area_struct型数据结构，但只有一个mm_struct型数据结构。task_structmm*mmap*pgdmap_countmm_struct*vm_next*vm_startvm_endvm_area_struct*vm_next*vm_startvm_endvm_area_struct一段虚拟区间一段虚拟区间页表页表页表索引0000000000000000000000000000000000000574537113426762542451 为了记录内存各块的使用情况，Linux设置了位示图bitmap，其某位为1，表示对应块空闲；为0，表示对应块正

14、在使用。o8.2.3 管理内存空间的数据结构管理内存空间的数据结构 Linux存储管理中，内存块(长度为4KB)是进行存储分配和释放的单位。系统设置存储分块表mem_map，每一个表项是mem_map_t型结构，对应一个内存块，记录着该块的有关信息。Linux不用bitmap进行存储分配和释放，而是用“空闲区队列表”：free_area。在空闲区队列表里，Linux按照不同的方式，形成最多11个空闲区队列。.free_area的第1项，是由单个空闲块形成的双向链表；free_area的第2项，是由两个连续空闲块(形成一个空闲区)形成的双向链表 ；free_area的第3项，是由四个连续空闲块(

15、形成一个空闲区)形成的双向链表；如此等等。.111111111111111111111111111bitmapfree_area表空闲区队列表123 Linux采用所谓的“伙伴伙伴(Buddy)”算法，来进行内存区的分配和释放。当进程提出存储请求时，它将大于、等于这个数目的最小2n个内存块分配出去。比如要求3个内存块，就分配22=4块；要求16个内存块，就分配24=16块；如此等等。系统总是按进程所需连续存储块的数量，到空闲区队列表free_area中能够满足要求的最小空闲区队列里查找。若队列不空，就把第1个空闲区分配出去；若该队列为空，那么就继续查找下面的队列（其空闲区的尺寸为上一个队列的2

16、倍）。当它里面有空闲区时，就把该空闲区一分为二：一个分配给进程使用；余下的一半，排到它前面的空闲区队列中去。.o8.2.4 内存区的分配和页面淘汰策略内存区的分配和页面淘汰策略.存储释放时，将释放区域连接到相应尺寸的空闲区队列里去。不过，应考虑空闲区的合并，以便能够得到更大的空闲区。做法是若队列里有与所释放空闲区相邻接的空闲区，那么就把它们合并，然后排到该队列后面的空闲区队列里去。.发生缺页中断、要把所需页面调入内存，而内存又无空闲区域时，就要把已在内存的页面淘汰出去。Linux采用称为“时钟（clock）”的算法。该算法涉及mem_map的表项mem_map_t里面的age字段。每当内存块被

17、访问时，其age就加1。另外，Linux定时对所有内存块进行扫描，若它的age不为0，就对age减1。这样，在淘汰页面时，就把age取值最小的块里的页面作为淘汰的对象。o8.3.1 Linux文件系统的构成文件系统的构成.8.3 Linux的文件管理的文件管理 所谓“虚拟文件系统虚拟文件系统(VFS)”，即是通过软件的方法，隐去多种不同文件系统各自的实现细节，抽象出一组标准的有关文件操作的系统调用。把这样的系统调用提供给用户后，就可以使用统一的界面，去完成对各种不同文件系统中文件的操作。Linux有了虚拟文件系统，就可支持多种不同的文件系统了。这时的文件系统，可看成是由两级构成：上面是用户面对

18、的虚拟文件系统VFS，内核里则是不同的文件系统，如Minix、Ext2、MSDOS。这时VFS接收来自用户对文件操作的请求，通过系统调用，把那些抽象的功能转换成针对某文件系统的具体操作，然后加以完成。.Linux 的虚拟文件系统：VFSVFS提供的系统调用界面用户空间系统空间用户程序(进程)MinixExt2WSDOS 普通文件：即通常意义下的磁盘文件，存放着用户和系统的有关数据和程序。它们都被视为无结构、无记录概念的字符流，文件的长度可以动态增减。.o8.3.2 Ext2对磁盘的组织对磁盘的组织1.Ext2的文件类型的文件类型.目录文件：由文件目录项组成的文件。在Ext2中，为了加快对文件目

19、录的搜索速度，便于共享，把文件控制块分成两部分：一个为文件的“索引节点索引节点”(即文件控制块)，简记为inode，里面存放着文件的长度、类型和访问权限、文件在辅存的位置、共享信息等；另一个仍称为“文件目录项文件目录项”，它里面只含文件名和该文件索引节点的编号。.特别文件：Ext2里，把块存储设备(如磁盘)和字符设备(如键盘、打印机)等都视为文件，不过它们只有文件目录项和相应的索引节点inode，并不占用实际的物理存储块。因此，有时也称它们为设备文件。Linux目录项的组成：文件名inode编号2.Ext2对磁盘的组织对磁盘的组织.Ext2中，普通文件、目录文件以及每个文件的inode节点都存

20、储在磁盘上。它把磁盘分区或软盘视为一个文件卷，把其上相邻磁道的物理块称为“块组块组”。因此，一个文件卷上可有多个块组。在一个块组上，既可存放普通文件的信息，存放目录文件的信息，也可存放文件的inode节点，另外还存放有对块组的管理信息（比如该块组中块的尺寸，块的数目，哪些块是空闲的，哪些块是已分配的等）。索引节点位图：用来管理块组中的索引节点，占用一个盘块。位图中的某位为0，表示索引节点表中的相应节点为空闲；为1，表示表中的相应节点已分配给某个文件使用。索引节点位图中位的编号，就是那个文件相应的inode节点的编号。索引节点表：文件索引节点的集合，构成Ext2的索引节点表。因此块组中的索引节点

21、表，就是存放在该块组里的所有文件的文件控制块的集合。数据区：存放文件具体信息的地方，它占用了该块组中最多的盘块。Ext2块组的组织结构.引导块块组0块组i块组i 的放大块组n超级块组描述符盘块位图索引节点位图索引节点表数据区1块k 块1块1块m 块n 块(1)(2)(3)1010000000011111索引节点位图索引节点表一个索引节点一个索引节点一个索引节点16个索引节点(4)盘块位图 盘块位图用来管理块组中数据区里的盘块。在块组中，它占据一个盘块。位图中的某位为0，表示数据区中的相应盘块为空闲；为1，表示数据区中的相应盘块已经分配给某个文件使用。(5)组描述符 每个块组都有一个组描述符，用

22、于给出有关这个块组整体的管理信息。(6)超级块 每个具体的文件系统(如Minix、Ext2等)，都有自己的超级块，用来描述该文件系统的信息。因此，超级块是一个文件系统的核心。每个块组里虽然都有一个超级块，但通常只用块组0里的超级块，其他块组里的超级块只是作为备份而已。o8.3.3 Ext2文件的物理结构文件的物理结构 把文件存储到磁盘上时，Ext2采用索引式结构，即通过该文件inode节点里的数组i_block，建立起文件的逻辑块号与相应物理块号间的对应关系，形成文件存储的索引表。该数组有15个元素，每个元素为一个索引项。可以形成四种不同的索引类型：索引项 i_block0i_block11

23、共12个元素，直接给出文件数据存放的磁盘物理块号，是直接索引；索引项 i_block12 为一次间接索引；索引项 i_block13 为二次间接索引；索引项 i_block14 为三次间接索引。1.Ext2文件的多级索引结构文件的多级索引结构 2.Ext2文件的各种索引结构文件的各种索引结构i_block0i_block 物理块i_block1i_block2i_block3i_block4i_block5i_block6i_block7i_block8i_block9i_block10i_block11i_block12i_block13i_block1412块直接索引.小型索引结构i_bl

24、ock0i_block 物理块i_block1i_block2i_block3i_block4i_block5i_block6i_block7i_block8i_block9i_block10i_block11i_block12i_block13i_block1412块一次间接索引物理块一块一次间接索引块b/4块.中型索引结构i_block0i_block 物理块i_block1i_block2i_block3i_block4i_block5i_block6i_block7i_block8i_block9i_block10i_block11i_block12i_block13i_block14

25、12块二次间接索引物理块一块一次间接索引块b/4块.大型索引结构b/4块一次间接索引块二次间接索引块(b/4)*(b/4)块物理块o8.3.4 虚拟文件系统虚拟文件系统VFS的数据结构的数据结构1.Linux的虚拟文件系统的虚拟文件系统VFS Linux的VFS随系统的初启建立，随系统的关闭消逝。为了管理所有安装的文件系统，VFS通过使用描述整个VFS的一组数据结构，以及描述实际安装的文件系统的数据结构，来处理实际文件系统之间的差别，达到管理的目的。VFS向用户提供一个统一的文件系统界面，实现从抽象功能到具体操作的转换。2.超级块（超级块（super_block）VFS是通过超级块来描述和管理

26、文件系统的，每个已安装的文件系统，在VFS里都有一个相应的超级块存在。对于VFS的超级块来说，它由两部分组成：一是VFS为了管理一个文件系统所需要的信息，一是所管理的文件系统的超级块信息。3.索引节点（索引节点（inode）VFS中的每个文件(包括数据文件和目录文件等)，都有一个唯一的索引节点。VFS的索引节点由两部分组成：一是VFS为了管理一个文件所需要的信息，一是所管理的文件的索引节点信息。有了这些内容，再加上拼接过来的具体文件的索引节点信息，就形成了VFS对一个文件进行管理的索引节点。8.4 Linux的设备管理的设备管理o8.4.1 Linux设备管理概述设备管理概述Linux设备驱动

27、的分层结构设备驱动的分层结构1.进程设备file结构.设备驱动程序应用层文件系统层inode节点：设备文件设备驱动层物理设备层 Linux内核中，利用控制寄存器来控制硬设备完成输入/输出任务的软件，叫“设备驱动程序”，也称为“设备驱动器”。通过抽象，Linux的VFS向用户提供使用设备的统一接口（如打开open()，读read()，写write()等）。在用户发出输入/输出请求后，首先进入文件系统，然后才去到相应的设备驱动程序，在指定设备上完成所要求的输入/输出。因此，文件系统是用户与设备之间的接口：一个进程要使用设备，要经过文件系统，再由设备驱动程序去控制物理设备完成各种具体的操作。这是一种

28、层次结构：进程位于应用层，设备位于最底层，中间是文件系统层和设备驱动层。Linux的三类设备的三类设备2.字符设备（character device）字符设备以字符为存取单位。在文件系统里，字符设备有自己的inode节点（比如/dev/tty1，/dev/lp0等）。找到了字符设备的索引节点，就可以得到对应的设备驱动程序，实现对设备的访问。.块设备（block device）块设备以“块”为存取单位。通常，512字节或1024字节为一块。一般地，系统中块的尺寸为2n*512字节（n为正整数）。块设备也是通过其在文件系统里的节点而访问。这两种设备间的不同，只是体现在内部数据管理方式上，这些差异对

29、于用户来说是透明的。.网络设备（net device）网络是一种经网络接口与主机交换数据的设备，在内核网络子系统的驱动下，网络接口完成对数据包的发送和接收。由于这种数据传输的特殊性，无法把网络设备纳入到文件系统进行统一管理。因此，在Linux的文件系统里，没有与网络设备相对应的索引节点。.字符设备和块设备的文件名 文件名由两部分组成：主设备号，次设备号。“主设备号主设备号”代表设备的类型，用来确定需要哪一个设备驱动程序；“次设备号次设备号”代表同类设备中的序号，以便在相同设备间进行区分。在请求设备进行输入/输出时，必须指定主设备号和次设备号。o8.4.2 Linux对字符设备的管理对字符设备的

30、管理 在Linux中，打印机、终端等字符设备，都是以字符特别文件的形式，出现在用户的面前。用户对字符设备的读写，使用标准的系统调用进行操作。.device_struct结构 Linux为每个已初始化的设备建立一个device_struct结构，该结构由name(登记该设备的设备驱动程序名)和*fops(指向该特别文件的文件操作表，即file_operations结构)组成。由一个device_struct结构，可知该设备使用的是哪个设备驱动程序，可知对该设备可以做哪些操作。.chrdevs结构数组 它里面的每个元素，都是一个device_struct结构。从设备文件的 inode 节点，可以得

31、到设备的主设备号；以主设备号为索引查 chrdevs数组，可以得到该设备的device_struct结构；由该设备的device_struct结构，可以知道应执行什么驱动程序，以及对设备可以做哪些操作。lseek()read()write()readdir()select()open()release()file_operations结构i设备文件的inode节点主设备号：name*fopsname*fopsname*fopschrdevs0:chrdevsi:chrdevsn:一个device_struct结构chrdevs树组o8.4.3 Linux对块设备的管理对块设备的管理块设备管理的

32、数据结构块设备管理的数据结构 1.device_struct结构 Linux为每个已初始化的设备建立一个device_struct结构，该结构由登记该设备设备驱动程序名的name和指向该特别文件的文件操作表(block_device_operations结构)的指针*fops组成。由一个device_struct结构，可知该块设备使用的是哪个设备驱动程序，可知对该设备可做哪些操作。.blkdevs结构数组 它里面的元素，都是一个device_struct结构。从块设备文件的 inode 节点，可得到设备的主设备号；以主设备号为索引查 blkdevs数组，可得到设备的device_struct结

33、构；由该设备的device_struct结构，可以知道应执行什么驱动程序，以及对设备可以做哪些操作。对块设备输入对块设备输入/输出请求管理的数据结构输出请求管理的数据结构 2.缓冲区与buffer_head结构 为匹配块设备与内存间数据流动的速度，Linux在内存区开辟了缓冲池，并把缓冲池中的每个缓冲区分成两部分：一是真正用于存放数据的部分，称为“缓冲区缓冲区”；一是用于管理的部分，称为“缓冲区首部缓冲区首部”。缓冲区首部是buffer_head结构，它与缓冲区之间为一、一对应的关系。在组成请求队列时，只需buffer_head结构去排队。.request结构 对块设备的请求，由request

34、结构管理。由里面的next指针，把对某一块设备的所有请求链接成单链表；通过buffer_head，把相同操作的请求链接在一起。nextrequest结构bhtailbhbuffer_headnextrequest结构bhtailbh对某块设备相同操作的缓冲队列对块设备操作的请求队列.blk_dev_struct结构和blk_dev数组 对每个块设备请求队列，用blk_dev_struct结构指示，里面至少有一个指针request_queue，指向对某一个块设备的一个I/O请求队列。系统中所有的blk_dev_struct结构汇集在一起，组成一个名为blk_dev的数组，管理全部的blk_dev_struct结构。nextrequest结构bhtailbhbuffer_headrequest_queue另一个request队列一个blk_dev_struct结构request_queue一个blk_dev_struct结构blk_dev数组