考研 408 · 进程同步与文件系统

这张图讲什么

「考研 408 · 进程同步与文件系统」是 SeekFlaw 编辑团队整理的思维导图,分 6 个一级分支:PV 操作大题的解题步骤;六个常见同步模型的 PV 写法;互斥算法分析:看代码判断违反哪条准则;文件目录、索引结点与文件共享;文件分配方式:最大长度与读盘次数;位示图、磁盘访问时间与磁盘调度,共 51 个节点、50 张记忆卡。

这张图面向考研 408 操作系统的 PV 操作和文件系统计算两类题型。共六块:PV 大题的解题步骤与自查;六个常见同步模型的写法(水果盘、读写公平、理发师、数量差、前驱图、单行桥);从代码分析互斥算法违反哪条准则;目录、索引结点与文件共享;连续、链接、索引分配下的最大文件长度和读盘次数;位示图、磁盘访问时间与磁盘调度。

5 个要点

  • PV 操作大题的解题步骤:PV 大题按「数进程、找关系、设信号量、写动作、做检查」五步走。
  • 六个常见同步模型的 PV 写法:生产者消费者之外,大题常见的变形有:多类生产者和消费者、读写公平、有限等候位、数量差限制、前驱关系、同向共享异向互斥。
  • 互斥算法分析:看代码判断违反哪条准则——选择题常给一段进入区和退出区的代码,问它能否实现互斥、会不会饥饿。
  • 文件目录、索引结点与文件共享:这一枝的计算围绕目录项多大、查一个文件要读几次盘。
  • 文件分配方式:最大长度与读盘次数——计算题的两个核心量: 每个盘块能放多少个地址项 (盘块大小除以地址项长度),以及访问一个逻辑块要先读多少个索引块或前驱块。

适用:考研备考。用法:点开任一节点先自己答,再翻面核对。

发布于

一句话:这张图把「考研 408 · 进程同步与文件系统」整理成 51 个节点、50 张记忆卡;点开节点翻面就能看答案。

从考研大题角度讲 PV 操作的解题步骤和常见模型、互斥算法分析,以及文件目录、索引分配、位示图、磁盘调度的计算,配自编算例。点开任一节点翻面看答案,登录后可存进自己的空间,按遗忘曲线复习。

SeekFlaw 求瑕是面向初中、高中、考研、考公考前速记的思维导图与记忆卡平台:把课件、讲义变成思维导图,节点翻面就是记忆卡,按遗忘曲线安排复习。

51 个节点 · 50 张记忆卡。作者:SeekFlaw 编辑团队;发布于 2026-11-18。

先看这 3 条

  1. PV 操作大题的解题步骤是什么:分五步:① 数进程 ,找出有几类并发进程、各自重复做什么动作;②找关系,哪些动作不能同时做(互斥),哪些有先后或数量上的制约(同步);③设信号量,每个制约关系设一个,写明含义和初…
  2. 单标志法为什么违反空闲让进:单标志法用变量 turn 表示轮到谁进入。
  3. 位示图里盘块号与字号、位号怎么换算:设每个字有 n 位。

PV 操作大题的解题步骤

  • PV 操作大题的解题步骤是什么:分五步:① 数进程 ,找出有几类并发进程、各自重复做什么动作;②找关系,哪些动作不能同时做(互斥),哪些有先后或数量上的制约(同步);③设信号量,每个制约关系设一个,写明含义和初值;④写出每类进程的动作序列,在动作前后插入 P、V;⑤检查…
  • PV 题里同步信号量的初值怎么定:初值等于开始时刻这种资源或条件 已经具备的数量 。 例 缓冲区容量为 5 且开始为空:表示空位的信号量初值 5,表示产品的信号量初值 0。「B 的动作必须等 A 的动作做完」:开始时 A 还没做,信号量初值 0。阅览室有 100 个座位:…
  • 怎样判断一道 PV 题需要几个信号量:数 等待条件 :进程在什么情况下必须停下来等,每一种等待条件对应一个同步信号量;再给需要保护的共享数据(缓冲区、计数变量)配互斥信号量。 例 容量为 n 的缓冲区:生产者要等「有空位」,消费者要等「有产品」,两者访问缓冲区要互斥,共 3 …
  • 同步信号量与互斥信号量的 PV 位置有何不同:互斥信号量的 P、V 在 同一个进程 里成对出现,把临界区夹在中间。同步信号量的 P、V 分在 两个进程 里:需要等待的一方在动作之前做 P,提供条件的一方在动作之后做 V。 例 缓冲区问题里, P(mutex) 和 V(mutex) 在…
  • 信号量的取值范围和含义怎么算:按「先减 1 再判断」的记录型信号量:值大于 0 表示 还可用的资源数 ;等于 0 表示资源用完且没有进程等待;小于 0 时,绝对值是阻塞在这个信号量上的进程数。 例 5 个进程用一个初值为 1 的信号量实现互斥:取值范围是 −4 到 1…
  • 进程等不到就离开时为什么不能直接用 P:P 操作在条件不满足时只会 阻塞等待 ,不会让进程「看一眼就走」。需要「满了就离开」的场合,用一个普通整型变量记数量,配一个互斥信号量保护它,再用 if 判断。 例 等候区有 N 把椅子, waiting 记录正在等候的人数, mutex…
  • 写完 PV 代码后怎样自查:按四条查: 每个 P 都有对应的 V 吗?是哪个进程、在什么时候做的? 相邻的 P,是否同步的在前、互斥的在后? 把 极端场景 走一遍:缓冲区全空时只有消费者到来,全满时只有生产者到来,会不会死锁? 临界区里是否只有对共享数据的访问? 例…

六个常见同步模型的 PV 写法

  • 多类生产者和消费者共用一个盘子怎么写:盘子只能放 1 个水果:父亲放苹果,母亲放橘子,女儿只吃苹果,儿子只吃橘子。设 plate=1 (盘子的空位)、 apple=0 (盘中的苹果数)、 orange=0 (盘中的橘子数)。 父亲: P(plate); 放苹果; V(appl…
  • 读者写者问题怎样改成读写公平:在读者优先的写法上加一个信号量 w=1 当排队的闸门:读者和写者进入前都先 P(w) 。写者一到就占住 w, 后来的读者被挡在 w 上 ,不能再插到写者前面。另设 rw=1 (读写互斥)、 mutex=1 (保护计数变量 count,初值…
  • 理发师问题(等候位有限)怎么写:设整型变量 waiting=0 (等候的顾客数)和三个信号量: mutex=1 保护 waiting; customers=0 表示等候的顾客,理发师没活时睡在它上面; barbers=0 表示理发师可以接待下一位。等候椅有 N 把。 理…
  • 两种产品数量差有限制的同步怎么写:仓库里放 A、B 两种产品,要求「A 的件数减 B 的件数」 大于 −M 且小于 N 。设 sa=N-1 (还能比 B 多放几件 A)、 sb=M-1 (还能比 A 多放几件 B)、 mutex=1 。 放 A: P(sa); P(mut…
  • 前驱图里的先后关系怎样用信号量实现:给前驱图的 每条有向边 设一个信号量, 初值都是 0 :边的起点语句执行完后做 V,边的终点语句执行前做 P。 例 前驱关系为 S1→S2、S1→S3、S2→S4、S3→S4,四条边依次设信号量 a、b、c、d: S1; V(a); V(…
  • 同方向可同行、反方向要互斥的问题怎么写:以单行桥为例:同方向的车可以同时在桥上,反方向的车不能同时上桥。这相当于 两拨读者 :每个方向设一个计数变量和保护它的互斥信号量,共用一个 bridge=1 。某方向第一辆上桥的车做 P(bridge) ,最后一辆下桥的车做 V(brid…

互斥算法分析:看代码判断违反哪条准则

  • 单标志法为什么违反空闲让进:单标志法用变量 turn 表示轮到谁进入。进程 i 的代码是 while(turn!=i); 临界区; turn=j; ,两个进程只能 严格交替 进入临界区。 例 turn 为 0,但进程 0 暂时不想进临界区:进程 1 想进,却一直卡在…
  • 双标志先检查法为什么做不到互斥:进程 i 的代码是 while(flag[j]); flag[i]=true; 临界区; flag[i]=false; 。问题在于「检查对方」和「给自己上锁」是两步, 中间可能被切换 。 例 进程 0 检查到 flag[1] 为假、通过 …
  • Peterson 算法怎样既互斥又不会互相死等:进程 i 的代码是 flag[i]=true; turn=j; while(flag[j] && turn==j); 临界区; flag[i]=false; 。flag 表示「我想进」,turn 表示「让对方先」:两个进程都想进时, 后写…
  • 记录型信号量怎样做到让权等待:P 操作:先把信号量的值减 1,如果 减完小于 0 ,就把当前进程放进这个信号量的等待队列并阻塞。V 操作:先把值加 1,如果 加完仍不大于 0 ,就从等待队列里唤醒一个进程。进程得不到资源时主动放弃处理机进入阻塞态,不再循环检查,所以满…

文件目录、索引结点与文件共享

  • 文件控制块和索引结点各存什么:文件控制块(FCB)存放管理一个文件所需的全部信息:文件名、类型、物理位置、长度、存取权限、建立和修改时间等;目录就是 FCB 的有序集合。索引结点是把 FCB 里 除文件名以外 的信息单独拿出来存放的结构,目录项里只留文件名和索引结点号…
  • 目录项只存文件名和索引结点号有什么好处:目录项变小,每个盘块能放更多目录项,目录占的盘块变少,按名查找时 读盘次数减少 。 例 盘块 1 KB,某目录下有 3200 个文件,顺序检索。目录项放完整的 FCB(128 B):每块放 8 项,目录占 400 块,平均要读 $\fra…
  • 按路径名查找文件要读几次磁盘:从根目录起逐级查:读目录的内容,找到下一级的索引结点号,读那个索引结点,再读下一级目录的内容,直到读入目标文件的索引结点。 例 查找 /usr/doc/a.txt ,假设根目录的索引结点已在内存,每个目录的内容只占 1 个盘块,每个索引结…
  • 硬链接和软链接的链接计数怎么变化:硬链接:新目录项指向 同一个索引结点 ,结点里的链接计数加 1;删除一个文件名只是把计数减 1,减到 0 才真正删除文件。软链接(符号链接):新建一个独立的文件,有自己的索引结点,内容是目标文件的路径名, 不改变目标的链接计数 。 例 文…
  • 打开文件时操作系统做了哪些事:open 按路径名逐级查目录,找到文件的 FCB(或索引结点),检查访问权限,把它调入内存并在 系统打开文件表 里登记(已经登记过就把打开计数加 1),再在本进程的打开文件表里加一项指向它,最后返回这一项的编号,即 文件描述符 。此后读写…
  • 索引顺序文件为什么比顺序文件查得快:索引顺序文件把记录分组,为每组的第一条记录建一个索引项。查找时先查索引表确定在哪一组,再在组内顺序查, 不用从头扫描全部记录 。 例 10000 条记录按关键字顺序查找:顺序文件平均约比较 5000 次。改成索引顺序文件,每组 100 条…
  • 单级、两级、树形和无环图目录有什么区别:单级目录:整个系统只有一张目录表, 不允许重名 ,查找慢 两级目录:主文件目录下每个用户一张用户文件目录,不同用户的文件可以重名,但用户不能再给自己的文件分类 树形目录:目录可以一级一级往下建,用路径名标识文件,便于分类;不同目录下的文件…
  • 文件保护有哪几种常见办法:常见三种:口令保护(给文件设口令,访问时核对)、加密保护(对文件内容加密,访问时解密)、 访问控制 (规定每类用户能对文件做哪些操作)。 例 访问控制表(ACL)为每个文件记录各个用户的权限。精简的做法是把用户分成三类:文件主、同组用户、…

文件分配方式:最大长度与读盘次数

  • 连续、链接、索引三种分配方式怎样比较:连续分配:目录项记录起始块号和长度,顺序访问和随机访问都快;但会产生 外部碎片 ,文件不容易增长。 链接分配:隐式链接在每个盘块里放下一块的指针,只能顺序访问;显式链接把指针集中放进文件分配表(FAT),FAT 调入内存后定位较快。没有外…
  • 混合索引的文件最大长度怎么算:先算每个盘块能放的地址项数 k(盘块大小除以地址项长度)。最大块数等于 直接地址个数 ,加一级间接个数乘 k,加二级间接个数乘 $k^2$,依此类推;再乘盘块大小得到最大长度。 例 盘块 4 KB,地址项 4 B,k 为 1024。索引结…
  • 混合索引下访问文件某个位置要读几次磁盘:先算逻辑块号(字节偏移除以盘块大小,取整),看它落在哪一级地址:直接地址读 1 次(数据块);一级间接读 2 次(一个索引块加数据块);二级间接读 3 次。前提是索引结点 已在内存 、索引块都不在内存。 例 盘块 4 KB,每块放 102…
  • FAT 的表项位数和 FAT 的大小怎么算:FAT 为磁盘上 每个簇(盘块)设一个表项 ,表项里存放下一簇的簇号,所以表项的位数至少要能表示所有簇号,即不小于「簇数取以 2 为底的对数」向上取整。FAT 的大小等于表项个数乘表项长度。 例 磁盘容量 1 GB,簇大小 4 KB:簇数…
  • 隐式链接和显式链接读第 k 块各要几次读盘:逻辑块从 0 编号、目录项已在内存时:隐式链接必须顺着盘块里的指针从第 0 块一直读到第 k 块,共 k+1 次 ;显式链接的 FAT 已在内存,在内存里顺着 FAT 查 k 步得到物理块号,只需读盘 1 次 。 例 读文件的逻辑块 5:…
  • 在文件里插入一个盘块要多少次磁盘读写:在最前面插入一块时,连续分配次数最多:原有 n 块逐块后移(读、写各 n 次),再写新块 1 次,共 2n+1 次;隐式链接和索引分配只改指针,各 1 次。这里设文件控制块和索引块已在内存、改完后的回写不计,读或写一个盘块各算 1 次,连…
  • 文件占用的磁盘空间为什么比文件长度大:磁盘空间按簇(盘块)为单位分配,文件长度不是簇大小的整数倍时, 最后一簇用不满 ,没用上的部分就是内部碎片。 例 文件长 10000 B,簇大小 4 KB(4096 B):需要 3 簇(2 簇只有 8192 B,不够),占用 12288 …

位示图、磁盘访问时间与磁盘调度

  • 位示图里盘块号与字号、位号怎么换算:设每个字有 n 位。 都从 0 编号 时:盘块号 $b=n\times i+j$,字号 i 是 b 除以 n 的商,位号 j 是余数。 都从 1 编号 时:$b=n\times(i-1)+j$,字号 i 是 b−1 除以 n 的商再加 1…
  • 位示图要占多大的空间:每个盘块对应 1 位,所以位示图的位数等于 盘块总数 ;除以 8 得字节数,再除以盘块大小并向上取整,得到位示图占用的盘块数。 例 磁盘容量 8 GB,盘块大小 4 KB:盘块数为 $2^{33}\div 2^{12}=2^{21}$,位…
  • 空闲磁盘空间有哪几种管理方法:常见四种: 空闲表法:登记每个空闲区的起始块号和块数,适合连续分配 空闲链表法:把空闲盘块或空闲盘区用指针链起来 位示图法: 每个盘块用 1 位 表示是否空闲,连续分配和离散分配都能用 成组链接法:把空闲块分成若干组,每组的第一块记录下一…
  • 柱面号、磁头号、扇区号怎样与逻辑块号互换:设每个柱面有 H 个磁道(即磁头数),每个磁道有 S 个扇区,三种编号都从 0 起,逻辑块按「先扇区、再磁头、最后柱面」的次序编号。柱面号 c、磁头号 h、扇区号 s 对应的逻辑块号为 $L=(c\times H+h)\times S+s…
  • 磁盘从出厂到能存文件要经过哪几步:三步:①低级格式化(物理格式化),把磁道划分成扇区;② 分区 ,把磁盘分成若干个逻辑上独立的区域;③高级格式化(逻辑格式化),在分区里建立文件系统,写入根目录和空闲空间管理结构等初始数据。 例 UNIX 类文件系统的一个分区里,常见的布局…
  • 一次磁盘读写的时间由哪几部分组成:三部分相加:寻道时间(磁头移到目标磁道)、旋转延迟(目标扇区转到磁头下)、传输时间(扇区从磁头下经过)。 平均旋转延迟取转半圈的时间 ;传输时间等于转一圈的时间乘「读写的扇区数除以每道扇区数」。 例 转速 6000 转每分,转一圈 10 …
  • 例:FCFS 与 SSTF 磁盘调度的寻道距离:磁头在 60 号磁道,请求按到达次序为 95、20、130、58、75、10、160。先来先服务(FCFS)共移动 524 个磁道,最短寻道时间优先(SSTF)共移动 254 个磁道。 步骤 FCFS 按到达次序:60、95、20、130…
  • 例:SCAN、LOOK 与循环扫描的寻道距离:磁道号 0 到 199,磁头在 60 且正向磁道号增大的方向移动,请求为 95、20、130、58、75、10、160。 SCAN(走到 199 再折返):$(199-60)+(199-10)=328$ LOOK(到最远的请求 160 就…
  • 各种磁盘调度算法的特点怎么比较:FCFS:公平、简单,但磁头来回摆动,平均寻道距离大 SSTF:平均寻道距离较小,但 可能饥饿 ,且不一定是总距离最短的方案 SCAN:不会饥饿,但刚被扫过的磁道要等磁头折返后才再被服务,两端磁道的等待相对更长 C-SCAN:只在一个方向…
  • 连续读同一磁道上的多个扇区要多少时间:只需 定位一次 :寻道一次、等待第一个扇区转到磁头下一次,之后各扇区依次从磁头下经过,传输时间按扇区数累加。 例 转速 6000 转每分(转一圈 10 ms),每道 200 个扇区,平均寻道时间 6 ms。读同一磁道上连续的 20 个扇区…

本图由 SeekFlaw 编辑团队整理。发现错误,欢迎到学习论坛指出。

打开这张导图:点节点翻面看答案 →