OSTest
OSTest
Catcat HeadOS是管理计算机硬件与软件资源的系统软件
操作系统的功能 进程管理、内存管理、设备管理、文件系统、人机接口
- 用户态（目态）：是用户程序执行时机器所处的状态，当CPU处于用户态时，此时CPU只能执行非特权指令；
- 核心态（暂态）：又称为系统态，是操作系统的管理程序执行时机器所处的状态，当CPU处于核心态时，此时特权指令、非特权指令都可执行。
传递系统调用参数→执行陷入指令(用户态)→执行系统调用相应服务程序(核心态)→返回用户程序
- 陷入指令是在用户态执行的，执行陷入指令之,后立即引发一个内中断，从而CPU进入核心态
- 发出系统调用请求是在用户态，而对系统调用的相应处理在核心态下进行
- 陷入指令是唯一一个只能在用户态执行，而不可在核心态执行的指令
进程是具有独立功能的程序在数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位
程序
计算机程序，是指为了得到某种结果而可以由计算机等具有信息处理能力的装置执行的代码化指令序列，或者可以被自动转换成代码化指令序列的符号化指令序列或者符号化语句序列。
有的进程可能需要“同时”做很多事，而传统的进程只能串行地执行一系列程序。为此，引入了“线程”，来增加并发度。
多线程可以实现并行处理，避免了某项任务长时间占用CPU时间。在单CPU计算机中，为了运行所有这些线程，操作系统需要为每个独立线程安排一些CPU时间，操作系统以轮换方式向线程提供时间片，在宏观上似乎这些线程都在同时运行。
(1)使用最先适应分配算法 就是遇到能放得下的就放进去
观察一下 系统区是给系统用的 咱不能放作业进去 JA JB已经占了 还剩三个空先区 空闲区一:16KB 二:150Kb 三: 10KB
显然J3 J4肯定得放空闲区二 那就两个顺序 3 4 或者4 3
j2也只能放在一 所以可能的顺序也就出来了
2 34 1
2 43 1
描述插入后内存的情况 画图表示:
- CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
计算页号P和页内偏移量W (如果用十进制数手算，则P=A/L，W=A%L;但是在计算机实际运行时，逻辑地址结构是固定不变的，因此计算机硬件可以更快地得到二进制表示的页号、页内偏移量)
比如32位逻辑地址空间 页表项4B 页面大小4KB
由页面大小就可以知道 页内偏移最大为2的十二次方 所以需要12个二进制表示
则 页号 32-12=20个位表示 那么最大页表项就为2的20次方
显然 页面大小4KB存储4B的页表项只能存2的10次方个
因此将页表分块 每1024个页表项做一个二级页表
引入页目录表管理 该目录需要1024个 指向1024个二级页表存放的内存块号
这样划分之后 再回到我们32位的逻辑机制 可以发现 页内偏移所需位数没有变 还是12个 但是我们把原来表示页表项的前20为划分成了两部分 前十位1024个表示 一级页号
后十位 1024个表示二级页号
最后找到二级页号之后拿着去快表中找
如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此,若快表命中，则访问某个逻辑地址仅需一次访存即可。
对快表的访存速度远大于对主表的访存速度
如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。
因此，若快表未命中，则访问某个逻辑地址需要两次访存(注意:在找到页表项后，应同时将其存入快表,以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换)。由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。
1M=1024KB=2的二十次方 所以就20位
主存容量1M=1024KB ÷ 256块
一块大小=4KB=4*1024B=2的12次方
所以每一页长度4KB 页内偏移需要12位
内存块号*内存块大小就是起始地址
十六进制 一位表示4个二进制 所以一共16位
且页面大小2K 可以知道页内偏移占11位 16-11=5位
所以5位表示页号
060C 0000 0110 0000 1100 看前五位 所以页号0 注意这个图隐含了页号 所以0号页号对应的页框号是12
12号页框 页面大小2K 所以12号页框起始地址是24K 与页内偏移链接
0110 0 与 110 0000 1100拼接 0110 0110 0000 1100
OX 660C
同理 OX1502 0001 0101 0000 0010 前五位00010 页号2
页框号为0 所以00000 链接起来 就是0000 0101 0000 0010
OX 0502
OX 1d71 0001 1101 0111 0001 看前五位 00011 页号3
查页表发现 页号3对应的有效位是0 不在内存中 发生缺页中断
OX2c27 0010 1100 0010 0111 前五位 00101 页号5
页框号15 所以前五位 01111
0111 1100 0010 0111
OX 7c27 (怎么和ppt给的不一样😄 )
OX 4000 0100 0000 0000 0000 前五位01000 页号8
最大页号是7 查页号8 就越界了
(段号,段内偏移)
段内偏移<段长
段内偏移>=段长的都不对
参考笔记 “OS”中记录的内容
分页存储系统
1 页表在内存 访问内存单元需要两次访存 一次查页表 一次查数据
2 二级页表 一次一级页表 一次二级页表 一次数据
3 0.9 查到TLB 0.1 查不到
查到 0.9*10
查不到 0.1 * 210 要注意这里是200+10
(0.9*10 + 0.1 * 210) +200
文件共享 且不同文件名 参考”OS”中 五环图目录结构
不同的User存储不同的FCB 存放不同的名字 只要让索引指向同一个文件就行
iNode引入的好处:
1105 / 512=2.15
所以在第三个逻辑记录 50->121->75 所以在75号磁盘块
1569/512=3.06
50->121->75->80
一共访问四个
普通文件 看那个描述 意思就是混合索引 前十个直接指向十个磁盘块 第十一个是一级索引 第十二个是二级索引
一级索引指向一个256大小的索引表 所以指向256个页
第十二个二级索引 先指向一个256 再指向256个256 所以256×256个页
启动磁盘次数的话 最少的情况肯定就是没一次找都能找到
跟目录下找A 一次 A目录下找D一次 以此类推
然后在Q目录上找到要读入的那个页 读入页 再加一次
（这里Q目录下找对应页的那一次 肯定就是直接索引找到的,因为要让次数最少）
第二种情况
题目说一个目录下 每个磁盘块存十个下级目录链接 最多存40个 所以目录可能最多会分散在四个磁盘块
根目录下找A 最多遍历四个磁盘块 以此类推 4×4
找到Q之后 二级索引 最多读入两次索引表 +2
最后读出目标页 +1
现代操作系统中，常采用一些虚拟技术来提高系统效率，如以牺牲时间效率来换取空间效率，或以牺牲空间效率来换取时间效率。请举出一个系统中的例子来说明常用的空间换取时间的技术并说明其工作原理。
1)对于有结构文件中的索引文件,建立一张索引表之后,可以解决顺序文件不方便增加删除的缺点,但是建立索引表本身需要消耗一定的空间,但是有索引表之后,因为索引表本身其实就是有结构的定长顺序文件,可以方便增删,也可以按照关键字顺序排列,方便查找
2)文件存储的物理结构,在文件的磁盘块如何组织这个问题上,如果链接分配的时候使用隐式链接,可以解决当使用顺序分配的时候造成的外部碎片问题,但是每次查找都要从头查找,IO很消耗时间,就可以使用显示链接,在内存中存放一张FAT表,存放磁盘块的先后顺序,实现随机访问,虽然FAT要占用一定空间,但是减少了IO次数,大大提高了访问磁盘块的速度
简述计算机系统中引入缓冲的目的。
解决设备之间的速度差异
改善CPU和I/O设备之间速度不匹配的情况。
协调传输数据大小不一致
为了减少中断次数和CPU的中断处理时间。如果没有缓冲，慢速I/O设备每传一个字节就要产生一个中断，CPU必须处理该中断。如果用了缓冲技术，则慢速的I/O设备将缓冲区填满时，才向CPU发出中断，从而减少了中断次数和CPU的中断处理时间。
为了解决DMA或通道方式下数据传输的瓶颈问题。DMA或通道方式都适用于成批数据传输，在无缓冲的情况下，慢速I/O设备只能一个字节一个字节的传输信息，这造成DMA方式或通道方式数据传输的瓶颈。缓冲区的设置适应了DMA或通道方式的成批数据传输方式，解决了数据传输的瓶颈问题。
维持“复制语义”
- 问题：当一个程序将数据写入另一个程序或设备时，用户可能希望在写操作完成后，继续修改原始数据而不影响已经传输的数据。然而，数据从写入到实际传输之间可能存在时间延迟。
- 缓冲的作用：缓冲区在数据写入时保存数据的一个副本，传输操作在缓冲中进行。这样，即使用户修改了原始数据，也不会影响已提交的传输数据，从而保证“写入完成后数据独立”的复制语义。
提高CPU与I/O设备之间的并行性。
在Unix的文件系统中引入i结点（iNode）的目的是什么？请举例说明引入i结点的好处。
引入iNOde 仅仅在iNode中存放文件名和指向文件数据的索引 信息
能够增加一个磁盘块中可存放的文件索引表项 这样在查询文件对应磁盘快的时候 ,可以减少IO次数
假设一个FCB 64B 磁盘块大小1KB 一个磁盘块只能放16个FCB
如果一个文件目录640个目录项 要占用640/16=40个磁盘块
当要查询某个文件的时候时候平均要20次IO
但是如果引入iNode
文件名假设14B 索引指针2B(2的16次方个索引)
那每个磁盘块就可以放 1KB/16B=64个目录项
640/64=10个磁盘块
平均IO5次就能找到项找的文件
是否安全只要看有没有安全序列就行
索引表在不在内存 一定要注意😕
一、假设某请求分页系统采用一级页表，TLB命中率为98%，TLB访问时间为10ns，内存访问时间是100ns，假设缺页率为10%，平均页面置换时间是200ns，并假设当TLB访问失败时才开始访问内存，求：
（1） TLB命中时的有效访问时间是多少？
（2） TLB不命中的有效访问时间是多少？
（3） 产生缺页中断，并进行页面置换后的有效访问时间是多少？
所以这个类型的题都要注意 取位置+取数据两部分
10+100ns
10+100+100ns
t快 + t内 + t中断 + t快 + t内 10+100+200+10+100
一、 有一个虚拟存储系统，每个进程在内存占有3页数据区，刚开始时数据区为空。有以下访页序列：
4、3、2、1、4、3、2、1、2、1、5、2、1
试给出下列情形下发生的缺页次数，并说明什么时候发生（即访问哪一页时发生）：
（1）系统采用先进后出算法（和FIFO相反，既当需要淘汰页面时，淘汰最后调入的页面）。
刚开始为空 所以一开始4 3 2 就要有三次缺页
（2）系统采用最近最少使用置换算法。（即LRU算法）
一、 有四个进程S1、S2、R1和R2，其中S1、S2向缓冲区BUFF发送消息，R1和R2从缓冲区BUFF接收消息。发送和接收规则如下：
（1）R1只取S1存放在缓冲区中的消息；
（2）R2只取S2存放在缓冲区中的消息；
（3）缓冲区BUFF任何时候只能存放2个消息；
（4）缓冲区BUFF不能同时存放2个S1的消息或2个S2的消息。
请用信号量机制来实现这4个进程间的同步，并说明所使用信号量的含义。
有四个进程S1、S2、R1和R2，其中S1、S2向缓冲区BUFF发送消息，R1和R2从缓冲区中接收消息。发送和接收的规则如下：
(1) 缓冲区BUFF任何时候只能存放2个消息；
(2) R1、R2每次同时取S1和S2存放在缓冲区中的消息；
(3)每个存放在缓冲区中的消息必须被R1和R2均接收后才能清除；
(4)缓冲区BUFF不能同时存放2个S1的消息或2个S2的消息。 请用信号量机制来实现这4个进程间的同步
//首先设置Empty信号量，用于S1、S2进程判断是否可以发送消息
//然后设置FULL信号量，用于R1、R2进程判断是否可以接收消息
EmptyS1R1 = EmptyS1R2 = EmptyS2R1 = EmptyS2R2 = 1;
FullS1R1 = FullS1R2 = FullS2R1 = FullS2R2 = 0;
Process(S1){
while(1){
P(EmptyS1R1);//判断S1发送给R1的消息是否被R1接收
P(EmptyS1R2);//判断S1发送给R2的消息是否被R2接收
SetMessage();
V(FullS1R1);//提醒R1接收消息
V(FullS1R2);//提醒R2接收消息
}
}
Process(S2){
while(1){
P(EmptyS2R1);//判断S2发送给R1的消息是否被R1接收
P(EmptyS2R2);//判断S2发送给R2的消息是否被R2接收
SetMessage();
V(FullS2R1);//提醒R1接收消息
V(FullS2R2);//提醒R2接收消息
}
}
Process(R1){
while(1){
P(FullS1R1);//判断S1是否发送给R1的消息
P(FullS2R1);//判断S2是否发送给R1的消息
ReciveMessage();
V(EmptyS1R1);//提醒S1发送消息
V(EmptyS2R1);//提醒S2发送消息
}
}
Process(R2){
while(1){
P(FullS1R2);//判断S1是否发送给R2的消息
P(FullS2R2);//判断S2是否发送给R2的消息
ReciveMessage();
V(EmptyS1R2);//提醒S1发送消息
V(EmptyS2R2);//提醒S2发送消息
}
}
