第一章:导论
1. 计算机系统的四个组成成分:计算机硬件、操作系统、系统程序和用户。可以大致分为硬件、软件和数据。
定义: 现代通用计算机系统由一个或多个CPU和若干设备控制器通过共同的总线相连而成,该总线提供了对共享内存的访问。
设备控制器维护一定量的本地缓冲存储和一组特定用途的寄存器。
2. 硬件:CPU(处理器),内存,输入和输出设备。
3. 可以将操作系统看成资源分配器,将计算机系统的资源进行有效分配,来优化资源使用,以解决CPU时间、内存空间、文件存储空间、I/O设备等问题。
操作系统是一直运行在计算机上的程序(通常称为内核),其他程序则为系统程序和应用程序。
4. 打开电源,计算机开始运行时,计算机运行一个初始化程序,成为计算机硬件中的固件,一般位于ROM 或EEPROM中。
5. 事件的发生通常通过硬件或软件中断来表示。事件总由中断或陷阱引起的,陷阱(或异常)是一种软件中断,源于出错(除0操作)或源于用户程序的一个特别请求(完成操作系统服务)。
①硬件可以随时通过系统总线向CPU发出信号,触发中断。
②软件通过执行特别的操作如系统调用来触发中断。
6. 中断要将控制转移到合适的中断处理程序中,简单方法是调用一个通用子程序检查中断信息,然后这个子程序会调用相应的中断处理程序。 →一般可以使用中断处理子程序的指针表。一般指针表位于低地址内存,可以通过唯一设备号索引。
中断系统结构还必须保存被中断的指令的地址,以及保存当前的状态,然后中断处理之后,被中断的计算重新开始。
7. RAM:随机访问内存。 DRAM:动态随机访问内存。
8. 指令运行周期: 取指令、译码、取操作数、执行操作数、存结果。
9. I/O设备操作:设备驱动程序在设备控制器中装载适当的寄存器→设备控制器检查寄存器的内容决定采取什么操作→控制器从设备向其本地缓冲区传输数据→完成数据传输后设备控制器会通过中断通知设备驱动程序已完成操作。
10. 单处理器系统:有一个主CPU能执行一个通用指令集,包括来自用户进程的指令。还可能包括其他特定目的的处理器,但他们只运行一个受限的指令集,并不运行用户进程。
11. 多处理器系统(并行系统 or 紧耦合系统):有多个紧密通信的cpu,共享计算机总线。
优点: ①增加吞吐量 ②规模经济 ③增加可靠性
两种类型:
1)非对称多处理:每个处理器都有各自特定的任务,一个主处理器控制系统,其他处理器或向主处理器要任务或做预先定义的任务。 主从关系
2)对称多处理SMP:所有处理器对等,允许进程和资源(包括内存)在各个处理器之间动态共享,能降低处理器之间的差异。
刀片处理器blade server:将多处理器板、I/O板和网络板全部置于同一底板上。
12. 集群系统clustered system:由两个或多个独立的系统耦合起来的。
定义:集群计算机共享存储并通过局域网络连接或更快的内部连接。
非对称集群:一台机器处于热备份模式,监视活动服务器,另一台运行应用程序。
对称集群:两个或多个主机都运行应用程序,互相监视,充分利用了现有硬件,所以更高效。
并行集群:允许多个主机访问共享存储设备上的相同数据。
WAN集群
13. 操作系统结构:→多道程序处理能力
多道程序设计:通过组织作业(编码或数据)使CPU总有一个作业可执行,从而提高了CPU利用率。
→操作系统将作业池中的多个任务保存在内存中,作为一个作业集。(这个作业集是作业池作业集的子集,作业池刚开始存储在磁盘中。)
分时操作系统:采用CPU调度和多道程序设计以提供用户分时计算机的一小部分。分时操作系统允许多个用户同时共享计算机。
→分时操作系统中需要操作系统保证合理的响应时间,通过交换得到,交换时进程被换入内存或由内存换出到磁盘,使用虚拟内存来完成交换。
分时系统通过定时器和调度算法通过cpu迅速循环进程,给其中的每一用户分配资源
分时操作系统也必须提供文件系统和磁盘管理。
14. 虚拟内存:优点是程序可以比物理内存大,将内存抽象成一个庞大且统一的存储数组,将用户理解的逻辑内存与真正的物理内存区分。
15. 进程:装入到内存并执行的程序通常称为进程。
16. 双重模式操作:两种独立的操作模式:用户模式和内核模式,使用模式位(mode bit)来区分,用户模式1,内核模式0
用户应用程序执行→用户模式; 操作系统获得了对计算机的控制,就处于内核模式
保护操作系统和用户程序不受错误用户程序影响:将能引起损害的机器指令作为特权指令,如果在用户模式下试图执行特权指令,则硬件不执行,且将其以陷阱形式告知操作系统。
一个特权指令:转换到用户模式
17. 系统调用:是一种进程请求操作系统执行动作的方法。
系统调用通常采用陷阱到中断向量中的一个指定位置的方式。
当系统调用被执行时,硬件会将它作为软件中断,控制权会通过中断向量转交到操作系统中的中断处理程序中,模式位设置成内核模式。
18. 定时器timer:可是使用定时器防止用户程序运行时间过长。
19. 进程管理:
进程是系统工作的单元,系统由多个进程组成,其中一些是操作系统进程,其他是用户进程。可以将进程视为作业或分时程序。
操作系统负责与进程相关的活动:
- 创建和删除用户进程和系统进程
- 挂起和重启进程
- 提供进程同步机制和通信机制
- 提供死锁处理机制
20. 内存管理:
内存通常是CPU所能直接寻址和访问的唯一大容量存储器。为了改善CPU的利用率和计算机的响应速度,通用计算机必须在内存中保留多个程序,从而产生对内存管理的需要。
操作系统相关的内存管理活动:
- 记录内存的哪部分正在被使用及被谁使用
- 当有内存空间时,决定哪些进程可以装入内存
- 根据需要分配和释放内存空间
21. 存储管理:
文件系统管理:文件是由其创建者定义的一组相关信息的集合。文件表示程序和数据。
操作系统相关的文件系统管理活动:
- 创建和删除文件
- 创建和删除目录来组织文件
- 提供操作文件和目录的原语
大容量存储器管理:
- 空闲空间管理
- 存储空间管理
- 硬盘调度
22. 信息通常保存在一个存储系统中(如内存)。当使用它时,它会被临时地赋值到更快的存储系统中→高速缓存中。在高速缓存中的信息可以被直接使用。
磁盘到内存的数据传递通常是由操作系统控制的。
23. I/O系统包括:
①一个包括缓冲、高速缓存和假脱机的内存管理部分。
②通用设备驱动器接口
③特定的硬件设备的驱动程序。
24. 保护是一种控制进程或用户对计算机系统资源的访问的机制。
安全的主要工作是防止系统不受外部或内部攻击。
25. 分布式系统是将一组物理上分开来的、各种可能异构的计算机系统通过网络连接在一起,为用户提供系统所维护的各种资源的计算机的集合。
网络就是两个或多个系统之间的通信路径。
26. 专用系统: 实时嵌入式系统、多媒体系统、手持系统
27. 计算机环境:
客户机-服务器计算:
→计算机服务器系统提供了一个接口,以接收用户所发送的执行操作的请求。
→文件服务器系统提供文件系统接口,以便客户机能创建、更新、访问和删除文件
28. 对等计算: 对等系统模式p2p。两种方法决定有哪些服务器可用:
①当一个节点加入网络时,它用网络集中查询服务来注册它的服务。
②作为客户机对等行动必须首先通过向所有网络中的其他节点广播服务请求,以发现哪个节点提供所需服务。
第二章:操作系统结构
1. 操作系统服务提供的函数:
1)用户界面:①命令行界面 ②图形用户界面
2)程序执行:系统能将程序装入内存并运行程序,系统必须能结束执行(正常或不正常的执行)
3)I/O操作:
4)文件系统操作
5)通信:①发生在同一台计算机运行的两个程序之间 ②运行在网络连接起来的不同计算机进程之间
6)错误检测 7)资源分配: 8)统计
9)保护和安全:保护即确保所有对系统资源的访问是受控的;安全指不受外界侵犯,保护外部I/O设备,记录所有非法闯入的企图。
2. 操作系统用户界面:
1)命令解释程序:作用是获取并执行用户指定的下一条指令。
执行命令有两种方法:① 命令解释程序本身包含代码以执行这些命令。②由系统程序实现绝大多数命令,命令解释程序只需要用命令来识别文件以装入内存中并执行。
2)图形用户界面:
3. 系统调用:C/C++/汇编指令编写
一般应用程序开发人员使用应用程序接口(API)设计程序,隐藏了系统调用。
API→程序的可移植性
向操作系统传递参数:
①通过寄存器传递,但有时需要的参数数量比寄存器数量多
②保存在内存的块和表中,并将块的地址通过寄存器传递。
③参数也可以通过程序放入堆栈中,并通过操作系统弹出。
4. 系统调用类型:
1)进程控制:执行的操作见P42
在非正常中断或陷入错误陷阱时,可能会有内存信息转储并产生一个错误信息,内存信息转储通常写到磁盘上,并被调试器检查和确定问题原因。不管是正常终止还是非正常终止,操作系统都会将控制权交给调用命令解释器。命令解释器接着读取下一条指令。
调用命令解释器:
①交互系统中,假定用户会采用合适的指令处理错误,它只简单的读取下一条指令。
②GUI系统中,弹出窗口提醒用户出错,并请求建议。
③批处理系统,命令解释器会终止整个作业,并继续下一个作业。也可以使用控制卡命令(是管理进程执行的命令)定义错误级别,命令解释器根据错误级别自动觉得下一个动作。
命令解释器可能会装入和执行一个新的程序,那么在这个新程序结束之后,需要将控制权返回现有程序,必须保存现有程序的内存镜像。
进程和作业控制:
①单任务操作系统举例MS-DOS:它是一个单任务操作系统 ,使用一种简单的方法执行程序且不创建新进程。
它将程序装入内存,并改写它自己的绝大部分,以便为新程序提供尽可能多的空间,然后它将指令指针设为程序的第一条指令,然后运行程序,或者一个错误引起中断,或者程序执行一个系统调用以终止。错误代码会保存在系统内存中以便在后面使用。然后,命令解释程序中尚未改写的部分会重新开始执行,其首要任务是从磁盘中重新装入命令解释器的其他部分,当完成任务时,命令解释器会向用户或下一程序提供上次的错误代码。
②多任务操作系统举例FREEBSD:命令解释程序在另一程序执行时可继续执行。shell使用fork()系统调用启动新程序,所选择的程序通过exec()装入内存,开始执行。根据命令发布的方式,shell可以等待程序执行完成,也可以在后台执行,后台执行时可以接收下一命令。可以调用exit()系统调用来终止。
2)文件管理:需要确定文件或目录的文件属性,文件属性包括文件名、文件类型、保护模式和记账信息。
3)设备管理:设备可以是物理设备,也可以是抽象或虚拟的设备(如文件
4)信息维护:进程信息(读取和设置进程属性),日期,系统信息
5)通信:两种通信模式→消息传递模型和共享内存模型
①消息传递模型: 客户机→服务器
通信进程之间通过彼此交换消息来交换信息。通信前必须打开连接。必须知道通信实体的名称→ 主机名,进程名(通常转换成标识符以便操作系统引用)。
消息传递对交换少量数据很有用,这是因为不必避免冲突。对计算机间的通信,也比共享内存更容易实现。
②共享内存模型:进程的变体→线程一般通过读写公共区域来通信。进程可以通过shared memory create和shared memory attach系统调用来获得其他进程所拥有的内存区域的访问权。
共享内存允许最大速度的通信并且十分方便,这是因为当通信发生在计算机内,它能以内存的速度进行。但在保护和同步方面,共享内存模型存在一定问题。
5. 系统程序:绝大多数操作系统是由应用和系统程序而不是系统调用所决定的。
计算机逻辑层次:硬件→操作系统→系统程序→应用程序
1)文件管理
2)状态信息
3)文件修改
4)程序语言支持
5)程序装入和执行
6)通信
6. 操作系统的设计和实现
1)需求可分为两个基本类:用户目标和系统目标。
2)策略policy和机制mechanism: 机制决定如何做,是底层架构,策略决定做什么。系统需要通用机制。
3)实现:使用高级语言或至少是系统实现语言来实现操作系统的优点&缺点:→P49
7. 操作系统结构:
1)两个系统
MS-DOS结构:没有很好的区分接口和功能层次。主要是利用最小的空间实现最多的功能,所以没有被仔细的划分成模块。受限于当时的硬件和本身的结构。
结构: 应用程序→系统驻留程序→MS-DOS设备驱动→ROM-DOS设备驱动→ROM BOIS设备驱动
UNIX结构:由内核和系统程序两个独立部分组成。内核进一步分成一系列接口和驱动程序。
结构: 物理硬件→内核→系统调用接口
内核通过系统调用以提供文件系统、CPU调度,内存管理和其他操作系统功能。单一式结构使得unix很难增强。
这两个系统都受到当时硬件功能限制。
2)分层方法:
最底层0层为硬件,最高层层N为用户接口。
操作系统层可作为抽象对象来实现,该兑现包括数据和操作这些数据的操作。
优点:构造和调试简单化。每层只能利用较低层的功能和 服务。每层只能利用较低层的功能,简化了调试和系统验证。
困难:如何对层进行详细定义,因为一层只能使用它下面的较低层。还有一个问题在于它与其他方法相比效率较差。每层都为系统调用增加了额外的开销。
3)微内核技术:模块化内核→将所有非基本部分从内核中移走,并将它们实现为系统程序或用户程序。
微内核通常包括最小的进程和内存管理以及通信功能。它的主要功能是使客户程序和运行在用户空间的各种服务之间进行通信。通信以消息传递形式提供。
优点:便于扩充操作系统。因为绝大多数服务是作为用户而不是作为内核进程来运行的,因此微内核也提供了更好的安全性和可靠性,如果一个服务器出错,那么操作系统其他部分不会受影响。
QNX→一个基于微内核设计的实时操作系统,提供了消息传递和进程调度服务。处理底层网络通信和硬件中断。
微内核必须忍受由于系统功能总开销的增加而导致的系统性能下降。
4)模块:
最新的操作系统设计方法是面向对象编程技术来生成模块化的内核。内核有一组核心部件,以及在启动或运行时对附加服务的动态连接。→使用动态加载模块。在现代的UNIX,例如Solaris、Linux、Mac OS X等很常见。
??Solaris操作系统的七个可加载的内核模块,这七个模块围绕一个核心模块(内核)→
①调度类 ②文件系统 ③可执行格式 ④STREAMS模块。 ⑤可加载的系统调用。 ⑥杂项模块。 ⑦设备和总线驱动。
这种设计可以允许内核提供核心服务,也能动态实现特定的功能。每个内核部分都有被定义和保护的接口。但它比分层系统更为灵活,任一个模块都可以调用其他模块。核心模块只有核心功能,以及其他模块加载和通信的相关信息。
例如:Mac OS X操作系统采用混合结构。采用分层技术构建操作系统。
①上层包括应用环境和一组向应用提供的图形接口的服务。
②他们下面是内核环境,主要包括Mach微内核和BSD内核。
Mach提供内存管理,支持远程程序调用(RPC)和进程间通信(IPC)工具,包括消息传递和线程调度。
BSD提供了BSD命令行接口,支持网络和文件系统,以及POSIX API的实现。
除Mach和BSD之外,还有为设备驱动的开发和动态加载模块提供的I/O工具。(Mac OS X中指的是内核扩展)。
8. 虚拟机
1)虚拟机的基本思想为:单个计算机(CPU、内存、磁盘、网卡等)的硬件抽象为几个不同的执行部件。(利用CPU调度和虚拟内存技术)
2)创建虚拟机的原因:在并行运行几个不同的执行环境时能够共享相同的硬件。
3)主要困难:与磁盘系统有关,因为虚拟机软件本身需要一定的磁盘空间以提供虚拟内存,所以不能为每个虚拟机分配一个磁盘驱动器时,可以提供虚拟磁盘。
4)虚拟机本身只能运行在用户模式。虚拟机软件可以运行在内核模式。虚拟机也有两种模式:虚拟用户模式和虚拟内核模式,这两种模式都运行在物理用户模式上。
5)优点:每个虚拟机完全独立于其他虚拟机,没有安全问题,但也没有直接资源共享。
6)提供共享的两种实现方法 :①可以通过共享小型磁盘来共享文件,这种方案模拟了共享物理磁盘。
②可以通过定义一个虚拟机网络,每台虚拟机通过虚拟网络来传递消息。(这种网络同样是按物理通信网络来模拟,但通过软件来实现的)。
9. 系统生成:
操作系统通常设置为能运行在一类计算机上,这些计算机需要位于不同的场所,并具有不同的外设配置。
对于某个特定的计算机场所,必须要配置和生成系统,这一过程有时称为系统生成。
10. 系统启动:装入内核以启动计算机的过程称为引导系统。大多数计算机系统都有一小块代码,它称为引导程序或引导装载程序。这段代码可以定位内核,将它装入内存,开始执行。
- 初始引导程序为只读存储器(ROM)形式,因为系统启动时RAM处于未知状态,由于不需要初始化和不受计算机病毒的影响,使用ROM很方便。
- 有些计算机系统有两步完成系统启动:一个简单的引导程序从磁盘上调入一个较复杂的引导程序,而后者再装入内核。
- 有些系统(手机、PDA和游戏控制台)会在ROM中保存完整的操作系统。在ROM中保存完整的操作系统适合小型的操作系统,它支持简单的硬件和操作。存在的问题是,改变引导程序代码需要改变ROM芯片。→可以通过使用可擦写只读存储器(EPROM)来解决这个问题。
- 大型操作系统(windows等)引导程序被存储在固件中,而操作系统保存在磁盘上。引导程序具有能够从磁盘固定位置(0区块)读取整块信息到内存的代码,并从引导块执行代码,存储在引导块的程序多半足够复杂,可以将一个完整的操作系统装载到内存并开始执行。 或者有些代码很简单(适合于单磁盘区块),只知道在磁盘的地址以及引导程序剩下的长度信息,所有这些磁盘绑定的引导程序和操作系统本身可以通过向磁盘写入新的版本,从而很容易改变。
- 具有引导分区的磁盘被称为引导磁盘或系统磁盘。
- 完全的引导程序被装入之后,就可以扫描文件系统,以找到操作系统内核,将之装入内存,启动并执行。
第三章:进程管理
3.1 进程概念
- 当一个程序被装入内存,一个程序就成为了进程。进程是执行中的程序。
- 文本段(代码段),当前活动(通过程序计数器的值和处理器寄存器的内容来表示),进程堆栈段,数据段,还有可能包括堆。
- 进程状态:新的;运行;等待;就绪;终止。
一次只有一个进程可以在处理器上运行,但可以有多个进程处于就绪或等待。
- 进程控制块PCB:包含许多与一个特定进程相关的信息。进程状态;程序计数器;CPU寄存器;CPU调度信息;内存管理信息;记账信息;I/O状态信息。
3.2进程调度
- 多道程序设计目的是无论何时都有进程在运行,从而使CPU利用率达到最大。分时系统的目的是在进程之间快速切换CPU,以便用户在程序运行时能与其进行交互。
- 调度序列:作业队列;就绪队列(使用PCB的链表来构成);设备队列(等待特定I/O设备的进程列表称为设备队列,每个设备都有自己的设备队列);
进程控制块(Linux)包含表示一个进程所需要的所有信息:①进程的状态;②调度和内存管理信息;③打开文件列表; ④指向父进程和所有子进程的指针。
新进程开始处于就绪队列。
- 进程调度的队列图P77,及其相应的操作。
- 调度程序:
对于批处理系统,被提交的进程放到缓冲池(磁盘or其他大容量存储设备中),然后进行调度。
长期调度程序、作业调度程序 →从缓冲池中选择进程,以装入内存准备执行。
短期调度程序、CPU调度程序→从准备执行的进程中选择进程,为之分配CPU
有些操作系统如分时系统,有中期调度程序 →能够将进程从内存或者CPU竞争中移出。之后,进程可以被重新调入内存,并从中断处继续执行。这种方案称为交换(swap)。
长期调度程序控制多道程序设计 的程度(内存中的进程数量)
- 上下文切换:
发生一个中断时,系统需要保存当前运行在CPU中进程的上下文,从而在其处理完后能恢复上下文。进程上下文用进程的PCB表示。 通过执行状态保存state save和状态恢复state restore来实现。
上下文切换(context switch):将CPU切换到另一个进程需要保存当前进程的状态并恢复另一个进程的状态,这一任务称为上下文切换。
3.3 进程操作
- 子进程可能从操作系统那里获得资源,也可能只从其父进程获得资源。父进程可能必须在其子进程之间分配资源或共享资源。限制子进程只能使用父进程的资源能防止创建过多的进程带来的系统超载。
- 子进程的初始化数据由父进程传递来。
- 当进程创建新进程时,有两种执行可能:
①父进程与子进程并发执行。
②父进程等待,直到某个或全部子进程执行完。
新进程的地址空间也有两种可能:
①子进程是父进程的复制品(与父进程有相同的程序和数据)
②子进程装入另一个新程序。
- 系统调用exec()将二进制文件装入内存,以用新程序取代进程的内存空间。
- 进程终止:exit(),只有被终止进程的父进程才能执行这一系统调用。
(有些系统)级联终止cascading termination:如果一个进程终止,那么它的所有子进程也将终止。通常由操作系统执行。
如果父进程终止,其所有子进程会以init进程作为父进程,因此子进程仍然有一个父进程来收集状态和执行统计。
3.4 进程间通信
- 独立 vs 协作
独立:不能影响其他进程或被其他进程影响的进程。
协作:一个进程能影响其他进程或被其他进程影响。→需要共享数据。
需要提供环境实现协作,原因:
①信息共享;②提高运算速度;③模块化;④方便
- 协作进程需要一种进程间通信机制(IPC)来允许进程相互交换数据与信息。
- 进程间通信的两种基本模式:①共享内存 ②消息传递。
①消息传递模型: 客户机→服务器
通信进程之间通过彼此交换消息来交换信息。通信前必须打开连接。必须知道通信实体的名称→ 主机名,进程名(通常转换成标识符以便操作系统引用)。
消息传递对交换少量数据很有用,这是因为不必避免冲突。对计算机间的通信,也比共享内存更容易实现。
消息传递使用系统调用来实现,需要更多的内核介入的时间消耗。
②共享内存模型:进程的变体→线程一般通过读写公共区域来通信。进程可以通过shared memory create和shared memory attach系统调用来获得其他进程所拥有的内存区域的访问权。
共享内存允许最大速度的通信并且十分方便,这是因为当通信发生在计算机内,它能以内存的速度进行。但在保护和同步方面,共享内存模型存在一定问题。
共享内存只需要在建立共享内存区域时需要系统调用,一旦建立了共享内存,所有的访问都被处理为常规的内存访问,不需要来自内核的帮助。
- 共享内存系统:→可以解决生产者消费者问题。
可以使用:无限缓冲(unbounded-buffer)或有限缓冲(bounded-buffer)
- 消息传递系统:
发送和接收操作
定长和变长信息
通信线路
逻辑实现线路和send/receive的方法:
①直接或间接通信
②同步或异步通信
③自动或显式缓冲
- 命名:
- 直接通信:需要通信的每个进程必须明确地命名通信的接收者或发送者。
属性P88
对称寻址:发送和接收进程必须命名对方以便通信。
非对称寻址:只要发送者命名接收者,而接收者不需要命名发送者。
对称和非对称寻址方案的缺点限制了 进程定义的模块化。改变进程的名称可能必须检查所有其他进程的定义。所有旧名称必须被找到,以便修改成为新名称。
- 间接通信:通过邮箱或端口来发送和接受信息。
属性
选择的方案
当拥有邮箱的进程终止,那么邮箱将消失。
- 同步:消息传递可以是阻塞或非阻塞——也可以是同步或非同步的。
阻塞send/非阻塞send
阻塞receive/非阻塞receive
- 缓冲:不管是直接或是间接,通信进程所交换的消息都驻留在临时队列中。队列实现三种方法:
零容量
有限容量
无限容量
第四章:线程
4.1 概述
- 线程是CPU使用的基本单元,它由线程ID,程序计数器,寄存器集合和栈组成。它与属于同一进程的其他线程共享代码段、数据段和其他操纵系统资源。
- 单线程进程的网页服务器耗时长:
→传统解决方法:服务器作为单个进程运行接受请求,当服务收到请求时,它会创建另一个进程以处理请求。进程创建耗时且耗资源。
→改进:一个具有多个线程的进程来达到要求。
- 多线程编程的优点:
①响应度高。
②资源共享。
③经济。
④多处理器体系结构的利用。
4.2多线程模型
- 两种不同的方法提供线程支持:
①用户层的用户线程
②内核层的内核线程。
用户线程受内核支持,而无须内核管理;内核线程由操作系统直接支持和管理。
- 多对一模型:将多个用户级线程映射到一个内核线程。
线程管理是由线程库在用户空间进行的。所以效率较高。但如果一个线程执行了阻塞系统调用,则整个进程都会被阻塞。且,因为任意时刻只有一个线程能访问内核,多个线程不能并行运行在多处理器上。
- 一对一线程:将每个用户线程映射到一个内核线程。
该模型在一个线程执行阻塞系统调用时,能允许另一个线程继续执行,所以它提供了比多对一模型更好的并发功能。它也允许多个线程能并行的运行在多处理器系统上。
缺点是:每创建一个用户线程就需要创建一个相应的内核线程。由于创建内核线程的开销会影响应用程序的性能,所以这种模型的绝大多数限制了系统所支持的线程数量。
- 多对多模型:多路复用了许多用户线程到同样数量或更小数量的内核线程上。内核线程的数量可能与特定的应用程序或特定机器有关。
变种:一个流行的多对多模型的变种仍然复用了许多用户线程到同样数量或更小数量的内核线程上,但也允许将一个用户线程绑定到某个内核线程上,这个变种被称为二级模型。
- 并发性比较:
①多对一模型允许开发人员创建任意多的用户线程,但是因为内核只能一次调度一个线程,所以并没有增加并发性。
②一对一模型提供了更大的并发行,但是不能在应用程序上创建太多线程。
③多对多模型可以创建任意多的用户线程,并且相应内核线程能在多处理器系统上并发执行。而且,当一个线程执行阻塞系统调用时,内核能调度另一个线程来执行。
-
- 线程库
- 线程库thread library:为程序员提供创建和管理线程的API。
两种方法来实现:
①在用户空间中提供一个没有内核支持的库。
Three primary thread libraries:
POSIX Pthreads
Windows threads
Java threads
②执行一个由操作系统直接支持的内核级的库。
Examples – virtually all general purpose operating systems, including:
Windows
Solaris
Linux
Tru64 UNIX
Mac OS X
- 线程Pthread:是由POSIX标准为线程创建和同步定义的API,这是线程行为的规范,而不是实现。
- 多线程问题
- 系统调用fork、exec的含义:
Fork():生成一个子进程。是需要复制当前进程的所有线程还是新进程只有单个线程?
Exec():如果一个线程调用exec,则exec参数所指定的程序会替换整个进程,包括所有线程。
Fork的两种形式与应用程序有关:如果调用fork之后立即调用exec,则没有必要复制所有线程,因为exec参数所指定的程序会替换整个进程,这时只复制调用线程比较适当。但是如果在fork之后另一进程并不调用exec,则另一进程就应复制所有线程。
- 取消:
线程取消thread cancellation:在线程完成之前来终止线程的任务。
异步取消
延迟取消
如果资源已经分配给这一线程,则需要操作系统回收取消线程的资源,但并不会回收所有资源,不会使所需的系统资源空闲。
延迟取消时会检查线程是否在安全的点被取消,pthread称这些点为取消点cancellation point
- 信号处理:信号在unix中用来通知进程某个特定事件已发生了。
根据需要通知信号的来源和事件的理由,信号可被同步或异步接收。
当一个信号由运行进程之外的事件产生,那么进程就异步接收这一信号。
处理信号:
①默认信号处理程序
②用户定义的信号处理程序。 ①可被②改写。
信号的模式/信号的发送位置
- 线程池thread pool:P124
多线程服务器的问题:
①关于在处理请求之前用以创建线程的时间,以及线程在完成工作之后就要被丢弃的这一事实。
②如果允许所有并发请求都通过新线程来处理,那么将无法限制在系统中并发执行的线程的数量。无限制的线程会使系统资源耗尽。
→线程池来解决。
线程池的主要思想是在进程开始时创建一定数量的线程,并放入池中等待工作。
线程池中的数量 由系统CPU的数量、物理内存的大小和并发客户请求的期望值等因素决定。
- 线程特定数据:每个线程可能需要一定数据的自己的副本,这种数据称为线程特定数据thread-specific data
- 调度程序激活:(内核与线程库之间的通信问题)
许多实现多对多模型或二级模型的系统在用户和内核线程之间设置一种中间数据结构。通常是 轻量级进程LWP,对于用户线程库,LWP表现为一种应用程序可以调度用户线程来运行的虚拟处理器。每个LWP与内核线程相连,该内核线程被操作系统调度到物理处理器上运行。如果内核线程组赛,LWP也阻塞。
解决用户线程库和内核间通信的方法称为调度器激活scheduler activation。
调度器激活过程中,内核必须告知与应用程序有关的特定事件,这个过程被称为upcall
- 同一进程间的线程究竟共享哪些资源呢,而又各自独享哪些资源呢?
共享的资源有
-
- 堆 由于堆是在进程空间中开辟出来的,所以它是理所当然地被共享的;因此new出来的都是共享的(16位平台上分全局堆和局部堆,局部堆是独享的)
- 全局变量 它是与具体某一函数无关的,所以也与特定线程无关;因此也是共享的
- 静态变量 虽然对于局部变量来说,它在代码中是“放”在某一函数中的,但是其存放位置和全局变量一样,存于堆中开辟的.bss和.data段,是共享的
- 文件等公用资源 这个是共享的,使用这些公共资源的线程必须同步。Win32 提供了几种同步资源的方式,包括信号、临界区、事件和互斥体。
独享的资源有
- 栈: 栈是独享的
- 寄存器: 这个可能会误解,因为电脑的寄存器是物理的,每个线程去取值难道不一样吗?其实线程里存放的是副本,包括程序计数器P
总结:
- 线程共享的环境包括:进程代码段、进程的公有数据(利用这些共享的数据,线程很容易的实现相互之间的通讯)进程打开的文件描述符、信号的处理器、进程的当前目录和进程用户ID与进程组ID。
- 进程拥有这许多共性的同时,还拥有自己的个性。有了这些个性,线程才能实现并发性。这些个性包括:
- 线程ID
每个线程都有自己的线程ID,这个ID在本进程中是唯一的。进程用此来标识线程。
- 寄存器组的值
由于线程间是并发运行的,每个线程有自己不同的运行线索,当从一个线程切换到另一个线程上 时,必须将原有的线程的寄存器集合的状态保存,以便将来该线程在被重新切换到时能得以恢复。
- 线程的堆栈
堆栈是保证线程独立运行所必须的。线程函数可以调用函数,而被调用函数中又是可以层层嵌套的,所以线程必须拥有自己的函数堆栈, 使得函数调用可以正常执行,不受其他线程的影响。
- 错误返回码
由于同一个进程中有很多个线程在同时运行,可能某个线程进行系统调用后设置了errno值,而在该 线程还没有处理这个错误,另外一个线程就在此时被调度器投入运行,这样错误值就有可能被修改。所以,不同的线程应该拥有自己的错误返回码变量。
- 线程的信号屏蔽码
由于每个线程所感兴趣的信号不同,所以线程的信号屏蔽码应该由线程自己管理。但所有的线程都 共享同样的信号处理器。
- 线程的优先级
由于线程需要像进程那样能够被调度,那么就必须要有可供调度使用的参数,这个参数就是线程的 优先级。
第五章:CPU调度
5.1基本概念
- 进程选择由短期调度程序或CPU调度程序执行。
- 就绪队列中的记录是PCB(进程控制块),可以是FIFO序列、优先序列、树或简单的无序链表。
- CPU调度决策发生在:
①当一个进程从运行状态切换到等待状态。
②当一个进程从运行状态切换到就绪状态。
③当一个进程从等待状态切换到就绪状态。
④当一个进程终止时
当调度只能发生在①和④两种情况下时,称调度方案是非抢占的nonpreemptive或协作的cooperative,否则,称调度为抢占的preemptive
使用非抢占式,一旦CPU分配给一个进程,那么该进程会一直使用CPU,直到进程终止或切换到等待状态。
抢占调度的问题:
A.抢占调度对访问共享数据是有代价的。
B.抢占对于操作系统内核的设计也有影响。→可以通过在上下文切换之前等待系统调用完成或等待发生I/O阻塞来处理这一问题。
C.因为根据定义中断能随时发生,而且不能总是被内核所忽视,所以受中断影响的代码段必须加以保护以避免同时访问。
- 分派程序dispatcher:分派程序是一个模块,用来将CPU的控制交给由短期调度程序选择的进程。其功能包括:
①切换上下文
②切换到用户模式、
③跳转到用户程序的合适位置,以重新启动程序。
分派程序停止一个进程而启动另一个要花的时间称为分派延迟dispatch latency
-
- 调度准则
1.准则包括:
①CPU使用率 ⑤响应时间
②吞吐量
③周转时间:从进程提交到进程完成的时间段称为周转时间
④等待时间
使CPU使用率和吞吐量最大化,周转时间和等待时间和响应时间最小化。
5.3调度算法
- 先到先服务first-come first-served FCFS:(是非抢占式的)使用FIFO队列实现。当一个进程进入到就绪队列,其PCB链接到队列的尾部,当CPU空闲时,CPU分配给位于队列头的进程。
所有其他进程等待一个大进程释放CPU,这称为护航效果convoy effect
- 最短作业优先算法shortest-job-first SJF:可证明是最佳的算法。真正困难是如何知道下一个CPU区间的长度。长期调度可以将用户提交作业时所指定的进程时间极限作为长度。
不能在短期CPU调度层次上加以实现。长期CPU调度的时间可以使用指数平均进行估计
SJF算法可能是抢占式或非抢占式的。抢占SJF算法可抢占当前运行的进程,而非抢占SJF算法会允许当前运行的进程先完成其CPU区间。抢占式SJF调度也称为最短剩余时间优先调度。
- 优先级调度priority scheduling algorithm PS:每个进程都有一个优先级与其关联,具有最高优先级的进程会分配到CPU,具有相同优先级的进程按FCFS顺序调度。
SJF是PS的一个特例。
优先级调度可以是抢占式或非抢占式的。
优先级调度的主要问题是:无穷阻塞(indefinite blocking)或饥饿(starvation)
低优先级进程无穷等待问题的解决之一是老化aging,老化是一种技术,以逐渐增加在系统中等待很长时间的进程的优先级。
- 轮转法调度round-robin RR:类似于FCFS调度,但增加了抢占以切换进程,定义一个较小时间单元,称为时间片time quantum/time slice。
RR是抢占式的。
要求时间片比上下文切换的时间长,且需要使80%的CPU区间小于时间片。
- 多级队列调度multilevel queue scheduling algorithm:将就绪队列分成多个独立队列。可以根据进程的属性,如内存的大小,进程优先级,进程类型,一个进程被永久地分配到一个队列,每个队列有自己的调度算法。
一个常用的划分方法是前台(交互)进程和后台(批处理)进程。
每个队列有自己的调度算法,队列之间也必须有调度,通常采用固定优先级抢占调度,或者在队列之间划分时间片。
因为多级队列调度的进程进入系统时被永久地分配到一个队列,所以这种设置优点在于低调度开销,缺点是不够灵活。使用6来进行改进。
- 多级反馈队列调度算法multilevel feedback queue scheduling algorithm:允许进程在队列之间移动,主要思想是根据不同的CPU区间的特点以区分进程。如果进程使用过多CPU时间,那么它会被转移到更低优先级队列。
这种方案将I/O约束和交互进程留在更高优先级队列,此外在较低优先级队列中等待时间过长的进程会被转移到更高的优先级队列,这种形式的老化阻止了饥饿的发生。
它也是抢占调度的。
5.4多处理器调度
1. 主要讨论处理器功能相同或同构的系统,可以将任何处理器用于运行队列内的任何进程(但对同构多处理器,也有一些调度限制,考虑一个I/O设备与一个处理器通过私有总线连接,希望使用该设备的进程必须调度到该处理器上运行)。
2. 非对称多处理方法asymmetric multiprocessing:让一个处理器(主服务器)处理所有的调度决定、I/O处理以及其他系统活动,其他的处理器只执行用户代码。简单,因为只有一个处理器访问系统数据结构。
3. 对称多处理symmetric multiprocessing(SMP):每个处理器自我调度,所有进程可能处于一个共有的就绪队列中,或者每个处理器都有一个它自己的私有就绪队列。调度通过每个处理器检查共有的就绪队列并选择一个进程来执行。→需要注意多个处理器试图访问和更新同一个共同的数据结构的情况。
下面的讨论都是针对SMP的。
4. 处理器亲和性:如果一个进程从第一个处理器迁移到第二个处理器上运行,它的代价是昂贵的,它需要将第一个处理器上的数据结构置为失效,然后将数据结构重新构建到第二个处理器上。所以,需要努力使一个进程在同一个处理器上运行,被称为处理器亲和性。
软亲和性 vs 硬亲和性。
优点:进程可以利用它在处理器缓存中的数据。
5.负载平衡:load balancing:设法将工作负载平均的分配到SMP系统的所有处理器上。负载平衡通常只对那些拥有自己私有的可执行进程的处理器而言是必要的。在具有共同队列的系统中,由于一旦处理器空闲,它立刻从共同队列中取走一个可执行进程,所以不需要负载平衡。
两种方法实现负载平衡:①push migration ; ②pull migration
负载平衡会抵消掉处理器亲和性的有点。
6.对称多线程SMT:在同一个物理处理器上生成多个逻辑处理器,向操作系统呈现一个多逻辑处理器的视图。每个逻辑处理器都有它自己的架构状态。包括通用目的和及其状态寄存器。每个逻辑处理器负责自己的中断处理,中断被送到并被逻辑处理器所处理,而不是物理处理器。
SMT是硬件,而不是软件。硬件应该提供每个逻辑处理器的架构状态的表示,以及中断处理方法。
5.5 线程调度
1. 系统调度的是内核线程,而不是进程,用户线程由线程库管理,内核并不了解它,为了能在CPU上运行,用户线程最终必须映射到相应的内核级线程,尽管这种映射可能是间接的,可能使用LWP。
2. 竞争范围:
用户级线程→LWP 进程竞争范围PCS
内核线程→CPU 系统竞争范围 SCS
一对一模型,调度仅使用SCS
PCS根据优先级完成。
- Pthread调度:用户线程→LWP→内核线程→CPU
5.6操作系统实例
1.Solaris调度/ Solaris9调度
2. Windows Xp调度
3.Linux调度
4.算法评估:①确定模型法deterministic modeling ②排队网络分析 queue ing-network analysis
③模拟simulation ④实现
第六章 进程同步
6.1背景
1. 竞争条件race condition:多个进程并发访问和操作同一数据且执行结果与访问发生的顺序有关,称为竞争条件。
2. 临界区critical section:每个进程有一个代码段称为临界区。在该区中进程可能改变共同变量、更新一个表、写一个文件等。
3. 处理操作系统的临界区问题的两种方法:①抢占内核preemptive kernel;②非抢占内核nonpreemptive kernel
抢占内核更适合实时编程,能允许实时进程抢占处于内核模式运行的其他进程。
6.3Peterson算法
6.4硬件同步
1. 锁:通过要求临界区用锁来防护,即一个进程在进入临界区时必须得到锁,而在其退出临界区时释放锁。
2. 禁止中断的缺点:增加延迟,费时,降低系统效率。
6.5信号量
1. 信号量semaphore:是一种同步工具。→两个标准原子操作wait() signal()
2. 二进制信号量称为互斥锁。
3. 计数信号量:该信号量初始化为可用资源的数量,当每个进程需要使用资源时,需要对该信号量执行wait()操作(减少信号量的计数),当进程释放资源时,需要对该信号量执行signal()操作(增加信号量的个数)。
4. 实现:
忙等待busy waiting:是信号量的主要缺点。
自旋锁spinlock:进程在等待时不进行上下文切换,而上下文切换可能需要花费很长时间,如果锁的占用时间短,则可以使用自旋锁。
- 死锁deadlock:两个或多个进程无限地等待一个事件,而这一事件只能由这些等待进程之一来完成。
无限期阻塞indefinite blocking
饥饿starvation
6.6经典同步问题
1. 有限缓冲问题
2. 读者写者问题
第一读者写者问题:要求没有读者需要保持等待,除非已有一个写者已获得允许以使用共享数据库。(写者可能饥饿)
第二读者写者问题:一旦写着就绪,那么写者会尽可能快的执行其写操作。(读者可能饥饿)
- 哲学家进餐问题
6.7管程
1. 是一种基本的,高级的同步构造,即管程模型monitor
2. 管程结构确保一次只有一个进程能在管程内活动。
需要额外的同步机制,这些可由condition结构来提供。
3.可以使用管程来解决哲学家进餐问题。
4. 基于信号量的管程实现。
5. 管程内的进程重启。
6.8同步实例
1. Solaris同步:适应互斥、读写锁、十字转门
- 适应互斥adaptive mutex:保护对每个临界数据项的访问,以自旋锁实现的标准信号量开始。
- 读写锁:用于保护经常访问但通常是只读访问的数据。
- 十字转门turnstile:是一个队列结构,包含阻塞在锁上的线程。每个同步对象有至少一个线程 在其上阻塞时,都需要有一个十字转门,但是Solaris不是将每个同步对象与一个十字转门相关联,而是给每个内核线程一个十字转门。
优先级倒置
优先级继承协议(为了防止优先级倒置)
2. Windows XP同步:自旋锁、调度对象
调度对象dispatcher object:共享数据可以通过要求线程获取访问数据的互斥拥有权和使用完后释放拥有权,来加以保护。
调度对象可以处于触发状态signal state或非触发状态nonsignaled state
3. Linux同步:自旋锁、信号量(还有这两种版本的读者写者版本)
4. Pthread同步:提供互斥锁、条件变量、读写锁
第七章:死锁
7.2死锁的状态
1. 进程使用资源的顺序:申请、使用、释放
2. 死锁:当一组进程的每个进程都在等待一个事件,而这一事件只能由这一组进程的另一进程引起,那么这组进程就处于死锁状态。
死锁的特征:
①互斥
②占有并等待
③非抢占
④循环等待
3. 资源分配图:申请边、分配边。
如果分配图中没有环,则系统就没有进程死锁;如果有环,则可能存在进程死锁。
7.3死锁的处理方法
1. 死锁预防 deadlock prevention:一组方法,以确保至少一个必要条件不成立。
针对:
互斥:
占有并等待:保证当一个进程申请一个资源时,它不能占有其他资源。
非抢占:如果一个进程占有资源并申请了另一个不能立即分配的资源,那么其现已分配的资源都可被抢占。
循环等待:对有所资源类型进行完全排序,且要求每个进程按递增顺序来申请资源。
2. 死锁避免deadlock avoidance:要求操作系统事先得到有关进程申请资源和使用资源的额外信息。
-
- 副作用:低设备使用率和系统吞吐率。
- 死锁避免算法动态地检测资源分配状态确保循环等待条件不能成立。
- 安全状态:如果系统能按照某个顺序为每个进程分配资源(不超过其最大值)并能避免死锁,那么系统状态就是安全的。
- 资源分配图算法:采用环检测算法,检测安全性。→针对每种资源只有一个实例
- 银行家算法:→针对每种资源有多个实例。
7.6死锁检测
1. 每种资源类型只有单个实例:等待图
2. 每种资源类型有多个实例:与银行家算法类似的检测算法。
3. 应用检测法
7.7死锁恢复
1. 进程终止:
终止所有死锁进程
一次只终止一个进程直到取消死锁循环为止
2. 资源抢占:
选择一个牺牲品
回滚
饥饿
第八章:内存管理
8.1背景
1. CPU直接访问的只有内存和处理器的寄存器。
2. 基地址寄存器base register 也称为重定位寄存器/ 界限地址寄存器 limit register
3. 将指令与数据绑定到内存地址有几种情况:
①编译时 ②加载时 ③执行时
4. 地址绑定:进程在执行时可以在磁盘和内存之间移动。在磁盘上等待调入内存以便执行的进程形成输入队列input queue
4.动态加载dynamic loading:优点是不用的子程序不会被加载。
- 动态链接dynamically linked:每个库程序的引用都有一个存根stub
静态链接static linking:
8.2交换
1. 交换swap:进程可以暂时从内存中交换到备份存储backing store中。
也称为滚出roll out和滚入roll in
2. 如果绑定是在汇编时或加载时所定的,那么就不可以移动到不同的位置。如果绑定是在运行时决定的,由于物理地址是在运行时确定的,那么进程就可以移到不同的地址空间。
3. 如果要缓存一个进程来释放内存,而该进程正在等待I/O操作,如果I/O异步访问用户内存的I/O缓冲区,则该进程就不能被换出。
两种解决:①不能换出有待处理I/O的进程,②I/O操作的执行只能使用操作系统缓冲区,仅当换入进程后,才执行操作系统缓冲与进程内存之间的数据转移。
8.3连续内存分配
1. 连续内存分配contiguous memory allocation:每个进程位于一个连续的内存区域。
重定位寄存器含有最小的物理地址值,界限地址寄存器含有逻辑地址的范围值。
2.内存映射与保护。
3. 内存分配:
1)将内存分为多个固定大小的分区。分区partition
2)使用可变分区variable-partition。→操作系统有一个表,用于记录哪些内存可用混合哪些内存已被占用。
一大块可用内存,称为孔hole
动态存储分配问题,从一组可用孔中选择一个空闲孔的最为常用的方法是:
首次适应first fit;最佳适应best-fit;最差适应worst-fit
4.碎片
外部碎片问题external fragmentation
解决:紧缩compaction:紧缩尽在重定位是动态并且在运行时可采用 。
内部碎片问题internal fragmentation
5. 交换需要备份内存。
8.5页表结构/分页
1. 层次页表,也称为向前映射表forward-mapped page table
2. 哈希页表 hashed page table
3.反向页表inverted page table
每个条目包含保存在真正内存位置的页的虚拟地址以及拥有该页的进程的信息。
实现共享时比较困难。
4. 分页paging内存管理方案:允许进程的物理地址空间可以是非连续的。分页避免了将不同大小的内存块匹配 到交换空间上这样的麻烦。
分页的优点之一是可以共享公共代码。
5. 帧frame:将物理内存分为固定大小的块,称为帧。
页page:将逻辑内存也分为同样大小的块,称为页。
→页大小是由硬件决定的,采用分页技术不会产生外部碎片。
分页的重要特点是用户视角的内存和实际的物理内存的分离。
- 帧表frame table:每个条目对应一个帧,以表示该帧是空闲还是占用。
- 转换表缓冲区translation look- aside buffer:TLB
地址空间标识符address-space identifier ASID
8.6分段segmentation
1. 段表segment table:将二维的用户定义地址映射为一维物理地址。
每个条目都有段基地址和段界地址
2. (8.7)本地描述符表local descriptor table LDT
全局描述符表global descriptor table GDT
3. Pentium 系统的Linux:
任务状态段 TSS的描述符在GDT上。TSS用来保护在上下文 切换中每个进程的硬件上下文。
第九章:虚拟内存
9.1背景
1. 虚拟内存将用户逻辑内存与物理内存分开。
2. 虚拟内存的优点P272
9.2按需调页demand paging
1.交换程序swapper对整个进程操作,而调页程序pager对进程的单个页进行操作。
2. 对标记无效的访问会产生页错误陷阱page-fault trap
3. 在次级存储器(一般为磁盘)上用于交换的这部分磁盘,称为交换空间swap space
4. 请求页面调换的关键要求是能够在页错误后重新执行指令。
主要困难在于一个指令可能改变多个不同的位置/
9.3 写时复制copy on write
1. 即对任何一个进程需要对页进行写操作,那么就创建一个共享页的副本。
9.4页面置换page replacement
1. 如果增加了多道程序的程度,那么就会过度分配over-allocating 内存。
2. 基本页置换P281
页置换是按需调页的基础。
3. 按需调页需要解决两个问题:
①帧分配算法 frame-allocation→为每个进程各分配多少帧
②页置换算法page-replacement
-
-
- FIFO页置换算法:存在Belady异常,对于该页置换算法,页错误率可能会随着分配的帧数的增加而增加。而原期待是为进程增加内存会改善其性能。
- 最优置换optimal page-replacement algorithm
- LRU页置换
计数器、栈
LRU和最优置换称为栈算法。
-
-
- 近似LRU页置换
第二次机会页置换算法second-chance page-replacement algorithm
附加引用位算法
增强型二次机会算法
-
-
- 基于计数的页置换
最不经常使用页置换算法LFU
最常使用的页置换算法MFU
-
-
- 页缓冲算法
9.5 帧分配
1. 帧分配受到多方面限制,必须分配至少最少数量的帧。
2. 分配算法:
- 平均算法equal allocation
- 全局分配和局部分配
全局置换 vs 局部置换
9.6系统颠簸
1. 频繁的页调度行为称为颠簸thrashing
2. 降低系统颠簸:
①降低多道程序 的程度。
②通过局部置换算法local replacement 或优先置换算法priority replacement来限制系统颠簸
③可以直接测量和控制页错误率以防止颠簸。
3. 工作集合模型
操作系统跟踪每个进程的集合,并为进程分配大于其工作集合的帧数。
4. 页错误率
9.7内存映射文件
1.文件的内存映射可将一磁盘映射成内存的一页或多页。
多个进程可以允许将同一文件映射到各自的虚拟内存中,以允许数据共享。
对映射到内存的文件进行写可能不会立即写到磁盘上的文件中。
2. 共享内存是通过内存映射文件来实现的。
9.8内核内存的分配
1.内核内存的分配通常是从空闲内存池中获取的,而不是从满足普通用户模式进程的内存链表中获取的,原因P303
2. Buddy系统;从物理上连续的大小固定的段上进行分配。
优点是可通过合并而快速的形成更大的段。
3. slab分配:优点P305
9.9其他考虑
1. 预调页prepaging
2.页大小,页大小的选择权衡P307
3.TLB范围:两种方法增加TLB范围P308
4. 反向页表:这种形式的页管理能降低为了跟踪虚拟地址到物理地址转换所需的物理内存的数量。
5.I/O互锁:解决方法P311
10 文件系统接口
10.1文件概念
1. 打开文件的相关信息P324
单个进程的表的一个条目指向整个系统的打开文件表
整个系统的表
10.2. 3访问方法、目录结构
1. 顺序访问、直接访问、
2. 目录概述,相关操作P333
3. 单层结构目录
树状目录结构
无环图目录 无环图 acyclic graph;实现共享文件和目录的方法→链接、P338
通用图目录
- 对每个双层目录的结构,都有:
用户文件目录user file directory UFD
主文件目录master file directory MFD
- 安装文件系统 安装mount
10.5文件共享
1. 多用户、
2. 远程文件系统、P344
①通过程序实现机器之间的文件人工传输
②分布式文件系统DFS
③万维网
3. 一致性语义consistency semantic
4. 保护:通过禁止访问可以实现完全的保护。
5. 访问控制:访问控制列表ACL
11 文件系统实现
11.1文件系统结构
1.磁盘的特点
2.文件系统的两个设计问题
3. 层次结构:
应用程序→逻辑文件系统→文件组织系统→基本文件系统→I/O控制
文件组织模块file-organization module
11.2 文件系统的实现
1. 文件系统的概述主要组成P355
2. FCB文件控制块
3.分区与安装:
生磁盘
引导信息(分区中)
根分区root partition
3. 虚拟文件系统:三个主要层次P359
11.3目录实现
1. 线性列表
2.哈希表
11.4分配方法
1.连续分配contiguous allocation:外部碎片问题、动态存储分配、如何解决文件分配太小空间问题、缺点&优点
2.链接分配linked allocation:没有外部碎片、缺点&优点、簇cluster解决指针空间太大问题
文件分配表FAT
3. 索引分配indexed allocation:浪费空间的问题&解决
4.性能
11.5空闲空间管理
1.位向量bit vector
2.链表
3.组
4.计数、
11.6效率与性能
1. 效率 3点,考虑的三个方面
2.性能:统一虚拟内存unified virtual cache vs 统一缓冲内存unified buffer cache
①统一缓冲内存unified buffer cache:①使用内存映射、②使用标准系统调用read&write
内存映射导致双重缓存double caching
3. 同步 or 异步
4. 马上释放free-behind
5. 预先读取read-ahead
11.7 恢复
1. 一致性检查程序consistency checker
2. 备份和恢复
11.8 基于日志结构的文件系统
环形缓冲
11.9 NFS:
允许透明的共享这些文件系统
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)