操作系统的学习笔记汇总

2021/05/12

一、操作系统的概论

1、操作系统的基本概念和操作系统的地位
2、操作系统的主要特征和基本功能
3、操作系统的体系结构
4、操作系统的发展和结构
5、常用操作系统结构设计方法


本章主要讲述计算机系统、操作系统的定义、操作系统的特征、操作系统发展、操作系统的分类、操作系统功能、操作系统设计等内容,重点掌握如下内容:
*1、计算机系统
计算机系统的分层接哦古、计算机系统的组成、计算机系统的资源分类
*2、操作系统的定义
*3、操作系统的分类
(1)批处理系统的基本工作方式、特点、工作原理、目标
(2)分时系统的基本工作方式、设计思想、特点
(3)实时系统的定义、设计目标
(4)嵌入式操作的特点、运行环境
(5)网络操作系统的定义、应用
(6)分布式操作系统的特征、优点
4、操作系统设计
(1)操作系统的设计过程
功能设计、算法设计、结构设计
(2)操作系统设计目标
可靠性、高效性、易维护性、可移植性、安全性、简明性
(3)操作系统的结构
整体式结构、层次式结构、微内核结构

1、计算机系统

1.定义
计算机系统是一种可以按用户的要求接收和存储信息、自动进行数据处理并输出结果信息的系统

2.分类:
广义:机械式系统和电子式系统
电子式系统:模拟式和数字式计算机系统
*现在使用的计算机系统是数字式计算机系统

3.组成:
硬件(子)系统和软件(子)系统
*软件层次有应用软件、支撑软件、系统软件

不同眼光来看,同一个软件可能是不同层次的软件
分层:
软件子系统:
应用软件:文字处理、Excel、Word、钉钉、微信
解:应用软件是按特点领域中某种需要而编写的专用程序。如,财务管理、人口普查等专用程序均属于应用软件
支撑软件:数据库、网络、多媒体、JDK、
解:支撑软件是可支持其他软件的开发和维护的软件,如数据库、各种接口软件、软件开发工具都是支撑软件。
系统软件:操作系统、编译程序
解:系统是计算机系统中与硬件结合最紧密的软件,也是系统中必不可少的软件;如操作系统、编译系统等都是系统软件;


硬件子系统:
中央处理器(CPU)、内储存器、外储存器(硬盘、磁带)、输入输出设备\IO设备(键盘、鼠标、显示器、打印机)


*计算机系统的资源:硬件资源、软件资源
在计算机系统中,集中了资源管理功能和控制程序执行功能的一种软件,称为操作系统。

定义:
操作系统是计算机系统的一个系统软件,它是这些程序模块的集合:它们能有效组织和管理计算机系统中的硬件及软件资源,合理地组织计算机工作流程,控制程序的执行,并向用户提供各种服务功能,使得用户能够灵活、方便、有效地使用计算机,并使整个计算机系统能高效地运行。

定义解析:
*1.组织和管理计算机系统地硬件和软件资源
在操作系统中,设计了各种表格和数据结构,将所有的软硬件资源都加以登记。登记何时使用,使用中,空闲、如何去使用等
如PCB、系统设备表等

*2.“有效”
CPU空转:待机情况下CPU是空转的,不处理事情占用着资源
指操作系统在管理计算机资源时要考虑到系统运行的效率和资源利用率。要尽可能提供中央处理器的利用率,让它尽可能少的空转,应该在保证访问效能的前提下尽可能有效地利用其他资源。
比如:减少内存、硬盘空间的浪费等

*3.“合理”
死锁:计算机调度不当会导致死锁,体现就是卡死
饥饿:让程序运行,但是一直得不到运行,饥饿是资源管理问题。 在这个问题中,等待进程长时间无法获得所需的资源,因为资源正在分配给其他进程。

指操作系统要"公平"对待不同的用户程序,保证系统不发生"死锁"和“饥饿”的现象

*4.“方便”
指操作系统的人机界面要考虑到用户使用界面和程序接口两个方面的易用性、易学性和易维护性。
用户使用接口:命令、图形界面如:Windows图形界面
程序接口:程序员能够使用操作系统提供的服务进行编程。如Window提供的API接口,Linxu的系统调用。

操作系统的特征
*1.并发性:
是指在计算机系统中同时存在着若干个运行着的程序,从宏观上看,这些程序在同时向前推进。微观上却是走走停停,并非同时运行,因为CPU的核数远远比不上程序的数量

*2.共享性:
操作系统需与多个用户程序共用系统中的各种资源,比如CPU、内存、外部设备等。操作系统要提供一种策略让CPU、内存等资源能够共享

*3.随机性\异步性:
操作系统不能对所运行程序的行为以及硬件设备的情况做出任何事先的假定。
既操作系统不能预知程序在什么时候运行,什么时候因为什么原因暂停,什么时候能得到资源继续运行,什么时候运行结束等,这些都是不可预知的。
比如:访问一个服务器,等待服务器返回就是个异步操作,因为你不知道服务器什么时候给你返回

操作系统的观点
1.操作系统是一种大型系统软件,它是多种功能程序的集合。有外在特性和内在特性。
外在特性:接口 如:提供用户使用的命令、窗口。提供给程序员使用的API等
内在特性:与硬件交互 如:我要使用打印机,我不直接直接使用打印机,而是通过操作系统来使用

2.资源管理的观点
操作系统负责登记谁在使用什么样的资源,系统种还有哪些资源空闲,当前相应了谁对资源的请求,以及回收哪些不在使用的资源等。

**3.进程的观点
并行:宏观上同一时刻,微观上同一时刻多个部件运行
把操作系统看作有多个同时独立运行的程序和一个对这些程序进行协调的核心。
侧重于分析系统各部分的并行工作,研究处理各项管理任务的分割以及这些管理任务相互之间的关系(直接关系、间接关系)
比如:
竞争资源:有可能两个进程同时申请打印机,打印机一次只能打印一张,所以要操作系统进行协调
进程通信:各个程序之间可能需要通信,让它们合理的进行通信,避免出现你没发任务,我这边要等你发任务才操作,然后你那边又要等我这边处理完返回给你,你才进行操作

4.虚拟机的观点
在操作系统的支持下,用户不需要直接使用硬件机器(裸机),而是通过操作系统提供的各种手段来控制和使用计算机。
例如,把所有对设备和文件的操作抽象为统一的打开、关闭、读、写等,用户感觉不到底层的操作差异。具体的实现有各个软件来实现,不用用户去学习复杂的操作,直接就可以打开、关闭、读、写
把操作系统的所有功能,包括系统调用、命令、作业控制语言等,称为操作系统虚拟机。

5.服务提供者观点
从用户的角度,站在操作系统之外观察操作系统,认为该服务提供者为用户提供了比逻辑功能更强、服务质量更高、更方便灵活的虚拟机。

*2、操作系统的功能

*1.进程管理
进程管理的实质:对中央处理器进行管理。或者称为处理机管理。
解:
运行多道程序,让谁先运行,让谁后运行,运行的策略是什么样的呢?这些都是进程管理来进行的


多道程序技术:多个程序同时放入内存,如果一个程序因为等待某个条件而不能运行,就把处理器专用权转交给另一个可运行程序
解:
多个程序同时放入内存,而不是同时运行,一个程序暂停了,立马让另一个程序顶上去,而不是停在那里


*进程的引入:为了描述多道程序的并发而引入
解:
进程是走走停停的,关键是它停了,我怎么知道它运行到什么地方了,它暂停是因为什么原因,它等待的事件什么时候发生?
操作系统会提供一个表格记录,进行管理,叫做PCB,每个进程都加了个进程控制块,记录了你这个程序在内存的什么位置,占用了哪些资源,你现在的状态,你是不是暂停的,什么原因暂停的,一会你等待的事情发生了,你该怎么办。

进程的简单定义:一个程序的运行过程。


*进程管理的内容:
进程控制
解:
创建进程:运行程序
阻塞进程:因为需要等待特定事件暂停进程
唤醒进程:特定事件发生了,唤醒进程
销毁进程:程序运行完了

*进程同步
解:同步就是你需要我达到条件后才能行动
生产者-消费者问题
如:进程A负责读数据到缓冲区 -> 进程B负责计算读取到的数据 —> 进程C负责输出结果
如果进程之间没有同步的话:
	1.若进程A未及时读取数据到缓冲区,进程B就直接取数据计算,这不就乱套了吗,进程B无法取到数据啊。
    2.若进程A及时读取数据到缓冲区了,进程B还没有来取,那进程A就要一直等待啊。
如果进程之间有同步的话:
	1.就有进程的同步机制来制约它们按照顺序来执行 
	2.就由进程的同步机制来通知B取数据,B取完数据,A再停止等待
进程之间的相互合作,相互制约,这就是进程的同步.

进程间的通信:
进程间通信的意思就是在不同进程之间传递信息,一个进程发送信息到另外一个进程中,这就是进程之间的通信。如:QQ你发消息给A,A那边接收,这就是一次通信
进程的通信我们有相应的机制,让其快速的通信,大批量数据的通信,保证通信不出错


*进程间的调度:
多道程序同时在内存中运行,这时候让谁先占用处理器来运行,要提供一些策略,这就是进程的调度



2.存储管理
(1)任务:存储管理是指对计算机内存资源的管理,不包括辅存、磁盘等,它的任务就是管理计算机的资源
(2)功能:
内存的分配与回收:当多个程序共享有限的内存资源时,要考虑如何为多个程序分配有限的内存空间,以及程序运行完毕还需要内存回收。
解:运行程序的时候是全部加载进内存呢,还是部分加载进内存呢,这里面有很多算法

存储保护:存储在内存中多个程序和数据应该彼此隔离、互不侵扰。
解:每个程序都有自己独立的内存空间,操作系统应该做好隔离机制,保证程序A不会读取到程序B的内存空间的东西。

内存扩充:将辅助存储器作为内存的扩充空间。
若想运行的程序大于当前内存空间,或者想运行多个程序,多个程序需要内存总和超过当前内存空间,这时候要怎么办?
可以采用一种叫做虚拟存储器的技术,我们把当前暂停的程序放到磁盘当中,要在运行的时候把它换进来,这个技术叫做交换
可以把程序要运行的一部分先加载进内存,运行完这一部分在全部加载进内存中,这叫做分页



3.文件管理
(1)任务:有效地支持文件的存储、检索和修改等操作,解决文件的共享、保密、保护问题,以便用户方便、安全地访问文件。
(2)功能:
文件存储空间的管理:
主要就是对磁盘、硬盘的管理,对存储空间的分配、回收、文件的存储以什么形式存储在磁盘上,你给这个文件分配的时候,是连续的空间呢还是不连续的空间呢,这都是文件存储空间的管理

目录管理:
文件存储在磁盘上,你如何找到文件呢,你用名字找到,从来不担心找不到。
每个文件建立一个文件控制块,然后把多个文件控制块组合在一起就形成一个文件的目录,文件的目录最终的目的就是提供按名存取文件,还有要提高检索速度,如Windows的资源管理的树形目录结构

文件系统的安全性
不受没有授权用户的损坏,或者是你文件出问题,应该怎么办,应该提前做些什么准备



4.设备管理
(1)设备管理的含义:
指计算机系统出了处理和和内存以外的所有输入输出设备的管理。

(2)功能:
负责外部设备的分配、启动和故障处理
在计算机系统中,用户需要使用设备都要向操作系统提出申请,操作系统管理所有设备,用户不可以随意使用,你提出申请后操作系统根据它的表格查看设备情况,如果可以使用就分配设备,启动设备,若是设备故障了还要处理故障

(3)采用的技术:
中断技术、通道技术、虚拟设备技术、缓冲技术,尽可能发挥设备和主机的并行能力。
如你使用打印机的同时,还可以录制视频

5.用户接口
从用户观点看,操作系统是用户与计算机之间的接口
任务:为用户提供一个使用系统的良好环境,使用户能有效地组织自己的工作流程,并使整个系统高效地运行。

3、操作系统的体系结构

现在的操作系统一般都是分层次的

Window

Windows操作系统的体系结构
1、内核
功能:线程调度、陷入处理和异常调度、中断处理和调度、多处理器同步、供执行体使用的基本内核对象。
解:主要是完成操作系统最基本的功能,叫做内核是因为这些功能是常驻内存的

2.硬件抽象层HAL
系统可移植性的关键部分,为运行在Windows操作系统上的硬件平台低级接口,隐藏了各种与硬件有关的细节,如I/O等专用和依赖于计算机平台的函数
解:你Windows可以使用奔腾的CPU运行也可以使用苹果的硬件运行,就是该层起到的作用起到的作用

3、执行体
属于内核,以系统函数的形式提供了系统的服务,可通过Win32API进行访问

4、系统进程和系统线程
执行系统代码

1603982143451

UNIX

1、内核层
shell是一种壳,区别于内核,例如Windows的cmd,Linux的终端都是shell
是操作系统管理和控制中心,常驻内存。有两种接口:内核与硬件的接口和内核与shell的接口。
内核本身分为两部分:进控制子系统和文件子系统

2.系统层
内核层与应用层之间,供程序员开发调用,包括进程管理、文件管理、中断状态。

3.应用层
面向用户操作的界面

1603982909093

Linux

四个部分:
内核、shell、文件系统和应用程序

1603982960612

Android

四个部分:
Android系统的内核都是Linux的内核
从低到高:应用程序层、应用框架层、系统运行库层和Linux内核层。

4、操作系统的阶段

发展过程
1、手工阶段
2、监控程序
3.多道批处理
4.分时与实时操作系统
5.UNIX通用操作系统
6.个人计算机操作系统
7.Android操作系统

*根据用户界面和功能特征分类
1.批处理系统
2.分时系统
3.实时系统

*新类型:
1.个人操作系统
2.网络操作系统
3.分布式操作系统
4.嵌入式操作系统

批处理操作系统

I/O设备的低速性

-、批处理操作系统
1、基础工作方式
用户将作业交给系统操作员,系统操作员在收到作业后,并不立即将作业输入计算机,而是收到一定数量的用户作业之后,组成一批作业,再把这批作业输入到计算机中。这批作业可在系统中形成一个连续的、自动转接的作业流。
系统操作员然后启动操作系统,系统自动、依次执行每个作业。
最后由操作员将执行完毕的作业交给用户。

*2、特点与分类
特点:成批处理,用户不能干预自己的作业运作
缺点:其中的某个任务出错了,也得等它全部执行完成,出了结果才能得知,用户哪怕提前知道也无法进行修正
目标:系统资源利用率高,作业吞吐率高。
解:单位时间内能够运行的作业个数叫做吞吐率,吞吐率越高越好,批处理的目的就是吞吐率高
分类:简单批处理和多道批处理
解:
简单批处理就是CPU一次执行一个作业,事先录入这些步骤,这样就可以减去人思考和操作速度有限,而导致CPU空转
多道批处理是由于程序步骤都是记录在磁带,要执行一个批处理就要录入一次,这就导致每次执行前都要重新录入磁带,所以支持一次性录入多个(一批)来进行一次性处理,当一个程序要执行I/O操作时,就从存储器的程序队列中取另外的程序进行运行,这样可以减少CPU空转。

3、设计思想
再监控程序启动之前,操作员有选择地把若干个作业合并成一批作业,将这批作业安装再输入设备上,然后启动监控程序,监控程序将自动控制这批作业的执行。
作业的运行和衔接都由监控程序自动控制,从而有效提高了作业运行的效率。

4、作业控制说明书
作业控制说明书是由作业控制语言编写的一段程序,它通常存储再被处理作业的前面
作业的运行由作业控制说明书来传递给监控程序,运行过程中,监控程序读入并解释作业说明书,以控制各个作业帮的执行。
作业控制语言是比python低级的语言

5.一般指令和特权指令
操作系统运行模式:用户模式和特权模式
解:用户模式是用户的模式,特权模式是操作系统所处的模式
处理器状态:目态和管态
解:目态是处理器的状态,是用户使用时的状态,也叫用户态。管态是操作系统使用的时候处理器的状态,也叫核心态、内核态
机器指令:
解:一般指令是由用户进行调用的,特权指令只能由操作系统来调用
系统调用:用户程序不能直接使用特权指令,必须向操作系统请求这些功能,这些功能通过系统调用完成。

6.系统调用的过程
首先,当系统调用发生时,由中断或异常处理程序,记录当前所处步骤,把控制流程转移到监控程序内的一些特定位置,处理器模式变为特权模式。
其次,由监控程序执行被请求的功能。
最后,恢复现场,就是说返回到记录的步骤中,运行模式转变为用户模式,控制权交给用户程序

7.SPOOLing技术
是多道程序设计的关键技术之一,也称为假脱机技术。
解:这个技能能把一台打印机变为一个共享的打印机,SPOOLing技术是实现虚拟设备的技术

分时操作系统

1604033836066

1.基本工方式
在分时系统中,一个主机连接了若干个终端,而每个终端可有一个用户时使用。用户通过终端交互式地向系统提出命令请求,系统接收用户命令之后,采用时间片轮转方式处理服务请求,并通过交互方式在终端上向用户显示结果
解:批处理是把步骤事先编写好,然后放到批处理系统中统一执行,分时操作系统是可以让用户执行步骤,然后输出步骤执行结果,这样如果发生错误就可以及时修正 ,分时操作系统是宏观上并行的,微观上不并行的。把计算机与许多终端用户连接起来,分时操作系统将系统处理机时间与内存空间按一定的时间间隔,轮流地切换给各终端用户的程序使用。由于时间间隔很短,每个用户的感觉就像他独占计算机一样

2.特点
多路性:
解:可以接收多个终端的指令
交互性:
解:给分时操作系统发出指令后,分时操作系统可以及时反馈出执行结果,然后由用户判断该结果,继续发出下一步的指令。
“独占性”:
解:由于分时操作系统反馈的结果很及时,用户就会以为只有自己在使用该操作系统,其实是有多个终端连接使用,
及时性:
解:给分时操作系统发出指令后,分时操作系统可以及时反馈出执行结果,如:发出一个打印的命令,操作系统立马就打印到屏幕上


实时操作系统

1604035300544


实时操作系统是指,使计算机能在规定时间内,及时响应外部事件的请求,同时完成对该事件的处理,并能够控制所有实时设备和实时任务协调一致地工作的操作系统。
目标:在严格时间范围内,对外部请求做出反应,系统具有高可靠性。
解:实时操作系统主要是要体现在实时和可靠性,如上图的实时发射声纳,实时接收返回的声纳,若是发现礁石,计算机系统必须要在几分钟内自动调动舵机转舵(调整方向)避开礁石,若是不是实时的话可能就会发生撞毁的情况。

分类:
硬实时系统和软实时系统
解:
硬实时系统是对时间要求十分严格,如上图的避礁系统,若是时间出现偏差就会导致船毁人亡的情况,会发生灾难性后果。
软实时系统对时间要求比较宽松,如12306买票这些软件,实时更新票数,但是时间延迟也没有关系。不会发生灾难性后果

能力:
除了多道程序系统的基本能力外,还有以下功能:
(1)实时时钟管理
解:如上图的声纳,若是声纳不及时采集,等船撞上在采集,那不就没有作用吗
(2)过载防护
解:如果系统中运行的程序过多,可能影响系统的性能,会导致实时性变差
(3)高可靠性
解:分时系统要求系统可靠,相比之下,实时系统则要求系统高度可靠。因为任何差错都可能带来巨大的经济损失甚至无法预料的灾难性后果。


嵌入式操作系统

1,定义
在各种电器、电子和智能机械上,嵌入安装着各种微处理器或微控制芯片。
嵌入式操作系统就是运行在嵌入式芯片环境中,对整个芯片以及它所操作、控制的各种部件装置等资源进行统一协调、调度、指挥和控制的系统软件。

实时性:
解:嵌入式系统广泛应用于过程控制、数据采集、通信、多媒体信息处理等要求实时响应的场合,因此实时性成为嵌入式操作系统的又一特点

微型化:
解:嵌入式操作系统的运行平台不是通用计算机,而是嵌入式计算机系统。这类系统一般没有大容量的内存,几乎没有外存,因此,嵌入式操作系统必须做得小巧,以尽量少占用系统资源。
解:嵌入操作系统也不全是微型化的,有些使用在导弹,航空航天设备的也是嵌入式操作系统

高可靠性

其他操作系统

1.个人计算机操作系统
2.网络操作系统
解:网络操作系统主要是实现设备的互联,大家共享资源
3.分布式操作系统
解:
能实现把一个计算问题分成若干子计算,每个子计算可以在计算机网络中的各计算机上并行执行的操作系统!
若是其中一个子计算,它还会自动迁移到其他计算机上执行。
分布式操作系统可以使系统中的计算机相互协作,共同完成一个大型计算机任务,既把一个计算任务分解成若干个并行执行的子任务,让每个子任务在不同的计算机上执行。

5、操作系统的设计过程

1.功能设计
确定所设计的操作系统应具备哪些功能以及操作系统的类型。跟目标有关。
解:如设计嵌入式操作系统,也要让外部的设备实时回应,也是一个实时系统。根据目标来选型

2.算法设计
选择和设计满足系统功能的算法和策略,并分析和估算其效能。

3.结构设计
解:有很多功能,要划分多少个模块,模块与模块之间的关系


操作系统的设计目标
不同的操作系统,目标也不一样,如批处理系统是高效性,实时系统是可靠性
1.可靠性
2.高效性
3.易维护性
4.可移植性
5.安全性
6.简明性

操作系统的结构设计
操作系统结构研究目标
1.系统模块化
2.模块标准化
解:模块标准化,提高标准的接口
3.通信规范化

操作系统的结构
1.整体式结构
解:早期的操作系统是一个整体,并不分层的
2.层次式结构
解:层次式结构的操作系统如:Linux、Uinx,最底层硬件,往上内核,往上系统调用,往上..
3.微内核(客户/服务器)结构
解:
在微内核操作系统中,内核是指精心设计的、能实现现代OS最基本的核心功能的部分。微内核并非是一个完整的OS,而只是操作系统中最基本的部分,它通常用于:
① 实现与硬件紧密相关的处理;
② 实现一些较基本的功能;
③ 负责客户和服务器之间的通信。
它们只是为构建通用OS提供一个重要基础,这样就可以确保把操作系统内核做得很小。

由于客户/服务器(Client/Server)模式,具有非常多的优点,故在单机微内核操作系统中几乎无一例外地都采用客户/服务器模式,将操作系统中最基本的部分放入内核中,而把操作系统的绝大部分功能都放在微内核外面的一组服务器(进程)中实现。例如用于提供对进程(线程)进行管理的进程(线程)服务器,提供虚拟存储器管理功能的虚拟存储器服务器,提供I/O设备管理的I/O设备管理服务器等,它们都是被作为进程来实现的,运行在用户态,客户与服务器之间是借助微内核提供的消息传递机制来实现信息交互的。




二、操作系统的运行环境

1.处理器
处理器的构成与基本工作方法、特权指令和非特权指令、处理器的工作状态、程序状态字

2、计算机系统硬件部分
存储器类型、存储分块、存储器的层次结构

3、中断机制
中断与异常的概念、中断系统

4、系统调用
系统调用与函数调用的区别、系统调用的处理过程


1、处理器
①处理器中的两类寄存器:用户可见寄存器、控制和状态寄存器
②特权指令和非特权指令概念
③处理器的工作状态:管态和目态及二者的转换
④程序状态寄存器(PSW)

2、计算机系统硬件部分
①存储系统的类型:ROM和RAM
②存储的最小单位:二进制;存储的最小编址单位:字节;内存分块。
③存储保护硬件支持:界地址寄存器
④I/O部件:通道、DMA、缓冲技术

3、中断机制
①中断与异常的概念、分类
②中断系统:中断请求、中断响应、中断处理、典型中断的处理
③中断优先级、中断屏蔽、中断嵌套的概念
④系统的调用:系统调用的概念、与函数调用的区别、处理过程
*1、处理器
处理器一般由运算器、控制器和一系列寄存器以及高速缓存构成。
运算器实现算数和逻辑运算。
控制器控制程序运行流程。
寄存器用于处理器执行指令的过程中暂存数据、地址及指令信息。
解:寄存器是用来存储将要处理的指令或者马上要处理的数据的
高速缓存:为CPU和内存提供一个高速的数据缓存区域
解:高速缓存是为CPU和内存之间提供一个存储空间,是为了提高CPU效率而设立的

1、处理器的寄存器
两类寄存器:
寄存器学习:https://book.51cto.com/art/201008/220611.htm
(1)用户可见寄存器,由编译程序分配,减少程序运行时访问内存的次数。一般包括
数据寄存器
解:
数据寄存器用来暂时存放由主存储器(内存)读出的一条指令或一个数据字;反之,当向主存(内存)存入一条指令或一个数据字时,也将它们暂时存放在数据寄存器中
地址寄存器
解:
用来保存当前CPU所访问的内存单元的地址。由于在内存和CPU之间存在着操作速度上的差别,所以必须使用地址寄存器来保持地址信息,直到内存的读/写操作完成为止
条件码寄存器
解:
条件码寄存器中保存着单个位的条件码,由CPU维护,通过检测这些寄存器的状态来执行条件分支指令
如:
CF: 进位标志。最近的操作使用最高位产生了进位。可以用来检查无符号操作数的溢出。
ZF: 零标志。最近的操作得出的结果为0.
SF: 符号标志。最近的操作得到的结果为负数。
OF: 溢出标志。最近的操作导致一个补码溢出——正溢出或负溢出。
条件码寄存器学习网址:https://blog.csdn.net/u010399029/article/details/77175066
学习C语言的时候可以定义变量,在C源码经过编译的时候,程序就会把马上使用的变量的值存到数据寄存器中ib且主要被具有特权的操作系统例程使用,以控制程序的执行。
常见的寄存器是:
程序计数器(PC)
解:记录马上要执行的指令地址,执行一条指令,并把地址变为下一个指令的地址
指令寄存器(IR)
解:用于暂存当前正在执行的指令。指令寄存器的时钟信号是clk,在clk的上升沿触发
程序状态字(PSW)
解:保存当前处理器的各种状态,执行完之后有没有产生进位啊,允不允许中断啊等等


2、指令执行的基本过程
解:简单就两个步骤,复杂的可以分到四到五个
最简单的两个步骤:
(1)读取指令,并将程序计数器的值变成下一个指令的地址
(2)指令放入指令寄存器,处理器解释并执行该指令

指令的分类:
访问存储器指令、I/O指令、算数逻辑指令、控制转移指令、控制器控制指令。

*二、特权指令和非特权指令
在多道程序环境下,指令分为特权指令和非特权指令。
1.特权指令:
在操作系统中那些只能由操作系统使用的指令。
不允许一般用户使用。
比如:
设置程序状态字、
解:要设置程序状态字允不允许中断,中断屏蔽位
启动某设备、
解:设备是由操作系统统一管理,用户是不能直接启动的
设置中断屏蔽字等

2、非特权指令:
普通用户使用的指令
解:操作系统也可以使用非特权指令,普通用户无法使用特权指令

*三、处理器的工作状态
1、管态和目态
管态:操作系统管理程序运行时的状态,又称内核态、系统态等,具有较高特权
目态:一般用户程序运行时的状态,又称用户态、普通态,具有较低特权
解:目态特权较低,无权限修改寄存器

2、处理器工作状态的转换
目态到管态的转换:唯一途径是通过中断。中断响应时交换中断向量,新的中断向量的PSW的处理器状态位管态。
解:系统调用也会产生中断
管态到目态的状态:可通过设置PSW指令,实现从操作系统到用户程序的转换

3、限制用户程序执行特权指令
当用户程序执行中,如果取到了一条特权指令,则处理器拒绝执行该指令,并形成一个“非法操作”事件。然后操作系统通知用户程序--程序中有非法指令。
解:如果当发生了“非法操作"事件后会产生一个中断

*四、程序状态字
为了解决处理器当前工作状态的问题,所有处理器都有一些特殊寄存器,用以表明处理器当前工作状态。用来指示处理器状态的寄存器,称为程序状态字。
比如CF:进位标志、ZF:结果为零标志等。如下图
解:程序状态字就是告诉程序应该怎么处理,如8+3=11就会产生一个进位,程序状态字就会被记录一个CF,用来指示当前处理器的状态

程序状态字一般包括:
CPU的工作状态代码:指明当前的工作状态是管态还是目态。
条件码:反映指令执行后的结果特征,比如结果为0、进位等
中断屏蔽码:指出是否允许中断
PSW用来存放两类bai信息:一类是体现当前指令执行结果的各种状态信息,如有无进位(CF位),另一类是存放控制信息,如允许中断(IF位),跟踪标志(TF位)等


1604234178336

*-、存储系统
(1)类型
读写型存储器(RAM),用来存储随机存取的程序和数据
解:临时内存,需要什么读取进去,一断电就读取的东西就没了。
只读存储器(ROM),存放一些固化的程序。
解:固定的,通常在硬件出场的时候就写入一些程序,如BIOSS,开机自检啊,这些东西,不会断电消失。出场后只能读取无法写入到里面。

*(2)存储分块
存储的最小单位:位(bit)
解:不是0就是1
最小编制单位:字节
解:八个bit等于一个字节  如:00010010  这就是八个bit也是一个字节
分块:为了分配和管理方便,将内存划分为大小相等的块(物理页Page),以块为单位分配内存空间大小一般为512B,1KB,4KB,8KB等
解:一般以4KB为一块,主要是为了好管理和读写的时候更快


*2、存储器的层次结构下图
(1)容量、速度和成本的匹配,,越往上速度越快,越往下成本越低
寄存器、
解:CPU直接操作寄存器信息,速度最快
高速缓存、
解:寄存器和内存的桥梁,可以加速存储部分的指令和数据,以加快CPU的运行,一个缓冲区,
内存储器、
解:程序常驻的地方,运行一个程序就是把一个程序放入内存中,操作系统也是一个程序
磁盘存储器、
解:存放数据的地方,比内存慢,内存和磁盘之间可以设置缓存器,
远程存储(云存储)
解:便宜,因为很少人会用到这么多

1604236794252

(2)存储访问局部性原理
程序执行时,除了少部分的转移和过程调用指令外,在大多数情况下时顺序执行的。
过程调用将会使程序的执行轨迹,由一部分区域转至另一部分区域。既程序将会在一段时间内,都局限在这些过程的范围内运行。
程序存在许多循环结构,这些虽然只由少数指令构成,但是它们将多次执行。
程序中还包括需要对数据结构的处理,如对数组进行操作,它们往往都局限于很小的范围内。
基于这一原理,设计多级存储的体系结构。
解:经过研究以上发现程序往往都是有局限性的、规律性的,所以只要根据局限性先把一部分数据加载进高速缓冲区就可以加快CPU的处理,等高速缓冲区数据没有了就在加载一批进去。

*3、存储保护
多道程序设计系统中,保证每个程序独立运行、互不干扰,称为存储器保护。
方法:界地址寄存器
解:运行程序的时候会在内存中划分一块地方给其运行然后把这块地址的起始值放入界地址寄存器中,在运行程序的时候会对这起始值进行比较,如果超过起始值就是越界了,这是不合法的,不可以这样,这就达到了一个程序保护的目的

二、I/O部件
1.I/O结构
2.通道
3.DMA技术
4.缓冲技术

三、时钟部件
功能:
(1)发现死循环,防止浪费
(2)分时系统中,时钟间隔实现时间片轮转执行
(3)实时系统中,按要求的时间间隔控制设备
(4)定时唤醒各个外部事件
(5)记录各个设备的使用时间和某外部事件发生的时间间隔
(6)记录用户和系统所需的绝对时间,既年、月、日

分类:
硬件时钟和软件时钟
用途分:绝对时钟和相对时钟



*中断

解析网址:https://www.cnblogs.com/frankyou/p/8649435.html
中断机制:
程序在运行当中很有可能会发生某些事情,程序不能运行下去了,程序该怎么做,中断机制就是处理该事件的

中断和异常的概念
*1、中断与异常
中断:指处理器对系统中或系统外发生的异步事件的响应
解:如你电脑在运行脚本,然后突然停电,这造成了一个中断

异步事件:指无一定时序关系的随机发生的事件,如外部设备完成了数据传输任务,某一实时控制设备出现异常情况等。
解:你使用U盘往磁盘传数据,传输完成后,会产生一个中断,告诉程序传输完成

中断源:引起中断的事情称为中断事件或中断源
解:如A程序需要处理器发送一个中断处理请求,要求处理器进行1+1的计算,那1+1的计算就是中断源,我们把引起中断的原因,或者能够发出中断请求信号的来源统称为中断源。

中断请求:中断源向处理器发出的请求信号
解:中断源向处理器请求的时候发出的信号,如:我手头有件急事要你处理,这一“申请”过程,称中断请求

中断处理程序:处理中断事件的程序
解:比如接收到A程序的一个中断请求需要先处理A程序的指令,A程序就是中断处理程序

断点:发生中断时正在执行的程序的暂停点
解:响应中断后,对当前程序运行到哪个位置打了个记号,处理完中断回来继续在这执行

中断响应:处理器暂停当前程序转而处理中断处理程序的过程 
解:程序暂停当前程序的运行,响应了中断处理请求,跑去处理中断处理程序的过程

中断返回:中断处理程序结束后恢复原来程序执行
解:处理器中断后,跑回断点处继续之前运行就是中断返回

中断向量表:为了使得中断装置可以找到恰当中断处理程序,专门设计了中断处理程序的入口
地址映射表,又称中断向量表
解:中断类型不支一种,不同的中断有不同的处理方法,根据中断类型号找到它的中断向量(即中断程序在内存中的地址),然后去执行这段程序(这段程序已经写好,在内存中),

异常:由正在执行的指令引发的中断
解:就是运行出错了。

中断服务程序:为了防止复用了同一个中断线的设备不发生冲突
解:进入网址:https://bbs.csdn.net/topics/391066991

2、中断和异常分类
典型的中断:
时钟中断、
解:时间片 、 定时采集信息等都是时钟中断
输入输出中断、
解:打印机打印完成、读写U盘完成等
控制台中断、
解:控制的Ctr+c 和Ctr+v等操作造成的中断
硬件故障中断。
解:掉电了,计算机某个硬件出现问题了。

典型的异常:
程序中断,
解:指令出错
访管指令异常。
解:用于实现在用户态下运行的进程调用操作系统内核程序,

二、中断系统
*1、中断请求的接收
中断系统如何接收中断源的中断请求,因机器而异。
一般有中断逻辑线路和中断寄存器实现

*2、中断响应
处理器的控制部件中有中断信号扫描结构,它在每条指令执行周期内的最后时刻扫描中断寄存器,查看是否有中断信号到来,若无中断信号,处理继续执行吓一跳指令,若有中断到来,处理器接收由硬件中断装置发来的中断向量代号,准备中断处理准备工作
中断请求响应吹过程:
①处理器接收中断信号;

②保护现场
解:需要保存系统上下文,如:PSW、PC、一些寄存器的值

③分析中断向量
解:查看是具体是哪个中断处理程序进行处理

④将处理器的PC值置为中断程序的入口地址
解:把程序计数器设置为中断处理程序的入口地址

⑤调用中断处理程序 


*3、中断处理
中断信号被接收和响应之后,进行中断处理,包括:检查I/O相关的状态信息,操作I/O设备或者在设备和内存之间传送数据等。
中断处理结束后,中断返回,恢复系统上下文,原有程序继续运行。处理器状态也从管态恢复成目态。
整个中断信号的接收、响应、处理过程,可归纳为以下步骤:
①接收和响应中断
②保护中断断点现场
③分析中断向量,调用中断处理程序
④中断处理结束恢复现场,原有程序继续执行


*4、几种典型中断处理
强迫式中断:
I/O中断、时钟中断、硬件故障中断、程序性中断
自愿中断:
系统服务请求:访管指令等

三、中断优先级、中断屏蔽和中断嵌套
*1、多级中断与中断优先级
作用:
①对各类中断信号依据其紧急程序和重要性划分级别,系统优先处理 最紧急或最重要的任务,
②解决如果有多个中断信号同时到达,如何选中首个被处理的中断信号的问题
解:主要是为了解决并行多个中断的,先处理哪个中断而设立的

*2、中断屏蔽
整个中断系统中,允许或者机禁止中断系统对某些类别中盾响应。PSW中设计有中断屏蔽位。
比如:某个I/O被中断屏蔽,意味着即使有I/O中断信号,处理器也不予响应。
注意:有些信号是不能被屏蔽的,一般这类中断信号属于机器故障中断,比如掉电,机器无法继续操作。一旦发生,无论信号是否被屏蔽,处理器都会立即响应,并进行处理
解:有些东西你可以不去管它,但是有些东西必须管,不然就会出大事

*3、中断嵌套
一般的计算机系统都有多个中断源,如果一个中断处理的过程又发生了中断,有两种策略处理:
①当处理一个中断时禁止其他中断
②中断嵌套。既中断按照优先级划分,允许优先级高的中断优先级低的中断处理过程,优先进行处理。
解:现在操作系统普遍用②不用①,主要因为有同时中断源的情况下,②的处理更好,优先级程度越高,越应该先处理,其他的等处理完优先级的在处理。如果有处理中断低优先级中断的时候来了个高优先级中断,会先保存低优先级中断的系统上下问,然后处理高优先级的中断,处理完高优先级的中断,在继续返回处,进行恢复现场继续处理低优先级中断  

1604324738691

*系统调用

系统调用概念:
就是用户在程序中调用操作胸痛提供的一些子功能,是操作系统提供给编程人员的唯一接口。
解:操作系统提供了两种接口,一种是用户图形操作界面,一种是编程人员的接口,就是系统调用
是一种特殊的过程调用,有特殊的机器指令实现,这条指令将系统转入管态

1、系统调用和函数调用的区别
①运行咋爱不同状态
解:系统调用运行在管态,函数调用运行在目态

②状态的转换
解:系统调用会进行中断,从目态进入管态,当系统调用运行完成胡,从管态转换到目态。但是函数调用是没有的

③返回问题
解:当你一个系统调用结束后,因为产生了一个中断,所以返回的不一定是你原来的,它有可能去运行优先级更高的程序,普通函数执行结束后,还是在原来的程序运行

④嵌套调用
解:系统调用允许去嵌套,但不似普通函数那样无限嵌套,最多嵌套四五层就够,以为产生了中断



*2、系统调用的分类
①进程控制类
解:open一个进程,close一个进程

②文件操作类
解:open一个文件,close一个文件

③进程通信类
解:发送信息,接收信息

④设备管理类
解:启动一个设备,修改设备信息等

⑤信息维护类
 
 
3、系统调用与库函数、API、内核函数的关系
解:系统调用是操作系统提供给应用程序服务用的,但是应用程序一般不直接系统调用,而是调用第三方类库/API,这样就可以不用关注细节,由第三方或API去具体实现

1604405338114

*陷入(trap):
	在系统中为了控制系统调用服务的机构称为陷入或异常处理机构。
陷入或异常(访管指令):
	把由于系统调用引起处理器中断的指令称为陷入指令或异常指令(或称访管指令)
	
系统调用流程程:
解:首先保存上下文,然后根据系统调用号去查找入口地址表,找到对应地址后,访问这个入口地址,进行处理,处理完成后返回现场,恢复上下文,(有时可能有多个系统嵌套调用所以就执行高优先级程序),不一定直接返回用户程序 。这个过程是从目态到管态

1604405844269

三、进程与线程

1、多道程序设计
	多道程序设计的概念、特点
2、进程
	进程的定义、进程与程序的区别、进程的特征、进程的状态与转换、进程控制块、进程的组成、进程的控制
3、线程
	线程的定义、引入线程的好处
4、进程调度
	进程调度的功能、时机、调度算法
	

本章主要讲述了进程和线程的基本概念、进程控制原语、进程调度算法等内容,重点掌握内容如下:
①、程序的顺序执行及其特点
②、程序的并发执行及其特点
③、进程的定义、特征
④、进程的状态转换,重点三状态转换模型
⑤、进程控制块
⑥、进程控制原语
⑦、线程的基本概念、线程的属性、线程和进程的比较
⑧、进程调度的功能、进程调度算法
⑨、内核的概念、内核的功能

多道程序设计

-、程序的顺序执行
1、顺序程序设计:
	程序是在一个时间上按严格次序前后相继的操作序列
	计算机也是以顺序方式工作的:计算机一次执行一条指令、对内存一次访问一个字节或字,对外部设备一次传送一个数据块等
	我们把一个具有独立功能的程序独占处理器直到得到最终结果的过程称为程序的顺序执行。
解:一次只能执行一道程序,无法执行多道程序

2、程序的顺序执行的特点
①顺序性
程序所规定的动作在机器上严格地按顺序执行。
解:总是按照程序规定的顺序执行是顺序性

②封闭性
程序运行后,其计算结果只取决于程序自身,程序执行得到的最终结果由给定的初始条件决定,不受外界因素影响。
解:程序运行后,结果不受外界的影响,结果由初始条件决定

③程序执行结果的确定性
程序执行的结果于其执行速度无关。
解:程序执行的结果于其执行速度无关这是程序的确定性

④程序执行结果的可再现性
如果程序在不同时间执行,只要初始条件相同,则结果就会相同。
解:不同时间执行,初始条件相同,结果就不会改变,这是程序的可在现性



*二、程序的并发执行
所谓并发执行,是指两个或两个以上程序在计算机系统中,同时处于已开始执行且尚未结束的状态
能够参与并发执行的程序称为并发程序。
并发程序的执行和程序顺序执行的特征不同
解:所谓的并发执行就是:你有一个处理器、一个处理器只能运行一个程序,但是你有两个程序要运行怎么办?那就这个执行一个时间片,哪个执行一个时间片,宏观上用户感觉是同时执行两个程序,微观上走走停停的,这就是并发

并发执行的特征如下:
①执行期间并发程序相互制约
解:如抢夺资源,CPU少,抢夺CPU资源时候,有的抢夺到了在运行,有的抢夺不到就停止在那。也有可能是访问设备资源,一个设备只能有一个程序访问,我访问了你不能访问,这就是相互制约。进程的同步有奖

②程序于计算不在一一对应了,允许多个程序共享一个程序段
程序段:段的概念,段是程序的一部分,整个程序所有组成部分分为一个个段,并且给每个段起一个名字 ,可以理解为函数
解:也就是说一个多个程序可能调用同一个function,一个function也可能调用多个程序

③并发程序的执行结果不可在现
并发程序与其只能怪的相对速度以及并发执行的多道程序之间的相互关系有关
解:由于并发程序要抢夺资源了,可能你抢到了,我没有,但我是你后置步骤,你就得等我,这就是生产者和消费者,也可能都要访问同一个变量,然后我在访问后直接修改了值,你读取的就是我修改的值,这也可能会影响结果,这可能会带来一个错误与时间有关的错误

④程序的并行执行和程序的并发执行
程序的并发执行时宏观上的同时,微观上时顺序,并行则是微观上的同时的。
解:并行就是喝饮料看电视,边喝边看,同时进行。并发就是你吃饭看电视,看一下电视,吃一口饭,夹一下菜。


1、多道程序设计技术的引入
所谓的多道程序设计,就是允许多个程序同时进入内存并运行,其根本目的时提高整个系统的效率
例如:A、B两个程序在顺序环境下和在并发环境下执行情况,如图

*因为是顺序执行,所以一次执行处理一个程序,所以要两次才能处理完成,总共80秒。

1604411072346

*因为是并发,可以同时处理两个程序,所以我在使用CPU时你不能用等我用完归还资源才能用,B程序和A程序一开始的的运行步骤都不一样,所以剩下了十分钟,你干你的事我干的事,同时进行大家都不碍事

1604410999281

1604494927807

2、多道程序设计环境特点
多道程序设计:就是允许多个程序同时进入内存并运行。根本目的是提高整个系统的效率。
吞吐量:是指单位时间内系统处理进程的道数,是衡量系统效率的尺度。
解:就是把操作系统比作一种生物,请求处理就是吞,处理完成就是吐。

①独立性
在多道环境下执行的每道程序都是逻辑上独立的,且执行速度与其他程序无关,执行的起止时间也是独立的。
解:你有很多程序,但是每个程序的执行逻辑都是独立的,不会受到其他程序的干扰,你执行的速度不会收到其他程序的干扰,你程序本身执行有多快现在就有多快。其他程序哪怕是慢死也不关你的事情。该那速度还是那速度

②随机性
程序的数据的输入与执行开始时间都是随机的。
解:程序也不知道自己什么时候开始执行,因为有多道程序执行,需要进行抢夺资源,这是异步性/随机性

③资源共享性
解:程序的资源都是共享的,比如:CPU、内部存储器、外部设备等。

3、多道程序设计环境缺陷
①可能延长程序的执行时间
解:A和B程序因为使用多道程序的设计就只需要45秒,但是可能单个程序时间会延长,因为A程序在使用处理器的时候,B程序也要用,但是处理器就一个,所以B程序就只能等待
②系统效率的提高有一定限度
解:因为道数不是越多越好,你程序放个十道八道就切换的时候就很麻烦了,所以适中就好

1604494929953

进程

一、进程的定义
进程是具有一定独立功能的程序在某个数据集合的一次运行活动,是系统进行资源分配和调度的一个独立单位。
分为:系统进程和用户进程

1、进程与程序的联系
程序是构成进程的组成部分之一,一个进程的运行目标是执行它所对应的程序。
进程=程序+数据+进程控制块(PCB) 
解:进程就是运行中的程序,运行程序就是为了操作数据,引入进程是为了并发,并发就是通过控制每个程序的进程控制块实现的。

2、进程和程序的区别
①程序是静态的,进程是动态的。
解:因为程序是存储在磁盘上的,进程是运行的程序,  而且进程在并发的过程中,是走走停停的,进程是有生命周期的。
②二者是多对多的关系。
解:一个程序可以创建多个进程,一个进程运行多个程序

2、可在入程序
一个能够被多个用户同时调用的程序称作是“可再入”程序。
可再入程序必须是纯代码,程序在执行过程中不会修改自己的代码,必须与数据区隔离。
比如:操作系统、编译程序,它们能同时被不同用户调用而形成不同的进程。
解:可以被共享的不可修改的程序叫做可再入程序。

**3、进程的特征
①并发性
解:一个进程是参与并发,大家都是走走停停,同时处于开始和结束状态之间
②动态性
解:进程是动态,由创建产生,停止消亡,中间有状态的变化。这就是动态性
③独立性
解:进程在运行的时候,它们是互不干扰的,是各玩各的。 独立的运行,独立的资源分配。独立的调度
③交往性
解:进程和进程之间,很可能产生关系,直接关系或间接关系,如:输入进程和输出进程之间的合作,共同抢夺CPU等
⑤异步性
解:进程在运行期间不知道自己什么时候运行,什么时候停止,什么进入什么状态这都是异步的
⑥结构性
解:运行的程序+数据+PCB(进程控制器)


1、三状态进程模型
不同的操作系统对进程的分类也不太一样,但是一般都有三种状态
①运行状态
解:正在占用处理机进行处理
②就绪状态
解:有一个进程就等处理机进行处理了
③等待状态/阻塞状态
解:进程因为某些事情需要暂停等待某些事情处理完成

①就绪 -> 运行
解:进程在就绪的状态下,直接进入处理器运行
②运行 -> 就绪
解:进程运行的好好的,结果时间片用完了或异步事件,导致停止,但是又没其他事情,就只能就绪在那候着
③运行 -> 等待
解:进程占用处理器完成了, 但是要输出结果,如:打印到屏幕就会进入到等待
⑤等待 -> 就绪
解:进程打印结果完成后又要进行运算,所以又进入就绪

三进程状态模型图

1604497444067

五状态模型

①运行状态
②就绪状态
③阻塞状态
④创建状态
解:程序要被加载进内存也要时间,所以有一个创建的进程,创建的进程是直接进入就绪状态的
⑤结束状态
解:进程执行完成后被释放掉了就是结束

1604498187247

七状态模型

①运行状态
②就绪状态
③阻塞状态
④创建状态
⑤结束状态
⑥就绪/挂起
解:程序运行的时候会由于内存不足而被放置的外部的储存器中挂起,在内存足够的时候重新激活放入内存资源
⑦阻塞/挂起
解:程序在运行的时候在等待某件事的时间,但是由于内存不足,所以挂起到外部存储器中,可能会被在内存足够的时候被激活,或者挂起期间某件事情发生了,但是内存还是不足,给释放到就绪/挂起上面去了

1604498507301

**进程控制块
为了便于系统控制和描述进程的活动过程,在操作系统和兴中定义了一个专门的数据结构,成为PCB。
PCB的作用:
	描述进程的基本情况以及进程的运行变化过程。
	PCB是进程存在的唯一标志,当系统创建一个进程时,为进程设置一个PCB,在利用PCB对进程进行控制和管理。撤销进程时,系统收货PCB,进程也随着消亡。
解:PCB就是进程还活着的证据,如果没有PCB,进程就不存在了。为了运行多个程序引入并发的概念,PCB就是为并发专门设计的数据结构

1、PCB的内容
①调度信息
供进程调度使用,包括
进程名、进程号、
地址空间信息、
解:你进程在内存的位置,你占了多大地方
优先级、
解:系统中有很多进程,根据优先级来进行处理
当前状态、
解:就绪、运行、阻塞
资源请求、
解:你占用哪些资源、你申请了哪些设备,你打开了哪些文件
"家族"关系、
解:你可以创建新进程,就叫子进程,你就叫父进程,你子进程又可创建子进程,就这样子子孙孙
消息队列指针、
解:进程之间要通行,需要记录队列的执政
进程队列指针、
解:等待队列啊、就绪队列啊都有相应的队列指针,PCB指针
当前打开文件等

②现场信息
刻画了进程的运行情况,主要是CPU寄存器的信息,如:程序状态字、时钟、界地址寄存器等。当程序中断时,需要保存现场信息   

2、进程的组成
进程有程序、数据和进程控制块组成
PCB是"灵魂";
解:PCB是进程的唯一标识,没有了PCB,进程就相当于不存在的
程序和数据是"躯体"。
解:程序是进程要执行的东西, 数据是进程要处理的内容

3、PCB组织
线性方式
解:排成一队执行,最前面的现执行

链接方式
解:分成三队加一人,一人是正在干活的,其他三队分别是就绪队,阻塞队,空闲队,队里每个人都得知道自己身后是谁,若是没有人就是0

索引方式
解:三个指针在根据自己手里的表,把进程叫出来,首先执行指针找一个最高优先级的进程先进行运算,然后就绪指针查看手里的就绪索引表,在最高优先级的进程处理完后把进程排在第一位的进程交上去处理。

1604582125799

1604582471193

4、进程的队列
就绪队列
解:往往是一个或者多个
等待队列
解:往往是多个,因为进程可能因为各种原因进入等待状态,一个原因就一个队列
运行队列
解:一个处理器就一个,几个处理器就几个

1604582708714

5、进程队列的组成
进程队列实际是PCB的链接,链接分为:单向链表和双向链表。
单向链表:排队的时候只需要记住自己下一个是谁就行了
双向链表:排队的时候要记住自己下一个是谁,上一个是谁
出队:一个进程从所在队列退出
解:如等待队列,等待的事情发生了
入队:一个进程排入到指定队列
解:如处理器处理一个进程,进程时间片用完了,就转到就绪队列种
插队:一个进程插入到某个进程队列的指定位置


四、进程控制
对进程整个生命周期中各种状态之间的转换进行的控制。由原语实现。
解:进程的生命周期创建-生成,撤销-销毁
原语:
就是由若干条指令组成的,用于完成一定功能的一个过程,是一个不可分割的基本,既原语在执行过程中,不允许被中断。原子操作在系统下执行,常驻内存。
解:原语就是一个整体,执行就执行一个原语。无法在执行原语的时候插一脚,去执行别的

1、进程控制原语
①创建原语
一个进程可以使用创建原语创建一个新的进程,前者称为父进程,后者称为子进程,子进程又可以创建新的进程,从而形成一个进程家族。
主要任务:建立进程控制块PCB
过程:先申请一空闲PCB,然后将有关信息填入PCB,置进程状态为就绪状态,插入就绪队列。 
解:有关信息:创建的时间,放入内存的地址等

②撤销原语
当一个基础南横完成任务后,就应当撤销它,以便及时释放它所占的资源。
撤销的实质:撤销进程控制块的PCB
过程:找到要被撤销进程的PCB,将它从所在队列消去,撤销属于该进程的一切"子进程",释放所占全部资源,并消去被撤销进程的PCB。
解:因为该进程的"子进程"是不可控的所以要消除, 现在的Linux系统会收养"子进程",因为Linux可以让其变得可控 

③阻塞原语
若某个进程的执行过程需要I/O操作,则该进程调用阻塞原语将其从运行状态变为阻塞状态
过程:产生中断,把处理器的当前状态保存在PCB的现场信息中,当前进程置为等待态,插入等待队列。 	

④唤醒原语
一个进程因为等待某事件的发生而处于等待状态,当该事件发生后,就用唤醒原语将其转换为就绪状态。
过程:在等待队列中找到该进程,将进程的当前啊状态置为就绪状态,然后将它从等待队列撤出并插入到就绪队列中排队,等待调度执行。 


2、UNIX操作系统的进程控制创建操作fork
#include<stdio.h>
void main(){
        __pid_t pid;
        int x =1;
        pid =fork();
        if (pid==0){
        printf("child:x=%d\n", ++x);
        }
        else
        {
        printf("parent:x=%d\n", --x);
        }
}

fork函数下图解
解:fork函数会创建一个子进程并且返回子进程的PID,然后给子进程的一个值为0,子进程会复制父进程的内存空间,然后在执行创建它之后的代码,创建它之前的指令无视掉。下图输出两次就是因为出现了一个子进程

1604586470855

1604586523338

线程

一、线程的基本该概念
解释地址:https://baike.baidu.com/item/%E7%BA%BF%E7%A8%8B/103101?fr=aladdin
线程(英语:thread)是操作系统能够进行运算调度的最小单位。它被包含在进程之中,是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流,一个进程中可以并发多个线程,每条线程并行执行不同的任务。在Unix System V及SunOS中也被称为轻量进程(lightweight processes),但轻量进程更多指内核线程(kernel thread),而把用户线程(user thread)称为线程。
线程是独立调度和分派的基本单位。线程可以为操作系统内核调度的内核线程,如Win32线程;由用户进程自行调度的用户线程,如Linux平台的POSIX Thread;或者由内核与用户进程,如Windows 7的线程,进行混合调度。
同一进程中的多条线程将共享该进程中的全部系统资源,如虚拟地址空间,文件描述符和信号处理等等。但同一进程中的多个线程有各自的调用栈(call stack),自己的寄存器环境(register context),自己的线程本地存储(thread-local storage)。
一个进程可以有很多线程,每条线程并行执行不同的任务。
在多核或多CPU,或支持Hyper-threading的CPU上使用多线程程序设计的好处是显而易见,即提高了程序的执行吞吐率。在单CPU单核的计算机上,使用多线程技术,也可以把进程中负责I/O处理、人机交互而常被阻塞的部分与密集计算的部分分开来执行,编写专门的workhorse线程执行密集计算,从而提高了程序的执行效率。

进程的属性
-一个可拥有资源的独立单位
解:比如内存资源
-可独立调度和分派的基本单位
解:处理器在调度的时候是以进程为单位进行调度

程并并发执行所需要付出的时空开销:
-创建关键进程的开销
	·内存空间、I/O设备、PCB
-撤销进程的开销
	·对其资源作回收
-进程切换的开销
	·保留CPU环境,设置新进程CPU环境
这些开销,限制了系统中进程的数目,进程切换也不宜频繁,限制了并发程度的进一步提高

引入线程的目的:
	引入线程式为了使多个进程并发执行
	引入线程式为了减少程序并发执行时所付出的时空开销。
解:因为进程是一个大整体,并发执行中每次都要保留一个整体的CPU环境,会造成过多的时空开销,线程是一个大整体中的一个小片段,切换程序时运行到哪个片段就保留哪个片段环境就行了,大整体就不用管他,这样就可以减少不必要的时空开销

1、什么是线程
在引入线程的操作中,线程是进程中的一个实体,是处理调度和分配的基本单位。
线程基本上不拥有系统资源,只拥有少量在运行中必不可少的资源,但它可与同属一个进程的其他线程共享进程所拥有的全部资源
解:程序你可以理解为有多条流程线的集合,然后一条流程线就是一个线程,线程是处理机实际调度的单位
解:资源是分配给进程的,线程是共享进程的资源的,线程是分配给处理器的单位

一个线程可以创建和撤销另一个线程;同一个程序中的多个线程可以并发执行。
解:python程序,其中的一个代码就是多线程执行的,那运行这段代码的线程就可以创建多个线程。

1604802663351

2、线程的属性
①每个线程有一个唯一的标识和一张线程描述表
解:线程描述表和进程的PCB功能类似,可以称为TCB(Thread)
②不同的线程可以执行相同的程序
解:python对接口进行并发请求,就是启动多线程,一条线程就是一个对接口请求的发射器
③同一个进程中各个线程共享该进程的内存地址空间
④线程是处理器的独立调度单位,多个线程可以并发执行
⑤一个线程具有生命周期,经历等待、就绪、运行等状态变化


3、引入线程的好处
①创建一个新线程花费时间少
②线程之间的切换花费时间少
③线程之间通信无需调用内核,不需要要额外的通信机制,使通信简单、信息传送速度快
解:因为线程是共享同内存空间的,所以A线程修改内存空间后,B线程就可以知道,进程通信时需要调用内核的,因为它们要走底层的接口进行通信

二、进程和线程的比较
1、调度
线程作为调度的基本单位,同进程中线程切换不引起基础进程切换,当不同进程的线程切换时才引起进程切换。
2、并发性
一个进程间的多个线程可并发,不同线程的多个线程也可以并发执行
解:并发性提高的了,一个进程就可以并发了

3、拥有资源
线程仅拥有隶属进程的资源;
解:包含TCB和一点点堆栈的指针,共享进程的资源
进程时拥有资源的独立单位。

4、系统开销
线程低、进程高


三、线程实现机制
解:https://www.cnblogs.com/lixiaochao/p/9490264.html
不同的操作系统使用不同的线程实现机制,大致分为三类
1、用户级线程
仅存在于用户空间,由用户层中的线程库提供对线程的创建、撤销、切换,以及线程之间的同步于通信等支持,而无须内核的支持

2、内核级线程
由OS直接支持,更灵活,方便
解:把内核分为多个内核线程,然后再把内核线程实现一种高级接口:轻量级线程,然后程序去调用轻量级线程,轻量级线程和内核线程是1:1的。

3、混合方式
解:线程创建、切换、撤销依然是在用户空间中,而轻量级线程则作为用户线程和内核线程的桥梁,这样可以使用内核提供的线程调度及处理器映射。用户线程和轻量级线程是N:M,

1604807570381

进程调度

1、进程调度的主要功能
①记录系统中所有进程的执行状态;
解:如:进程所处状态、所处的内存位置,运行了多长时间,是什么原因停止	 
②根据一定的调度算法,从就绪队列中选出一个进程,准备把处理器分配给它;
③分配处理器

2、进程调度的时机
①正在执行的进程运行完毕
③正在执行的基础进程由于某种错误而终止运行
③时间片完
解:分时系统比较常用
④正在执行的进程调用阻塞原语将自己阻塞起来
⑤创建了新的进程
解:可能新创建的进程的优先级、紧急度比较高。所以就让其线执行
⑤正在执行的进程调用了唤醒原语操作激活了等待资源的进程。

处理的调度方式:非抢占式和抢占式
①非抢占式
一旦把处理机分配给某个进程后,就一直让它运行下去,绝不会因为时钟中断,或任何其他原语,去抢占该正在运行进程的处理机,直至该进程完成,或发生某事件而被阻塞时,才把处理机分配给其他进程。
解:一直运行该程序,直至该进程完成或阻塞。

②抢占方式
运行调度程序根据某种原则,去暂停某个正在执行的进程,将已分配给该进程的处理机,重新分配给另一进程
抢占方式能满足实时任务的需求。但抢占方式比较复杂,所需付出同开销也较大
解:抢占式,就是允许你抢夺CPU允许时间,但是你要符合抢占的要求,判断你是否能抢占需要一些资源,相比非抢占式就多使用了一些资源。

调度算法设计原则
1、进程行为
I/O密集型和计算密集型
解:I/O密集型的进程优先调度,因为I/O直接处理一下就可以了,计算密集型却需要占用CPU长时间进行计算机

2、系统分类
批处理、交互式、实时系统
解:不同的操作系统对算法的需求也不一样,批处理需要提高吞吐量,实时系统要提高实时和可 靠性等

3、调度算法的设计目标
共同目标:资源利用率高、公平、平衡、强制执行策略。
批处理目标:平均周转时间短、系统吞吐量高、处理机利用率好
解:周转时间就是每个任务的运行时间
分时系统目标:响应时间快、均衡性
解:一个命令很长,我等久一点可以,但是一个很短的命令,你响应慢就有点说不过去了
实时系统的目标:截至时间的保证、可预测性
解:截至时间是必须在一个时间开始,必须在一个时间结束  

进程调度算法

周转时间:程序从进入处理就绪到执行完成的时间。 
1、先来先服务
①算法思想:总是把处理机发呢配给最先进入就绪队列的进程,一个进程一旦分得处理,便执行下去,直到该进程完成或阻塞时,才释放处理机
②优点:实现简单
③缺点:没考虑进程的优先级
解:有些进程的优先级比较高的,执行时间短的进程没考虑进去,因为进程时间短让它先执行可以降低整体的周转时间。不然就是大家都是同样时间进来的,我处理的事件的时间只需你的百分之一,但是我还是要等你处理完在处理我的

1604810945801

2、最短进程优先算法
①算法思想:该算法从就绪队列选出"下一个CPU执行期"的最短的进程,为之分配处理机。
②优点:所有进程都同时可运行时算法最优
解:这种算法就是大家的事情都重要性都一样的时候是最优的算法,这样可以降低平均周转时间。从整体来看是最优的。这是非抢占式的

1604811962864

3、最短剩余时间优先算法
算法思想:
总是选择剩余时间最短的哪个进程运行。当一个新的进程到达时,其整个时间同当前进程的剩余时间做比较,如果新进程时间更少,则当前进程被挂起,运行新的进程。
解:这是抢占式的,最短进程优先是非抢占式的。

4、最高响应比优先算法
①算法思想:总是优先调度响应比最大的进程
②性能:先来先服务器和最短进程优先算法的折中
解:响应比Rp越大的进程,越早运行,可以杜绝饥饿,因为按照响应比公式Rp,预计运行时间越久,等待时间就越长。公式是以运行时间为默认是,等待时间越长权重比越大。一次响应一次计算
预计运行时间是10
等待时间是2
公式转换:
响应比Rp公式: 1 + 预计运行时间分之等待时间
等于:十分之十 + 十分之二
等于:十分之十二 化假分数带分数为:一又十分之二

1604813883902

1604820694702

5、转轮算法
①算法的思想:
最早来自于分时系统。
将处理器的处理时间划分成一个个时间片,就绪队列中的诸多进程轮流与运行一个时间片,当时间片结束时,就强迫运行进程让出处理器,该进程进入就绪队列,等待下一次调度。

②影响时间片设置的因素:
系统响应时间
解:如果响应时间慢就把时间片设置长一些,如果响应时间快就把进程时间设置短一些
就绪进程数目
解:如果就绪进程数目多就把时间片设置长一些,如果就绪进程数目少,就把时间片设短一些
计算机的处理能力
解:如果计算机处理能力好就设置短,计算机处理器能力不怎么行就设置长
小结:时间片设的太短, 导致过多的进程切换;太长响应时间变长。合理的时间片20~50ms
解:如果响应时间太长就不能忍受,如果时间变得比每个进程都长,那就退化成先来先服务了

6、最高优先级算法
①算法思想:
为每个进程设立一个优先级,每次将处理器分配给具有最高优先级的就绪进程。
②可以保证紧迫性进程优先运行

7、多级反馈队列算法
结合了先进先出、时间片轮转、可抢占式最高优先级调度算法。
算法思想要点:
①被调度队列的设置
解:这种算法有n个调度队列,每个队列的优先级都不一样,优先级越低,时间片越长
②在同一个队列的调度原则
解:在同一个队列中,以先来先服务来进行调度
③在不同调度队列之间的调度原则
解:分为优先级,只有最高优先级队列没有进程才会调度第二个优先级的进程,高优先级抢占时,被抢占的进程放回原就绪队列末尾。 
④进程优先级的调整原则
解:进程在最高优先级队列中被调度,如果没有时间片耗尽,没有运行完成,就降到第二队列中

1604823041216

内核

  • 内核的概念:
    为了提高系统的运行效率,保护系统的关键部分不被破环,一般把操作系统中提供支持系统运行的各种基本操作和基础功能的一组程序模块集中安排,形成一个操作系统的核心,称为系统态那个核心或系统内核,简称内核。
      
    内核本身不是进程,是系统进程和用户进程赖以活动的基础,一般内核常驻内存,操作系统其他部分则根据需要调进或调出内存。
      
    内核的功能:
    ①、中断处理程序
    ②、进程同步与互斥
    ③、进程调度
    ④、进程控制与通信
    ⑤、存储管理
    ⑥、时钟管理
    内核的各种功能通过执行原语操作来实现
      
      
      
      
    

四、进程同步与互斥

1、进程间相互作用
相关进程和无关进程、与时间有关的错误
2、进程的同步与互斥
进程的同步、进程的互斥、临界区
3、信号量及PV操作
信号量、PV操作、用PV操作实现互斥、PV操作实现进程同步
4、经典的进程同步问题
简单生产者-消费者问题、多个生产者-消费者问题、读者-写者问题、同步与互斥问题的综合应用
5、进程间通信
三类解决方案:共享内存、消息机制、共享文件

本章主要描述了进程同步和互斥的基本概念、进程同步机制、信号量机制及PV操作等内容,重点掌握内容如下:

  1. 进程同步和互斥的概念
  2. 临界区、临界资源,进入临界区的原则
  3. 信号量及PV操作的定义、物理含义及相关注意事项
  4. 进程同步典型算法:生产者–消费者问题、读者写者文件
  5. 进程通信:共享内存、消息通信和管道通信机制

进程间相互作用

  1. 相关进程:在逻辑上具有某种联系的进程

  2. 无关进程:在逻辑上没有联系的进程

  3. 举例:

    ①为两个不同的源程序进行编译的进程,它们可以并发执行,但它们之间无关,是 无关进程

    ②三个进程,分别是读数据进程、处理数据进程、打印结果进程,它们相互依赖、相互合作,是一组相关的进程

对于进程来说,可能有若干并发进程同时使用共享资源,既一个进程一次使用未结束,另一进程也开始使用,形成交替使用共享资源。

结果:形成与时间有关的错误

解释:与时间有关的错误可以这样描述:程序并发执行时若共享了公共变量,其执行结果将与并发程序执行的相对速度有关,即给定相同的初始条件,也可能会得到不同的结果,此为与时间有关的错误。

解:下列中①②执行都没有问题,第三个出现了与时间有关的错误,第三个首先运行了程序B,运行到一半去运行了程序A,运行完程序A后又返回现场运行程序B。这导致A的运行无意义,或者出错了。

1605013204092

进程的同步与互斥

进程的同步:***进程的同步就是你要我先做特定的动作,你才能执行操作

​ 是指进程之间一种直接的协同关系,一些进程相互合作共同完成一项任务。

例如:

​ 进程A从硬盘上读记录,每读出一条记录就存入缓冲区,进程B从缓冲区中取出记录加工,直至所有记录处理结束。

直接制约关系:A若没有把记录读入缓冲区,B等待;反之,B若没有从缓冲及区取出记录,A等待。

解:即是相互合作也是相互制约

进程的互斥:*** 互斥是我用了,你不能用*

在系统中,许多进程常常需要共享资源,而这些资源往往需要排他性的使用,既一次只能为一个进程服务,因为各进程间只能互斥使用这些资源,进程间的这种关系就是进程的互斥

例如:

​ 多个进程竞争使用打印机、一些变量、表格等资源。

进程间的互斥是一种间接制约关系

临界区

  1. 临界资源:若在系统中的某些资源一次只运行一个进程使用,则这类资源称为临界资源或共享变量

    解:A进程要调用X文件,B进程也要调用X文件,那X文件就是临界资源

  2. 临界区:访问临界资源的那段代码

    解:A进程中使用X文件的代码就叫临界区,B程序使用X文件的代码也叫临界区

  3. 相关临界区:如果又若干进程共享某一临界资源,则该临界区称为相关临界区

    解:A进程的临界区和B程序的临界区使用的是同一个临界资源,那这两个临界区就是相关临界区

  4. 相关临界区的调度使用原则

    ①当灵界资源空闲,若有一个进程要求进入临界区,应允许它立即进入。–有空让进,有效利用资源。

    ②若有一个进程已在临界区,其他要求进入临界区的进程必须等待。–无空等待,互斥进入

    ③当没有进程在临界区,而同时有多个进程要求进入临界区,选择其一进入,其他等待。–多种择一

    ④任意进程进入临界区的要求应在有限时间满足–有限等待,避免死等、饥饿

    解:死等是怎么也等不来

    ⑤处于等待状态的进程应放弃占用处理器。–让权等待,避免忙等。

    解:忙等是一直占用着资源不操作,比如你得到了打印机资源,但是你进程因为某些事情陷入了等待。那打印机一直被占用,但是没有被使用

信号量及P、V操作

  • 为了保证进程的同步与互斥,系统中应该有解决这些问题的机制,称为同步机制。
  • 实际上,同步时并发进程之间的执行时序的一种相互制约关系。
  • 进程互斥的实质也是同步,可把进程互斥看做是一种特殊的进程同步。

  • 同步机制有两类:硬件同步机制,软件同步机制

  • 同步的操作要放到互斥操作的前面

信号量

  1. 信号量的提出

    1965年,荷兰学者Dijkstra首先提出关于信号量的概念,他把信号量定义为一个用于表示资源数目的整型量S,与一般整型量不同,除初始化外。仅能通过两个标准的P操作和V操作来访问。

  2. P、V操作的使用

    放在程序中,用P(S)和V(S)表达,实现进程的同步与互斥

    ①P操作定义:

    P(S)
    {
    	S= S-1;
    	若S<0,则该进程状态置为等待状态,然后将该进程的PCB插入相应的S信号量等	待队列队尾,直到有其他进程在S上执行V操作为止;若是不小于0证明有资源可以使用就不用等待
    }
    

    解:P操作时请求资源。因为只有你去请求了才有 可能等待。

    ②V操作定义:

    V(S)
    {
    	S= S+1;
    	若S<=0,唤醒在S信号量队列中等待的一个进程,将其状态改变为就绪态,并将其	插入就绪队列;执行本操作的进程继续执行
       
    }
    

    解:V操作时释放资源,因为释放了资源,一个进程顶上去运行,空出了个位置,才会去等待队列拉一个进就绪队列

信号量和P、V操作的物理含义

​ 信号量S表示某类可用的资源。对于不同的资源,用不同的信号表示。

​ S>0时,S表示某类资源的可用数量

​ S<0时,其绝对值表示排在S等待队列中进程的数目

​ 执行一次P操作,表示请求一个资源;

​ 执行一次V操作,表示进程释放一个资源

用P、V操作实现进程之间的互斥

​ 假设有进程A、B竞争进入临界区,用P、V操作实现进程之间的互斥。

​ 首先定义互斥型信号量S,并使之初值为1。

解: A、B在临界区操作之前均要进行P操作,之后均要进行V操作。初值为1的情况, 进程A进入处理器,进行P操作信号量S-1,现在S的值是0,然后进行判断,若是S不小 于0就代表当前是有资源的,就让该进程使用资源。然后B进程进入处理,进行P操作, 若是当前A程序仍在临界区未进行V操作,则B进行P操作后,S的值应为-1,判断S小于 0的话,让进程进入等待队列。A程序处理完后,执行V操作后,S的值变为0,V操作判 断S小于等于0,则代表有进程在等待队列,就让其加载进就绪队列。

1605018256415

用P、V操作实现进程间的同步

解题思路:

​ 如果有两个进程同步,设置两个信号量S1,S2,初始值可用设为0。为了表达同步,同一个信号量的P、V从左分属与两个进程,

解:信号量数量可以随意设置,初始值可设为任意值,达到目的即可

解:

​ ①执行之后需要达到某些条件才能再次执行的,信号量设置为1,由其达到某些条件的 进程执行V操作

​ ②若是有前置条件信号量设置为0 ,由前置条件进行V操作

​ ③既有前置又有后置,设置两个信号量,前置的信号量为0,后置的为1.前置的由前置 执行V操作,后置的由后置的执行V操作

例一:

步骤:首先把信息送入缓冲区然后把信息从缓冲区取走。

解:定义S1信号量和S2信号量为0假设下图中B进程先进入处理器,首先S1信号量变为-1,然后进入等待状态,等待状态后,程序A进入了处理器,把信息送入缓冲区;然后把S1的信号量变为0,这时候进程B就从等待队列转移到就绪队列了,然后进程A把S2变为-1,进程A进入S2等待队列。这时候进程B恢复现场,把信息从缓冲区取走;然后把S2变为0,这时候就把进程A从S2的等待队列拉出,执行

例二:

​ 有三个进程,进程get从输入设备上不断读取数据,并放入缓冲区buffer1;进程copy不断地将缓冲区buffer1中的内容复制到缓冲区buffer2;进程put则不断将buffer2的内容在打印机上输出。

解:定义S1、S4信号量为1,定义S2、S3为0

# 进程get
{
P(S1)
从输入设备不断读取数据
V(S2)
}
# 进程copy
{
P(S2)
P(S4)
将缓冲区buffer1中的内容复制到缓冲区buffer2
V(S1)
V(S3)
}
# 进程put
{
P(S3)
将buffer2的内容在打印机上输出
V(S4)
}

1605021030037

例3:

A B C D

S1 = 1
{
P(S1)
A
V(S2)
}
S2 = 0
S3 = 1
{
P(S2)
P(S3)
B
V(S1)
V(S4)
}
S4 = 0
S5 = 1
{
P(S4)
P(S5)
C
V(S3)
V(S6)
}
S6 = 0
{
P(S6)
C
V(S5)
}

经典的进程同步问题

一、简单生产者–消费者问题

问题描述:

设有一个生产者进程P,一个消费者进程Q,他们通过一个缓冲区联系起来,如图4-2所示。

1605586505267

  1. 二者关系描述:

    1. 生产者生产产品放入缓冲区,消费者从缓冲区取产品,进行消费;
    2. P进程不能往已经“满”的缓冲区放产品,Q进程不能从“空”缓冲区中取产品
  2. 信号量设置:

    1. empty,初值为1,用于指示空缓冲区数量

      解:因为一开始的时候,是有一个空缓冲区的,设置这个为1的话,如果生产者先生产就可以直接放入缓冲区

    2. full,初值为0,用于指示满缓冲区数量

      解:因为一开始的时候,缓冲区是空的,如果消费者这时候去缓冲区取数据就会导致错误,所以就不可以设置为0,这样消费者进行消费前执行P操作就会被阻塞进入等待

  3. 解决方案:

    1605586872699

二、多个生产者–消费者问题

  1. 问题描述

    设有若干个生产者P1,P2,..,若干消费者,Q1,Q2,…,他们通过一环形缓冲池联系起来。

    1605586985071

  2. 同步问题和信号量设置:

    1. 生产不能往“满”缓冲区中放产品,设置信号量empty,初始值为k,指示缓冲池中空缓冲区数目。

    2. 消费者不能从“空”缓冲区中取产品,设置信号量full,初始值为0,指示缓冲池中的满缓冲区数目。

    3. 互斥问题和信号量设置:缓冲池必须互斥访问,设置信号量mutex,初值为1。

      解:这个缓冲池是大家共享的,要互斥访问,不然P1往缓冲池放产品,P2,也往缓冲池放产品,这样就导致这个缓冲池被放了两个产品,但是缓冲池是无法放入两个产品的,

    4. 其他变量设置:

      整型量i,j初值为0,分别用于指示空缓冲区和满缓冲区位置

      解:i是空缓冲区在缓冲池的位置,使用(i+1) mod k可以让空缓冲区指针在越界前重新计算如:

      我有10个空缓冲区,用了9个,这时候i的值应为9,然后生产者往第十个缓冲区放入产品的时候,这时候的i就进行计算机i= (1+9) mod 10 ,这时候没有余数就是变为0,就重新开始了一轮。

    5. 算法:

      1605610859374

三、读者–写着问题

  1. 问题描述

    假定有某个共享文件F,系统允许若干进程对文件进行读或写,读文件的进程称为读者,写文件的进程称为写者,他们遵守如下规定:

    • 多个进程可以同时读文件F
    • 当一个进程对文件F进行写时,不允许其他进程文件进行读或写
    • 当有进程正在读文件时不允许任何进程去写文件
  2. 问题分析:

    • 写者进程与读者进程之间互斥文件F
    • 写者进程与第一个读者之间互斥访问文件。
  3. 变量设定

    • read_count:整型量,当前正在读的读者进程个数,来一个读者,数量加1,走一个读者,数量减1;
    • mutext:互斥信号量,对read_count互斥访问。
      • 解:进程从来都不是线性的是贪婪的,该信号量是为了防止同时进来两个读进程,然后两个都在进行检查,然后两个读者都在对write变量进行P操作
    • write:互斥信号量,写者与写者的互斥,写者与读者之间的互斥。
    # 读者
    read_count = 0
    mutext = 1
    write = 1
    while(True):
    	P(mutext)
    	if read_count == 0:
    		P(write)
        read += 1
    	V(mutext)
    	# 读文件 
    	P(mutext)
        read_count -= 1
    	if read_count =0:
    		V(write)
    	V(mutext)
    
    # 读者
    while(True):
    	P(write)
    	# 写文件
    	V(write)
    

例题:

若有一个文件F,供多进程读。先把进程分为A、B两组,规定同组的进程可以同时读文件F,但不同组的进程不能同时读文件F。使用PV操作写出该问题的同步算法。

变量设置:

定义两个计数器C1和C2分别记录A组和B组正在读文件的进程数,它们的初始值均为0.

信号量设置:设置三个信号量S1、S2和SAB才能保证正确并发执行。S1用来保证A组进程对C1的互斥访问,S2用来保证B组队C2的互斥访问,SAB用来保证A组进程和B组进程队文件F的互斥访问,它们的初始值均为1;

# A组
C1 = 0
S1 = 1
SAB = 1

while(True):
    P(S1)
    if C1 == 0 :
        P(SAB)
    C1 += 1 
    V(S1)
    # A组读文件
    P(S1)
    C1 -= 1
    if a_read_count == 0:
        V(SAB)
	V(S1)
# B组
C2 = 0
S2 = 1
SAB = 1

while(True):
    P(S2)
    if C2 == 0 :
        P(SAB)
    C2 += 1 
    V(S2)
    # B组读文件
    P(S2)
    C2 -= 1
    if C2 == 0:
        V(SAB)
	V(S2)

管程

信号量及PV操作的缺点:

  • 程序易读性差

  • 程序不利于修改和维护

  • 正确性难以保证

    为了更易于编写正确的程序,引入管程

定义:

​ 是一个由过程、变量及数据结构等组成的一个集合,它们组成一个特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程。

组成:

​ 管程名称、共享数据说明、队数据进行操作的一组过程,对共享数据赋初值的语句。

进程通信

一、共享内存

  1. 原理

    在相互通信的进程之间设有一个公共内存区,一组进程想该公共内存中写,另一组进程从公共内存中读,通过这种方式实现两组进程之间的信息交互

1605614719555

二、消息机制–消息缓冲

  1. 消息缓冲通信原理:

    进程间的数据交换,是以格式化的消息(也称为报文)为单位的。程序员直接利用操作系统提供的一组通信命令(原语),实现大量数据的传递,通信过程对用户是透明的。

    解:有进程要要发消息时,便申请一个消息缓冲区,然后把消息放入缓冲区,将缓冲区插入到接收进程的消息队列中。

    消息格式:

    struct message_buffer{

    ​ int sender; //发送者进程标识符

    ​ int size; // 消息长度

    ​ char *text;// 消息正文

    ​ struct message_buffer *next;//指向下一个消息缓冲区的指针

    }

1605615191938

2.信箱通信原理

​ 为了实现进程间通信,可以设计一个通信机构–信箱,以发送信件和接收信件为进程间通信的基本方法。

解: 由于发送方和接收方都是独立工作的,如果发得快而收得慢,则信箱会溢出。相反,如果发得慢而收得快,则信箱会变空

3.管道通信

​ 所谓“管道”,是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件,又名pipe文件。

​ 最早出现在UNIX系统中,时UNIX系统进程通信的一大特色

1605616107172

五、死锁

  1. 死锁的基本概念、死锁的定义、死锁产生的原因和死锁产生的四个必要条件
  2. 解决死锁的四个方法:死锁预防、避免死锁、检测和解除死锁、忽略死锁
  3. 安全状态与不安全状态的意义,银行家算法
  4. 资源分配图及化简方法,死锁定理和判断死锁的方法
  • 在多道程序系统中,同时又多个进程并发执行,共享系统资源,从而提高了系统资源利用率,提高了系统的处理能力。
  • 但是,在进行资源分配时会产生一个随机性的错误–死锁
  • 在许多应用中,如实时控制和监视系统中,如果遇到死锁会带来很大的危害。

本章小结

​ 本章主要描述了死锁的基本概念、产生死锁的原因和必要条件以及解决死锁的各种方法,重点掌握内容如下:

  1. 死锁的定义,产生死锁的原因和必要条件
  2. 死锁预防的概念、资源的静态分配策略、资源有序分配
  3. 避免死锁的概念、安全状态和安全序列,银行家算法
  4. 死锁检测的时机、死锁检测算法、死锁解除方法
  5. 资源分配图和死锁定理
  6. 哲学家就餐问题

一、死锁的定义

​ 指在多道程序中,一组进程中的每一个进程均无限期等待被该组进程中的另一个进程所占用且永远不不会释放的资源。

解:占用资源且永远不会释放的进程称为死锁进程

  1. 资源的概念

    1. 永久性资源(可重用资源):如内存、外部设备、处理器等硬件资源。各种数据文件、表格、共享程序代码等软件资源

      解:哪些运行一定要有,或者一直存在的资源。

    2. 临时性资源(消耗资源):指由每个进程产生,只为另一个进程使用,经过短暂时间后便不再使用的资源。如I/O和时钟中断信号、同步信号、消息等。

      解:临时数据,如我使用进程创建一个变量,使用完这个变量就舍弃了,变量既临时性资源

  2. 产生死锁的原因

    1. 竞争资源:资源再系统分配时出现失误、进程间对资源的相互争夺而造成僵局
    2. 进程推进顺序不合理
  3. 死锁的例子

    1. 申请不同类资源产生死锁

      进程P1和P2再运行中都使用输入、输出设备,假定系统中只有一台输入设备和一台输出设备,则进程P1和P2可有如下形式:

      1606106494139

      上图中,如果P1申请一台输入设备后,并发执行到P2,P2申请一台输出设备,那P2要申请输入设备时,被P1占用,P1要申请输出设备时,被P2占用,因为它们的执行顺序时,先使用完再统一释放

    2. 申请同类资源产生死锁

      假定有一类可重用资源R,如内存,它包含m个页面,由n个进程P1、P2、…、Pn(2 <= m <= n)共享,假定每个进程按下述顺序依次申请和释放页面:

      1. 申请页面
      2. 申请页面
      3. 释放页面
      4. 释放页面

      1606107061166

      上图中,P1申请页面后占用了一个页面,并发执行到P2进程去了,然后P2也占用了一个页面,然后并发回P1,P1又要申请一个页面,这时候没有页面可以占用了,这就导致P1一直在申请。陷入死锁。因为它们先申请两个页面后,才释放页面

    3. 1606107996720

      上图是因为生产者P操作mutex后,然后又P操作了empty,这时候empty被P操作后陷入等待,这时候消费者P操作了mutex,因为之前生产者没有V操作mutex,导致消费者陷入了等待。这时候就是死锁了

    4. 对临时性资源的使用不加限制产生的死锁

      1606135070668

      1606135006053

      上图是会陷入死锁的情况是因为,P1进程需要接收P3发送S3信息才会进行发送消息S1给P2,它们进行了一个依赖,如果P3没有发送S3,然后P1就会陷入等待,然后这个圈就陷入了等待。把send操作往上提,receive操作往下移就行了。如果有多个依赖的情况下,程序会变得复杂

      三、产生死锁的四个必要条件

      对于永久性资源,产生死锁的四个必要条件:

      • 互斥条件 解:一个资源每次只能被一个进程使用。
      • 不可剥夺条件 解::进程已获得的资源,在末使用完之前,不能强行剥夺。
      • 请求和保持条件 解: 进程因请求资源而阻塞时,对已获得的资源保持不放。
      • 循环等待条件 解:若干进程之间形成一种头尾相接的循环等待资源关系

      四、解决死锁的方法

      • 预防死锁 解:通过设置一些限制条件,去破坏产生死锁的必要条件
      • 避免死锁 解:在资源分配过程中,使用某种方法避免系统进入不安全的状态,从而避免发生死锁
      • 检测与解除死锁 解:程序运行过程,动态检测是否产生死锁,然后动态干掉死锁进程
      • 检测死锁 解:允许死锁的发生,但是通过系统的检测之后,采取一些措施,将死锁清除掉
      • 解除死锁 解:该方法与检测死锁配合使用

死锁预防

​ 是指在任何系统操作前(如分配资源、调度进程等),事先评估系统可能情况,严格采取措施,使得产生死锁的四个必要条件不成立。

基本思想:防患于未然。

具体作坊:破坏产生死锁的四个必要条件之一

解:互斥条件是无法被破环的,因为在使用临界资源的时候是一定要保证的。

静态的资源分配策略

  1. 破环不可剥夺条件

    两种方法:

    • 若一个进程以占用了某些资源,又要申请新的资源,在得不到新资源的同时释放原有资源,然后等待。
    • 若一个进程申请新资源,首先系统检查该资源是否可用,如果可用则分配。否则从其他等待进程剥夺资源分配给该进程,如果没有等待进程占有该条件,该进程必须等待。在等待过程中,资源也可能被剥夺
  2. 破坏请求和保持条件

    方法:

    • 每个进程必须在开始执行前就申请它所需要的全部资源,仅当系统能满足进程资源请求且把资源一次性分配给进程后,该进程才能开始执行。

三、资源的有序分配法

破环循环等待条件

方法:

  • 对系统所有资源类型进程线性排序,并赋予不同的序号。进程申请资源时,必须严格按照资源编号的顺序进行。既一个进程先得到编号小的资源,才能申请编号大的资源。释放资源时,次序相反。
  • 一般原则:较为稀缺、稀少的资源编号较大
  1. 对它所必须使用的而且属于同一类的所有资源,必须一次申请完;

  2. 在申请不同类资源时,必须按各类设备的编号依次申请。

    例如:进程PA,使用资源的顺序是R1,R2;
    进程PB,使用资源的顺序是R2,R1;
    若采用动态分配有可能形成环路条件,造成死锁。
    采用有序资源分配法:R1的编号为1,R2的编号为2;
    PA:申请次序应是:R1,R2
    PB:申请次序应是:R1,R2

解:如果有ABC三个程序,A进程需要先申请Az、Bz、Cz三个资源,B进程需要先申请Bz、Az、Cz三个资源,C进程需要申请Cz、Az、Bz这样就会导致,A进程申请Az后并发到B进程,B进程申请到Bz后阻塞了,然后A、B就陷入死锁了。如果采用排资源有序的话,Az、Bz、Cz排序为1、2、3,B进程在申请Bz时要先申请Az才能申请Bz,这样就破环了循环等待条件。

死锁预防策略,总体上是增加了较强的限制条件,从而使实现较为简单,但却严重影响了系统性能。

死锁避免

基本思想:

​ 系统对进程发出的每一个系统能够满足的资源申请进行动态检查,并根据检查结果决定是否分配资源;如果分配后系统不会发生死锁,则给予分配,否则,不予分配。

和死锁预防的区别:

死锁预防是破坏产生死锁的四个必要条件之一,严格地防止死锁的出现。而死锁避免是在系统运行过程中注意避免死锁的产生,即使死锁的必要条件存在,也不一定发生死锁。

二、安全状态和安全序列

  1. 安全状态:
    • 如果操作系统能保证所有进程在有限时间内得到所需的全部资源,则称系统处于“安全状态”,否则说系统是不安全的。
    • 判别:如果存在一个由系统中所有进程构成的全部序列{(P1,P2,….,Pn)},则系统处于安全状态。
  2. 安全序列:
    • 系统能按某种进程推进顺序{P1,P2,…,Pn},为每个进程Pi分配所需资源,直至满足每个进程对资源的最大需求,使每个进程都可以顺利地完成。此时称为{P1,P2,..,Pn}为安全序列。
    • 系统在接收资源请求的时候,会遍历资源,根据银行家算法找安全序列,若存在安全序列就分配资源,否则不予分配,安全序列可能不止一个
  3. 安全状态与不安全状态的关系:
    • 系统种不存在安全序列,则称系统为不安全状态。
    • 1606193215488
  4. 安全与不安全状态
    • 1606193452638
    • 该状态安全,系统资源剩余三个,而P3还需要两个资源,把两个资源分配给P3后,系统资源剩余一个,P3得到满足就会释放资源,然后剩余资源就是剩余的一个加上P3释放的四个就是五个。然后去满足P2,满足完P2,在满足P1。 这里面的安全序列就是{P3,P2,P1}
    • 下图是不安全状态,P1的请求不会被满足
    • 1606193817551

三、银行家算法

由Dijkstra发明

原意:

  • 确保银行在发放现金贷款时,不会发生不能满足所有客户需要的条件。

操作系统中:

  • 保证系统不会进入不安全状态的算法
  • 下面举例说明银行家算法的资源分配算法

例一:

​ 假定系统中有个五个进程{P1,P2,P3,P4,P5}和三类资源{A、B、C},各种资源的数量分别时10、5、7,资源分配情况如图所示。

1606194818322

上面存在安全序列。安全序列是{P2,P4,P5,P1,P3} 。 安全序列不一定是唯一的。

例二:

​ 某系统中有3个并发进程,都需要同类资源三个,试问该系统不会发生死锁的最少资源是多少。

答:7个,假设三个并发进程都只差一个同类资源就可以得到满足释放资源,这时候就需要6个,然后给一个同类资源让其一满足。其中一个一满足就释放了三个资源,其他两个就可以得到满足了。

死锁的检测与解除

假如系统为进程分配资源时,不采取任何限制性措施来避免和预防死锁,而是在操作系统运行过程中,不断地监督程序的执行和资源占用情况,判断是否发生死锁,一旦发生死锁,采取专门的措施解除死锁,并以最小代价使系统恢复正常。

死锁检测时机

  1. 检测的实质:
    • 检测算法检测是否存在“循环等待”条件。
  2. 时机:
    • 一次资源分配后
    • 每次调度后
    • 定时器定时运行检测程序
    • 当某个进程长期处于阻塞状态或阻塞程序过多时

算法规则:

​ 当任一进程Pj申请一个已被占用的资源Ri时,进行死锁检测,反复查找资源分配表和等待进程表,来确定Pj对资源Ri的请求是否导致形成环路,若是,出现死锁。

1606222203709

  1. 剥夺资源

    • 一旦死锁,挂起一些进程,剥夺它们占用的资源给死锁进程,以解除死锁。
  2. 撤销进程

    • 撤销部分死锁进程,将它们占有的资源分配给另一些死锁进程,直到死锁解除为止。
    • 可以一次撤销所有死锁进程,也可以逐个撤销

资源分配图

  1. 作用
    • 描述系统中资源分配和申请清空,对死锁进行分析并采取对策。
  2. SRAG定义
    • 是一张有向图,可定义为一个二元组,既,SRAG=(V,E),其中V是顶点的集合,包括进程集合、资源集合,E是有向边的集合,是一种有序对<Pi,ri>
    • 解:下图矩形代表资源,圆形代表进程,矩形中间的白色圆点是资源个数,白色圆点延伸的指向圆形的箭头是该进程占有该资源,圆形延伸指向白色圆点是请求该资源
    • 下图没有死锁。
    • 如图:1606223178609

死锁定理

  1. 作用:判断死锁的法则
  2. 死锁定理:
    • 如果资源分配图中没有环路,则系统无死锁
    • 如果资源分配图中出现了环路,则可能存在死锁。具体判断如下:
      • 如果处于环路中的每个资源类中均包含一个资源实例,则环路存在意味着死锁的存在。此时,环路是死锁的重复必要条件。如下图:
      • 1606223999413
    • 存在环路P1->r1->P3->r2->P1,但无死锁。
      • 1606224050769

资源分配图简化方法

可以使用资源分配图简化方法,来检测是否为死锁状态。步骤如下:

  1. 在资源分配图中,找出一个既不阻塞又非独立的进程结点Pi。在顺利的情况下,Pi可获得所需资源而继续运行,直至运行完毕,在释放其所占有的全部资源,这相当于消去pi的请求边和分配边,使之称为孤立的节点。
  2. 将Pi释放的资源分配给申请它的进程,若该进程能顺利运行完,释放资源,再次成为孤立节点。
  3. 重复1,2步骤,直到找不到符合条件的进程节点。
  4. 经过化简后,若能消去所有的边,则该图可完全简化,系统不存在死锁;否则不可完全简化,存在死锁。
  5. 1606224405830

哲学家就餐问题

  1. 问题描述

    1. 有五个哲学家围坐在一圆桌旁,每人面前有一只碗,碗里有面条,每两人之间放一只筷子;
    2. 每个哲学家行为是思考,感到饥饿,然后吃饭;
    3. 为了吃饭,每个哲学家必须拿到两只筷子,并且每个人只能直接从自己的左边或右边去取筷子。
    4. 1606225323096
  2. 算法描述

    1. 为每个筷子设置一个互斥型信号量

    2. a = {1,1,1,1,1}

    3. # 会产生死锁的算法
      do{
      P(a[i]);  //拿左筷子
      P(a[(i+1) % 5]); // 拿右筷子
      ...
      eat;
      ...
      V(a[i]); //放左筷子
      V(a[(i+1) % 5]); //放右筷子
      ...
      think;
      }while(True);
      

      1606226069870

    4. 改进:

      1. 采用资源有序发呢配算法,给每个筷子编号,规定每位哲学家先拿编号小的筷子再拿编号大的筷子。哲学家i(1<=i<=4)不变,第五个哲学家的程序改进如下:

      2. # 不会产生死锁的算法
        do{
        P(a[1]) #拿右筷子
        P(a[5]) # 拿左筷子
        ...
        eat;
        ...
        V(a[1]) // 放右筷子
        V(a[5]) // 放左筷子
                 
        ...
        think;
        }
        
      3. 解: 哲学家就餐就是给筷子编号,然后让哲学家拿自己两边编号小的筷子,在拥有编号小的情况下才可以拿编号大的筷子,这样就打破了环路。如上面五个筷子。其中四个哲学家拿起筷子后,第五个哲学家就得和第一个哲学家抢夺同一个筷子。

      4. 哲学家算法本质就是打破死锁的”循环等待”条件的资源有序分配法

六、存储管理

  1. 存储管理的任务
  2. 内存空间的划分、分配和回收
  3. 可变分区存储管理方案
  4. 覆盖技术与交互技术
  5. 虚拟页式存储管理**
  6. 页面置换策略**

本章小结:

本章主要讲述存储管理的相关概念以及存储管理的方法等内容,重点掌握如下内容:

  1. 重要概念
    • 绝对地址
    • 逻辑地址
    • 地址重定位
    • 动态重定位
    • 静态重定位
  2. 存储管理的任务
    • 内存的分配与回收
    • 存储共享
    • 存储保护
    • “扩充”内存容量
  3. 分区管理方案
    • 为程序提供是一个连续分区,程序运行前必须全部装入内存。
    • 固定分区基本思想,内存分配与回收
    • 可变分区基本思想、紧缩技术、实现、空闲分区分配策略、分区的回收、分区的保护;
    • 分区管理方案的优缺点。
  4. 覆盖于交换技术-了解
  5. 虚拟页式存储管理
    • 基本思想
    • 硬件支持
    • 地址结构
    • 分配与回收地址转换
    • 缺页处理
    • 页面置换算法

存储管理概述

1606227029336

内存空间一般分为两个区域:

系统区:存放操作系统常驻内存部分,用户不能占用这部分空间

用户区:分配给用户使用,用于装入和存储用户程序和数据,随时变化。

存储管理的实质:用户空间的管理

二、存储管理的任务

内存管理问题主要包括:

  1. 内存管理方法
  2. 内存的分配与释放算法
  3. 虚拟存储器的管理
  4. 控制内存和外存之间的数据流动方法
  5. 地址变换技术
  6. 内存数据保护和共享技术

  7. 内存的分配和回收

    1. 功能
      • 记住每个存储区域的状态:空闲与否
      • 实施分配:用户提出请求,分配内存
      • 回收:回收用户释放的区域
    2. 内存分配表
      • 位示图表示法
      • 空闲页面法
      • 空闲块表法
    3. 内存分配方式
      • 静态分配:程序运行前分配内存,不允许“搬家”
      • “搬家”:程序从一个地方移动到另一个地方
      • 动态分配:程序运行时动态分配内存,且允许“搬家”。
  8. 存储共享

    • 所谓存储共享是指两个或多个进程共用内存中相同区域。
    • 包括:代码共享和数据共享。
    • 目的:节省内存空间,提高内存利用率;通过内存共享实现进程通信。
  9. 存储保护

    目的:位多个程序共享内存提供保障,使在内存中各道程序,只能访问它自己的区域,避免各道程序互相干扰。

    • 方法:
      • 地址越界保护 == 界地址保护
      • 权限保护 == 规定每个进程的权限,读写权限,你没有写的权限,你就不能写
  10. “扩充”内存容量

    • 用户在编制程序时,不应该受内存容量的限制,所以要采用一定技术来“扩充”内存的容量,使得用户得到比实际内存容量大得多的内存空间。
    • 借助虚拟存储技术或交换技术完成,达到在逻辑上扩充内存容量的目的。

三、地址转换

  1. 地址重定位

    1. 一字节等于8bit,1bit等于一个二进制位,0或1

    2. 绝对地址:存储器以字节位单位编址,每个字节都有对应的地址。假定内存容量为n,则编号顺序为0,1,2,…,n-1,该地址成为物理地址或绝对地址。

    3. 物理地址空间:由绝对地址对应的内存空间称为“物理地址空间”。

    4. 逻辑地址:在多道程序系统中,内存中同时存储了多个用户程序,每个用户不能预先直到他程序被存储到什么地方。为了方便,每个用户都可认为自己的程序和数据存储在一组“0”地址开始的连续空间中,用户程序中使用的地址,称为“逻辑地址”或“相对地址”

    5. 逻辑地址空间:由逻辑地址对应的地址空间称为逻辑地址空间。

      解:逻辑地址不能直接使用,要地址重定位才能使用,重定位为绝对地址

    • 当用户把程序装入内存时,存储管理为他分配的内存空间可能时从某个单元开始的一组连续地址空间,它的起始地址不固定,既逻辑地址与物理地址经常不一致
    • 把逻辑地址转换为绝对地址的工作称为“地址重定位”,分为“静态重定位”和“动态重定位”两种。
  2. 静态重定位

    • 内存在装入程序时,把程序的指令和数据地址全部转换为绝对地址,该过程在程序运行前进行,程序运行过程无需转换,这种转换方式称为“静态重定位”。
    • 1606229453649
    • 上图的逻辑地址时0到168,在装入内存的时候,因为空闲的绝对地址已经到800,这时候,这个逻辑地址就加入到内存就每个逻辑地址加上800,原本逻辑地址66的,变为绝对地址866.在程序加入内存之前要转换完成。
  3. 动态重定位

    • 内存在装入程序时,不进行地址转换,而是直接把程序装入到分配的内存中,程序在执行过程中完成地址的转换,这种地址方式称为“动态转换”。
    • 1606229852392
    • 上图的逻辑地址是0到700,在逻辑地址为100的地址有个操作,把逻辑地址500的数据装入到LOAD1这个寄存器中,如果是动态重定位的话,比如我执行到逻辑地址100行了,执行第100行的时候我会区读取重定位寄存器的值,然后与逻辑地址进行一个相加,得到绝对地址,进行一个操作。 要操作内存的时候,或执行一行就要读取一次重定位寄存器进行一个相加

分区管理方案

一、固定分区

  1. 基本思想:
    • 多道程序环境下,整个用户空间划分为若干个固定大小的区域,每个分区只装入一道作业。分区的大小可以相同也可以不同。
  2. 内存分配表与分区的分配、回收
    • 内存分配表是一张分区说明表,记录分区号、分区大小、分区起始地址及使用状态等。
    • 分配时按照进程的内存需求,按一定策略从分区表中找到空闲分区进行分配。
    • 回收时,将内存分区登记在分区说明表中,并将其状态置为空闲状态。
  3. 解:由于一开始内存空间已经划分好内存区域,之后程序只需要根据算法装入到分好的内存区域中就行了。但是这样会导致内存的空间的浪费。如:一个程序需要93kb的空间,根据算法最接近的固定区域为100kb,这时候这个程序就会被分配给内存为100kb的固定区域中,这样就导致浪费了7kb。

二、可变分区

  1. 基本思想:

    • 系统不预先划分固定分区,而是在装入程序时划分内存分区,使为程序分配的内存大小正好等于程序的需求量,且每个分区的个数时可变的。
    • 1606231380654
    • 图1一开始有94kb的空闲空间,程序D进入内存时请求了70kb的空间,94满足就从94中划分70出来,第三幅图是进程A执行完成,归还了16kb的进程
  2. 紧缩技术

    • 内存经过一段时间分配后,会存在很多很小的空间。如上面的最有右边的那张图,假定此时有进程E(40kb),此时空闲分区都不能满足它的需求。
    • 解决办法:紧缩
    • 把进程位置移动一下,搬一下家,把空闲的碎片合并到一起
    • 下图紧缩后,空闲的整理到一起有80kb,这样就可以放入进程E
    • 1606231791042
    • 紧缩应注意问题:
      • 增加系统开销
      • 移动是由条件的
      • 比如进程正与设备交换信息,此时不能移动,移动的话,设备就会报错了。设备就会找不到进程。
      • 所以,采用紧缩技术时,应该尽可能减少需要移动的进程树和信息量。
  3. 可变分区的实现

    1. 硬件支持

      • 两个专用控制寄存器:
        • 基址寄存器:记录了内存起始值;每个进程都有
        • 限长寄存器:记录了程序逻辑地址的长度。每个进程都有
    2. 绝对地址形成

      • 程序装入内存后,分区的起始地址和长度装入两个寄存器,程序执行后,取出指令中的逻辑地址,绝对地址=逻辑地址+机制寄存器内容
    3. 地址越界

      • 当逻辑地址<限长寄存器值时,产生”地址越界“中断。
      • 因为逻辑地址的下标是从0开始,所 以是小于而不是小于等于
      • 地址转换过程,下图:1606233125017
      • 内存分配表:两个表格
      • 1606233248616
    4. 可变分区的分配策略

      1. 首次适应算法
        • 思想:当接到内存申请时,查找分区说明表,直到找到一个大小能满足要求的空闲分区为止,将其分割并分配
        • 优点:简单,可以快速做出分配决定,直接在表中找到了大小满足要求的就切割分配,不管你是不是很大或者很小,反正第一个见到你
        • 空闲分区表的地址会从低到高排序
      2. 最优适应算法
        • 思想:当接到内存申请时,查找分区说明表,找到一个大小能满足要求的最小空闲分区,将其分割并分配。
        • 优点:节省空间
        • 缺点:形成许多碎片
        • 空闲分区表的会按空间大小从小到大排序
      3. 最坏适应算法
        • 思想:当接到内存申请时,查找分区说明表直到找到一个大小能满足要求的最大空闲发呢去,将其分割并分配。
        • 优点:碎片少
        • 缺点:分割了大的空间,遇到较大申请,无法满足。
        • 空闲分区表会按空间大小从大到小排序,若是对比第一位,查看是否满足空间。
    5. 分区的回收

      当用户程序执行结束后,系统回收已使用完毕的分区,将其记录在空闲区表中。假定归还的分区起始地址为S,长度为L。考虑如下四种可能性:

      回收区与插入点的上邻空闲分区F1相邻接, 回收区要与F1合并

      回收分区与插入点的下邻空闲分区F2相邻接, 回收区要与F2合并

      回收区同时与插入点的上、下两个空闲分区相邻接, 回收区要与F1,F2合并

      回收区既不与F1邻接,又不与F2临界, 空闲分区表直接登记回收区起始地址和长度

      1606234644714

虚拟页式存储管理方案

  1. 基本思想
    • 利用大容量外存来扩充内存,产生一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间,简称虚存。
    • 采用二级存储器方式
    • 是一种设计技巧,受外存容量的限制
  2. 虚拟内存你需要硬件支持
    • 系统有容量足够大的外存
    • 系统有一定容量的内存
    • 实现虚-实转换的地址映射机制
  3. 工作原理
    • 程序部分装入内存便可运行,其他部分需要运行时在装入内存。
    • 因为程序的局部性所以可用实现这种技术,程序可能在一段时间内都在一个程序段运行。
  4. 与交换技术的区别
    1. 交互技术交换单位时进程,也就是把如果要运行一个程序的时候内存不足,就直接暂停一个内存中的进程,交换到磁盘中,然后把要运行的程序交换进来。这时候你可以看出,交换是把整个进程都给写入磁盘
    2. 虚拟内存以页为单位进行交换,就是一个程序要用到的一小部分加载进内存,剩下一部分在磁盘中。
  5. 物理页面和页面

    • 物理页面:将内存分成大小相等的许多区,每个区称为一个“物理页面”。

    • 页面:将程序中的逻辑地址页进行分页,页的大小和物理页面大小一致

    • 虚拟地址是由 虚拟页号 + 页内地址组成的

    • 逻辑地址结构分为两部分,虚拟页号和页内地址。16页表示范围为0~2的四次方,页号可以用四位,每页2048字节,业内地址范围为0~2的十一次方减一,可以用11位编址合起来是15位。

    • 设有一页式存储管理系统,想用户提供的逻辑地址空间是最大16页,每页2048字节,试问逻辑地址至少应为多少位?
           
      答:15位, 15位数,不过这15位数字不是1就是0。
      因为操作系统记录内存地址是采用二级制的形式进行记载的。
      16个地址就只需要4个二进制就可以表示完全了。
      2048个地址需要11个二进制才可以表示完全。
           
      二进制数:0 或者 1
      4个二进制: 0000 , 1010  这些都是二进制数,四个二进制有十六种组合,所以可以表示内存地址,业内地址同理
      

三、物理内存的分配与回收

  1. 位示图

    • 位示图中每一个位与物理块对应,其值位0/1,表示空闲/占用。
    • 1606311323416
  2. 内存分配与回收

    • 分配:在位示图中找出空闲物理页面数,如果满足,则分配,并把相应位置为1,计算物理页面号

    • 回收,当归还物理页面时,计算归还页面在位示图中对应的,位置,将1改为0。

    • 方括号表示取整,mod表示取余, i是归还的块号

虚拟页式存储地址转换过程

  1. 页式存储管理的地址转换
    • 硬件支持:页表始址寄存器和页表长度寄存器,分别用来存储正在运行程序的页表在内存的起始地址和页表的长度。

    • 解:程序放入内存可以不是连续的地址,一个程序切分分为N页,然后取程序的一个页放入内存中内存地址的一个页中,然后页号、块号记录在页表中。

    • 页号就是程序逻辑地址的号码,块号就是内存中物理地址的号码

    • 1606451983354

    • 地址转换过程:
    • 在执行检索前,先将页号与页表长度进行比较,若页号大于或等于页表长度,则地址越界
    • 若未出现越界错误,则将页表始址与页号和页表项长度的乘积相加,则找到该表项在页表中的位置,找到该页的物理页号。
      • 页表项:页表就是一块内存,然后页表项就是这块内存中的一小块,页表项。
        • 如:一个64字节的页表,由2个页组成。页表项的长度就是32字节
      • 页表始址:页表在内存中开始的地址。
    • 将有效地址的业内地址送入物理寄存器的块内地址字段中
    • 1606710220547

    • 页式存储管理的地址转换

      • 十进制计算:

        • 物理地址=物理页面号*块长+页内地址

        • 1606711364453

        • 解:

          • 因页大小为4k,1k = 1024byte,4k等于4096byte

          • 逻辑页内地址0处于页号为0号的页面中,因每页大小有4k,所以0号页面有0~4096-1个地址,

          • 通过查询页表可得页号0对应的物理块号为2,可使用计算机公式

          • 物理块长 == 逻辑页的大小

          • 得出结果,十进制:8192是0的物理地址
      • 二进制计算:

        • 物理页面号作为绝对地址的高位地址, 页内地址作为它的地址部分。
        • 1606735334019
        • 解:
          • 十六进制为方便阅读会在后面加个H,二进制加个B,表示这是几机制
          • 十六进制是0~9,ABCDF(10~15),总共16位
          • 2F6AH 转换为二进制是:0010 1111 0100 1010
          • 2的十次方等于1024,页面大小是4096字节是2的十二次方,所以后面的十二个二进制位就是一个页的所有地址,前面的四个数就是页号
          • 每8个bit组成1个物理地址,计算机存储最小单元式byte,1byte等于8个二进制,每byte就有一个物理地址。
          • 查看前面得出页号为2,二进制直接把页号替换为块号就可以了。
          • 答案:1011 1111 0100 1010
    • 页表项

      • 物理页面号:页面在内存对应的物理页面号
      • 有效位:页面是在内存还是外存
      • 访问位:页面在内存中是否被访问过
      • 修改位:页面在内存中是否被修改过
      • 保护位:页面能否读/写
    • 页表

      • 多级页表
      • 散列页表
      • 反置页表
    • 转换检测缓冲区(TLB)

      • 高速缓存,也称为快表,登记了页表中的部分页号和物理页面的对应关系。
      • 首先逻辑地址P和页表长度寄存器进行比较,若是成功,则进入到TLB中查找是否存在该地址,若有则直接快表读取,访问,若是TLB没有则去内存寻找,找到后把该逻辑地址与其对应的块号添加到TLB中然后访问,若是TLB满了就通过算法置换一个出去
      • 地址转换过程及原理:
      • 1606735935201
    • 缺页异常处理

      • 缺页异常:若在页表中发现所要访问的页面不在内存,则产生缺页异常
      • 处理:查看有无空闲页面,若有,把要访问的页面调入内存;若无,选择一页换出内存,再把要访问的页面调入内存。
    • 页面调度策略

      • 调入策略:决定什么时候将一个页由外存调入内存。两种方法:
        • 请求调页:不在内存,调入内存
        • 预调页:预先认为可能会被调入内存,提前调入内存
      • 置业策略:当产生缺页时,将所调入的页面置于何处。
      • 置换策略:如果内存已满,确定哪个页面从内存中移出,为新的页面腾出空位。三种方法:
        • 固定分配局部置换:给进程分配指定的空间,若是缺页了,调入后就置换该进程的指定空间的页面
        • 可变分配全局置换: 页了就整个系统去找,有没有空闲页面可以使用
        • 可变分配局部置换:
  2. 页面置换算法

    “抖动”或“颠簸”:刚被换出的页面由立即要用,把它转入内存后,不久又被换出,换出不久又被调入内存,如此反复,使得调度非常频繁,这种现象称为“抖动”或“颠簸”

    • OPT–理想页面置换算法:
      • 由belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面,将是以后永不使用的,或者是在最长(未来)时间内不再被访问的页面。采用OPT算法,通常可保证获得最低的缺页率。
      • 1606738415979
    • FIFO–先进先出
      • 总是选择最先装入内存的页面调出,或者说把驻留在内存中时间最长的那一页调出。
      • 某程序在内存中使用三个页面,初始为空,所需页面的走向为1,2,3,4,1,2,5,1,2,3,4,5. m=3,m=4时,使用FIFO算法,计算缺页次数。说明所出现的现象。
        • 当m=3时,缺页次数为9
        • 当m=4时,缺页次数为10
        • belady现象:当分配给进程页面数增加时,缺页次数反而增加的现象
      • 1606738498476
    • LRU–最近最少使用
      • 总是选择举例现在最长时间内没有被访问过的页面先调出。
      • 1606738563986
  3. 缺页率

    • 缺页率

      • 影响缺页率的因素:
        • 分配给程序的物理页面数
        • 页面的大小
        • 程序编制方法
        • 页面调度算法

虚拟页式存储管理的优点缺点

  1. 优点:不要求进程的程序短和数据短在内存中连续存放,有效解决了碎片问题,提高了内存利用率
  2. 缺点:存在页面空间的浪费,程序的最后一页往往由一部分得不到利用

虚拟存储管理的性能问题

  1. 颠簸问题
    • 缺页率高引起,如页面置换算法不合理。
    • “活动”页面:进程在一段时间内集中访问的一些页面,与程序的局部性有关。
    • 如果分配给进程的物理页面少,则活动页面不能全部装入内存,可能频繁产生缺页,从而导致颠簸。
  2. 工作集模型
    • 工作集:对于给定进程访问序列,从时刻(t-△)到时刻t之间所访问页面的集合,成为该进程的工作集。△称为工作集窗口。
    • 1606739557550
    • 采用工作集模型可以解决颠簸问题
    • 解决方法:操作系统为每个进程保持一个工作集,并为该进程提供与工作集大小相等的物理页面数,这一过程可动态调整。
    • 1606739637568

七、文件管理

  1. 文件、文件名及文件系统的概念
  2. 文件控制块、目录项、文件目录及目录文件的概念
  3. 文件的逻辑地址和物理结构
  4. 目录检索、磁盘空间管理、记录的成组与分解
  5. 文件和目录的各种操作
  6. 文件共享和文件保护的方法、文件的保密措施

本章主要讲述文件系统的基本概念、功能、文件的组织形式、存储空间的管理等内容,重点掌握内容如下:

  1. 文件管理的基本概念,包括文件管理的任务、文件的存储介质及存取方式、文件的分类
  2. 文件的逻辑结构和物理结构
  3. 文件目录的实现,包括文件目录、当前目录、目录项、目录文件、目录项分解法、UNIX文件目录实现
  4. 文件存储空间的管理,包括磁盘空间的分配与回收算法、UNIX系统的空闲块成组链法
  5. 文件系统的实现,包括系统打开文件表和用户文件表及二者关系。
  6. 文件及文件目录的操作
  7. 文件系统的性能,磁盘告诉缓存的概念,记录的成组与分解
  8. 文件共享、文件保护和保密,包括文件共享、文件存取控制、UNIX的文件使用权限管理方案、文件的保密措施。

文件系统的基本概念

文件系统的任务

  1. 文件的的定义

    • 研究文件系统的两种观点:
      • 用户观点:关心文件由什么组成,如何命名,如何保护文件,可以进行何种操作
      • 系统观点:文件目录是怎样实现的,怎样管理存储空间,文件存储位置,磁盘实际运作方式,存取速度,磁盘利用率等等。
    • 文件的定义:一组带标识的、在逻辑上有完整意义的信息项的序列
    • 读写指针:读指针用来记录文件当前的读取位置,写指针用来记录文件当前的写入位置。
    • 特点:存储在磁盘,可长期保存
  2. 文件系统的定义

    • 文件系统时操作系统中统一管理信息资源的一种软件,它管理文件的存储、检索、更新,提供更安全的共享和保护手段,并且方便用户使用。

    • 功能:

      • 统一管理文件的存储空间,实施存储空间的分配与回收

      • 实现文件按名存取,以对用户透明的方式管理名字空间

      • 实现文件信息的共享,并提供文件的共享和保密措施。

      • 想用户提供一个方便使用的接口,提供图标方便访问

      • 系统维护及向用户提供有关信息,创建信息等

      • 保持文件系统的执行效率

      • 提供与I/O的统一接口 ,打开时open,关闭时close,提供一个统一接口

文件的存储介质及存取方式

  1. 外存储设备的特点
    • 特点:容量大、断电后仍可保存信息
    • 组成:
      • 驱动部分:让磁盘转起来
      • 存储介质部分:保存文件的内容
    • 种类:磁盘、磁带、磁鼓、纸带、光盘、闪存
  2. 外存储设备的存储介质
    • 磁带
      • 特点:容量大,存取速度慢,适合顺序存储
      • 1606742614523
    • 磁盘
      • 分类:软盘和硬盘
      • 特点:容量大,成本低,适合随机存储
      • 盘面:一个磁盘有多个盘面,有些磁盘的的磁片式双面的
      • 磁道:一个盘面有多个磁道
      • 柱面:不同盘面相同磁道组成柱面
      • 磁头:一个磁盘有多个磁头与盘面对应
      • 扇面:把磁盘分出一小块
      • 1606742833301
    • 光盘
      • 是利用在激光的作用下特性发生变化的一些材料制成的非磁性记录介质
      • 特点:容量大、速度快、价格便宜
    • 闪存
      • 特点:电擦除,随机存取、可靠性高、寿命长
  3. 文件在存储设备的存取方式
    • 顺序存取:按从前到后的次序依次访问文件的各个信息项
    • 随机存取:又称直接存取,允许用户按任意的次序、直接存取文件中的任意一个记录,或者根据存取命令把读写指针移到为你教案中的指定记录处读取 。

文件的分类

  1. 按文件的用途分类
    • 系统文件:操作系统的文件
    • 库函数文件:编写C程序的时候经常包含的头文件、相应的库函数实现
    • 用户文件:普通用户的文件
  2. 按文件的组织方式分类
    • 普通文件:记录一组逻辑信息的文件
    • 目录文件:把文件的信息项,组织的时候,名字组织到一起,形成一个目录
    • 特殊文件:设备看成一个特殊文件,如打印机、键盘等等
  3. 一些常见的文件分类方式
    • 按文件的保护方式:只读文件、读写文件、可执行文件、无保护文件
    • 按信息的流向分:输入文件、输出文件、输入输出文件
    • 按存放时限分:临时文件、永久文件、档案文件
    • 按存储介质分:磁盘文件、磁带文件、卡片文件等
    • 按文件的组织接哦古分类:逻辑文件、物理文件
  4. UNIX类操作的文件分类
    • 普通文件
    • 目录文件
    • 特殊文件

文件的逻辑结构和物理结构

  • 文件的逻辑结构:
    • 从用户观点出发所观察到的文件组织形式
    • 如.JPG这些文件格式就是用户可以观察到的
  • 文件的物理结构:
    • 又称为文件的存储结构。是指系统将文件存储在外存上所形成的一种存储组织形式,是用户不能看见的。
    • 存储在磁盘等外存上的结构,是离散的存储还是连续的存储。用户不清楚

文件的逻辑结构

  • 设计文件逻辑结构的原则:
    • 易于操作:如word可以自己操作,数据库等
    • 查找快捷
    • 修改方便
    • 空间紧凑
  • 文件的逻辑结构
    • 文件的逻辑结构所描述的信息是文件中信息的组织形式,可分为三类:
      • 流式文件:有序字符的集合,基本单位是字符。源程序、目标代码等属于流式文件
      • 记录文件:是一组有序记录的集合,基本单位是记录。
        • 记录:如数据库中一个字段就是一条记录
        • 定长记录文件:每个记录的长度是固定的,这就是定长记录
        • 变长记录文件:每个记录的长度是不固定的,各有长短
  • 文件的物理结构
    • 顺序结构原理
      • 又称连续结构,它把逻辑上连续的文件信息依次存放在连续编号的物理块中。
      • 1606822275358
      • 优缺点
      • 优点
        • 存取速度快,一旦知道了文件在存储设备上的起始块号和文件长度,便能快速进行存取。
        • 知道了起始块号,和文件长度就可以很容易找到文件
        • 支持顺序存放和随机存取
          • 随机存取:我知道了文件的起始块号,然后我想要读取其中i块,直接起始块号+i就可以读取到了。
      • 缺点:
        • 文件不能动态增长:因为已经分配好了空间,之后的空间又可能被别的文件占据,就无法增长了,它的空间必须是连续的
        • 要求为一个文件分配连续的存储空间
        • 不能灵活地删除和插入记录:如果要在其中插入一个记录,后面的文件的所有位置都要向移动
        • 出现碎片
    • 链接结构
      • 链接结构原理
        • 将逻辑上连续的文件分散存储在若干个不连续的物理块中。每个物理块都设有一个指针,指向其后续的物理块。
      • 1606823553401
      • 链接结构的优缺点
      • 优点
        • 解决了碎片问题,提高了磁盘空间利用率
        • 文件可以动态扩充
      • 缺点
        • 存取速度慢,不适于随机存取
          • 随机存取就是你想要存储或获取文件其中的一块的内容
          • 链接结构就要从首指针开始一级级的读取,直到读取到你需要的那块
        • 可靠性差 :中间一段,吧唧,少了个指针,该指针后面的所有文件不见了
    • 索引结构
    • 索引结构原理
      • 为每个文件分配一个索引表(表),把分配给该文件的所有盘块号,都记录在该索引块中
    • 1606824862559
    • 优缺点
      - 优点:
      • 文件动态增长
      • 不要求为一个文件分配连续的存储空间
      • 能灵活地删除和插入记录
      • 能顺序存取和随机存取
        • 缺点:
      • 引起较多的寻道次数和寻道时间
      • 索引表本身增加了存储空间的开销
    • 多级索引
      • 当文件太多,其索引块太多时,单级索引方式过于低效。此时,应为这些索引块在建立一级索引,称为第一级索引,既系统再分配一个索引块,作为第一级索引的索引块,将第一块、第二块、….等索引块的盘块号,填入到此索引表中,这样便形成了两级索引分配方式。如果文件非常大还可用三级、四级索引分配方式。
      • 1606825708998
      • 文件不大的情况在主索引表中就可以了,文件很大就要建立多级索引

文件目录

  1. 文件控制块
    • 为文件设置的用于描述和控制文件的数据结构。文件管理程序可借助于文件控制块中的信息,对文件施以各种操作。
    • 称为FCB
  2. 文件目录:
    • 文件控制块的有序集合(文件与文件控制块一一对应)称为文件目录,一个文件控制块就是一个文件目录项。
  3. 文件控制块的内容
    • 基本信息类:
      • 文件名
      • 文件物理位置
      • 文件逻辑结构
      • 文件的物理结构
    • 存取控制信息类:
      • 文件主的存取权限
      • 核准用户的存取权限以及一般用户的存取权限。
    • 使用信息类:
      • 文件的建立日期和时间
      • 文件上一次修改的日期和时间
      • 当前已打开该文件的进程数
      • 是否被其他进程锁住
      • 文件在内存中是否已被修改但尚未拷贝到盘上等。

文件目录和当前目录

  1. 一级目标结构
    • 优点:简单且能实现目录管理的基本功能一一按名存取
    • 缺点:查找速度慢、不允许重名
    • 1606827286833
  2. 二级目录结构
    • 为改变一级目录文件目录命名冲突,并提高对目录文件检索速度而将目录分为两级:
    • 一级称为主文件目录,给出用户名,用户子目录所在的物理位置;二级称为用户文件目录,给出该用户所有文件的PCB。
    • 优点:解决了文件崇明和文件共享问题,提高搜索速度,查找时间降低。
    • 缺点:不太适合大量用户和大量文件的大系统,增加了系统开销。
    • 1606827460341
  3. 多级目录
    • 多级目录结构也称为树形目录,产生于UNIX操作系统,已被现代操作系统广泛采用。
    • 优点:层级结构清晰,便于管理和保护;有利于文件分类;解决重名问题;提高文件检索速度;能进行存取权限的控制。
    • 缺点:查找一个文件按路径名逐层检查,由于每个为你教案都放在外存,多次访盘影响速度。
    • 1606827616808
  4. 当前目录和目录检索
    • 当前目录:当前正在使用的目录(也称为工作目录或值班目录)
    • 目录检索:用户和与访问文件时,需要进行目录检索,这时用户给出的文件名,系统按名寻找目录项。
    • 检索方法:全路径名(绝对路径名),相对路径名

目录项和目录文件

  • 目录项
    • 一个文件控制块做成一个定长记录,这个记录称为目录项。
  • 目录文件
    • 多个文件的文件控制块集中在一起组成了文件的目录。
    • 文件目录以文件的形式保存,该文件称为目录文件。

目录项分解法

  • 目的:
    • 加快目录检索速度
  • 分解:
    • 目录项分解成两部分:符号目录项(次部)和基本目录项(主部)。
    • 符号目录项:包含文件名和文件号
      • 用于检索时使用,检索的时候只要把符号目录项读取到内存中。文件号就是指向基本目录项的指针
    • 基本目录项:除文件名以外的FCB的其他全部信息。
      • 用于要使用的时候在读取到内存。
  • 优点:
    • 减少磁盘的访问次数,提高文件目录检索速度
  • 1606886025992

UNIX的文件目录结构

  1. i节点的引入
    • 文件目录通常是存放在磁盘上,可能要占用大量盘块,在查找过程中,需要多次启动磁盘。
    • UNIX系统,采用把文件名于文件描述信息单独形成一个称为索引结点的数据结构,简称为i结点。
    • 1606886369021
  2. i结点的内容
    • 文件主标识符、文件类型、文件存取权限、文件物理地址、文件长度、文件连接计数、文件存取时间等。
  3. 物理结构
    • 三级索引结构
    • 下图的查找顺序:在根查usr文件名的结点得到结点6,通过查询结点6的物理地前往磁盘的132盘块中,然后去磁盘的132找ast文件名得到结点26,然后………….
    • 1606886823705

FAT文件系统的实现

  • FAT的含义:
    • 文件分配表–File Allocation Table,最初为DOS胸痛设计,适合小容量的磁盘,分配给文件的所有盘块号都放在该表中。
    • 三个版本:后面的数值是字长
      • FAT-12
      • FAT-16
      • FAT-32

文件存储空间管理

磁盘空间管理

  • 基本思想
    • 对于磁盘空间的分配和回收的方法。
  • 位示图
    • 0代表空闲,1代表使用中
    • 1606908962514
  • 空闲块表
    • 通过第一个空闲盘块号加上空闲盘块数得到空闲盘
    • 1606909097555
  • 空闲块链
    • 每个空闲盘块后面都有一个指向下一个空闲盘块的指针
    • 1606909261965
  • 空闲块成组链接法
    • 成组链接的含义
      • 文件中的所有空闲盘块,被分成若干个组, 比如:将每100个空闲盘块作为一组
      • 将每组含有盘块总数N和该组所有的盘块号,记入其前一组的第一个盘块中。这样,由各组的第一个盘块可链成一条链。
      • 1606909492956
      • 成组链接法的分配:
        • 在空闲块链中,不足100块的组,通常放在内存专用块中,系统初始化时,先把专用块内容读到内存中,需要分配时,就直接在内存中找到哪块是空闲的,然后进行分配,空闲块数减1,如果这一组的第一个空闲块也要分配,在分配之前,先把其保存的下一组的空闲盘块号读入内中,在分配出去,依次类推。
      • 成组链接法的回收:
        • 归还一个空闲盘块时,把要归还的块号登记在当前组中,空闲块数加1,如果当前组已满100块,则把这100个块号写到要归还的那块中,该块就成为新组的第一块。
      • 成组链接法的优点:
        • 分配和回收空闲块时均在内存中查找和修改,只有在一组空闲块分配完或空闲的磁盘块构成一组时才需要启动磁盘读写,效率高,能快速找到大量空闲盘块的地址,UNIX采取这种方案。

实现文件系统的表目

  • 系统打开文件表
    • 专门用来保存已打开文件的文件控制块,通常放在内存。
    • 共享计数:记录在多少个进程同时打开该文件。
    • 修改标志:指文件控制块或i结点的内容是否被修改过,如果修改过,则关闭文件时要将文件控制块写回磁盘
    • 1606910263527
  • 用户打开文件表
    • 每个用户都有“用户打开文件表”,其位置记录在PCB中,以UNIX为例,内容如下:
    • 1606910350246
  • 系统打开文件表于用户打开文件表之间的关系,如下:
    • 左边两个用户打开文件表,右边一个系统打开文件表。
    • 1606910489341

文件及目录的操作

典型文件的操作

  1. 建立文件
  2. 打开文件
  3. 读文件
  4. 写文件
  5. 关闭文件
  6. 删除文件

典型的目录操作

以UNIX系统为例

  1. 创建目录creat
  2. 打开目录opendir
  3. 读目录readdir
  4. 创建链接link
  5. 删除链接ulink
  6. 修改目录名rename
  7. 关闭目录closedir
  8. 删除目录delete

文件系统的性能

磁盘高速缓存

  • 基本思想:

    • 系统在内存中保存一些磁盘块,这些磁盘块在逻辑上属于磁盘,内存的这一区域被称为块高速缓存。
    • 运行时,系统检查所有的读请求,查看文件块是否在高速缓存,在,则读,不在,首先启动磁盘,将所需块读到高速缓存,在复制到其他内存区域。若高速缓存已满,按照淘汰算法,选择较少使用的磁盘块换出
    • 块高速缓存要定期协会磁盘,以保存对磁盘块的修改。
  • 文件系统一致性问题:

    • 如果在修改过的磁盘块写回磁盘之前,系统出现故障,则文件系统有可能会处于不一致状态。特别时一些未被写回的块是i结点、目录块或者包含空闲表的磁盘块时,问题尤为严重,这一问题称为文件系统一致性问题。
  • 高速缓存的典型应用:

    • 记录成组

      • 把若干个逻辑记录合成一组存储在一个物理块的工作,称为记录的成组。每块中的逻辑记录个数称为“块因子”。

      • 实现原理:信息交换以块为单位,故成组需要用内存缓冲区来完成。

      • 1606912612843
    • 记录的分解

      • 从一组记录中把一个逻辑记录分离出来的操作,称为记录的分解。
      • 过程:当用户请求某记录时,文件系统首先找到该记录所在的磁盘块的位置,然后将把含有该记录的物理块全部读入内存缓冲区,从内存缓冲区分解出指定的记录,然后送到用户工作区。
      • 1606912855422
    • 记录的成组

      • 优点:提高了磁盘利用率,减少了启动磁盘的次数,提高系统工作效率。
      • 要考虑的因素:
        • 定长记录:比较好检索,记录的长度是一样的。
        • 不定长记录:记录的时候要记录“记录”的长度,计算长度,得出位置
    • RAID是英文Redundant Array of Independent Disks的缩写,中文简称为独立冗余磁盘阵列。

      • 简单的来说,RAID是一种把多个独立的硬盘(物理硬盘)按不同的方式组合形成一个硬盘组(逻辑硬盘),从而提供比单个硬盘更高的存储性能和提供数据备份技术。
      • 好处主要有以下三种:
        • 通过把多个磁盘组织在一起作为逻辑卷提供磁盘跨越能力;
        • 通过把数据分成多个数据块(Block)并行写入/读出多个磁盘以提高访问磁盘的速度;
        • 通过镜像或校验操作提供容错能力;
      • RAID技术经过不断的发展,现在已拥有从RAID 0 到 7 八种基本的RAID级别。另外,还有一些基本RAID级别的组合形式,如RAID 10(RAID 0 到RAID 1的组合),RAID 50(RAID 0与RAID 5的组合)等。不通过RAID级别代表着不同的存储性能、数据安全性和存储成本。
      • 我们最为常用的是下面的几种RAID形式。
        • RAID 0
        • RAID 1
        • RAID 0+1
        • RAID 3
        • RAID 5

文件共享、保护和保密

文件共享

  • 文件共享的概念:
    • 文件共享是指一个文件可以允许多个用户共同使用
  • 文件共享的分类
    • 从共享时间段上看,共享文件有两种使用情况:
      • 文件可以同时使用
      • 文件不允许同时使用
      • 在文件共享具体方式上,有三种共享方式:
        • 文件被多个用户使用,由存取权限控制
        • 文件被多个用户使用,但分别用自己的读写指针
        • 文件被多个程序使用,但共享读写指针
  • 文件共享的实现方法
    • 多级目录结构,常用的是连接发,分两种:
      • 允许目录项连接到任一表示文件目录的结点上。
      • 解:用户能共享目录结点和目录结点下所有的文件结点
      • 只允许连接到表示普通文件的结点
      • 解:用户只能共享普通文件结点
      • 1606914710372

文件保护

  • 人为因素:人们有意或无意的行为,会使文件系统中的数据遭到破坏或丢失;
  • 系统因素:由于系统的某部分出现异常情况,而造成数据的破坏或丢失,特别是作为数据存储主要介质的磁盘,一旦出现故障,会产生难以估量的影响
  • 自然因素:随着时间的推移,存放在磁盘上的数据会逐渐消失。
  • 为了确保文件系统的安全性:可采取的措施
    • 建立副本,即把同一个文件保存到多个存储介质上。
    • 定时转储,即每隔一定时间就把文件转储到其他存储介质上。
    • 规定文件的存取权限。可采用树形目录结构和存取控制表两种方法
  • UNIX的文件使用权限管理方案
    • 存取控制矩阵
      • R=读, W=写, E=执行
      • 1606915156735
    • 二级存取控制
      • 1606915233931
    • UNIX中的文件存取权限
    • UNIX中对文件的存取权限划分为两级
    • 在第一级中访问者或者用户进行分类识别。讲用户分为:文件主(owner)、文件主的同组用户(other)、其中用户(other)
    • 在第二级中,对文件操作权限的权限设置。包括:读(r)、写(w)、执行,不执行任何操作(-)。
    • 1606915536667

文件的保密措施

  • 文件保密的目的:
    • 是防止不经过文件拥有者授权而窃取文件。
    • 常用的文件保密措施有以下几种:
      • 隐蔽文件目录
      • 设置口令
      • 使用密码
      • 病毒防范

八、I/O设备管理

  1. I/O设备管理的基本概念
  2. I/O硬件和I/O软件组成
  3. I/O设备控制方式
  4. 设备分配与回收
  5. 磁盘驱动调度
  6. 缓冲技术
  7. 虚拟设备技术

I/O设备管理的基本概念

  • I/O设备管理的任务
    • 解决I/O设备和CPU速度不匹配的矛盾
    • 提供简单易用,实现对设备的统一管理
      • 普通用户接口
      • 编程接口
    • 保证设备安全性
      • 设备有权限才能使用
  • I/O设备分类
    • 按设备的使用特性分类
      • 输入设备
      • 输出设备
      • 交互式设备:鼠标键盘都可以算
      • 存储设备:磁盘
    • 按设备的信息组织方式分类
      • 字符设备:打印机、鼠标、键盘、处理单位是字符
      • 块设备:磁盘 传输是按块传输
    • 按设备使用的可共享性分类
      • 独占设备:
      • 共享设备:
      • 虚拟设备:虚拟设备是指一类设备上模拟另一类设备,目的是为了提高设备利用率
        • 把独占设备改造成共享设备,打印机,一次只能一个进程使用,本应是独占设备,但是现在可以多个用户“一起使用”,虽然一次还是只能一个用户去实际操作
  • I/O设备管理与文件管理的关系
    • I/O设备管理对象:
      • I/O设备,是对资源的管理,提供标准接口供用户用这些设备。
    • 文件管理对象:
      • 设备里面存储的数据和信息,提供一整套对这些资源的管理规则,并且以文件及其配套的概念来具体实施。
    • UNIX系统中:
      • 所有设备都当作文件对象来管理。

I/O硬件和I/O软件的组成

I/O硬件组成

  • 不同的人对于I/O硬件的理解不同
    • 电子工程师:I/O硬件就是芯片、导线、电源
    • 程序员:I/O硬件提供给软件的接口,如硬件能够接收的命令,它能够完成的功能以及让能够报告的错误等。
    • 本节主要介绍怎样对I/O设备编程,而不是设计、制造和维护硬件。0
  • 硬件角度,I/O硬件由物理设备和电子部件两部分组成。
    • 物理设备是达成I/O硬件功能的基础,对操作而言更注重的是其电子部件的控制方式。
    • 典型的硬件结构:
    • 1606973269751
    • 第一层:处理器和内存,通过总线与接口部件连接
    • 第二层:接口(设配器)
    • 第三层:设备控制器,是一种电子部件,每个设备控制器都有若干寄存器与存器进行通信,网卡,显卡等
    • 第四层:外围设备,设备并不直接与CPU进行通信,而是与设备控制器进行通信。

I/O软件组成

  • I/O软件结构的基本思想
    • I/O软件组成一系列层次,较低的层次处理与硬件相关的细节,并将硬件的特征y与较高的层隔离;较高层则向用户提供一个友好的、清晰而规整的I/O接口
    • I/O软件结构
      • 四层:
        • 中断处理程序
        • 设备驱动程序
        • 设备独立层软件
        • 用户层软件
      • 1606996147705

设备独立性

  • 含义:
    • 除了直接与设备打交道的底层软件之外,其他部分的软件并不依赖于硬件。既应用程序中所使用的设备,不局限于使用某个具体的物理设备,也称为设备无关性。
  • 优点:
    • 当I/O设备更新时,没有必要重新编写全部I/O软件。实际应用只要安装了驱动程序,可以方便地安装好新的I/O设备。
    • 设备更新了只要把新的驱动程序安装一下就好了。
  • 设备独立性软件的功能如下:
    • 设备命名
      • 在操作系统的I/O软件中,借用了与文件系统统一命名的方法,既采用文件系统路径名的方法来命名设备
      • 例如:UNIX系统中,/dev/tty00,确定一个特殊文件,其中包含了主设备号和次设备号。主设备号用于寻找对应的设备驱动程序,而次设备号提供了设备驱动程序的有关参数,用来确定要读写的具体设备。
    • 设备保护
    • 防止未授权用户对设备的非法使用
    • UNIX系统:存取权限模式,rwx位进行保护。
    • 提供一个与设备无关的逻辑块
      • 不同的设备,存储空间大小、读取速度、传输速率各不相同,与设备无关软件通过向上层提供大小统一的逻辑块屏蔽这种不同,使得上层软件只与抽象设备打交道,而不必考虑上述不同
    • 缓冲:防止速度不匹配
    • 存储设备的块分配
    • 独占设备的分配和释放
    • 错误处理

I/O设备控制方式

  • I/O设备的控制方式取决于I/O设备硬件与处理器和内存的连接方式以及设备的驱动程序,主要有四种方式:

    • 程序控制方式
    • 中断控制方式
    • DMA控制方式
    • 通道控制方式
  • 程序控制方式

    • 程序控制方式也称为PIO(Programmer I/O)方式,是指由用户进程直接控制处理器或内存和外围设备之间进行信息传送的方式,也称为“忙-等”方式,轮询方式或循环测试方法,这种方式的控制者是用户进程。

    • 以输入数据为例:

      1607001290296

      1. 处理器向控制器发出一条I/O指令,启动输入设备输入数据,同时把状态寄存器中的忙/闲标志busy置为1
      2. 不断循环测试busy(称为轮询)。当busy=1时,表示输入机尚未输完一个字(符),处理机应该对该标志进行测试,直至busy=0,表明输入机已将输入数据送入控制器的数据寄存器中。
      3. 处理机将数据寄存器中的数据取出,送入内存指定单元中,这样便完成了一个字(符)的I/O。接着在去启动下一个数据,并置busy=1。如此循环
    • 优点:

      • 处理器和外设的操作能通过状态信息得到同步,而且硬件结构比较简单
    • 缺点:

      • 处理器效率较低,传输完全在处理器控制下完成,对外部出现的异常事件无实时响应能力。
  • 中断控制方式

    • 中断处理方式的处理过程
      • 1607001870895
    • 中断控制方式的处理过程
      1. 处理器通过数据总线发出命令,启动外设工作,当前进程 阻塞,调度程序调度其他进程;
      2. 外设数据准备好,置为中断请求触发器
      3. 若此时接口中断屏蔽器状态为非屏蔽状态,则接口向处理器发送中断请求(IR)。
      4. 处理器接收中断请求,且中断为允许中断,则中断判忧电路工作。
      5. 中断判忧电路对优先级最高的中断请求给予响应(INTR),处理器中断正在执行的其他进程,转而执行中断服务程序。
    • 优点:
      1. 处理器与外设并行工作,提高计算机的利用率
      2. 具有实时响应能力
      3. 可及时处理异常情况,提高计算机的可靠性
  • DMA方式控制原理

    • DMA(直接访问内存)方式,是一种完全由硬件执行I/O数据交换的工作方式,数据交换不经过处理器,而直接在内存和I/O设备之间
    • 1607002773752
    • DMA方式传送过程
      1. 预处理阶段:由处理器执行I/O指令对DMAC(DMA控制器)进行初始化与启动。
      2. 数据传送阶段:由DMAC控制总线进行传送。当外设数据准备好,发DMA请求,CPU当前机器周期结束,响应DAM请求,DAMC从CPU接管总线的控制权,完成对内存寻址,决定数据传送的内存单元地址,对数据传送字进行计数,执行数据传送的操作。
      3. 后处理阶段:传送结束,DMAC向处理器发中断请求,报告DMA操作结束。处理器响应中断,转入中断服务程序,完成DMA结束处理工作,包括数据校验,决定是否结束传送等。
    • 优点:
      • 操作均有硬件完成,传输速度块;处理器只在初始化和结束时参与,对数据传输基本不干预,可以减少大批量数据传送时处理器的开销;处理器与外设并行工作,效率高。
    • 缺点:
      • 虽然能传输成批的数据,但是无法传输不连续的空间
  • 通道控制方式

    • 引入通道的目的
      • 通道是一个特殊功能的处理器,他有自己的指令和程序,可以实现对外围设备的统一管理和外围设备与内存之间的数据传送。
      • 引入通道的目的是为了进一步减少数据输入输出对整个系统效率的影响。
    • 通道的优点
      • 与DMA方式相比,通道方式增加了处理器与通道操作的并行处理能力;增加了通道之间或同一通道内各设备的并行操作能力;为用户提供了灵活增加外设的可能性。
    • 通道的分类
      • 选择通道
      • 数组多路通道
      • 字节多路通道
    • 通道的功能
      • 接收处理器的指令,按指令要求与指定的外围设备进行通信
      • 从内存读取属于该通道的命令,并执行通道程序,向设备控制器和设备发送各种命令
      • 组织外围设备和内存之间进行数据传送,并根据需要提供数据缓存的空间,以及提供数据存入内存的地址和传送的数据量。
      • 从外围设备得到设备的状态信息,形成并保存通道本身的状态信息,根据要求将这些状态新送到内存的指定单元,供处理器使用。
      • 按外围设备的中断请求和通道本身的中断请求,按序及时报告处理器。

设备分配与回收

  • 数据结构:系统设备表、设备控制表(DCT)、控制器控制表、通道控制表。

    • 系统设备表
      • 1607056115982
    • 设备控制表DCT
      • 等待/不等待:是否有进程在等待该设备
      • 忙/闲:是设备是否正在使用
      • 重复执行次数或时间:传输数据可能失败,进行重传的
      • 设备队列的队首指针:等待队列的队首指针
      • 1607056145760
    • 控制器控制表
      • CPU不直接操作设备,而是通过控制器操作设备,设备与控制器是键值对的关 系
      • 控制器队列的队首指针是等待该控制器的队首指针
      • 1607056169468
    • 通道控制表
    • 传输的流程是CPU - 控制器 - 通道
    • 通道队列的队首指针:这是想要使用该通道的队列
    • 1607056198636
  • 分配原则
    • 要充分发挥设备的使用率,尽可能让设备忙碌,但又要避免由于不合理的分配方法造成死锁
    • 要做到把用户程序和具体物理设备隔离开来,既用户面对的是逻辑设备,而分配程序将在系统的逻辑设备转换成物理设备之后,在根据要求的物理设备号进行分配
    • 设备分配效率:静态分配和动态分配
      • 静态分配是程序在分配好所需资源在运行。
      • 静态分配效率低,动态分配可能死锁
  • 分配策略
    • 主要考虑的因素:I/O设备的固有属性、分配算法、设备分配的安全性以及设备独立性
    • 设备固有属性:独占设备、共享设备、虚拟设备欸
    • 分配算法:先来先服务、高优先级优先

独占设备的分配

  • 设备的绝对号与相对号
    • 绝对号:系统为每一台设备确定的一个编号,用来区分和识别各种不同类型的外部设备,以便进行管理
    • 相对号:由用户在程序中定义的设备编号称为设备的”相对号“
    • 二者的对应关系:规定用户使用”设备类 相对号“来提出使用设备的要求,而系统在为用户分配具体设备的同时,建立设备的”绝对号“与用户使用的”设备类相对号“的对应关系。
  • 设备的指定方式
    • 两种方式
      • 绝对号
        • 使用绝对号的缺点,当指定的设备出现故障,即使还要其他同类设备,作业的请求任然得不到满足,必须等待。
        • 相当于我指定使用指定打印机,哪怕这台打印机有其他人使用,还有其他打印机空闲可以用,也只能能等着使用指定打印机
      • 设备类相对号
        • 适合用设备类 相对号的好处:实现了设备的独立性,既用户程序使用的逻辑设备与程序实际执行时使用的物理设备无关。
        • 这个就和上面相反
  • 独占设备的分配和释放
  • 设备分配表组成
    • 两部分:
      • 设备类表:记录有哪些设备
      • 设备表:记录分配给了谁
    • 1607575535250
  • 分配过程
    1. 用户作业提出某类外部设备申请
    2. 系统首先检查“设备类表”,现存台数能满足请求,则取得该类设备的“设备表”始址;否则等待
    3. 系统再依次检查该类设备再设备表中的登记项
    4. 若找到“设备状态”为好,且未分配的设备则准备进行分配,否则等待
    5. 修改设备类表和设备表,进行设备分配
  • 释放过程
    1. 系统回收设备时,对该台设备的“设备表”中的有关登记项进行修改,既把“分配状态”改为“未分配”同时撤销该设备的作业名和设备相对号,最后,再该类设备的“设备类表”中,把该类设备的现存台数加1。
  • 共享设备的分配
    • 共享设备可被多个进程共享,但在每个I/O传输的单位时间内只由一个进程所占用,以块为传输单位,可以交叉进行,没有明显的申请和释放活动。
    • 宏观的同时使用,微观还是独占。
    • 使用方法:
      1. 申请设备,如设备被占用,则进行设备等待队列,否则分配设备。
      2. 启动设备。I/O传输
      3. 释放设备,当设备结束,发出中断信号,系统唤醒一个等待设备的进程。

磁盘调度策略

  • 信息传输时间
    • 信息再磁盘上按柱面存储,同一柱面的各磁道存储满,再放到下一个柱面。

    • 启动磁盘执行输入输出操作时,要把移动臂移到指定的柱面,再等待指定扇区旋转到磁头位置下,然后让指定的磁头进行读写

    • 执行一次输入

      • 输出的时间:
        • 寻找时间:移动磁头到指定柱面的时间
        • 延迟时间:移动该磁道的指定扇区到磁道的时间
        • 传送时间:写数据或者读数据的时间
      • 1607576918597
    • 执行一次输入输出的时间:

      • 寻找时间 和 延迟时间 与位置有关
      • 传送时间是固定的
    • 位置计算:

      • 块号:磁盘一个扇区就是一个块,每个磁片都有多个扇区

      • 块号计算:

        • t:每个柱面上的磁道数
        • s:每个盘面上的扇区数
        • i:柱面
        • j:磁头
        • k:扇区
      • 块号反算为柱面号,磁头号,扇区号

        • 假定要访问的磁盘块为p:
        • d=s*t;
        • m =[p/d];
        • n=p mod d
        • 则第p块再磁盘上的位置为:
          • 柱面号 = m
          • 磁头号=[n/s]
          • 扇区号= n 取余 s
  • 移臂调度及调度算法

    • 移臂调度:
      • 根据访问者指定的柱面位置来决定执行次序和调度,称为“移臂调度”。
      • 目的:尽可能减少操作中的寻找时间
      • 常用算法:先来先服务调度算法,最短寻找时间优先调度算法、电梯调度算法、单向扫描调度算法
    • 例子:
    • 如一次要访问的柱面号是:
      • 130,199,32,159,15,148,61,99,调度次序如下图:
    • 先来先服务调度算法
      • 根据进程访问磁盘的先后顺序进行调度
      • 优点:公平和简单
      • 缺点:效率低
        • 1608464845786
      • 寻找距离=80+69+157+127+144+133+87+38=845
      • 平均寻找时间:845 / 8 = 108.625
    • 最短寻找时间优先调度算法:
      • 思想:选择这样的进程,其要求访问的柱面号,与当前磁头所在的柱面距离最近,以使每次的寻找时间最短
      • 优点:
        • 平均每次磁头移动的距离明显抵御FCFS的距离,固有较号的寻道性能,过去曾一度被广泛使用。
      • 缺点:
        • 可能发生饥饿的情况,因为始终在寻找距离自己最短的,如果有个进程需要的资源与其他资源相隔很远,那就不会去寻找这个进程需要的资源
      • 1608465365586
      • 寻找距离=11+29+17+84+31+11+40=223
      • 平均寻找距离=223/7=31.857142
    • 电梯调度算法
      • 思想:
        • 当移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱面访问,如果沿臂的移动方向无请求,就改变臂的移动方向再选择。
      • 由里向外
        • 1608465920138
        • 移动距离=18+17+46+38+41+18+11+40=229
      • 由外向里
        • 1608466092941
        • 移动距离=11+38+31+18+11+40+167+17=333
    • 单向扫描调度算法
      • 思想:
        • 不考虑访问者等待的先后次序,总是从0号柱面开始向里扫描,按照各自所需要访问的柱面位置的次序去选择访问者。当移臂到达最后一个柱面后,立即返回0号柱面,再次进行扫描
      • 1608466355189
  • 旋转调度优化

    • 旋转调度:
      • 在移动臂定位后,若有若干个访问者等待访问该柱面的情况下,若从减少输入输出操作的总时间为目标出发,应该优先选择延迟时间最短的访问者去执行。
      • 根据延迟时间来决定执行次序的调度称为”旋转调度“

目 录