《计算机操作系统》重点知识笔记整理(二)

简介: 《计算机操作系统》重点知识笔记整理(二)

第五章 虚拟存储器

1 特征和局部性原理(P164)

(1)特征:

一次性、驻留性

(2)局部性原理:

原理概述:

程序在执行时将呈现出局部性规律,即在一较短的时间内,程序的执行仅局限于某个部分,相应的,它所访问的存储空间也局限于某个区域。

论点:

  • 程序执行时,除了少部分的转移过程调用指令之外,在大多数情况下是顺序执行的。
  • 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域。但经研究看出,过程调用的深度在大多数情况下都不超过5。
  • 程序中存在许多循环结构,这些结构虽然只由少数指令构成,但是他们将被多次执行。
  • 程序中还包括许多对数据结构的处理,比如对数组进行操作,但是这些操作都被局限在很小的范围内。
    局限性表现的两个方面:
    (1)时间局限性 (2)空间局限性

2 请求分页存储管理方式(P168)

概念:

建立在基本分页的基础之上,为了能支持虚拟存储器功能,而增加了请求调页功能和页面置换功能。

(1)页表和相关概念

(2)地址变换过程

请求分页和基本分页有什么不同?

请求分页不要求资源一次性全部装入内容,而普通分页则不需要。

3 *页面的置换算法(P174)

(1)最佳置换算法(OPT)和先进先出置换算法(FIFO)

①OPT

核心思想:选择的被淘汰页面将是以后永不使用的,也可能是在最长(未来)时间内不再被访问的页面。[无法实现]

实例:系统分配给一个作业的物理块为3,并且作业的页面走向为1、2、3、4、1、2、5、1、2、3、2、5,画出页面的变化过程

②FIFO

核心思想:总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面给予淘汰。

实例:系统分配给一个作业的物理块为3,并且作业的页面走向为1、2、3、4、1、2、5、1、2、3、2、5,画出页面的变化过程

(2)最近最久未使用*(LRU重点)和最少使用置换算法(LFU)

① *LRU

核心思想:根据页面调入内存后的使用情况做决定,选择最近最久未使用的页面给予淘汰。利用最近的过去,给每个字段赋予上次被访问以来所经历的时间t,当有页面需要淘汰时选择t值最大的给予淘汰。[性能较好]

实例:系统分配给一个作业的物理块为3,并且作业的页面走向为1、2、3、4、1、2、5、1、2、3、2、5,画出页面的变化过程。

②LFU

核心思想:选择最近时期最少使用的页面给予淘汰,为每个页面设置一个移位寄存器(访问计数器),用来记录页面的被访问频率,认为"如果数据过去访问频率很高,那么将来被访问的频率也很高"

实例:系统分配给一个作业的物理块为3,并且作业的页面走向为1、2、3、4、1、2、5、1、2、3、2、5,画出页面的变化过程

(3)Clock置换算法

核心思想:[LRU和FIFO的折中],为每一页设置一个访问位,再讲内存中所有的页面都通过链接指针链接成一个循环队列。当页面被访问时,其访问位被置为1,置换算法在选择被淘汰的页面时只检查该页的访问位。如果是0,就选择该页换出,若为1,则重新将它置0,暂不换出,给予该页第二次驻留内存的机会,再按照FIFO算法检查下一页面。

实例:系统分配给一个作业的物理块为3,并且作业的页面走向为1、2、4、1、5、3、2、5(比较复杂在这里就简单举例下)画出页面的变化过程

4 请求分段存储管理方式(P185)

(1)硬件支持—段表

(2)硬件支持—缺页中断机构

请求分段的系统中采用的是请求调段的策略,每当发现运行进程所要访问的段尚未调入内存时,便由缺段中断机构产生一缺段中断信号,进入OS后,由缺段中断处理程序将所需的段调入内存。

在这里就借用下教科书上的图吧:

(3)硬件支持—地址变换机构

因为被访问的段并非全在内存,所以在地址变换时,若发现所要的访问的段不在内存,必须先将所缺页的段调入内存,并修改段表,然后才能再利用段表进行地址变换。

在这里也借用下教科书的图(教科书真的太棒了!)

第六章 输入输出系统

申请设备时使用逻辑地址

1 设备分配(P215)

设备分配中的数据结构(4个):

(1)设备控制表DTC:用于记录设备情况。

(2)控制器控制表COCT:用于记录控制器情况。

(3)通道控制表CHCT

(4)系统设备表SDT:记录系统中全部设备的情况。

2 假脱机(Spooling)系统(P220)

假脱机技术用途:将一台物理I/O设备虚拟为多台逻辑I/O设备,可以允许多个用户共享一台物理I/O设备。

目的:为了缓和CPU的高速性与I/O设备的低速性间的矛盾。

概念:SPOOLing是Simultaneous Peripheral Operation On-Line (即外部设备联机并行操作)的缩写,它是关于慢速字符设备如何与计算机主机交换信息的一种技术,通常称为"假脱机技术"。

特点: SPOOLing技术是在通道技术和多道程序设计基础上产生的,它由主机和相应的通道共同承担作业的输入输出工作,利用磁盘作为后援存储器,实现外围设备同时联机操作。

组成:

  • 输入井和输出井
  • 输入缓冲区和输出缓冲区
  • 输入进程和输出进程
  • 井管理程序

    原理:

3 *缓冲管理(P223)

引入缓冲区的原因

(1)缓和CPU与I/O设备间速度的不匹配问题

(2)减少对CPU的中断频率,放宽对CPU中断响应时间的限制

(3)解决数据粒度不匹配的问题

(4)提高CPU和I/O设备间的并行性

缓冲区种类

(1)单缓冲

每当用户进程发出一个I/O请求,操作系统便在主存之中为之分配一个缓冲区。

(2)双缓冲(也称为缓冲对换)

在设备输入时现将数据送入第一缓冲区,装满后便转向第二缓冲区。

(3)环形缓冲

(4)缓存池

4 磁盘调度算法(P233)

(1)先来先服务(FCFS)

根据进程请求访问磁盘的先后次序进行调度。

例如:进程请求顺序为55、58、39、18、90、160、150、38、184(从100磁道开始)

被访问的下一个磁道 移动距离(磁道数)
55 45(|100-55|)
58 3(|55-58|)
39 19(|58-38|)
18 21
90 72
160 70
150 10
38 112
184 146
平均寻道长度 55.3

(2)最短寻道时间优先(SSTF)

要求访问的磁道与当前磁头所在的磁道距离最近,以使每次的寻道时间最短,但不能保证平均寻道时间变短。

例如:进程请求顺序为55、58、39、18、90、160、150、38、184(从100磁道开始)

被访问的下一个磁道 移动距离(磁道数)
90 10
58 32
55 3
39 16
38 1
18 20
150 132
160 10
184 24
平均寻道长度 27.5

(3)扫描算法(SCAN)

又称为电梯调度算法,该算法不仅考虑到欲访问的磁道与当前磁道间的距离,更优先考虑的是磁头当前的移动方向。

例如:进程请求顺序为55、58、39、18、90、160、150、38、184(从100磁道开始)

被访问的下一个磁道 移动距离(磁道数)
150 50
160 10
184 24
90 94
58 32
55 3
39 16
38 1
18 20
平均寻道长度 27.8

第七章 文件管理

1 文件的逻辑结构(P243)

类型—按是否有结构分类

(1)有结构文件

记录长度

  • 定长记录
  • 变长记录

(2)无结构文件

类型—*按文件的组织方式分类

(1)顺序文件:

指由一系列记录按某种顺序排列所形成的文件,其中的记录可以时定长记录或可变长记录。

(2)索引文件:

指为可变长记录文件建立一张索引表,为每个记录设置一个表项,以加速对记录的检索速度。

(3)索引顺序文件:

指为每个文件建立一张索引表时,并不是为每一个记录建立一个索引表项,而是为一组记录的第一个记录建立一个索引表项。

2 文件目录(P249)

文件控制块(FCB):

为了能对一个文件进行正确的存取,必须为文件设置用于描述和控制文件的数据结构,称之为文件控制块。

文件目录:

文件控制块的有序集合称为文件目录。

文件目录作用:

标识系统中的文件及其物理地址,供检索时使用。

目录管理要求:

(1)实现“按名存取”

(2)提高对目录的检索速度

(3)文件共享

(4)允许文件重名

3 树形目录结构(P253)

小规则:

主目录成为根目录,在每个文件目录中,只能有一个根目录,每个文件和每个目录都只能有一个父目录

第八章 磁盘存储器的管理

1 设备(外存)的组织方式(P268)

(1)连续组织方式

又称为连续分配方式,要求为每一个文件分配一组相邻接的盘块。

优点:

①顺序访问容易

②顺序访问速度快

缺点:

①要求为一个文件分配连续的存储空间

②必须事先知道文件的长度

③不能灵活的删除和插入记录

④对于那些动态增长的文件,由于事先很难知道文件的最终大小,因而很难为其分配空间,而即使是事先知道文件的最终大小,在采取预分配存储空间的方法时,也会使大量的存储空间长期空闲。

(2)链接组织方式

优点:

①消除了磁盘的外部碎片,提高了外存的利用率

②对插入、删除和修改记录都非常容易

③能适应文件的动态增长,无需事先知道文件的大小。

缺点:

①只适合于顺序访问

②对随机访问是极其低效的

(3)FAT技术

利用文件分配表FAT来记录每个文件中所有盘块之间的链接。

发展:

在FAT中引入了“卷”的概念,支持将一个物理磁盘分成四个逻辑磁盘,每个逻辑磁盘就是一个“卷”。

(4)NTFS(New Technology File System)的文件组织方式

是专门为Windows NT开发的,适用于Windows2000/XP及后续的Windows OS

特性

①使用了64位磁盘地址。

②更好的支持长文件名,单个文件名限制在255个字符以内,全路径名为32767个字符。

③具有系统容错性。

④保证系统的数据一致性。

⑤提供了文件加密、文件压缩等功能。

磁盘组织

NTFS是以簇为磁盘空间分配和回收的基本单位。一个文件占用若干个簇,一个簇只属于一个文件。

文件的组织

在NTFS中,以卷为单位,将一个卷中所有的文件信息、目录信息以及可用的未分配空间信息,都以文件记录的方式记录在一张主控文件表MFT中,该表时NTFS卷结构的中心,从逻辑上讲,卷中的每个文件作为一条记录,在MFT表占有一行,其中还包括MFT自己的这一行。

(5)*索引组织方式

① 单级索引

优化版的链接组织方式,优点是可以直接访问。

②多级索引

为索引增加索引,优点是大大加快了对大型文件的查找速度。

③增量式索引

更加全面的照顾到小、中、大及特大型作业,可采用多种组织方式来构成文件的物理结构。

2 文件存储空间的管理(P278)

(1)空闲表法和空闲链表法

空闲表法:

属于连续分配方式,与内存的动态分配方式相似,为每个文件分配一块连续的存储空间。

空闲链表法:

将所有的空闲盘区拉成一条空闲链,根据构成链所用的基本元素不同,可以把链表分成两种形式:空闲盘块链空闲盘区链

(2)*位示图法

位示图法是利用二进制的一位来表示磁盘中的一个盘块的使用情况,当其值为“0”时,表示对应的盘块空闲,为“1”时表示已分配。磁盘上的所有盘块都有一个二进制位与之对应,所产生的集合就叫做位示图。

借用下书上的图:

盘块的分配(三步)

① 顺序扫描位示图,从中找出一个或一组其值为“0”的二进制位。

② 将找到的一个或一组二进制位转换成与之对应的盘块号。并按如下公式计算:

b = n(i-1) + j
 i:其值为“0”的二进制位于位示图的第i行
 j:其值为“0”的二进制位于位示图的第j行
 n:每行的位数

③ 修改位示图,让map[i,j] = 1

盘块的回收(两步)

①将回收盘块的盘块号转换成位示图中的行号和列号,公式为

i = (b-1)DIV n+1
                          j = (b-1)MOD n+1

②修改位示图,让map[i,j] = 0

(3)成组链接法

在UNIX系统中广泛使用,将空闲表法和空闲链表法相结合成的一种空闲盘块管理方法,克服了表太长的缺点。

空闲盘块的组织:

① 空闲盘块号栈,存储当前可以的一种空闲盘块的盘块号(<=100)以及栈中尚有的盘块数N

② 文件区中的所有空闲盘块被分成若干个组

③ 将每一个组含有的总盘块数N和该组所有的盘块号记入其前一组的第一个盘块的S.free(0)-S.free(99)中

④ 将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中,作为当前可供分配的空闲盘块号。

⑤ 最末一组只有99个可用盘块,某盘块号分别记入前一组的S.free(1)~S.free(99)中,而在S.free(0)中则存放“0”,作为空闲盘块链的结束标志。

全部完结!


相关文章
|
25天前
|
安全 Linux Shell
操作系统究竟是什么?在计算机体系中扮演什么角色?
操作系统究竟是什么?在计算机体系中扮演什么角色?
28 0
|
1月前
|
存储 安全 Unix
计算机的操作系统
计算机的操作系统
12 2
|
1月前
|
存储 Ubuntu Unix
【Linux】1、操作系统、计算机硬件和软件、Linux 介绍
【Linux】1、操作系统、计算机硬件和软件、Linux 介绍
41 0
|
2月前
|
存储 安全 自动驾驶
计算机软考之操作系统
计算机软考之操作系统
51 0
|
3月前
|
Linux 数据安全/隐私保护 虚拟化
操作系统:计算机的大脑
操作系统:计算机的大脑
61 0
|
3月前
|
存储 资源调度 算法
《计算机操作系统》重点知识笔记整理(一)
《计算机操作系统》重点知识笔记整理(一)
52 0
|
4月前
|
调度
计算机操作系统-第十六天
计算机操作系统-第十六天
|
4月前
计算机操作系统-第十五天
计算机操作系统-第十五天
|
4月前
计算机操作系统-第十四天
计算机操作系统-第十四天
|
4月前
|
存储 Linux
计算机操作系统-第十三天
计算机操作系统-第十三天