选择题

T3：循环队列

不同指针指向，队列判空/判满条件

    1. rear:指向队尾元素 front:指向队头元素前一个位置
    （1）牺牲一个存储空间
    （2）判空条件：front == rear
    （3）判满条件：(rear+1)%MaxSize == front

    2. rear:指向队尾下一个元素 front:指向队头元素
    （1）牺牲一个存储空间
    （2）判空条件：front == rear
    （3）判满条件：(rear+1)%MaxSize == front

    3. rear:指向队尾元素 front:指向队头元素 ——注意判空和判满条件
    （1）牺牲一个存储空间
    （2）判空条件：(rear+1)%MaxSize == front
    （3）判满条件：(rear+2)%MaxSize == front
           

    区别与联系
    （1）上述三种指针指向的判空/判满条件均是牺牲一个存储空间，上述三种需要特别注意第三种的指针指向（可以通过画一个换装图好好体会）。
    （2）均可以在结构体内增加 tag (标记上一步是入队还是出队操作，只有入队才会造成假溢出现象) 或 size（标记循环队列中存储数据元素的个数，以此用来区分队满和队空）
    （3）基本入队、出队操作略有不同（具体见代码）

T8：图的基本概念

T9：散列表性能分析

        注意散列表的平均查找长度依赖于 装填因子，不直接依赖于记录数和散列表长度！

        要与查找效率区分开！

T11：堆排序

T13：IEEE754浮点数表示

T14：存储器的分类

T17：标志位

T19：指令系统

        1、空操作指令，取指操作后，PC+1.

        2、不采用指令预取技术，每个指令周期都需要取指令。

T20：中断类型号

• 硬件向量法识别中断源（向量中断、80x86采用）
  • 中断类型号（向量地址）：中断服务程序的入口地址的地址。指针的指针，对应一个中断服务程序
  • 中断向量表（入口地址）：中断服务程序的入口地址
  • 
  • 中断类型号用于指出中断向量的地址，CPU响应中断请求后，将中断应答信号INTR 发回到数据总线上，CPU从数据总线上读取中断类型号后，查找中断向量表，找到相应中断处理程序的入口

T22：

        CPU时间就是电脉冲的指令周期，一次脉冲运算一次。

T26：IO软件结构层次

T29：抖动现象、对换

• 抖动/颠簸：频繁的页面调度行为，根本原因是分配给每个进程的物理块太少。
• 在具有对换功能的操作系统中，通常把外存分为文件区和对换区。前者用于存放文件，后者用于存放从内存换出的进程。
• 抖动现象是指刚刚被换出的页很快又要被访问，为此，又要换出其他页，而该页又快被访问，如此频繁地置换页面，以致大部分时间都花在页面置换上。
• 撤销部分进程可以减少所要用到的页面数，防止抖动。
• 对换区大小和进程优先级都与抖动无关。

 T30：编译链接与装入，3种装入方式（2种重定位技术与绝对装入）

• 应用程序从用户编写的源文件到内存中执行的进程，大致分为3个阶段：
  • 首先，经过编译程序(Compiler）将源代码编译为若干个目标模块（Object Module);
  • 其次，通过链接程序(Linker）将编译好的目标模块以及所需的库函数链接在一起，形成完整的装入模块（LoadModule);
  • 最后，通过装入程序（Loader）将这些装入模块装入内存并执行。简单来说，从源程序到执行的进程，经历了编译、链接、装入三个步骤。
• 注：
  • 对程序设计者来说，数据的存放地址由数据名称决定，称为名地址或符号名地址，源程序的地址空间称为名空间或符号名空间。源程序经过编译之后得到目标代码，由于编译程序无法得知代码驻留在内存中的实际位置（即物理地址)，一般总是从0号单元开始编址，并顺序分配给所有的地址单元，这些都不是真实的内存地址，因此称为相对地址或者虚拟地址。
  •  一个完整的程序可以由多个模块构成，这些模块都是从0号单元开始编址。当链接程序将多个模块链接为装入模块时，链接程序会按照各个模块的相对地址将其地址构成统一的从0号单元开始编址的相对地址。
  • 当装入程序将可执行代码装入内存时，程序的逻辑地址与程序在内存的实际地址（物理地址)通常不同，这就需要通过地址转换将逻辑地址转换为物理地址，这个过程叫作重定位。

• 静态地址重定位
  • 即在程序装入内存的过程中完成，是指在程序开始运行前，程序中的各个地址有关的项均已完成重定位，地址变换通常是在装入时一次完成的，以后不再改变，故成为静态重定位。
  • 优点：无需硬件支持
  • 缺点：1）程序重定位之后就不能在内存中搬动了；2）要求程序的存储空间是连续的，不能把程序放在若干个不连续的区域中。
• 动态地址重定位
  • 不是在程序执行之前而是在程序执行过程中进行地址重定位。更确切的说，是在每次访问内存单元前才进行地址变换。动态重定位可使装配模块不加任何修改而装入内存，但是它需要硬件一定位寄存器的支持。
  • 优点：1）目标模块装入内存时无需任何修改，因而装入之后再搬迁也不会影响其正确执行，这对于存储器紧缩、解决碎片问题是极其有利的；2）一个程序由若干个相对独立的目标模块组成时，每个目标模块各装入一个存储区域，这些存储区域可以不是顺序相邻的，只要各个模块有自己对应的定位寄存器就行。
  • 缺点：需要硬件支持。
• 页式存储管理是动态重定位。

T31：甘特图

T33：参考模型提供服务 给我记住555

        面向连接的虚电路方式和无连接的数据报方式。

        数据报和虚电路方式是分组交换的两种方式。

T34：数据传输速率（比特率）与波特率

T36：重复 repeat

T37：路由表

T40：TCP累计确认

        后退n帧协议中的累积确认（偶尔捎带确认）：在连续接收好几个正确的数据帧后，才对最后一个数据帧发确认信息

        TCP中的累计确认：只确认数据流中至第一个丢失字节为止的字节。

        累积确认：对按序到达的最后一个分组发送确认

解答题

T44：CPU访问存储系统的整体流程

计组 | 【三 存储系统】强化阶段 —— 应用题与例题类型总结_西皮呦的博客-CSDN博客 

1、CPU访问存储系统的整体流程

• 1）程序员交给CPU逻辑地址，进行虚实地址转换才能找到该虚拟地址所对应的数据实际存放的位置。
• 2）虚实地址转换：页表、TLB
  • 虚页号与实页号的对应关系存在页表中，页表存在主存中，比较活跃的页表项存在TLB中，TLB相当于专用于存页表项的Cache。
  • 故转换时先查TLB，若TLB不命中，再查页表，若页表不命中，说明该页面还未调入主存，需发出缺页中断，从辅存中调入并更新页表和TLB。
• 3）页框号+页内地址拼接得到物理地址，访问Cache-主存体系操作相应的数据。
  • 先访问Cache，若Cache未命中，说明该块在主存中，需要先把该块调入Cache再处理，或者边调入Cache边处理。
  • 注:TLB或页表命中后说明该页面在主存中。

2、地址结构

• 虚拟地址分为虚页号和页内地址; 
• 物理地址分为实页号和页内地址。
• 实页号 = 物理页号 = 页框号
• Cache-主存体系中，地址先分为块号和块内地址。
• 对应不同的映射方式，主存地址的块号需要拆分成不同的字段，高位均为标记字段，需要存入Cache。
• 注：页表到TLB的映射与主存到Cache的映射方式类似。

3、是否命中

        1)页表：求出虚页号，看页表中是否有对应项且有效位为1

        2)Cache：根据Cache字块标记找到映射到的Cache行，该行有效位为1且标志与当前地址中的标记字段相同

        3)TLB：与Cache类似

T45：PV大题自我救赎Tips

• 1．草稿上写出进程行为轨迹，多留点空位
• 2．按逻辑一步一步推进，分析:哪些地方可能会等待?哪些地方会访问临界资源?
• 3．坚持一个原则，PV操作一定是成对出现的。利用这个特性，先在可能阻塞的地方P一下，再思考应该在什么地方V
• 4．先确定PV操作的位置，再思考该设置什么样的信号量、信号量的含义是什么

T46：文件物理结构及存储方式

注意！创建新文件 不是 对文件进行增加记录！

        优点：支持随机访问，随机访问速度最快，且存储空间利用率最高

        缺点：文件数据的“增/删/改”不方便。

        优点∶文件数据的“增/删/改”方便；

        缺点∶“查”不方便，不支持随机访问，只能顺序访问，需要使用额外的存储空间来存放磁盘块之间的链接指针;

        优点∶文件数据的“增/删/改”方便，也支持随机访问，但随机访问速度不如连续分配方式；

        缺点∶索引表的存放需要消耗额外的存储空间。 

        在本题所述场景中，不需要对文件进行“增/删/改”的操作，因此应该使用连续分配方式，可以使文件访问效率最高，存储空间利用率最高。为了定位文件数据块，需要在FCB中记录文件的<起始块号，块数>或<起始块号，结束块号>

        将所有的FCB集中存放，文件数据块集中存放。在按名查找文件名时，只需访问存储FCB的几个块。可减少磁头移动和磁盘I/O次数。

        FCB与对应的文件数据块连续存储:只能逐一读入包含各个文件FCB的磁盘块，每往后找一个文件就要读一个磁盘块。总体lo次数更多，磁头移动距离更长

部分内容参考于

队列——顺序存储结构实现( 循环队列 - 不同指针指向)_一个很懒的人的博客-CSDN博客_循环队列指针