精华内容
下载资源
问答
  • 成组链接法

    万次阅读 多人点赞 2016-06-18 12:25:58
    首先说一下,成组链接法出现的背景和意义,它的出现带来了什么好处。 成组链接法作为文件存储空间管理方法之一(主要是空闲盘区的管理),还有其他三种管理方法分别是:空闲表法、空闲链表法和位示图法,它克服了空闲...

    首先说一下,成组链接法出现的背景和意义,它的出现带来了什么好处。

    成组链接法作为文件存储空间管理方法之一(主要是空闲盘区的管理),还有其他三种管理方法分别是:空闲表法、空闲链表法和位示图法,它克服了空闲链表法表太长的缺点,但是保持了其优点,即分配和回收一个盘块比较简单。

    这么好的文件存储空间管理方法,我们当然要认真学咯。。

    首先来看文字解释:成组链接法是Unix系统中常见的管理空闲盘区的方法,它把空闲块分为若干组,每100个空闲块为一组,每组的第一个空闲块记录了空闲块总数和下一组物理空闲块的物理盘块号。理解这一点很重要。特别是对于看下面这张神图。


    这张图我得好好解释一下,首先来看左边绿色的空闲盘块号栈,这是第一组(唯一进入内存的一组,只有它会占据存储空间)。看到S.free = 100了没,这表示该组有100个空闲块数目,再往下看,第0号对应的是300,表示下一组物理空闲块的物理盘块号为300,你看它指向的是不是300号对应的磁盘块。再看黄色的块,这些块里保存的才是真正的可用的空闲块,也就是说每组中只有99个块可用。尽管如此,每组还是有100个块的。特别要注意的是,最后一组的下一组盘块号不是没有么,我们这里采用的是结束标记“0”,也就是最右边一个蓝色块的第二项为0。


    下面说一下,磁盘块分配和回收的过程。

    首先检查超级空闲盘块号(第一组)栈是否已上锁,(提示:这是临界资源),若已上锁则进程睡眠等待;否则,给空闲磁盘块号栈上锁后,将S.free减1,若S.free仍大于0,即第一组不止一个空闲盘块,则将s_free[s_nfree]中登记的空闲盘块分配出去;若S.free为0,即当前空闲盘块号栈中只剩下最后一个空闲盘块,必须先将该盘块的内容读入超级块的空闲盘块号栈中,然后再将该盘块分配出去。若s_nfree为0,而且栈底登记的盘块号为0,则表示系统中无空闲盘块可分配。


    磁盘回收过程:

    系统回收空闲盘块时,若第一组不满100块,则只需将回收块的块号填入超级块的空闲盘块号栈栈顶,并将其中的空闲盘块数加1;若第一组已有100块,则必须先将超级块中的空闲盘块数和空闲盘块号写入回收块中,然后将盘块数1和回收块号记入超级块中。


    记住一点的是,分配过程是从前往后分配,先分配第一组,然后分配第二组……

    回收过程是正好相反,从后往前分配,先将释放的空闲块放入第一组,第一组满了,再开辟一组,之前的第一组变为第二组……


    展开全文
  • 实例讲解成组链接法

    万次阅读 多人点赞 2017-06-22 11:20:43
    成组链接法是一种用来记录磁盘空闲盘块的方法,它使得磁盘盘块的分配和回收都变得十分简单,而且没有空闲表法和空闲链表法它们的表太长的缺点,因此被引用到UNIX系统当中。 成组链接法介绍计算机上的文件是记录在...

    成组链接法是一种用来记录磁盘空闲盘块的方法,它使得磁盘盘块的分配和回收都变得十分简单,而且没有空闲表法和空闲链表法它们的表太长的缺点,因此被引用到UNIX系统当中。

    成组链接法介绍

    计算机上的文件是记录在磁盘上的,而磁盘空间的分配是以盘块为单位的,那么如何管理磁盘中已经被使用的块和未被使用的块是操作系统必须要考虑的问题。下面将介绍比较实用又有点复杂的成组链接法,看它是如何把磁盘中所有的空闲盘块都记录起来,又不耗费太多的内存空间。
    请看下图:
    这里写图片描述

    下面的文字来自汤氏的操作系统教材:

    1、空闲盘块的组织

    (1)空闲盘块号栈:用来存放当前可用的一组空闲盘块的盘块号(最多含100 个号),以及栈中尚有的空闲盘块号数N。顺便指出,N 还兼作栈顶指针用。例如,当N=100 时,它指向S.free(99)。由于栈是临界资源,每次只允许一个进程去访问,故系统为栈设置了一把锁。(只有这个是放在内存中的,其它是在磁盘上。)
    (2) 文件区中的所有空闲盘块被分成若干个组,比如,将每100 个盘块作为一组。假定盘上共有10 000 个盘块,每块大小为1 KB,其中第201~7999 号盘块用于存放文件,即作为文件区,这样,该区的最末一组盘块号应为7901~7999;次末组为7801~7900……;第二组的盘块号为301~400;第一组为201~300,如上图右部所示。
    (3) 将每一组含有的盘块总数N 和该组所有的盘块号记入其前一组的第一个盘块的
    S.free(0)~S.free(99)中。这样,由各组的第一个盘块可链成一条链。
    (4) 将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中,作为当前可供分配的空闲盘块号。
    (5) 最末一组只有99 个盘块,其盘块号分别记入其前一组的S.free(1) ~S.free(99)中,而在S.free(0)中则存放“0”,作为空闲盘块链的结束标志。(注:最后一组的盘块数应为99,不应是100,因为这是指可供使用的空闲盘块,其编号应为(1~99),0号中放空闲盘块链的结尾标志。)

    2、空闲盘块的分配与回收

    当系统要为用户分配文件所需的盘块时,须调用盘块分配过程来完成。该过程首先检查空闲盘块号栈是否上锁,如未上锁,便从栈顶取出一空闲盘块号,将与之对应的盘块分配给用户,然后将栈顶指针下移一格。若该盘块号已是栈底,即S.free(0),这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号,因此,须调用磁盘读过程,将栈底盘块号所对应盘块的内容读入栈中,作为新的盘块号栈的内容,并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。然后,再分配一相应的缓冲区(作为该盘块的缓冲区)。最后,把栈中的空闲盘块数减1 并返回。
    在系统回收空闲盘块时,须调用盘块回收过程进行回收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部,并执行空闲盘块数加1 操作。当栈中空闲盘块号数目已达100 时,表示栈已满,便将现有栈中的100个盘块号记入新回收的盘块中,再将其盘块号作为新栈底。

    实例讲解成组链接法

    如果对上面的讲解感到迷惑的话,请看下面的例子,这是一个很经典的练习题:
    例题.某个系统采用成组链接法来管理磁盘的空闲空间,目前磁盘的状态如图1所示。

    (1) 该磁盘中目前还有多少个空闲盘块?

    (2) 请简述磁盘块的分配过程。

    (3) 在为某个文件分配3个盘块后,系统要删除另一文件,并回收它所占的5个盘块,它们的盘块号依次为700、711、703、788、701,请画出回收后的盘块链接情况。
    图一

                                    图1:当前磁盘状态
    

    解答:
    (1):301;首先看空闲盘块号栈,此时N=2,表示有两个空闲盘块299、300,而盘块300号上面又写着有100个空闲盘块:301-400,它还有下一个链接的盘块400;在盘块400中,记录有100个空闲盘块401-500;然后又链接到500号盘块,在500号盘块中,虽然N=100,但是第一个是0,它表示空闲盘块链的结尾。因此,总共的空闲盘块有:299、300、301-400、401-500、501-599;即301个空闲盘块。
    (2):参考介绍部分。
    (3):这个是最重要的部分,也是理解整个成组链接法的关键部分,我看很多博客都没有详细写明分配和回收的过程,因此这也正是我写这篇博客的原因。
    步骤1、分配三个空闲盘块:
    分配的过程是这样的,首先看空闲盘块号栈,发现N=2,那么到达栈顶即S.free[2-1]=299,即把299号盘块分配出去了,这时磁盘状态如下:
    这里写图片描述

    然后分配第二个盘块,这时N=1,如果再分配就会变成空栈了,因为S.free[N-1]=S.free[0]!=0,所以需要将300号盘块的内容拷贝到空闲盘块号栈,并分配300号盘块(如果S.free[0]=0,则表示没有空闲盘块,将会阻塞进程):
    这里写图片描述
    接下来分配301号盘块你也会做啦:
    这里写图片描述

    回收700、711、703、788、701号盘块:
    回收的过程也是从栈顶开始的,首先看N=99,然后回收700,会将700放在S.free[N]的位置,然后将N加1变成100:
    这里写图片描述
    然后回收711号盘块,因为此时空闲栈的N=100,已经满了,如果再回收,需要将空闲盘块栈的内容移动到711号盘块上,然后将空闲盘块栈的S.free[0]设置为711,N设置为1:
    这里写图片描述
    最后回收703/788/701也是同理:
    这里写图片描述

    相信经过这样的举例说明以后,大家都对成组链接法比较了解了吧~

    展开全文
  • 成组链接法 恩赐解脱

    千次阅读 2015-03-24 18:53:42
    成组链接法

    成组链接法  即空闲表和空闲链里两种方法相结合。


    将空闲块按100块为一组进行组织,利用空闲块每组的第0块来存放前一组的100块的地址,所以第0块既是可以分配的空闲块,同时也充当了数据结构。

    具体来说,每100块分为一组(第一组为99块,这里的是s_free[0]是用来标识空闲盘块链的链尾标志,即表示下面已经没有索引表登记空闲块了)


    s_nfree表示这个表中有多少空闲块,s_free表示这个表中的第几块空闲块

    1.png

    每一组相当于一个栈,s_free[0]相当于栈底,s_free[99]相当于栈顶,在一个组存放到100之后,就开一个新组来存放,新组的栈底就是上一组的栈顶,这样就可以把这些组给连接起来,组间是链,组内是表。


    分配时,先分配栈顶的空闲块,直到s_free[0]内的值为0,说明已经到了空闲盘块链尾,没有盘块可以分配了,这是分配程序就将错误信息打印出来,并返回一个NULL给调用者,相当于出栈。


    回收时,把回收的空闲块放入栈顶,如果前一个栈已经放满,就再在这组之后开一个新组,放入新组栈顶,并置s_nfree:为1;如果前一个栈未放满,就填入原组表中第一个 占用的项,相当于压栈。


    这种后进先出的栈式管理和成组链接方法加快了磁盘的分配和释放的速度,减少了系统的时空开销,提高系统效率。

    展开全文
  • 成组链接法详解+Java代码

    千次阅读 2018-06-27 01:37:21
    成组链接法介绍 在UNIX系统中,将空闲块分成若干组,每100个空闲块为一组,每组的第一空闲块登记了下一组空闲块的物理盘块号和空闲块总数。 在UNIX系统中,将空闲块分成若干组,每100个空闲块为一组,每组的第一...

    一.成组链接法介绍

           在UNIX系统中,将空闲块分成若干组,每100个空闲块为一组,每组的第一空闲块登记了下一组空闲块的物理盘块号和空闲块总数。

     

    在UNIX系统中,将空闲块分成若干组,每100个空闲块为一组,每组的第一空闲块登记了下一组空闲块的物理盘块号和空闲块总数。如果一个组的第二个空闲块号等于0,则有特殊的含义,意味着该组是最后一组,即无下一个空闲块。

    分配空闲块的时候,从前往后分配,先从第一组开始分配,第一组空闲的100块分完了,才进入第二组。

    释放空闲块的时候正好相反,从后往前分配,先将释放的空闲块放到第一组,第一组满了,在第一组前再开辟一组,之前的第一组变成第二组。

    二.详细讲解分配过程

        首先我们来看一个图,这里我们假设系统具有7个盘块,每组3块,最左边的0解释代表第一块。

     

    2.1.模拟

    首先看空闲盘块号栈,也就是第一组的第一块,数字为3,表示有三个空闲盘块,之后它有一个指针指向了1号连接盘块,是是因为它的第一块空闲盘块块号为1,再接着看1号连接盘块指向了4号连接盘块,是因为它的第一块盘号为4,以此类推。

    2.2.空闲块的分配

    到达栈顶,块号为3,我们可以先把3分配出去,接下来我们可以继续把2号给分配出去,如下图

        分配完之后,我们发现这时空闲盘块号栈只剩一块了,如果再想分配就会变成空栈了。没有空闲盘块,进程就会阻塞。所以,需要把1号盘块号链的内容拷贝到空闲盘块号栈,然后再分配1号空闲盘块,如下图:

    2.3.对应的java代码实现逻辑如下:

    //分配空闲块
    public static void allocate() {
        //空闲块数,分配的盘块号
        int freeNum, allocativeNum;
        //当前组盘块大于1块
        if (groups[0][0] > 1) {
            freeNum = groups[0][0];
            allocativeNum = groups[0][freeNum];
            groups[0][0]--;
            freeList.remove((Integer) allocativeNum);
            System.out.println("分配的块号为:" + allocativeNum);
    
        }
        //只剩一个空闲块
        else if (groups[0][0] == 1) {
            //不是链尾,还有其它空闲块组
            if (groups[0][1] != 0) {
                allocativeNum = groups[0][1];
                for (int j = 0; j < groups[allocativeNum].length; j++)
                    //当前组已经分配完,下一组拷贝到当前组
                    groups[0][j] = groups[allocativeNum][j];
                //groups[0][0]--;
                freeList.remove((Integer) allocativeNum);
                System.out.println("分配的块号为:" + allocativeNum);
    
            } else {
                System.out.println("已经没有空闲块了");
                return;
            }
        }
        //当前组已经分配完
        else {
            System.out.println("当前组已经分配完了");
        }
        display();
    }

    1.首先判断空闲盘块号栈的盘块是否大于1块,如果是,就得到它的块数,然后把最后一块给分配出去,然后块数减1。

    2.如果只剩一个空闲块了呢,首先还得判断它的第一个数是否为0,因为0代表最后一组,表示已经没有空闲盘块号了;否则,把下一组的内容拷贝到空闲盘块号栈,如果allocativeNum是1的话,对应二维数组的第一行,也就是上面的1号盘块号链。

    3.若果空闲盘块号都不满足以上条件,表示为0,已经分配完了。

     

    2.4.空闲盘块的回收

    1.首先我们回收刚才分配的3号盘块,但是我们发现空闲盘块已经满了,如果想回收3号,我们需要将空闲盘块的内容移动到3号盘块号链上,然后空闲盘块号链的指针指向3号空闲盘块号链,如图:

    2.其他盘块的回收同理:

    2.5.下面是java代码的模拟实现:

    //回收空闲块
    public static void recycling() {
        int freeNum;
        System.out.println("请输入你想回收的空闲盘块的盘块号:");
        int recyclingNum = scanner.nextInt();
        for (int i = 0; i < freeList.size(); i++) {
            if (freeList.get(i) == recyclingNum) {
                System.out.println("该空闲块已经存在");
                return;
            }
        }
        //当前组不满3块
        if (groups[0][0] < 3) {
            freeNum = groups[0][0];
            groups[0][freeNum++] = recyclingNum;
            freeList.add(recyclingNum);
            groups[0][0]++;
        } else {
            for (int j = 0; j <= 3; j++)
                groups[recyclingNum][j] = groups[0][j];
            groups[0][0] = 1;
            groups[0][1] = recyclingNum;
            freeList.add(recyclingNum);
        }
        display();
    }

     

    1.首先我们是数据要回收的盘块号,然后判断是否存在。

     

    2.如果当前组不满3块,我们就得到盘块的数目,然后把盘块添加到栈顶,盘块数加1.

    3.如果当前组等于3块,我们需要把空闲盘块号栈的内容复制到盘块号链号为当前回收的盘块号的盘块号链上,如果我们回收的是3号,我们就需要把空闲盘块号栈复制到3号盘块号链上,然后空闲盘块的盘块号数目赋值为1,第一个盘块为我们刚才回收的盘块。

    2.6.下面的代码是显示出当前的空闲盘块

    public static void display() {
        //空闲盘块数
        int freeNum, temp, groupNum = 1;
        //空闲盘块号链没有结尾,后面还有很多组
        if (groups[0][1] != 0) {
            freeNum = groups[0][0];
            System.out.println("第一组盘块:");
            //输出第一组空闲盘块
            for (int j = 1; j <= freeNum; j++) {
                System.out.print(groups[0][j] + " ");
            }
            System.out.println();
            //下一组盘块
            temp = groups[0][1];
            //盘块组数
            groupNum++;
            //当空闲盘块号链没有结束
            while (groups[temp][1] != 0) {
                System.out.println("第" + groupNum + "组盘块:");
                freeNum = groups[temp][0];
                for (int j = 1; j <= freeNum; j++) {
                    System.out.print(groups[temp][j] + " ");
                }
                System.out.println();
                groupNum++;
                //s.free判断是否为末尾
                temp = groups[temp][1];
            }
            //退出后表示S.free为0,为盘块号链的结束
            System.out.println("第" + groupNum + "组盘块,也是最后一组:");
            freeNum = groups[temp][0];
            //1号为0,所以这次从2开始
            for (int j = 2; j <= freeNum; j++) {
                System.out.print(groups[temp][j] + " ");
            }
            System.out.println();
    
        }
        //表示空闲盘块链只有一组,1为0
        else {
            freeNum = groups[0][0];
            //1表示只有0
            if (freeNum == 1) {
                System.out.println("空闲盘块已经全部被分配:");
            } else {
                System.out.println("第一组盘块为:");
                for (int j = 2; j <= freeNum; j++) {
                    System.out.print(groups[0][j] + " ");
                }
                System.out.println();
            }
        }
    }

     

    1.首先判断空闲盘块号栈的第一个数是否为0,判断是否为最后一条链,如果是,进入第二步,否则,进入第三步

    2.判断空闲盘块数是否为0,也就是第一个数如果为1,表示只有代表结束标识的0,表示没有盘块,若非,从第一个位置开始,输出所有的空闲盘块。

    3.得到空闲盘块号栈的盘块数,输出空闲盘块号栈的盘块号。

    3.1.然后把空闲盘块号栈的第一个数赋值给一个临时变量,接着输出其他组的内容。

    3.2.我们用一个while循环来判断,如果每一条链中的第一个数不是0,代表不是最后一条链,就需要继续输出其他组的空闲块号。

    3.3.步骤基本如下:得到临时变量temp的块数,输出所有块号,然后把输出完的哪一组的第一个数赋值给临时变量判断是否为最后一组,是的话退出。

    3.4.最后输出最后一组,第一个位置为0,从第二个位置开始输出。

    2.7.程序运行

           

     

    三.这是完整代码的连接,需要的朋友请下载

    https://download.csdn.net/download/sirius_hly/10860602

    展开全文
  • 成组链接法习题

    千次阅读 2018-05-22 17:26:19
    操作系统】成组链接法刚刚学习完文件管理这一章的内容,这道题用来练习和理解成组链接法还是很合适的。例题.某个系统采用成组链接法来管理磁盘的空闲空间,目前磁盘的状态如图1所示。 (1) 该磁盘中目前还有多少...
  • 文件存储空间的管理:成组链接法

    千次阅读 2017-04-29 15:20:49
    成组链接法是Unix系统中常见的管理空闲盘区的方法。   在UNIX系统中,将空闲块分成若干组,每100个空闲块为一组,每组的第一空闲块登记了下一组空闲块的物理盘块号和空闲块总数。如果一个组的第二个空闲块号等于0...
  • 【操作系统】成组链接法详解

    千次阅读 多人点赞 2019-12-22 17:48:40
    成组链接法介绍 计算机上的文件是记录在磁盘上的,而磁盘空间的分配是以盘块为单位的,那么如何管理磁盘中已经被使用的块和未被使用的块是操作系统必须要考虑的问题。下面将介绍比较实用又有点复杂的成组链接法,看...
  • 文件系统——空闲块成组链接法的模拟 (1)设计合适的数据结构模拟磁盘空闲块的情况。 (2)模拟分配空闲块的过程。 (3)模拟回收空闲块的过程。 (4)模拟对所有空闲块进行分析、凑连续块 的维护过程。 思路 构造...
  • 操作系统 | 成组链接法练习题

    万次阅读 多人点赞 2017-05-08 23:51:04
    【操作系统】成组链接法 刚刚学习完文件管理这一章的内容,这道题用来练习和理解成组链接法还是很合适的。   例题.某个系统采用成组链接法来管理磁盘的空闲空间,目前磁盘的状态如图1所示。  (1) 该磁盘中...
  • 文件系统——空闲块成组链接法的模拟 文章目录文件系统——空闲块成组链接法的模拟内容思路代码 内容 设计合适的数据结构模拟磁盘空闲块的情况。 (操作系统第二版 孟庆昌 5.4下的第4点) 模拟分配空闲...
  • 操作系统原理之成组链接法

    万次阅读 2016-04-03 18:24:31
    成组链接法是UNIX/Linux等大型文件系统采用的文件空间管理方法。在UNIX/Linux系统中,将空闲块分成若干组,每100个空闲块为一组,每组的第一个空闲块登记了下一组空闲块的物理盘块号和空闲块总数。如果一组的第一个...
  • 操作系统 ---成组链接法(盘块的分配和回收)

    万次阅读 多人点赞 2019-01-07 12:56:11
    成组链接法介绍 计算机上的文件是记录在磁盘上的,而磁盘空间的分配是以盘块为单位的,那么如何管理磁盘中已经被使用的块和未被使用的块是操作系统必须要考虑的问题。下面将介绍比较实用又有点复杂的成组链接法,看...
  • 成组链接法 0.思维导图 1.存储空间的划分与初始化 2.空闲表法 如何分配? 如何回收? 3.空闲链表法 空闲盘块链 空闲盘区链 4.位示图法 如何分配与回收? 5.成组链接法 超级块的作用 如何分配? 需要...
  • 4、文件存储空间管理思维导图文件的初始化和划分文件存储空间管理方法1、存储空间管理——空闲表法2、存储空间管理——空闲链表法3、存储空间管理——位示图法4、存储空间管理——成组链接法 思维导图 文件的初始化...
  • 操作系统------成组链接法

    千次阅读 2019-03-16 12:00:19
    参考博客:https://blog.csdn.net/ajay666/article/details/73569654
  • <br /> <br />在UNIX系统中,将空闲块分成若干,每100个空闲块为一,每的第一空闲块登记了下一空闲块的物理盘块号和空闲块总数。如果一个的第一个空闲块号等于0,则有特殊的含义,意味着该是...
  • 文章目录三元顺序表行逻辑链接的顺序表十字链表 三元顺序表   稀疏矩阵由于其自身的稀疏特性,通过压缩可以大大节省稀疏矩阵的内存代价。具体操作是:将非零元素所在的行、列以及它的值构成一个三元(i,j...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 145,461
精华内容 58,184
关键字:

成组链接法