【操作系统问题】某文件系统采用索引文件结构多重索引结构搜索文件内容?

存储介质:磁盘、光盘、磁带…
完成外存信息的管理和存取


在前面的学习中,我们知道文件也是一种系统资源。

这里先给出文件和文件系统的定义。

外存中具有符号名的一组有逻辑意义的信息项的集合。

指OS中管理文件的那一部分软件。它负责管理文件的存储、检索、更新,提供安全可靠的共享和保护手段,并为用户提供一整套方便有效的文件使用和操作方法。它在OS接口中占比例最大,是I/O系统的上层软件。文件系统面向用户的主要任务是实现文件的“按名存取”
按名存取是文件系统最为主要的任务!!!

主要属性有:文件名、识别符、类型、位置、大小、创建时间、上次修改时间、文件所有者和保护信息等。

文件的结构指文件中信息的配置和构造方式,有逻辑结构和物理结构之分。
用户眼中文件信息的组织形式叫文件的逻辑结构。它包括记录式文件和流式文件两种,每种文件信息的逻辑单位分别是记录和字符。
UNIX系统视所有文件的逻辑结构为无结构的流式文件
早期有结构的记录式文件又分定长和不定长两种
文件的逻辑结构与文件的存储介质无关

 文件的逻辑结构可以分为无结构文件(流式),有结构文件(记录式)

根据各条记录的长度(占用的存储空间)是否相等,又可以分为定长记录和可变长记录两种。

根据有结构文件中的各条记录如何组织,可分为三类

这里进行检索效率的分析:

看完文件的逻辑结构的划分,是不是觉得好像在哪里学过类似的组织方式?

回想一下在计算机组成原理中Cache的组织方式,是不是也是这样的?

地址映像的直接映像、全相联映像、组相联映像不就对应着顺序文件、索引文件、索引顺序文件?

文件目录是文件系统管理文件最为重要的依据。

文件控制块(FCB):是OS为管理文件而设置的数据结构,存放了为管理文件所需的所有有关信息(文件属性),也叫文件目录项
文件控制块是文件存在的标志
基本信息:文件的名字、地址、大小、结构、类型
存取控制信息:文件属主、存取权限或属性或口令
使用信息:共享计数,文件的建立、修改日期等

文件目录:把所有的FCB组织在一起,就构成了文件目录,即文件控制块的有序集合
目录文件:为了实现对文件目录的管理,通常将文件目录以文件的形式保存在外存,这个文件就叫目录文件
目录主要是为了系统快速实现“按名存取”而引入的,查目录是文件系统最频繁的操作,因此目录的合理组织很重要

2、目录结构—单级目录结构

系统为所有文件建立一个目录文件(线性表)
限制了用户对文件的命名(存在“命名冲突”问题)
顺序检索文件时平均检索时间长

3、目录结构—两级目录结构

为克服单级目录结构存在的命名冲突问题,并提高对目录文件的检索速度而引入
目录分为两级:一级称为主文件目录,给出用户名,用户子目录所在的物理位置;二级称为用户文件目录(又称用户子目录),给出该用户所有文件的FCB
优点:解决了文件的重名问题和文件共享问题;

4、目录结构—多级目录结构

多级目录结构又称为树形目录结构

这里再介绍一下相对路径绝对路径的概念

在树形目录结构中,对文件的访问可以按文件的绝对路径名相对路径名符号链接

 树形目录结构可以很方便地对文件进行分类,层次结构清晰,也能更有效地进行文件的管理和保护。但是,树形结构不便于实现文件的共享。为此,提出了"无环图目录结构"

5、目录结构—无环图目录结构

6、索引结点(FCB的改进)

  根据FCB中文件物理地址等信息,求出文件的任意记录或字符在存取介质上的地址,称为文件寻址。

对FCB过大的改进方法
 采用目录项分解法,把FCB分成两部分。
 符号目录顶(次部)
 基本目录项(主部)

设物理块大小512字节,一个FCB有48个字节,符号目录项占 8字节,文件名6字节,文件号2字节,基本目录项占 48-6=42字节。若把含有128个目录项的某单级目录文件改造成符号文件目录和基本文件目录的结构,试说明改造后查找一个文件的平均访盘次数,谈一下自己的认识。

四、文件的物理结构(文件的分配方式)

系统眼中文件信息的组织形式叫文件的物理结构。它包括顺序文件、链接文件、索引文件三种(实为连续文件与不连续文件两大类)
文件的物理结构也叫文件的存储结构,指文件在外存上的存储组织形式,它与存储介质的性能和外存的分配方式有关

 在很多操作系统中,磁盘块的大小与内存块、页面的大小相同

2、文件分配方式—连续分配

连续分配方式要求每个文件在磁盘上占有一组连续的块。

 这里需要明白一下磁盘读取的原理

结论:物理上采用连续分配,存储空间利用率低,会产生难以利用的磁盘碎片。

可以用紧凑来处理磁盘碎片,但需要耗费很大的时间代价。

文件的信息存放在若干连续的物理块中。

优点:实现简单,顺序存取速度快,至此顺序访问和直接访问(随机访问)

缺点:但分配慢,不方便文件拓展,存储空间利用率低,外存碎片多(似内存的可重定位可变分区分配)

3、文件分配方式—链接分配

链接分配采取离散分配的方式,可以为文件分配离散的磁盘块。分为隐式链接显示链接两种。

 看到这里是否想到了数据结构中的静态链表?

 注意:一个磁盘仅设置一张FAT!FAT的各个表项在物理上连续存储,且每一个表项长度相同,因此“物理块号”字段可以是隐含的。

隐式链接方式只支持顺序访问,不支持随机访问;显示链接支持随机访问!

4、文件分配方式—索引分配

注意:在显式链接的链式分配方式中,文件分配表FAT是一个磁盘对应一张表。而索引分配方式中,索引表是一个文件对应一张。

但如果出现一个磁盘块不能装下文件的整张索引表,该如何解决这个问题?

 支持随机访问?

这个范例是帮助读者深入比较文件物理组织的各种方案:顺序文件的连续分配、链接文件的链接分配、二级索引分配。

一个文件系统中有一个20MB大文件和一个20KB小文件,当分别采用连续、链接、二级索引分配方案时(每块大小为4096B,每块地址用4B表示),问:
1.各文件系统管理的最大的文件是多少?
2.每种方案对大、小二文件各需要多少专用块来记录文件的物理地址(说明各块的用途) ?
3.如需要读大文件前面第5.5KB和后面(16M+5.5KB)信息,则每个方案各需要多少次盘I/O操作?

1.各种分配方案的文件系统可管理的最大文件
 连续分配:不受限制,可大到整个磁盘文件区。
 链接分配:同上。
 二级索引:由于盘块大小为4KB,每个地址用4B表示,一个盘块可存1K(4)个索引表目,二级索引可管理的最大文件容量为4KB×1K×1K=4GB,如要管理更大的文件需采用三索引,它可管理4TB大小文件。

 2.每种分配方案对20MB大文件和20KB小文件各需要多少专用块来记录文件的物理地址?
连续分配:对大小二个文件都只需在文件控制块FCB中设二项,一是首块物理块块号,另一是文件总块数,不需专用块来记录文件的物理地址。
链接分配:对大小二个文件都只需在文件控制块FCB中设二项,一是首块物理块块号,另一是文件总块数;同时在每块存文件的物理块中设置存贮下一块块号的指针。
二级索引:对大小文件都固定要用二级索引,对20KB小文件,用一块作第一级索引,用另一块作二级索引,共用二块专用物理块作索引块,对于20MB大文件,用一块作第一级索引,用5块作第二级索引,共用六块专用物理块作索引块。(20MB=5×1K×4KB)

3.为读大文件前面第5.5KB和后面(16M+5.5KB)信息需要多少次盘I/O操作?
连续分配:为读大文件前面和后面信息都需先计算信息在文件中相对块数,前面信息相对逻辑块号为5.5K/4K=1,后面信息相对逻辑块号为(16M+5.5K)/4K=4097。再计算物理块号=文件首块号+相对逻辑块号,最后化一次盘I/O操作读出该块信息。
链接分配:为读大文件前面5.5.KB的信息,只需先读一次文件头块得到信息所在块的块号,再读一次第1号逻辑块得到所需信息。而读大文件后面16MB+5.5KB的信息,要先把该信息所在块前面块顺序读出,共化费4097次盘I/O操作,才能得到信息所在块的块号,最后化一次I/O操作读出该块信息。所以总共需要4098次盘I/O才能读取(16MB+5.5KB)字节信息。
二级索引:为读大文件前面和后面信息的操作相同,首先进行一次盘I/O读第一级索引块,然后根据它的相对逻辑块号计算应该读第二级索引的那块,第一级索引块表目号=相对逻辑块号/1K,对文件前面信息1/1K=0,对文件后面信息4097/1K=4,第二次根据第一级索引块的相应表目内容又化一次盘I/O读第二级索引块,得到信息所在块块号,再化一次盘I/O读出信息所在盘块,这样读取大文件前面或后面信息都只需要3次盘I/O操作。

 某文件系统采用单级索引文件结构,假定文件索引表的每个表项占3B存放一个磁盘块的块号,磁盘块的大小为512B。试问:
(1)该文件系统能支持的最大文件大小是多少字节?能管理的最大磁盘空间是多大?

(2)若采用3级索引,该文件系统能支持的最大文件大小是多少字节?

(1)由于索引表占用一个大小为512B的磁盘,所以该文件系统的索引表可以管理512/3=170个表项,而每一个表项对应一个物理块,因此该文件

能管理的最大磁盘空间:

抽象类不能创建对象,主要用来创建子类。

抽象数据类型指明了可能的类型和允许进行的操作,但是没有提供实现。

用于方法或变量定义,限定了哪些类可以访问该方法或变量。

没有访问标识符修饰的方法或变量默认可见性为“package”。

活动记录是包含了实现子程序调用必须的所有信息,包括参数值、子程序中的本地变量和子程序调用结束时计算机的返回地址。

活动记录存储在栈中,使得多个子程序调用同时活跃成为可能。

这对递归非常重要,递归时对同一个子程序的多个调用要求同时激活。

子程序的参数叫做声明。当调用执行时,通过声明把值传递给自函数。实参也叫做“参数”。

计算机内存中的每个位置都有一个地址,表示该位置的编号。内存中的位置按序号排列。

在现代计算机中,内存中的每个字节都有自己的地址。在存储或读取内存信息时用需要用到地址。

完成某项任务所需要的一步一步的过程,过程本身没有歧义,且可以保证在有限的步骤内完成该任务。

颜色组成用来描述颜色的透明度或不透明度。阿尔法组成越高,颜色越不透明。

应用编程接口。针对软件包或“工具箱”的接口说明。

API包含了工具箱中所有类或子程序及其使用说明。

与可以单独运行的应用程序不同,Applet是一种在Web浏览器中运行在Web页面上的Java程序。

由一组静态图片快速显示展示出动态效果。每一幅静态图片叫做帧。

在Java中,动画通常由 Timer 对象驱动。

每次定时器触发时,会显示动画的下一帧。

当图形和文本以像素方式显示时,可以通过调整像素的颜色减轻“锯齿”效应。

反锯齿画图时,图形只覆盖像素的一部分,图形的颜色与该像素之前的颜色混合而成。混合的程度由覆盖像素的多少决定。

一个顺序排列的元素列表。列表中,每个元素都可以由自己的索引标识,即序号。

在Java中,数组里所有元素必须类型相同,该类型也称作数组的基类型。

数组是一种可随机访问的数据结构,也就是说,你可以随时直接访问数组中的任意元素。

这种数据类型的值是数组。比如类型的名字为 Type,那么 Type[] 就是数组类型,基类型为 Type。

计算机程序中的一种语句,可以读取或计算数值,并将其存储到变量中。

Java中的赋值语句形式为:变量名 = 表达式。

异步事件指发生时间不可预料的事件,计算机程序无法对其控制。

像点击鼠标、按键这样的用户输入事件都是异步的。

美国信息交换标准码。这种编码使用7个比特对字符编码。

ASCII码只支持128个字符,不支持重音字符、非英语字符、特殊符号或非字符化语言的表意符号,比如中文。

Java采用了容量更大、更加完整的Unicode编码处理字符。

在递归算法中,基线条件可以直接处理不需要继续递归。

数值被编码为一组0、1序列。一般数字以“10为基数”,二进制数与其类似,只是以“2为基数”。

二叉树是一种链式数据结构。可以为空树,或者由两棵更小的二叉树(可能为空树)与根节点组成。

根节点包含了指向两棵子树的指针。这两棵更小的二叉树被称作左子树和右子树。

一位二进制数,可能是0或1。

指系统或组件在使用时无需关心内部结构。黑盒包括接口和实现。在系统中,被当做组件使用的黑盒叫做模块。

在Java编程中,被花括号({})包围的一组语句称为块。(代码)块用来将一组语句组合成一条语句。

块可以为空,表示不包含任何语句,即一对空的花括号。

一个操作如果需要等待某些事件发生就称为“阻塞”操作,比如从网络连接读取数据。

执行阻塞操作的线程会一直处在“阻塞”状态,直到事件发生。处于阻塞状态时,线程不能执行任何指令。

而程序中的其它线程可以继续执行。

当阻塞队列为空时,出队操作会引发阻塞,直到队列中有新成员加入。

如果阻塞队列有大小限制,当队列填满时,入队操作也会引起阻塞。

自底向上设计是一种软件设计方法。从系统的基础组件开始设计,然后将它们组合成更复杂的组件,诸如此类。

BufferedImage类展示了“屏外画布”,即图片存储在计算机内存中,可以在屏幕外进行绘制。

分支是一种控制结构,计算机通过分支从2个或多个不同的执行路径中进行选择。

字节是一种由8个比特组成的内存单元。

一个字节可以保存8个比特二进制数。

“Java字节码”是Java虚拟机机器语言的常用名称。

Java程序会被编译成Java字节码,后者由JVM执行。

字符集是一种将字符数据编码为二进制的特定编码形式。例如UTF-8和ISO-8859-1。

在Java中受检异常必须处理,可以通过 try catch 语句捕获,或者在方法上使用 throw 语句抛出该异常。

如果没有用这两种方式处理受检异常,会报告语法错误。

类是Java的基础编程单元。

类是静态方法、非静态方法和变量的集合。

静态成员是类自身的一部分,非静态或“实例”成员是创建对象的蓝本,由此创建的对象“属于”该类。

“静态变量”和“静态方法”的别名。它们是类的一部分,与对象无关。

其中,“服务器”在网络上守候某个已知地址,等待“客户端”向它发起连接请求。

这是TCP/IP协议的基础通讯模型。

一种计算机交互方法。用户向计算机输入命令,计算机对每个命令进行响应。

在一个计算机程序中,注释是那些被计算机忽略的文本。注释的目的是方便人们阅读,帮助理解程序。

编译器是一种计算机程序,将某种计算机语言(通常是高级语言)编写的程序翻译成机器语言程序。

组件是对GUI可视元素的泛称,包括窗口、按钮或菜单等。

在Java中,组件表现为 ponent 子类创建的对象。

类的一种特殊子程序,主要用来创建类的对象。

构造函数一般使用 new 操作符进行调用,通常不被看做“方法”。

类似 JPanel 这样的组件,容器可以包含其它GUI组件。

调用容器的 add 方法可以向其添加组件。

它指明了方法及其调用者的职责,如何调用该方法,以及正确调用方法时会执行的任务。

方法契约应当在该方法的Javadoc注释中完整说明。

类似 if 语句、while 循环这样可影响程序控制流(即程序中指令执行顺序)的程序结构。

中央处理器。CPU是计算机中实际执行计算和运行程序的部分。

经过组织的数据集合。在程序中被当做一个单元处理。

一种多个线程无限等待的情况。出现死锁的原因,比如每个线程都在等待其它线程锁定的资源。

Java 8 接口中的方法,该方法提供了自己的实现。

所有实现带有默认方法的接口都可以使用默认实现,但是不能覆盖默认方法。

通过 default 保留字标记默认方法。

Java 7不支持默认方法。

没有在带有名字的包中声明的类都归属默认包。

在程序中,变量在使用前必须确保已经被赋值。

局部变量只有在赋值后才能合法使用。

为了达到这个要求,编译器必须对变量从声明开始到使用的每条路径都进行赋值检查。

表示已经废弃,但为了先后兼容仍然保留。

弃用的Java类或方法仍然是Java语言的一部分,但不建议在新代码中使用。

在未来的Java版本中,弃用的内容会被移除。

对话框是依赖其它窗体创建的新窗体。

弹出对话框通常用作获取用户信息或展示消息。

一种在由网络连接的多个计算机中进行的并行处理。

调用子程序时,用来代替实际传入参数的标识符。

虚参数也叫“形式参数”(有时候会用“变元 argument”表示实参,这时虚参数也叫做“参数”)。

枚举类型的定义中列举了该类型所有可能值。

在Java中,枚举类型是一个类,所有可能的值都是对象。

在GUI编程中,事件指发生在程序控制以外的操作,比如点击鼠标。

程序必须对发生的事件进行响应。

程序控制流程之外的错误或异常情况。

指CPU执行机器语言程序的过程。

CPU会从内存获取(即读取)指令,执行(运行)指令,然后再循环重复该过程。

设为 true 时表示达到某些条件或发生了某种事情。

可利用二进制数中的某个比特位作为标志。

“虚拟参数”的另一种说法。

组成动画的某一幅画面,也是活动记录的另一种说法。

自动回收内存的过程。被回收的内存由对象占用但已不再会对其访问。

编写的代码不仅限于单一数据类型,可适应多种数据类型。

Java集合框架及其它使用了相似技术的类都是泛型编程的实例。

类中的一个实例方法,用来读取类的某个属性值。

通常,属性代表一些实例变量的值。按惯例,getter方法被命名为 getXyz,其中 xyz 是属性的名字。

成员变量的别名。强调类中的成员变量可以在类方法外存在。

用来绘制某些特定地点所必须得数据和方法。Java中的图形上下文是属于 Graphics 类的对象。

图形用户界面是与计算机的现代交互方式。

计算机通过GUI在显示器上展示类似按钮和菜单这样的接口组件,用户可以通过像鼠标点击这样的方式与之交互。

一种优化的数据结构,可以高效搜索、插入和删除对象。哈希表包含对象的地址数组。

对象存储的地址由自身的“哈希代码”决定。通过对象的内容可以高效地计算出地址整数值。

计算机内存中存储对象的区域。

类似Java这样的计算机语言,方便人们阅读,但在执行前需要翻译成机器语言。

其中颜色由3个数值表示(在Java中,实际的数值在0.0到1.0之间)。分别代表色调、饱和度和亮度。

带图形用户界面的编程环境,集成了创建、编辑和执行程序的各种工具。

在程序中可用作名字的一组标识符。

标识符可用作变量名、方法名和类名。

元素在数组中的位置编号。

黑盒的内部实现,比如子程序的实现代码。

不可变对象构造完成后不能改变,因为实例中所有变量都标记为 final。

循环永远不会结束,因为它的循环条件永远判定为 true。

一个类可以继承另一个类。

继承者会从父类继承数据和行为。

指归属于类(或者该类型子类)的对象。

当类用作对象模板时,对象由类中的构造函数创建的对象归属于这个类。

类中的非静态方法,该类的所有实例都具有该方法。

类中的非静态变量,该类的所有实例都包含该变量。

对如何使用类似子程序这样的黑盒子一种通用说法。

接口对其内部发生的情况没有提供任何信息。“interface”同时也是Java中的保留字。

从这个意义上说,接口是一种定义了一个或多个抽象方法的类型。实现该接口的对象必须提供这些方法的定义。

一种执行程序的计算机程序,被执行的程序由某种编程语言编写。

通过从程序中一个接一个读取指令然后逐条执行(将指令翻译为等价的机器语言)。

计算机程序与其它部分的通讯方式,比如向用户展示数据、从用户那里获取信息、读写文件、通过网络发送和获取数据。

与 list 或 set 这样的集合相关联的对象。可用来对该集合进行遍历。

迭代器会轮流访问集合中的每个元素。

一组实现了泛型数据结构的标准类。包括 ArrayList、TreeSet 等。

新的应用程序GUI工具集。

在Java 8中推荐使用。

JavaFX不在本书的讨论范围。

支持编译、运行Java程序的基本软件。

JDK包含命令行编程环境以及JRE。

要编译Java源代码或执行预编译程序时,需要使用JDK。

支持运行已编译的标准Java程序。

JRE包括一个Java虚拟机和所有标准的Java类。

一种解释器和编译器的结合,在解释程序某部分的同时可对其进行编译。

接下来对该部分程序执行时比首次运行更快速。

这样可以大大提高执行速度。现代JVM都使用了即时编译器。

将Java字节码作为机器语言执行的虚拟计算机。

也用来称呼解析字节码程序的计算机程序。

要在计算机上运行Java程序需要使用JVM。

负责对容器中组件进行布局的对象。

进行的部分操作包括设置大小和位置。

不同类型的布局管理器实现的布局策略各不相同。

一组由之指针相互链接的对象数据。

这些指针存储在对象的实例变量中。

链式数据结构包括链表和二叉树。

一种链式数据结构,节点之间由指针串连形成线性链表。

在GUI编程中,可以向对象注册特定事件的触发通知。

因此可以说,对象在“监听”这些事件。

在程序中键入的一组字符序列,表示常量值。

例如,当A在Java程序中出现时,’A'是一个常量字符。

计算机内存由一系列位置组成。

这些位置顺序编号,标识特定位置的编号被称为该位置的地址。

在方法内部声明的变量,只能在该方法内部使用。

代码块中声明变量的有效性,从声明处开始到该代码块的尾部结束。

一种控制结构,重复执行一组指令。

for 循环中的变量,每次执行 for 循环时都会修改循环变量值,通过检查该变量决定是否结束循环。

由计算机能够直接执行的指令组成的编程语言。

机器语言中的指令会被编码成二进制数。

每种类型的计算机都有自己的机器语言。

用其它语言编写的程序必须翻译为该计算的机器语言,才能在它上面执行。

程序和数据可以存储在计算机的主内存中,主内存可以被CPU直接访问。

其它形式的内存,比如磁盘驱动器,虽然也能存储信息,但是唯有主内存可被CPU直接访问。

磁盘分区中的程序和数据只有拷贝到内存中才能被CPU访问。

这种数据结构将一组(Collection)中的某个对象与摸个集合(Set)中的所有对象关联在一起。

定义在类中的变量,但不属于任何方法。

成员变量与本地变量不同,后者在某个方法中定义。

计算机中的内存用来存储程序和数据。

子程序的另一种称呼,在面向对象编程中使用。

方法指包含在类或对象中的子程序。

大型系统中的组件,与系统中其它部分以简单、定义清晰、直接的方式进行交互。

一次执行多个编程任务。

要么在多个任务之间快速来回切换,要么同时逐个执行多个任务。

进行多任务处理时使用多个处理器。

这样,多个任务可以同时逐个执行。

防止两个线程同时访问相同的资源。

在Java中,这种方法应用于多个线程同时访问同步方法或同步语句中的资源。

互斥可以阻止竞态条件,但是可能引发死锁。

模型-视图-控制器模式。

一种用在GUI组件中进行职责划分的策略。

模型代表组件的数据,视图指该模型在屏幕上的展示,控制器负责响应模型变化事件。

在MVC模式中,这些职责由不同的对象负责处理。

Double.NaN表示一种特殊的 double 值,表示未定义或非法值。

链式数据结构中,某个对象的常用称呼。

一种特殊的指针值,表示“没有指向任何东西”。

使用逼近法研究算法的领域,比如实数以及从逼近计算中得到的错误。

一种常见错误,处理时多减或多加了一个元素。

通常是技术错误或者循环时由其它原因过早停止或过度执行造成的。

计算机程序中带有数据(变量)和行为(方法)的实体。

Java中的对象必须以某个类作为创建模板。对象所属的类决定了对象包含的类和方法。

这种类型的值是对象而非基础类型。

类和接口都是对象类型。

一种计算机程序设计和实现的方法。

OOP使用类和对象创建、表示实体及实体间的交互。

在计算机中一直运行的基础软件。

没有操作系统的计算机无法工作。

类似“+”、“<=”或”++”这样的操作符,可以在表达式中计算一个或多个值。

相同操作符可以在不同类型的数据上使用。

比如“+”操作可以同时应用于数字和字符类型。

同一个类中定义了几个名称相同的方法,区别在于各个方法的签名不同。

子类中,对从父类继承的方法重新定义,新定义的方法就是对原方法进行重写。

在Java中,相关类和子包的有名集合称为包。

同时执行多个任务,可以是多个处理器,也可以由一个处理器在多个任务间返复执行。

调用子程序时,参数用来向子程序提供信息。

在执行子程序代码前,子程序调用语句中的“实参”会分配给子程序定义的“虚参数”。

类似 ArrayList 这样,包含了一种或多种类型参数的类型(这里的参数类型是String)。

确定预演中字符串语法结构的过程。

解析字符串用来确定字符串中是否遵循该语言的语法;如果是,那么会确定该字符串是如何根据语法进行创建。

数组是用来存储数量各异的元素。

部分完全数组表示为一个带有追踪元素个数计数器的普通数组。

指屏幕或图片中的“图像元素”。

一幅图像由像素的行和列组成。每个像素的色彩都可以单独设置。

多态是指调用实例方法的意义取决于调用方法时对象的实际类型。

也就是说,如果变量的类型是 var,那么调用方法的语句。

比如 var.action 取决于执行时 var 所指向的对象类型,而非 var 变量的类型。

代表计算机内存中某个地址的值,因此可以看做“指向”具有该地址的位置。

在Java中,变量不存有对象;变量只是指向存储该对象的位置。指针也称作“引用”。

描述如何编写好程序的经验法则。

例如样式规则、程序组织指南都是编程语用学的一部分。

操作符的优先级指,在没有括号的情况下,表达式中多个操作符的作用顺序。

在程序的执行过程中,为了让程序正确运行,前置条件必须判定为 true。

子程序的前置条件是指,为了让子程序正确运行必须满足的前置条件。

子程序的前置条件通常是对传入的子程序的实参值进行的限制。

一种表示元素结合的数据结构,其中每个元素都有自己的“优先级”。

优先级队列具有添加和移除操作。

可以按照任意的顺序添加元素,但移除时总是先移除优先级最低的元素。

(某些版本的优先级队列会先移除优先级最高的元素)

在执行程序的某个节点,该条件的计算结果为 true。

子程序的后置条件在子程序执行结束后必须为 true。

函数的后置条件通常表示为函数的返回值。

基本类型变量存储了真实的值,而非指向数值的指针。

与线程关联的整数值,可以影响线程的执行顺序。

优先级高的线程比优先级低的线程提前执行。

并行编程中的一种经典模式,一个或多个生产者生产的产品被一个或更多的消费者使用。

生产者和消费者设计为可以并行执行。

这里的难点在于,如何安全、高效地从生产者向消费者非配产品。

在Java中,通过阻塞队列实现生产者/消费者模式。

用某种合适的编程语言编写的一组指令,由计算机执行。

用做动词时,表示创建该指令的动作。

用来为计算机编程的一种语言。

编程语言的复杂性,从机器语言到像Java这样的高级语言跨度很大。

在指定上下文中,构成合法通信的一组规范。

协议中规定了合法的消息、传送的时间、期待的恢复类型等。

与实际编程语言相比,伪代码更加接近英语。

并且,通常无需明确地写出过程的每个细节。

由一组元素构成的数据结构。

只能在列表的一头添加数据,在列表的另一头移除数据。

并行编程中可能的错误源。

由于某个线程改变了第二个程序依赖的程序状态(比如变量值),从而引发错误。

计算机主内存的同义词。

然而,从技术角度看,RAM是指在任意时间内都可以同样访问内存地址。

RAM也意味着可以同时读写数据。

用自身的形式定义自己。

特别地,递归子程序可以直接或通过一系列其它子程序间接调用自己。

递归算法的工作方式,通过将一个复杂问题拆分成更小的子问题。

子问题要么可以直接解决,要么可以“递归”使用相同的算法。

颜色由3个数值定义(在Java中,数值的范围从0到255)。

分别表示颜色中的红色、绿色和蓝色组成。

《使出“牛”劲上传资料,三重奖励等你来!

上传30-50个资料奖励10元

上传个资料奖励400元

上传个资料奖励500元

在基础奖金的基础上,对上传不同数量的优质完整资料的用户,追加奖励:

超过100个追加奖励50元;

超过300个追加奖励100元;

超过500个追加奖励200元,

超过1000个追加奖励500元。

三、E币奖励,对上传数量前五名分别奖励数量不等的E币【前往E币商城兑换礼品】

第2、3名:奖励800E币

第4、5名:每人分别奖励500E币

操作系统是指控制和管理整个计算机系统的硬件和软件资源,并合理地组织调度计算机的工作和资源分配,以提供给用户和其他软件方便的接口和环境,是计算机中最基本的系统软件

进程是对运行时程序的封装,是系统进行资源调度和分配的的基本单位,实现操作系统的并发

PCB:保存进程运行期间相关的数据,是进程存在的唯一标志

程序段:存放要执行的代码

数据段:存储程序运行期间的相关数据

创建进程,实际上是创建进程实体中的PCB;撤销进程是撤销进程中的PCB

进程的管理者(操作系统)所需的数据都在PCB中

而程序段和数据段只存放程序本身运行的数据

线程是进程的子任务,是CPU调度和分派的基本单位,用于保证程序的实时性,实现进程内部的并发;线程是操作系统可识别的最小执行和调度单位

一种比线程更加轻量级的存在,协程完全由程序控制,也就是在用户态执行。这样性能得到了很大的提升,不会像线程切换那样消耗资源。协程看上去也是子程序,但执行过程中,在子程序内部可中断,然后转而执行别的子程序,在适当的时候再返回来接着执行

(4)线程和进程的区别

①一个线程只能属于一个进程,而一个进程可以有多个线程,但至少有一个线程。线程依赖于进程而存在

②进程在执行过程中拥有独立的内存单元,而多个线程共享进程的内存

③进程是资源分配的最小单位,线程是CPU调度的最小单位

④线程之间共享同一个进程的地址空间,线程间通信简单,同步复杂,线程创建、销毁和切换简单,速度快,占用内存少,适用于多核分布式系统,但是线程间会相互影响,一个线程意外终止会导致同一个进程的其他线程也终止,程序可靠性弱。而多进程间拥有各自独立的运行地址空间,进程间不会相互影响,程序可靠性强,但是进程创建、销毁和切换复杂,速度慢,占用内存多,进程间通信复杂,但是同步简单,适用于多核、多机分布。(多线程和多进程区别)

⑤线程间通信:由于多线程共享地址空间和数据空间,所以多个线程间的通信是一个线程的数据可以直接提供给其他线程使用,而不必通过操作系统;进程间的通信则不同,它的数据空间的独立性决定了它的通信相对比较复杂,需要通过操作系统

⑥进程间通信方式:管道、系统IPC(包括消息队列、信号量、信号、共享内存等)、以及套接字socket;线程间通信方式:临界区,互斥量,信号量,事件

(5)线程和协程的区别

①一个线程可以多个协程,一个进程也可以单独拥有多个协程

②线程进程是同步的,而协程是异步的

③协程能保留一次调用的状态,每次过程重入时,就相当于进入上一次调用的状态

(6)生产者/消费者模式比较

①使用线程实现生产者/消费者模式时,若干个生产者线程向队列中写入数据,若干个消费者线程从队列中消费数据会存在同步锁,线程状态和上下文切换问题。非常耗费性能

②使用协程实现生产者/消费者模式时,在主线程中生产数据,协程中消费数据。使用yield让协程暂停,和线程的阻塞是有本质区别的。协程的暂停完全由程序控制,线程的阻塞状态是由操作系统内核来进行切换。因此,协程的开销远远小于线程的开销。

分页存储管理,是将一个进程的逻辑地址空间分成若干个大小相等的片,称为页面或页,并为各页加以编号,从0开始。把内存空间分成与页面相同大小的若干个存储块,称为物理块或页框,也同样为它们加以编号。在为进程分配内存时,以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片,称之为“页内碎片”。

在分页系统中的页面其大小应适中,且页面大小应是2的幂,通常为512 B~8 KB

一方面虽然减少内存碎片,提高内存利用率,但是每个进程占用较多的页面,从而导致进程的页表过长,占用大量内存,还会降低页面换进换出的效率。

虽然可以减少页表的长度,提高页面换进换出的速度,但是页内碎片增大。

Linux虚拟地址空间

为了防止不同进程同一时刻在物理内存中运行而对物理内存的争夺和践踏,采用了虚拟内存。

所有进程共享同一物理内存,每个进程只把自己目前需要的虚拟内存空间映射并存储到物理内存上。在每个进程创建加载时,内核只是为进程“创建”了虚拟内存的布局,初始化进程控制表中内存相关的链表,建立好虚拟内存和磁盘文件之间的映射。等到运行到对应的程序时,才会通过缺页异常,来拷贝数据。请求分页系统、请求分段系统和请求段页式系统都是针对虚拟内存的,通过请求实现内存与外存的信息置换。

②内存保护:每个进程运行在各自的虚拟内存地址空间,互相不能干扰对方。虚存还对特定的内存地址提供写保护,可以防止代码或数据被恶意篡改。

③公平内存分配。采用了虚存之后,每个进程都相当于有同样大小的虚存空间。

④当进程通信时,可采用虚存共享的方式实现。

⑤当不同的进程使用同样的代码时,比如库文件中的代码,物理内存中可以只存储一份这样的代码,不同的进程只需要把自己的虚拟内存映射过去就可以了,节省内存

⑥虚拟内存很适合在多道程序设计系统中使用,许多程序的片段同时保存在内存中。当一个程序等待它的一部分读入内存时,可以把CPU交给另一个进程使用。在内存中可以保留多个进程,系统并发度提高

⑦在程序需要分配连续的内存空间的时候,只需要在虚拟内存空间分配连续空间,而不需要实际物理内存的连续空间,可以利用碎片

①虚存的管理需要建立很多数据结构,这些数据结构要占用额外的内存

②虚拟地址到物理地址的转换,增加了指令的执行时间

③页面的换入换出需要磁盘I/O,这是很耗时的

④如果一页中只有一部分数据,会浪费内存

操作系统的程序的内存结构

(1)一个程序本质上都是由BSS段、data段、text段三个组成的

用来存放程序中未初始化的全局变量和静态变量的一块内存区域(静态分配)

存放程序中已初始化的全局变量的一块内存区域(静态分配)

存放程序执行代码的一块内存区域

(2)可执行程序在运行时又多出两个区域:栈区和堆区

由编译器自动释放,存放函数的参数值、局部变量等

用于动态分配内存,位于BSS和栈中间的地址区域

在分配时只是建立了进程虚拟地址空间,并没有分配虚拟内存对应的物理内存。当进程访问这些没有建立映射关系的虚拟内存时,处理器自动触发一个缺页异常。在请求分页系统中,可以通过查询页表中的状态位来确定所要访问的页面是否存在于内存中。每当所要访问的页面不在内存时,会产生一次缺页中断,此时操作系统会根据页表中的外存地址在外存中找到所缺的一页,将其调入内存。

(2)缺页本身是一种中断,与一般的中断一样,需要经过4个处理步骤:

3、转入缺页中断处理程序进行处理

4、恢复CPU现场,继续执行

(3)缺页中断是由于所要访问的页面不存在于内存时,由硬件所产生的一种特殊的中断,与一般的中断存在区别:

1、在指令执行期间产生和处理缺页中断信号

2、一条指令在执行期间,可能产生多次缺页中断

3、缺页中断返回是,执行产生中断的一条指令,而一般的中断返回是,执行下一条指令

fork与vfork都可以创建一个进程,但vfork是由fork封装得来的

使用fork创建一个进程时,子进程只是完全复制父进程的资源。这样得到的子进程独立于父进程,具有良好的并发性。在子进程中,成功的fork( )调用会返回0。在父进程中fork( )返回子进程的pid。如果出现错误,fork( )返回一个负值。

使用vfork创建一个子进程时,操作系统并不将父进程的地址空间完全复制到子进程,用vfork创建的子进程共享父进程的地址空间,也就是说子进程完全运行在父进程的地址空间上。子进程对该地址空间中任何数据的修改同样为父进程所见。对vfork( )的成功调用所产生的结果和fork( )是一样的

fork创建一个子进程是哪个进程先运行取决于系统的调度算法。

vfork创建一个进程时,vfork保证子进程先运行,当调用exec或exit之后,父进程才可能被调读运行

Linux采用了写时复制的方法,以减少fork时对父进程空间进程整体复制带来的开销。写时复制是一种采取了惰性优化方法来避免复制时的系统开销

①fork( )的子进程拷贝父进程的数据段和代码段;vfork( )的子进程与父进程共享数据段

②fork( )的父子进程的执行次序不确定;vfork( )保证子进程先运行,在它调用exec或exit之后父进程才可能被调度运行。若在调用这两个函数之前子进程依赖于父进程的进一步动作,则会导致死锁。

如何修改文件最大句柄数

linux默认最大文件句柄数是1024个,在linux服务器文件并发量比较大的情况下,系统会报"too many open files"的错误。故在linux服务器高并发调优时,往往需要预先调优Linux参数,修改Linux最大文件句柄数。

①ulimit -n ,将当前进程的最大句柄数修改为指定的参数(对当前进程有效)

②修改Linux系统参数(对所有进程有效)

(1)并发(在单核cpu上的多任务)

宏观上看起来两个程序在同时运行,从微观上看两个程序的指令是交织着运行的。在单个周期内只运行了一个指令。这种并发并不能提高计算机的性能,只能提高效率。

(2)并行(多核cpu,不同任务在不同核上)

指严格物理意义上的同时运行,两个程序分别运行在两个核上,两者之间互不影响,单个周期内每个程序都运行了自己的指令,提高了计算机的效率和性能

MySQL的端口号查询和修改

修改:编辑/etc/my.cnf文件,早期版本有可能是my.conf文件名,增加端口参数,并且设定端口,注意该端口未被使用,保存退出

页式内存管理,内存分成固定长度的一个个页片。操作系统为每一个进程维护了一个从虚拟地址到物理地址的映射关系的数据结构,叫页表,页表的内容就是该进程的虚拟地址到物理地址的一个映射。页表中的每一项都记录了这个页的基地址。通过页表,由逻辑地址的高位部分先找到逻辑地址对应的页基地址,再由页基地址偏移一定长度就得到最后的物理地址,偏移的长度由逻辑地址的低位部分决定。一般情况下,这个过程都可以由硬件完成,所以效率还是比较高的。页式内存管理的优点就是比较灵活,内存管理以较小的页为单位,方便内存换入换出和扩充地址空间

单核机器上写多线程程序,是否需要考虑加锁

在单核机器上写多线程程序,仍需要线程锁。因为线程锁通常用来实现线程的同步和通信。在单核机器上的多线程程序,仍存在线程同步的问题。因为在抢占式操作系统中,通常为每个线程分配一个时间片,当某个线程时间片耗尽时,操作系统会将其挂起,然后运行另一个线程。如果这两个线程共享某些数据,不使用线程锁的前提下,可能会导致共享数据修改引起冲突

线程在切换的过程中需要保存当前线程Id、线程状态、堆栈、寄存器状态等信息。其中寄存器主要包括SP PC EAX等寄存器,其主要功能如下:

SP:堆栈指针,指向当前栈的栈顶地址

PC:程序计数器,存储下一条将要执行的指令

EAX:累加寄存器,用于加法乘法的缺省寄存器

信号量是一种特殊的变量,可用于线程同步。它只取自然数值,只支持PV操作

互斥量又称互斥锁,主要用于线程互斥,不能保证按序访问,可以和条件锁一起实现同步

条件变量,又称条件锁,用于在线程之间同步共享数据的值。条件变量提供一种线程间通信机制:当某个共享数据达到某个值时,唤醒等待这个共享数据的一个/多个线程

游戏服务器应该为每个用户开辟一个线程还是一个进程,为什么?

游戏服务器应该为每个用户开辟一个进程。因为同一进程间的线程会相互影响,一个线程死掉会影响其他线程,从而导致进程崩溃。因此为了保证不同用户之间不会相互影响,应该为每个用户开辟一个进程

死锁发生的条件和死锁的解决

死锁是指两个或两个以上进程在执行过程中,因争夺资源而造成的下相互等待的现象

进程对所分配到的资源不允许其他进程访问,若其他进程访问该资源,只能等待,直至占有该资源的进程使用完成后释放该资源;

进程获得一定的资源后,又对其他资源发出请求,但是该资源可能被其他进程占有,此时请求阻塞,但该进程不会释放自己已经占有的资源

进程已获得的资源,在未完成使用之前,不可被剥夺,只能在使用后自己释放

进程发生死锁后,必然存在一个进程-资源之间的环形链

解决死锁的方法即破坏上述四个条件之一,主要方法如下:

①资源一次性分配,从而剥夺请求和保持条件

②可剥夺资源:当进程新的资源未得到满足时,释放已占有的资源,从而破坏不可剥夺的条件

③资源有序分配法:系统给每类资源赋予一个序号,每个进程按编号递增的请求资源,释放则相反,从而破坏环路等待的条件

操作系统中的结构体对齐,字节对齐

①平台原因(移植原因):不是所有的硬件平台都能访问任意地址上的任意数据的;某些硬件平台只能在某些地址处取某些特定类型的数据,否则抛出硬件异常。

②性能原因:数据结构(尤其是栈)应该尽可能地在自然边界上对齐。原因在于,为了访问未对齐的内存,处理器需要作两次内存访问;而对齐的内存访问仅需要一次访问。

①数据成员对齐规则:结构(struct)(或联合(union))的数据成员,第一个数据成员放在offset为0的地方,以后每个数据成员的对齐按照#pragma pack指定的数值和这个数据成员自身长度中,比较小的那个进行。

②结构体作为成员:如果一个结构里有某些结构体成员,则结构体成员要从其内部最大元素大小的整数倍地址开始存储

通过预编译命令#pragma pack(n),n=1,2,4,8,16来改变这一系数,其中的n就是指定的“对齐系数”

Linux的四种锁机制

(1)互斥锁(mutex)

用于保证在任何时刻,都只能有一个线程访问该对象。当获取锁操作失败时,线程会进入睡眠,等待锁释放时被唤醒

分为读锁和写锁。处于读操作时,可以允许多个线程同时获得读操作。但是同一时刻只能有一个线程可以获得写锁。其它获取写锁失败的线程都会进入睡眠状态,直到写锁释放时被唤醒。 注意:写锁会阻塞其它读写锁。当有一个线程获得写锁在写时,读锁也不能被其它线程获取;写者优先于读者。适用于读取数据的频率远远大于写数据的频率的场合

在任何时刻同样只能有一个线程访问对象。但是当获取锁操作失败时,不会进入睡眠,而是会在原地自旋,直到锁被释放。这样节省了线程从睡眠状态到被唤醒期间的消耗,在加锁时间短暂的环境下会极大的提高效率。但如果加锁时间过长,则会非常浪费CPU资源

在修改数据时,首先需要读取数据,然后生成一个副本,对副本进行修改。修改完成后,再将老数据update成新的数据。使用RCU时,读者几乎不需要同步开销,既不需要获得锁,也不使用原子指令,不会导致锁竞争,因此就不用考虑死锁问题了。而对于写者的同步开销较大,它需要复制被修改的数据,还必须使用锁机制同步并行其它写者的修改操作。在有大量读操作,少量写操作的情况下效率非常高。

生产者消费者问题利用互斥锁和条件变量可以很容易解决,条件变量这里起到了替代信号量的作用

即输入/输出设备,是用于计算机系统与人通信或与其他机器通信的所有设备,以及所有外存设备

(2)进程的五种基本状态

①创建状态:进程正在被创建

②就绪状态:进程被加入到就绪队列中等待CPU调度运行(等待被调度使用cpu的运行权)

③执行状态:进程正在被运行

④等待阻塞状态:进程因为某种原因,比如等待I/O设备,而暂时不能运行。

⑤终止状态:进程运行完毕

当多个进程竞争内存资源时,会造成内存资源紧张,并且,如果此时没有就绪进程,处理机会空闲,I/0速度比处理机速度慢得多,可能出现全部进程阻塞等待I/O。在交换技术上,将内存暂时不能运行的进程,或者暂时不用的数据和程序,换出到外存,来腾出足够的内存空间,把已经具备运行条件的进程,或进程所需的数据和程序换入到内存。从而出现了进程的挂起状态:进程被交换到外存,进程状态就成为了挂起状态。

①交换技术:换出一部分进程到外存,腾出内存空间。

②虚拟存储技术:每个进程只能装入一部分程序和数据。

(4)活动阻塞,静止阻塞,活动就绪,静止就绪

①活动阻塞:进程在内存,但是由于某种原因被阻塞了。

②静止阻塞:进程在外存,同时被某种原因阻塞了。

③活动就绪:进程在内存,处于就绪状态,只要给CPU和调度就可以直接运行。

④静止就绪:进程在外存,处于就绪状态,只要调度到内存,给CPU和调度就可以运行

活动就绪 —— 静止就绪(内存不够,调到外存)

活动阻塞 —— 静止阻塞(内存不够,调到外存)

执行 —— 静止就绪(时间片用完)

为了解决文件共享问题,Linux引入了软链接和硬链接。除了为Linux解决文件共享使用,还带来了隐藏文件路径、增加权限安全及节省存储等好处。

1个inode号(索引节点号)对应多个文件名,即同一个文件使用了不同的别名

文件用户数据块中存放的内容是另一个文件的路径名指向,即是一个普通文件,有自己独立的inode,但是其数据块内容比较特殊。

大端是指低字节存储在高地址;小端存储是指低字节存储在低地址。我们可以根据联合体来判断该系统是大端还是小端。因为联合体变量总是从低地址存储。

用户态和内核态是操作系统的两种运行级别,两者最大的区别就是特权级不同。用户态拥有最低的特权级,内核态拥有较高的特权级。运行在用户态的程序不能直接访问操作系统内核数据结构和程序。内核态和用户态之间的转换方式主要包括:系统调用,异常和中断。

(1)如何设计server,使得能够接收多个客户端的请求

一个程序由多个线程在同时执行

如果并发的线程数量很多,并且每个线程都是执行一个时间很短的任务就结束了,这样频繁创建线程就会大大降低系统的效率,因为频繁创建线程和销毁线程需要时间。通过线程池使得线程可以服用,在执行完一个任务,而不被销毁,从而继续执行其他的任务

单个线程通过记录跟踪每一个Sock(I/O流)的状态来同时管理多个I/O流

(1)改进连接时新建线程的效率低和死循环问题

①提前创建好一个线程池,用生产者消费者模型,创建一个任务队列,队列作为临界资源,有了新连接,就挂在到任务队列上,队列为空所有线程睡眠。

(2)唤醒被阻塞的socket线程

(3)确定当前线程是繁忙还是阻塞

同步的时候用一个互斥量,在访问共享资源前对互斥量进行加锁,在访问完成后释放互斥量上的锁。对互斥量进行加锁以后,任何其他试图再次对互斥量加锁的线程将会被阻塞直到当前线程释放该互斥锁。如果释放互斥锁时有多个线程阻塞,所有在该互斥锁上的阻塞线程都会变成可运行状态,第一个变为运行状态的线程可以对互斥量加锁,其他线程将会看到互斥锁依然被锁住,只能回去再次等待它重新变为可用。在这种方式下,每次只有一个线程可以向前

两个进程访问临界区资源,会不会出现都获得自旋锁的情况

单核cpu,并且开了抢占可以造成这种情况

当用户有操作(鼠标,键盘等)时,系统会将这些时间转化为消息。每个打开的进程系统都为其维护了一个消息队列,系统会将这些消息放到进程的消息队列中,而应用程序会循环从消息队列中取出来消息,完成对应的操作

指运行在使用者空间的程序向操作系统内核请求需要更高权限运行的服务。系统调用提供了用户程序与操作系统之间的接口

操作系统中的状态分为核心态和用户态。大多数系统交互式操作需求在内核态执行。如设备IO操作或者进程间通信。特权指令:一类只能在核心态下运行而不能在用户态下运行的特殊指令。不同的操作系统特权指令会有所差异,但是一般来说主要是和硬件相关的一些指令。用户程序只在用户态下运行,有时需要访问系统核心功能,这时通过系统调用接口使用系统调用。

应用程序有时会需要一些危险的、权限很高的指令,如果把这些权限放心地交给用户程序是很危险的(比如一个进程可能修改另一个进程的内存区,导致其不能运行),但是又不能完全不给这些权限。于是有了系统调用,危险的指令被包装成系统调用,用户程序只能调用而无权自己运行那些危险的指令。另外,计算机硬件的资源是有限的,为了更好的管理这些资源,所有的资源都由操作系统控制,进程只能向操作系统请求这些资源。操作系统是这些资源的唯一入口,这个入口就是系统调用。

(1)用户态切换到内核态的3种方式

用户进程主动要求切换到内核态的一种方式,用户进程通过系统调用申请操作系统提供的服务程序完成工作。而系统调用的机制其核心还是使用操作系统为用户特别开放的一个中断来实现

当CPU在执行运行在用户态的程序时,发现了某些事件不可知的异常,这是会触发由当前运行进程切换到处理此。异常的内核相关程序中,也就到了内核态,比如缺页异常

当外围设备完成用户请求的操作之后,会向CPU发出相应的中断信号,这时CPU会暂停执行下一条将要执行的指令,转而去执行中断信号的处理程序,如果先执行的指令是用户态下的程序,那么这个转换的过程自然也就发生了有用户态到内核态的切换。

执行了一个中断响应的过程,因为系统调用实际上最终是中断机制实现的

①从当前进程的描述符中提取其内核栈的ss0及esp0信息。

②使用ss0和esp0指向的内核栈将当前进程的cs,eip,eflags,ss,esp信息保存起来,这个过程也完成了由用户栈找到内核栈的切换过程,同时保存了被暂停执行的程序的下一条指令。

③将先前由中断向量检索得到的中断处理程序的cs,eip信息装入相应的寄存器,开始执行中断处理程序,这时就转到了内核态的程序执行了

(3)为什么要分内核态和用户态

为了安全性。在cpu的一些指令中,有的指令如果用错,将会导致整个系统崩溃。分了内核态和用户态后,当用户需要操作这些指令时候,内核为其提供了API,可以通过系统调用陷入内核,让内核去执行这些操作。

源码到可执行文件的过程

除了最基本的进程、线程管理、内存管理外,将文件系统,驱动,网络协议等等都集成在内核里面

稳定性差,开发过程中的bug经常会导致整个系统挂掉

内核中只有最基本的调度、内存管理。驱动、文件系统等都是用户态的守护进程去实现的

稳定性好,驱动等的错误只会导致相应进程死掉,不会导致整个系统都崩溃

正常情况下,子进程是通过父进程创建的,子进程再创建新的进程。子进程的结束和父进程的运行是一个异步过程,即父进程永远无法预测子进程到底什么时候结束。 当一个进程完成它的工作终止之后,它的父进程需要调用wait()或者waitpid()系统调用取得子进程的终止状态

一个父进程退出,而它的一个或多个子进程还在运行,那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养,并由init进程对它们完成状态收集工作

一个进程使用fork创建子进程,如果子进程退出,而父进程并没有调用wait或waitpid获取子进程的状态信息,那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵尸进程。僵尸进程是一个进程必然会经过的过程:这是每个子进程在结束时都要经过的阶段。

如果进程不调用wait / waitpid的话, 那么保留的那段信息就不会释放,其进程号就会一直被占用,但是系统所能使用的进程号是有限的,如果大量的产生僵死进程,将因为没有可用的进程号而导致系统不能产生新的进程。

通过kill发送SIGTERM或者SIGKILL信号消灭产生僵尸进程的进程,它产生的僵死进程就变成了孤儿进程,这些孤儿进程会被init进程接管,init进程会wait()这些孤儿进程,释放它们占用的系统进程表中的资源

子进程退出时向父进程发送SIGCHILD信号,父进程处理SIGCHILD信号。在信号处理函数中调用wait进行处理僵尸进程。

fork两次,原理是将子进程成为孤儿进程,从而其的父进程变为init进程,通过init进程可以处理僵尸进程。

GDB 是自由软件基金会的软件工具之一。它的作用是协助程序员找到代码中的错误。如果没有GDB的帮助,程序员要想跟踪代码的执行流程,唯一的办法就是添加大量的语句来产生特定的输出。但这一手段本身就可能会引入新的错误,从而也就无法对那些导致程序崩溃的错误代码进行分析。

GDB的出现减轻了开发人员的负担,他们可以在程序运行的时候单步跟踪自己的代码,或者通过断点暂时中止程序的执行。此外,他们还能够随时察看变量和内存的当前状态,并监视关键的数据结构是如何影响代码运行的。

条件断点是当满足条件就中断程序运行

调用者调用了某个函数,等待这个函数返回,期间什么也不做,不停的去检查这个函数有没有返回,必须等这个函数返回才能进行下一步动作

非阻塞等待,每隔一段时间就去检测IO事件是否就绪。没有就绪就可以做其他事。

用套接口进行信号驱动IO,安装一个信号处理函数,进程继续运行并不阻塞,当IO时间就绪,进程收到SIGIO信号。然后处理IO事件。

(4)IO复用/多路转接IO

linux用select/poll函数实现IO复用模型,这两个函数也会使进程阻塞,但是和阻塞IO所不同的是这两个函数可以同时阻塞多个IO操作。而且可以同时对多个读操作、写操作的IO函数进行检测。知道有数据可读或可写时,才真正调用IO操作函数

linux中,可以调用aio_read函数告诉内核描述字缓冲区指针和缓冲区的大小、文件偏移及通知的方式,然后立即返回,当内核将数据拷贝到缓冲区后,再通知应用程序。

事件循环就是不停循环等待时间的发生,然后将这个事件的所有处理器,以及他们订阅这个事件的时间顺序依次依次执行。当这个事件的所有处理器都被执行完毕之后,事件循环就会开始继续等待下一个事件的触发,不断往复。

①设置一个生产者消费者队列,作为临界资源

②初始化n个线程,并让其运行起来,加锁去队列取任务运行

③当任务队列为空的时候,所有线程阻塞

④当生产者队列来了一个任务后,先对队列加锁,把任务挂在到队列上,然后使用条件变量去通知阻塞中的一个线程

样式扫描和处理语言。它允许创建简短的程序,这些程序读取输入文件、为数据排序、处理数据、对输入执行计算以及生成报表,还有无数其他的功能。

内存是用于存放数据的硬件,程序执行前需要先放到内存中才能被CPU处理。内存有一个个小房间,其为存储单元,内存地址从0开始,每个地址对应一个存储单元

逻辑地址空间:指一个源程序在编译或者链接装配后指令和数据所用的所有相对地址的空间;

物理地址空间:内存中物理单元的集合

注意:编写的代码会翻译成CPU能识别的指令,其只需关心逻辑地址(相对地址),实际放入内存中再想办法根据起始位置得到物理地址(绝对地址)。

通过地址转换将逻辑地址转换为物理地址

在CPU中设置一对上、下限寄存器,存放进程的上、下限地址。进程的指令要访问某个地址时,CPU检查是否越界

②利用重定位寄存器和界地址寄存器判断

重定位寄存器存放的是进程的起始物理地址,界地址寄存器中存放的是进程的最大逻辑地址

内部碎片:分配给某进程的内存区域中,有些部分没用上

外部碎片:指内存中的某些空闲分区由于太小而难以利用

拼接/拼凑技术:代价较高

离散分配方式:允许将作业/进程离散放到多个不相邻的分区,避免拼接

为用户进程分配的可以是一些分散的内存空间

内存分为固定的块,按物理结构划分,会有内部碎片;主存、进程都划分为大小固定的块,进程在执行时,以块为单位申请主存中的块空间;进程中的块为页,内存中的块为页框。系统为每个进程建立一张页表,页表记录页面在内存中对应的物理块号,实现从页号到物理块号的地址映射;页式管理中地址空间是一维的;

内存块的大小不固定,按逻辑结构划分,会有外部碎片;段式管理方式按照用户进程中的自然段划分逻辑空间。段内要求连续,段间不要求连续。段号和段内偏移量必须由用户显示提供。方便编程、共享、保护、动态链接和增长。

基本分段和基本分页的结合,会有内部碎片;作业的逻辑地址分为:段号、页号和页内偏移量;采用分段方法来分配和管理用户地址空间,采用分页方法来管理物理存储空间;开销大

预先设定覆盖段,覆盖掉暂时不用的内容,通常在同一个程序之中进行

把处于等待的程序暂时移到外存,通常在不同程序之间进行

允许一个作业分多次调入内存,其实现需要建立在离散分配的内存管理方式基础上

页表机制:通过查表获取相关信息;

缺页中断机构:要访问页不在内存时产生缺页中断

地址变换机构:把逻辑地址变换成物理地址

当访问一个内存中不存在的页,并且内存已满,则需要从内存中调出一个页或将数据送至磁盘对换区,替换一个页,这种现象叫做缺页置换

Belady现象:进程的缺页次数随着分配给进程的页框个数的增加而增加

柱面号、盘面号、扇区号

寻道时间:将磁头移动到指定磁道所需要的时间

延迟时间:磁头定位到目标扇区所需要的时间

传输时间:从磁盘读出或向磁盘写入数据所经历的时间

启动时间(一般忽略):控制器的启动时间

算法规则:根据进程请求访问磁盘的先后顺序进行调度

算法规则:优先处理与当前磁道最近的磁道,可以保证每次寻道时间最短,但不能保证总的寻道时间最短(贪心算法思想,选择眼前最优,但是总体未必最优)

算法规则:在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求,只有在磁头移动到最外侧磁道时才会往内移动;移动到最内侧磁道时才会往外移动;

优点:性能较好,平均寻道时间较短,不会产生饥饿现象

缺点:①只有到达最边上的磁道时才能改变磁头移动方向。②各个位置磁道的响应频率不平均

磁头朝某个特定方向移动时才处理磁道访问请求,而返回时直接快速移动至起始端而不处理任何请求

优点:比起扫描算法,对于各个位置磁道的响应频率很平均

缺点:比起扫描算法,平均寻道时间更长

我要回帖

更多关于 某文件系统采用索引文件结构 的文章

 

随机推荐