《操作系统课件.ppt》由会员分享，可在线阅读，更多相关《操作系统课件.ppt（54页珍藏版）》请在第壹文秘上搜索。
1、 1. 数据结构：数据结构：序号序号第一空闲盘块号第一空闲盘块号空闲盘块数空闲盘块数124293315504 2. 分配与回收：分配与回收： 连续分配方式连续分配方式 (1)空闲盘块链空闲盘块链 6 5 7 8 10 300 310 5 6 7 8299300310特点：特点： 分配、回收简单；分配、回收简单； 但分配回收时需要大量的但分配回收时需要大量的I/O操作，效率低操作，效率低 。 (2)空闲盘区链空闲盘区链 分区序号、起始块号、分区序号、起始块号、盘块数等盘块数等 1.位示图概念位示图概念每一位每一位 01磁盘块磁盘块 空闲空闲已分配出去已分配出去0 1 2 3 4 5 6 7 8
2、9 10 11 12 13 14 15 012341 1 0 0 0 1 1 1 1 0 0 1 0 1 1 11 1 1 1 1 1 0 0 1 1 0 0 0 0 1 11 1 0 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 0 1 1 1 1 0 1 1 1 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0. (1) 顺序扫描位示图，从中找出一个或一组其值为顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位的二进制位(“0”表示空闲时表示空闲时)。 (2) 将所找到的一个或一组二进制位，将所找到的一个或一组二进制位， 转换成与之相应转换
3、成与之相应的盘块号。假定找到的其值为的盘块号。假定找到的其值为“0”的二进制位，位于位示的二进制位，位于位示的第的第i行、第行、第j列，如果行号、列号、块号都从列，如果行号、列号、块号都从0开始编号，开始编号，则其相应的盘块号应按下式计算：则其相应的盘块号应按下式计算： b=ni+j式中，式中， n代表每行的位数。代表每行的位数。 (3) 修改位示图，修改位示图， 令令mapi,j=1。 2.盘块的分配盘块的分配 3.盘块的回收盘块的回收 (1) 将回收盘块的盘块号将回收盘块的盘块号b转换成位示图中的行号转换成位示图中的行号i和列和列号号j。 转换公式为：转换公式为： i=b DIV n j=
4、b MOD n(2) 修改位示图。修改位示图。 令令map i,j=0。 如果行号、列号、块号都从如果行号、列号、块号都从1开始，则：开始，则：b=n(i-1)+ji=(b-1)DIV n+1j=(b-1)MOD n+11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 123451 1 0 0 0 1 1 1 1 0 0 1 0 1 1 11 1 1 1 1 1 0 0 1 1 0 0 0 0 1 11 1 0 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 0 1 1 1 1 0 1 1 1 10 0 0 0 0 0 0 0 0 0 0
5、0 0 0 0 0.4.特点特点 位示图位示图常用于微型机和小型机中。它的特点：常用于微型机和小型机中。它的特点： 找空闲块容易；找空闲块容易； 磁盘容量不大时，位示图很小，可事先读入内存，磁盘容量不大时，位示图很小，可事先读入内存，从而加快分配、回收的速度。从而加快分配、回收的速度。 例子：例子：MINIX（分配单位叫区段，类似于（分配单位叫区段，类似于FAT的簇）的簇） i-结点区结点区1个磁盘块个磁盘块i结点位示图结点位示图 区段位示图区段位示图数据区数据区 0# 1#引导块引导块 超级块超级块MINIX文件卷布局文件卷布局5.位示图的一种变形位示图的一种变形 采用采用FAT的文件系统：
6、的文件系统： 一个一个FAT表项表项 0其他其他磁盘数据区的一簇磁盘数据区的一簇 空闲空闲已分配出去、坏簇已分配出去、坏簇或保留簇或保留簇根目录区根目录区FAT文件卷布局文件卷布局数据区数据区1个扇区个扇区FAT1 FAT2 0# 引导块引导块FAT32(1)将所有的空闲盘块分成若干组：将所有的空闲盘块分成若干组： 最后最后1组组99块；块； 其余每组其余每组100块；块； 剩余的、不超过剩余的、不超过100块的盘块成为第块的盘块成为第1组。组。(2)将各组空闲盘块链起来：将各组空闲盘块链起来： 把后一组的盘块数和各个盘块的块号记入前一组的最把后一组的盘块数和各个盘块的块号记入前一组的最后一个
7、盘块中；后一个盘块中； 最后一组最后一组99块，加上结束标记块，加上结束标记“0”，仍记作，仍记作100块；块； 第一组的块数和各个盘块的块号则记录到超级块的空第一组的块数和各个盘块的块号则记录到超级块的空闲盘块号栈中。闲盘块号栈中。1. 空闲盘块的组织空闲盘块的组织 （如：（如：UNIX）引导块引导块超级块超级块索引结点区索引结点区数据区数据区对换区对换区 0 1 2 200 201 7999 8000999978017802789979003013023994002012022993007901790279997701770277997800引导块引导块超级块超级块索引结点区索引结点区数据
8、区数据区对换区对换区 0 1 2 200 201 7999 8000999910007999790279017801780278997900301302399400201202299300790179027999 07701770277997800s_nfrees_free0s_free1s_free98s_free99100300299202201超级块超级块1007900789978027801100500499402401100400399302301空闲盘空闲盘块号栈块号栈引导块引导块超级块超级块索引结点区索引结点区数据区数据区对换区对换区 0 1 2 200 201 7999 800
9、09999超级块超级块 超级块也叫做卷资源表，用来记录整个文件卷的资源及超级块也叫做卷资源表，用来记录整个文件卷的资源及使用情况。使用情况。 超级块中的内容主要有：超级块中的内容主要有： 索引节点区占用的盘块数；索引节点区占用的盘块数；整个文件卷的总块数；整个文件卷的总块数；磁盘块的大小；磁盘块的大小；用来登记空闲磁盘块的空闲盘块号栈用来登记空闲磁盘块的空闲盘块号栈 及及 锁标志；锁标志；用来登记空闲磁盘用来登记空闲磁盘i结点的空闲结点的空闲i结点栈结点栈 及及 锁标志；锁标志； 只读标记只读标记 等信息。等信息。 当某个文件卷被安装到整个文件系统的目录树上时，其当某个文件卷被安装到整个文件系
10、统的目录树上时，其超级块便被读入内存超级块表中。超级块便被读入内存超级块表中。2.空闲盘块的分配空闲盘块的分配 s_frees_nfree 0?将将bno号盘块的内容读到号盘块的内容读到超级块的空闲盘块号栈中超级块的空闲盘块号栈中返回返回YN将将s_nfree置置0；置错误标记为：无空闲块置错误标记为：无空闲块s_nfree0?NY（系统已无空闲盘块）（系统已无空闲盘块）将将s_nfree减减1；bno= s_frees_nfree; s_nfree0?Y遇到结束遇到结束标记标记已是第一组已是第一组的最后一块的最后一块N将将bno号盘块分配给进程号盘块分配给进程1000799979027901
11、7801780278997900301302399400201202299300790179027999 07701770277997800s_nfrees_free0s_free1s_free98s_free99100300299202201超级块超级块1007900789978027801100500499402401100400399302301引导块引导块超级块超级块索引结点区索引结点区数据区数据区磁盘磁盘内存内存安装文件卷时安装文件卷时9998情况情况1：第一组超过一块：第一组超过一块10040039930230110007999790279017801780278997900301
12、302399400300790179027999 07701770277997800s_nfrees_free0s_free1s_free98s_free99超级块超级块1007900789978027801100500499402401100400399302301磁盘磁盘内存内存13002992022010情况情况2：第一组只有一块且不是结束标记：第一组只有一块且不是结束标记10040039930230110007999790279017801780278997900301302399400790179027999 07701770277997800s_nfrees_free0s_free
13、1s_free98s_free99超级块超级块1007900789978027801100500499402401磁盘磁盘内存内存情况情况2：第一组只有一块且不是结束标记：第一组只有一块且不是结束标记 0s_nfrees_free0s_free1s_free98s_free9910超级块超级块s_nfrees_free0s_free1s_free98s_free9900情况情况3：第一组只有一块但是结束标记：第一组只有一块但是结束标记3.空闲盘块的回收空闲盘块的回收 返回返回N将将s_nfree置为置为1；将结束标记将结束标记0登记到登记到 s_free0中中;s_nfree0?NY（回收前已
14、无空闲盘块）（回收前已无空闲盘块）Y第一组没第一组没满满100块块第一组已满第一组已满100块块s_nfree100?将超级块的空闲盘块号栈内容将超级块的空闲盘块号栈内容写到写到bno号盘块上号盘块上;再将再将s_nfree清清0；块号块号bno登记到登记到 s_frees_nfree中；中；将将s_nfree加加1;设回收块块号为设回收块块号为bno超级块超级块s_nfrees_free0s_free1s_free98s_free990情况情况1：系统已没有空闲盘块：系统已没有空闲盘块超级块超级块s_nfrees_free0s_free1s_free98s_free9910回收回收156#块
15、块s_nfrees_free0s_free1s_free98s_free99101562超级块超级块156 0 0情况情况2：第一组还没满：第一组还没满100块块s_nfrees_free0s_free1s_free2s_free98s_free992超级块超级块156 0回收回收156#块块回收回收329#块块101563293293超级块超级块s_nfrees_free0s_free1 s_free98s_free9910001567991001情况情况3：第一组已满：第一组已满100块块156 0回收回收666#块块7991001 66610001567991001超级块超级块s_nfr
16、ees_free0s_free1 s_free98s_free9910001567991001156 0799100106661 空闲块的登记基本不占用额外的空间。空闲块的登记基本不占用额外的空间。 绝大部分的分配和回收工作都在内存中进行，效率高。绝大部分的分配和回收工作都在内存中进行，效率高。 超级块用栈方式管理，空闲盘块数即栈顶指针，便于超级块用栈方式管理，空闲盘块数即栈顶指针，便于分配和回收。分配和回收。分配和回收过程中，空闲盘块号栈是临界资源，多个分配和回收过程中，空闲盘块号栈是临界资源，多个进程对它的访问必须互斥地进行，因此在超级块中还进程对它的访问必须互斥地进行，因此在超级块中还设置了空闲盘块号栈的锁标志。设置了空闲盘块号栈的锁标志。4.特点特点 1、在、在UNIX系统中有空闲盘系统中有空闲盘块栈如图所示：块栈如图所示：(1) 现有一个进程要释现有一个进程要释放放4个物理块，其块个物理块，其块号为号为150、156、172、177，画出，画出空闲盘块栈的变化。空闲盘块栈的变化。(2) 在（在（1）的基础上假）的基础上假定一个进程要求分配定一个进程要求分配5个空闲块，画出分个
