操作系统的部分笔记
1.绪论
- 操作系统:操作系统是一组控制和管理计算机硬件和软件资源,合理地对各类作业进行调度,以及方便用户使用的程序的集合。操作系统的目标:
- 有效性:提高系统资源的利用率 提高系统资源的吞吐量
- 方便性
- 可扩充性
- 开放性
-
OS是用户与计算机硬件之间的接口,用户可以通过三种方式来使用计算机:
- 命令方式,这是由OS提供了一组联机命令接口,用户用键盘输入相关命令来取得操作系统的服务。
- 系统调用方式:OS提供了一组系统调用,用户可以在自己的应用程序种通过相应的系统调用来实现与操作系统的通信,并获取它的服务。
- 图形,窗口方式:就是你现在正在用的方式。
-
OS实现了对计算机资源的抽象。
-
无操作系统的计算机系统:
- 人工操作系统:用户独占全机,CPU等待人工操作。
- 脱机输入/脱机输出:先把数据通过外围机输入到此带上,CPU需要这些数据时,直接从磁带上调入内存。输出时,CPU先间数据输出到磁带上,磁带在外围机的控制下输出到相关的设备。优点:减少了CPU的空闲时间,提高了IO速度
-
单道批处理系统:系统对作业的处理都是成批的,且内存中始终都只有一道作业,故称为单道批处理系统。
-
多道批处理系统:
- 优点1:资源利用率高:由于在内存中驻留了多道程序,它们共享资源,可以保持资源处于忙碌状态,从而使个各种资源都得到充分利用。
- 优点2:系统吞吐量大:因为CPU和其他资源充分保持着忙碌状态,仅当作业完成时或着运行不去时才进行切换,系统开销小。
- 缺点1:平均周转时间长:在批处理系统中,由于作业要排队,依次处理,因而作业的周转时间长。
- 缺点2:五交互能力。一旦把作业交给系统,直到作业完成,用户都不能和作业交互。
-
分时系统:经常被用于查询系统中,满足许多查询用户的需求。主要为:人机交互, 共享主机,便于用户上机。分时系统的特征:
- 多路性:允许在一台主机上同时链接多台联机终端,系统按分时的分时的原则为每一个用户服务。在微观上,每个用户作业轮流运行一个时间片。多路性即同时性,它提高了系统的资源利用率,降低了费用。
- 独立性:每个用户独占一个终端,彼此独立操作,互不干扰。
- 及时性:用户的请求能够在极短的时间内获得响应。
- 交互性:用户可以通过终端与系统进行广泛的人机对话。
-
实时操作系统:实时控制,实时信息处理。实时操作系统与分时操作系统的比较:
- 多路性:实时信息处理系统也能按照分时的原则为多个终端服务。
- 独立性:对信息的采集与对对象的控制独立,互不干扰。
- 及时性:实时控制系统的及时性,时以控制对象所要求的开始时截止时间或者完成截止时间来确定的。
- 交互性:实时信息处理系统虽然也有交互性,但是仅限于访问系统中某些特定的专用服务程序。
- 可靠性:实时操作系统要求系统又高度的可靠性。
-
操作系统的基本特性:
- 并行与并发:并行性是指两个或则和多个事务在同一时刻发生,并发性是指两个或者多个事务在同一个时间间隔内发生。在多道程序环境下,并发性是指在一段时间内宏观上有多个程序同时运行,但是在单机处理系统中,每一时刻却仅能有一道程序,故微观上这些程序这能是分时地交替执行。
- 引入进程:通常程序是静态的实体,在多道程序系统中,他们是不能够独立运行的,更不能和其他的程序并发执行。在操作系统中,引入进程的目的,就是为了使得多个程序能够并发执行。
- 进程:为了使得多个程序能够并发的执行,系统必须分别为每个程序建立进进程。简单的说,进程是指在操作系统中能独立运行并且作为资源分配的基本单位。它是由一组机器指令,数据和堆栈组成的。是一个能够独立运行的活动实体。多个进程之间可以并发执行和交换信息。一个进程在运行时需要一定的资源,如CPU,存储空间及IO等设备。
- 引入线程:由于进程拥有自己的资源,故使得调度进程的开销非常大。通常在一个进程中可以包含多个线程。他们可以利用进程所拥有的资源,在引入线程的OS中,通常都是把进程作为分配资源的基本单位。而把线程作为独立运行和独立调度的基本单位。线程比进程小,基本上不拥有系统资源。
-
共享性:在操作系统的环境下,所谓的共享,是值系统中的资源可以供内存中多个并发执行的进程(线程)共同使用。
- 互斥共享方式:系统中的某些资源,如打印机,磁带机,虽然他们可以提供给多个进程(线程)是以哦那个,但是为使所打印或者记录的结果不混淆,规定在一段时间内只允许有一个进程(线程)访问该资源。计算机系统中的大所示物理设备,以及某些软件中所使用的栈,变量,表格,都属于临界资源。他们求奥求被互斥的共享。
- 同时访问方式:系统中有一类资源,允许在一段时间内多个进程“同时”访问,这里的同时,在单处理机的环境下往往是宏观上的,而在微观上,这些进程可能是交替读对该资源进行访问。最典型的可以工多个进程同时访问的资源就是磁盘设备,一些用冲入代码编写的文件也可以被同时共享。
-
虚拟技术:虚拟技术是值通过某一种技术把一个物理实体转变为若干个逻辑上的对应物。
- 虚拟处理及技术:在虚拟处理机技术中,利用多道程序设计技术,为每一道程序建立一个进程,让多道程序并发的执行,一次来分时的使用一台处理机。
- 虚拟设备技术:我们通过虚拟设备技术,将一台物理IO设备虚拟为多台逻辑上的IO设备。并且允许每个用户占用一台逻辑上的IO设设备。
- 虚拟磁盘技术:通常在一台机器上只配置一台硬盘,我们可以通过虚拟磁盘技术将一台硬盘虚拟为多台虚拟硬盘。这样使用起来方便安全。例如:1,2,3,4四个卷,在通过安装程序将他们分别安装在C,D,E,F四个逻辑驱动器上。这样,机器上便有了四个虚拟硬盘。
- 虚拟存储器技术
-
异步性:由于受制于资源等因素,使得进程的执行通常不是一气呵成的,而是以走走停停的方式运行。
-
处理机管理功能:
- 进程控制:进程控制的主要功能是为作业创建进程,撤销已经结束的进程,以及控制进程在运行过程中的状态转换。在现当代OS中,进程控制开应该具有一个进程创建若干个线程的功能和撤销已经完成的线程的功能。
- 进程同步:进程同步有的主要任务是为多个进程(含线程)的运行进行协调。有两种协调方式:进程互斥方式,进程同步方式。实现进程同步的最常见的机制是信号量机制。
- 进程通信:进程通信的任务就是用来实现相互合作的进程之间的信息交换。
- 作业调度:作业调度的基本任务是从后被队列中按照一定的算法,选择出若干个作业,为他们分配运行所需要的资源。
- 进程调度:进程调度的任务是从进程的就绪队列中,按照一定算法选出一个进程,把处理及分配给它,并且为它设置运行现场。
-
存储器管理功能:
- 内存分配:内存分配的主要任务是为每道程序分配内存空间,提高存储器的
利用率,允许正在运行的程序申请附加的内存空间。OS在实现内存分配时,可以采用静态和动态两种方式,在静态分配内存中,每个作业的空间时在作业装入时确定的,在作业装入后的整个运行期间,不允许该作业再申请新的内存空间,也不许作业在内存中移动。在动态分配方式中,每个作业所要求的基本内存空间也时在装入时确定的,但是允许作业在运行过程中继续申请新的附加内存空间,以适应程序和数据的动态增长。也允许作业在内存中移动。 - 内存保护:内存保护的主要任务时确保每道用户程序都旨在自己的内存空间内运行,比起互不干扰。绝不允许用户程序访问操作系统的程序和数据,也不允许用户程序转移到非共享的其它用户程序中执行。
- 地址映射:简单的说就是把程序中的逻辑地址映射到实际的物理地址。
- 请求调入功能:允许在装入一部分用户程序合和数据的情况下,就能启动该程序运行。在运行过程中,若发现要继续运行时所需要的程序和数据尚未装入内存,可以向OS发出请求,由OS从从盘中将所需要部分调入内存,以便继续运行。
- 置换功能:若发现内存中一节那个没有足够的空间来装入需要调入的程序和数据时,系统应能将内存中的一部分暂时不用的程序和数据调至盘上,以腾出内存空间,然后在将所需要调入的部分装入内存。
- 内存分配:内存分配的主要任务是为每道程序分配内存空间,提高存储器的
-
设备管理功能:
- 缓冲管理:缓冲区为了解决设备的速度不匹配,缓冲区由OS中的缓冲管理机制将他们管理起来。
- 设备分配:设备分配的基本任务是根据用户进程的 I/O 请求、系统的现有资源情况以及按照某种设备的分配策略,为之分配其所需的设备。
- 设备处理:设备处理程序又叫做设备驱动程序,其基本任务是用于实现CPU和设备驱动器之间的通信。
-
文件管理功能:
- 文件存储空间的管理:系统应该设置相应的数据结构,用于记录文件存储的空间的使用情况,以供分配存储空间时参考。系统还应具有对存储空间仅从分配胡回收的功能。为了提高存储空间的利用率,对存储空间的分配,通常是离散式的,为了减少外存零头,并且以盘块为基本单位分配。
- 目录管理:为了使用户方便地在外存上找到自己所需要的文件,通常由系统为每个文件建立一个目录项。目录项包括:文件名,文件属性,文件在磁盘上的物理位置…由若干个目录项又可以构成一个目录文件。
-
OS与用用户之间的接口:
- 用户接口:它是提供给用户使用的接口,用户可以通过该接口起的操作系统的服务。
- 程序接口:它是提供给程序员在编程时使用的接口,是用户程序获取操作系统服务的唯一途径。
-
程序接口:由一组系统调用组成,每一个系统调用都是一个能完成特定功能的子程序。每当应用程序要求OS提供某种服务功能时,便调用具有相应共功能的系统调用。在高级语言以及C语言中,往往提供了与各系统调用一一对应的库函数,这样,应用程序便可通过调用对应的函数库来实现系统调用。但是在近几年的操作系统中,如UNIX,其系统调用本身就是用C语言来编写的,并且以函数形式提供,故在用C语言编写的程序中,可以直接进行系统调用。
2 进程管理
-
进程的特征和定义:在多道程序环境下,程序的执行属于并发执行,此时它们失去其封闭性,并且具有间断性以及不可再现性的特征。这决定了通常的程序是不能参与并发执行的,因为程序执行的结果不可再现,这样,程序的运行就失去了意义。为了使程序能并发执行,且对并发执行的程序加以描述和控制,人们引入了“进程”的概念。
- 结构特征:通常的程序是不能并发执行的。为了使得程序(含数据)能够独立运行,应该为之配置一个进程控制块PCB(Process Control Block)。而由程序段,相关的数据段和PCB三部分便构成了进程实体。在许多情况下所说的进程,实际上是指进程实体。例如:所谓的创建进程,实质上是创建进程实体中的PCB,而撤销进程,实质上是撤销进程的PCB。
- 动态性:进程的实质就是进程实体的一次执行过程。因此,动态性是进程的最基本的特征。动态性还表现在:它由创建而产生,由调度而执行,由撤销而消亡。可见,进程实体由一定的生命期,而程序则只是一组有序的指令集和,并且存放于某种介质上,其本身并不具有运动的含义,所以是静态的。
- 并发性:这是指多个进程实体同存在于内存中,并且能在一段时间内运行。并发性是进程的重要特性,同时也是OS的重要特征。引入进程的目的正式为了使其进程实体能和其他进程实体并发运行,而程序(没有建立PCB)是不能并发执行的。
- 独立性:在传统的OS中,独立性是指的进程实体是一个能独立运行,独立分配资源和独立接受调度的基本单位。凡是没有建立PCB的的程度都不能作为一个独立的单位参与运行
- 异步性:进程都是按照各自独立的,不可预知的速度向前推进,或者说进程实体按照异步的方式运行。
-
进程的三种基本状态:
- 就绪状态:当进程已经分配了除CPU以外的所有资源后,只要获得CPU,便可以立刻执行。这样的状态叫做就绪状态。在一个系统中处于就绪状态的进程可以有多个。它们通常排列成一个队列,称为就绪队列。
- 执行状态:进程已经获得了CPU,其程序正在执行,在单处理机系统中,只有一个进程处于执行状态。在多处理机系统中,则有多个进程处于执行状态。
- 阻塞状态:在执行的进程由发生某种事情而暂时无法执行时,便放弃处理机而处于暂停的状态。即进程的执行收到阻塞,把这种暂停状态称为阻塞状态。典型事件:请求IO,申请缓存空间等。注意,正在运行的进程时间片用完后变为就绪状态,不是阻塞状态(因为它不缺其他的资源,只是暂时不能用CPU了)。
-
进程控制块的作用:为了描述和控制进程的运行,系统为每个进程都定义了一个数据结构:进程控制块(PCB)。它是进程实体的一部分,是操作系统中最重要的记录型数据结构。
- PCB中记录了操作系统所需要的,用于描述进程当前情况以及控制进程运行的全部信息。进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据),成为一个能够独立运行的基本单位。一个与其他进程并发执行的进程。
- OS是根据PCB对并发进行的进程进行控制和管理的。例如:当OS需要调度某一个进程执行时,要从该进程的PCB中查出其现行状态以及优先级。
- 在调度某个进程后,要根据其PCB中所保存的处理机状态信息,设置该进程回复运行的现场。并根据其PCB中的程序和数据的内存地址,找到其程序和数据。
- 进程在执行过程中,当需要和与之合作的进程实现同时,通信或者访问文件时,也要访问PCB。
- 当进程由于某种原因需要暂停执行时,又要将断点的处理机环境保存在PCB中。
-
在进程的整个生命周期中系统总是通过PCB来对进程进行控制的。系统是根据PCB来感知进程的存在的。所以说,PCB是进程存在的唯一标志。
-
因为PCB经常被系统访问,尤其是被运行频率很高的进程及分派程序访问,故PCB应该常驻于内存。
-
原语:是由若干条指令组成的,用于完成一定功能的一个过程。它与一般过程的区别在于:它们是原子操作,原子操作,指的是一个操作中的所有动作要么全都做,要么全都不做。他是一个不可分割的基本单位。因此,在执行过程中不允许被中断。原子操作是在管态下执行的,常驻内存。
-
子进程可以继承父进程所拥有的资源,例如,继承父进程打开的文件,继承父进程所分配的缓冲区等。当子进程被撤销时,应将其从父进程那里获得的资源归还给父进程。此外,在撤销父进程时,也要撤销其所有的子进程。
-
引起进程创建的事件:
- 用户登录:在分时操作系统中,用户在终端键入登录命令后,如果合法用户,系统将为该终端建立一个进程,并把它插入道就绪队列中。
- 作业调度:在批处理系统中,当作业调度程序按照一定的算法调度某作业时,便将该作业装入内存,为它分配必要的资源,并立刻为它创建进程,在插入到就绪队列中。
- 提供服务:当运行中的用户程序提出某种请求后,系统将专门为其创建一个进程来提供用户所需要的服务。
- 应用请求:基于应用进程的需求,由它自己创建的一个新进程,使得进程以并发运行方式完成特定的任务。
-
引起进程终止的事件:
- 正常结束
- 异常结束:越界错误,保护错,非法指令,特权指令错,运行超时,等待超时,算术运送错误(比如除0),IO故障
- 外界干预:操作员或者是操作系统请求,父进程请求,父进程终止
-
引起进程阻塞和唤醒的事件:
- 请求系统服务:当正在执行的进程请求操作系统提供服务时,由于某种原因,操作系统并并不立刻满足该进程的要求,该进程只能转变为阻塞状态来等待。例如:一个进程请求使用某种资源,如打印机,由于系统已经将打印机分配给其他进程而不能分配给请求进程,这时请求者进程只能被阻塞,仅在其他进程在释放打印机的同时,才能将进程唤醒。
- 启动某种操作:当进程启动某种操作后,如果该进程必须在操作完成后才能执行,则必先使该进程阻塞,以等待该操作的完成。
- 新数据尚未到达:对于相互合作的进程,如果其中一个进程需要获得另一个进程提供的数据后才能对数据进行处理,则只要其所在的数据尚未到达,该进程就只能被阻塞。
- 无新工作可做:系统往往设置一些具有某特定功能的系统进程,每单那个这种进程完成任务后,便把自己阻塞起来以等待新任务的到来。(听起来有点像自闭....)
-
进程的阻塞:正在执行的进程,当发现上述的某种事情时,由于无法继续执行,于是进程便通过调用阻塞原语block把自己阻塞住。可见,进程的阻塞是进程自身的一种行为。
-
临界资源:许多的硬件资源,如打印机,磁带机等,都属于临界资源。进程之间应采取互斥的方式,实现对这种资源的共享。
-
临界区:人们把在每个进程中访问临界资源的那段代码称为临界区。欣然,若能保证进程互斥地进入自己的临界区,便可以实现进程对临界资源的互斥访问。
-
同步机制应该遵循的规则:
- 空闲让进:当无进程处于临界区是,表明临界资源处于空闲状态。应该允许一个请求进入临界区的进程立即进入自己的临界区,以有效的利用临界资源。
- 忙则等待:当自己有进程进入临界区时,表明临界资源正在被访问,因而其他试图进入临界区的进程必须等待,以保证对临界区资源互斥的访问。
- 有限等待:对要求访问临界资源的进程,应保持在有限的时间内能进入自己的临界区,以避免陷入“死等”状态。
- 让权等待:当进程不能进入自己的临界区时,应该立即释放梳理及,以免进程陷入“忙等”状态。
-
管程:代表共享资源的数据结构,以及由对该数据结构实施操作的一组过程 所组成的资源管理程序,共同构成了一个操作系统的资源管理模块,我们称之为管程。管程被请求和释放资源的进程所调用。一个管程定义了一个数据结构和能为并发进程所执行(在该数据上)的一组操作,管程由四部分组成:
- 管程的名称
- 局部于管程内部的共享数据结构说明
- 对该数据结构进行操作的一组数据
- 对局部于管程内部的共享数据设置初始值的语句
-
管程相当于围墙,它把共享变量和对它进行操作的若干过程围了起来,所有的进程要访问临界资源时,都必须经过管程(相当于通过未将的门)才能进入。而管程每次只允许一个进程进入管程,从而实现了进程互斥。
-
管程时一种程序设计语言结构成分,它和信号量由同等的表达能力,从语言的角度来看,管程主要有以下的特征:
- 模块化,管程是一个基本程序单位,可以单独编译。
- 抽象数据类型,管程中不仅有数据,而且有对数据的操作。
- 信息掩蔽,管程中的数据结构只能被管程中的过程访问,这些过程也是在管程内部定义的,供管程外的进程调用,而管程中的数据结构以及过程(函数)的具体实现外部不可见。
-
管程和进程的区别:
- 虽然二者都定义了数据结构,但是进程定义的是私有数据结构PCB,管程定义的是公共数据结构,如消息队列。
- 二者都存在对各自数据结构上的操作,但进程是由顺序程序执行有关的操作,而管程主要是进行同步操作和初始化操作。
- 设置进程的目的是在于实现系统的并发性,而管程的设置则是解决共享资源互斥使用的问题。
- 进程通过调用管程中的过程对共享数据结构实行操作,该过程就如通常的子程序一样被调用,因而管程为被动工作方式,进程为主动工作方式。
- 进程之间能并发对的执行,而管程不能与其调用者并发。
- 进程具有动态性,由创建而诞生,由撤销而消亡,而管程则是操作系统中的一个资源管理模块,供进程调用。
-
进程通信:目前,高级通信机制可以分为三大类:共享存储器系统,消息传递系统,管道通信系统。
-
共享存储器系统:在共享存储器系统中,相互通信的进程共享某些数据结构或者共享存储区,进程之间能够通过这些空间进行通信。据此,又可以把它们分成以下两种类型:
- 基于共享数据结构的通信方式:在这种通信方式中,要求进程公用某些数据结构,借以实现进程之间的信息交换。
- 基于共享存储区的通信方式:为了传输大量数据,在存储器中划出了一块共享存储区,进程可以通过对共享存储区中的数据读或者写来实现通信。
-
消息传递系统:程序员直接利用操作系统提供的一组通信命令(原语),不仅能实现大量数据的传递,而且还隐藏了通信的实现细节,使通信对过程对用户是透明的,从而大大简化了通信程序编制的复杂性,因而获得了广泛的使用。
-
管道通信:管道是一种共享文件,是指的用于链接一个读进程和一个写进程以实现它们通信的一个共享文件,又名pipe文件。向管道文件提供输入的发送进程,以字符流形式将大量数据送入管道,而接收管道输出的接收进程,则从管道中就收数据,由于发送进程和接收进程是利用管道进行通信的,故称为管道通信。
-
线程的引入:在操作系统中引入进程的目的,是为了使多个程序能并发的执行,以提高资源的利用率和吞吐量,那么在操作系统中再引入线程,则是为了减少程序再并发执行时所付出的时空开销,使OS有更好的并发性。
-
由于进程是一个资源的拥有者,因而再创建,撤销和切换中,系统必须为之付出较大的时空开销。在引入线程的操作系统中,通常一个进程都会有若干个线程,至少也会有一个线程。
-
线程与进程的比较:
进程 线程 调度 资源拥有的基本单位 调度和分派的基本单位 并发性 进程之间可以并发执行 一个进程中的多个线程也可以并发的执行 拥有资源 拥有资源 不拥有资源(当然还是要有一点必不可少的资源) 系统开销 高 低 -
线程的属性:在多线程操作系统中,通常一个进程中包括多个线程,每个线程都是作为利用CPU的基本单位,是花费最小开销实体。线程具有以下的属性:
- 轻型实体:线程中的实体基本上不拥有系统资源,只是有一点必不可少,能保证其独立运行的资源。
- 独立调度和分派的基本单位:在多线程OS中,线程是能独立运行的基本单位,因而也是独立调度和分派的基本单位。
- 可并发执行:在一个进程中的多个线程之间可以并发的执行,甚至允许在同一个进程中的所有线程都并发的执行。同样的,不同进程中的线程也可以并发的执行。
-
线程的终止:同进程一样,线程也是有生命周期的,终止线程的方式有两种:
- 在线程完成了自己的工作后自愿退出。
- 线程在运行中出现错误或者由于某种原因被其他线程强行终止。
-
线程之间的同步:貌似和进程差不多
-
内核级线程:对于通常的进程,无论是系统进程还是用户进程,进程的创建,撤销以及要求由系统设备完成的IO操作,都是利用系统调用进入内核,在由内核中相应的处理程序予以完成的。进程的切换同样是在内核的支持下实现的。因此我们说,无论什么进程,它们都是在操作系统的支持下运行的,是与内核紧密相关的。
这里所谓的内核支持线程,也是同样在内核的支持下运行的。即使无论是用户进程中的线程,还是系统进程中的线程,他们的创建,撤销和切换等也是依靠内核,在内核空间中实现的,此外,在内核空间还为每一个内核支持线程设置了一个线程控制块(听起来好像和PCB有点像)。内核时根据该控制块而感知某线程的存在,并对其加以控制。
-
内核级线程实现方式的优点:
- 在多处理器系统中,内核能够同时调度同一个进程中的多个线程并行执行。
- 如果其中一个线程被阻塞,内核还可以调度该进程中的其他线程占有处理器运行,也可以运行其他进程中的线程。
- 内核支持线程具有很小的数据结构和堆栈。线程的切换比较快,切换开销小。
- 内核本身也是可以采用多线程技术。可以提高系统的执行速度和效率。
-
用户级线程:
- 用户级线程仅存在与用户空间中。对于这种线程的创建,撤销,线程之间的同步与通信功能,都无须利用系统调用来实现。对于用户级线程的却换,通常发生在一个应用的诸多线程之间,这时,也同样无需内核的支持。由于切换的规则远比进程调度和切换的规则简单,因而使用线程的切换速度特别快。由于这种线程是于内核无关的,用户级线程的任务控制块都在用户空间,而线程所执行的操作也无需内核的帮助,因而内核完全不知道用户级线程的存在。
-
值得说明的是,对于设置了用户级线程的系统,其调度仍是以进程为单位进行的,假如系统中设置的是内核支持线程,则调度便是以线程为单位进行的。(操作系统教材中写的,不过王道考研中貌似没有涉及到这一点。我去,好他喵的纠结。如果真要是碰上这种问题就....好吧,因该就按着教材上写吧)
-
用户级线程的优点:
- 线程的切换不需要转换到内核空间,对一个进程而言,其所由的管理数据结构均在该进程的用户空间中,管理线程切换的线程库也在用户地址空间运行。
- 调度算法可以是进程专用的。在不干扰操作系统调度的情况下,不同的进程可以根据自身需要,选择不同的调度算法对自己的线程进行管理和调度,而与操作系统的低级调度算法是无关的。
-
用户级线程的缺点:
- 系统调用的阻塞问题。在基于进程机制的操作系统中,大多数系统调用将阻塞进程,因此,当线程执行一个系统调用时,不仅该线程被阻塞,而其进程内的所有线程都会被阻塞。而在内核支持级线程方式中,进程中的其他线程还可以运行。
- 在单纯的用户级线程实现中,多线程并不能利用处理机的多重处理的有优点,内核每次分配给一个进程的仅有一个CPU,因此进程中仅有一个线程执行。在该线程放弃CPU之前,其他线程只能等待。
-
用户及线程以内核控制线程链接:
- 一对一模型:该模型为每一个用户线程都设置一个内核控制线程与之链接,当一个线程被阻塞时,允许调度另一个线程运行。该模型的并行能力较强,但是每次创建一个用户级别线程就要创建一个内核级线程,因此开销较大。
- 多对一模型,将多个用户级线程映射到一个内核控制线程上,为了管理方便,这些用户线程一般(注意是一般)属于一个进程,运行在该进程的用户空间,对这些线程的调度和管理也在该进程的用户空间中完成。当用户线程需要访问内核时,才将其映射到一个内核控制线程上,但每一次只允许一个线程进行映射。该模型的主要优点时管理的开销小,效率高,但是当一个线程在访问内核时发生阻塞,整个进程照样也会被阻塞。而且,在多处理机的系统中,一个进程的多个线程无法实现并行。
- 多对多模型:将多个用户线程映射到多个内核控制线程,内核控制线程的数目可以根据应用进程和系统的不同而变化,可以比用户线程少,也可以与之相同,但是不能比用户线程多(我认为可能是因为多了没有意义)。
3.处理机调度
-
高级调度,中级调度,初级调度(这里王道上貌似没有涉及,考研貌似也没有涉及)
- 高级调度:又称为作业调度,或者长程调度。其主要功能是根据某种算法,把外存上处于后被队列中的那些作业调入内存,也就是说,它的调度对象是作业。
- 中级调度:又称为中程调度,引入中级调度的主要目的是提高内存的利用率和吞吐量。决定哪些进程在内存中。中级调度实际上是存储器管理中的兑换功能。
- 低级调度:通常也把低级调度称为进程调度或者短程调度,它所调度的对象是进程(或者是内核级线程)。
-
周转时间:指的是从作业被提交给系统开始,到作业完成的这段时间间隔。对于每个用户而言,都希望自己的作业周转时间最短,但是作为计算机系统的管理者,则总是希望能使得平均周转时间最短。这不仅会有效的提高系统资源的利用率,而且能让多数用户满意。平均周转时间就是N个周转时间的平均值。
-
响应时间:响应时间是指从用户通过键盘提交第一个请求开始,直到系统首次产生响应为止的时间。这是分时操作系统中进程调度算法的重要准则之一。
-
带权周转时间:就是周转时间T与为它提供服务时间Ts的比值,即为W=T/Ts。平均带权周转时间就是所有带权周转时间的平均值。
-
先来先服务算法(FCFS):顾名思义,先到先得。最简单的一种调度算法,该算法既可以用于作业调度,也可以用于进程调度。
- 先来先服务算法有利于长作业,不利于短作业。
- 先来先服务算法有利于CPU繁忙型的作业,而不利于IO繁忙型的作业。通常科学计算属于CPU繁忙型作业,目前大多数事务处理都属于IO繁忙型作业。
-
短作业有限(SJF)算法:对于短作业或者短进程优先调度的算法。短作业有限算法能够有效的降低平均作业等待时间,提高系统的吞吐量。但是有以下几个缺点:
- 该算法对于长作业不利,而且肯能会导致长进程长期不会被调度。
- 该算法完全没有考虑作业的紧迫度,不能保证紧迫性的进程会被及时处理。
- 由于作业的长短只能是根据用户所提供的执行时间而顶的,而用户有可能有意或者无疑的缩短其作业的估计运行时间,导致该算法不一定真正的做到短作业优先。
-
非抢占式优先权算法和抢占式优先权算法:简单的说就是为每一个作业设置一个优先级,优先级高的作业先运行,非抢占式算法中,一个进程如果获得了处理机,就会一直运行到其结束,即使中途有更高优先级的进程需要调度也不会放弃处理机,抢占式算法就是如过新来的进程优先级更高,正在运行的进程就会放弃处理机,让给新来的进程,新来的的进程就要挂在就绪队列上,等待处理机。(这个算法王道考研中没有涉及,貌似真的考研中也没有涉及)
-
高响应比优先算法:相应比:(等待时间+要求服务时间)/要求服务时间。相应比高的进程优先得到调度。高响应比优先算法的特点:
- 等待时间相同时,短作业优先被调度。所以该算法对短作业有利
- 当服务时间相同时,等待时间长的作业优先被调度,等待时间越长,优先级越高,以此来实现先来先服务。
- 对于长作业,随着等待的时间增加,其优先级也逐渐提高,从而获得处理机。
-
高响应比优先算法照顾了短作业,又考虑了作业到达的先后顺序,不会使得长作业一直得不到服务,因此该算法是一个比较好的折中,当然在利用此算法时,都要先计算响应比,这会增加系统开销。
-
时间片轮转法:简单的说,就是把所有的作业都排成一个队列,每一次都为队头的作业服务一段时间。如果队头的作业被处理完成,就离开队列,处理下一个作业,否则就把这个作业从处理机上撤下,插进队尾,处理新的队头作业,这样周而复始....这个算法的时间片的大小对性能影响很大,如果时间片很小,有利于短作业,如果,但是会频繁的发生中断,切换进程,从而加大系统的开销,然是如果时间片很长,这个算法的退化成先来先服务算法....一个较为合理的时间片大小时,时间片略大于一次经典交互所需要的时间。
-
多级反馈队列调度算法(我去,这个算法貌似有点复杂):
- 首先设置多个就绪队列,编号为q1,q2,q3....qn,其中q1的优先级最高,q2的优先级第二…qn的优先级最低。其中系统分配q1队列中的任务时间片最短,q2的时间片比q1长一倍,q3的时间片比q2长一倍....(教材和王道考研中的时间片长度是按照*2的关系给的)
- 当一个新的进程来到内存中时,先把它插入到q1的队尾,然后系统先为q1对头的作业服务,如果在q1的时间片内完成了,就调出队列,服务q1中下一个作业。如果没有完成,就调入q2的队尾,服务q1中的下一个作业....
- 假设q1中的作业全都服务过一遍,现在q1为空,系统便开始服务q2中的作业,和刚才一样,首先服务q2队头的作业,完成就出队,否则就挂在q3的队尾…
- 假设q2中的作业全都服务过一边,现在q2为空,q1也为空(注意,如果某时刻又来了新的作业,也要挂在q1上,这个进程会抢占处理机,然后再按照刚才的逻辑执行),系统便开始服务q3中的作业....
-
多级反馈队列调度算法的性能:
- 终端型作业用户:由于终端型作业用户提交的作业大多数都属于交互性作业,作业通常比较小,系统只需要能使这些作业在第一队列所规定的时间内完成,变可以使终端作业用户都满意。
- 短批处理作业用户:对于很短的批处理型作业,开始时像终端作业一样,如果仅仅在第一队列中执行一个时间片即可完成,便可获得与终端型作业一样的响应时间。对于稍长的作业,通常也只需在第二队列和第三队列各执行一个时间片即可完成,其周转时间仍然较短。
- 长批处理作业用户,对于长作业,它将依次在1,2,3,4…n个队列中运行,然后再按轮转的方式运行,不用担心得不到处理。
-
死锁: 产生死锁的原因可以归结为以下两点:
- 当系统中提供多个进程共享的资源,如打印机,公用队列等,其数目不足以满足诸多进程的需要时,会引起进程对资源的竞争而产生死锁。
- 进程间的推进顺序非法性。进程在运行过程中,请求和释放资源的顺序不当,也同样会导致产生进程死锁。
-
产生死锁的必要条件:
- 互斥条件:指进程对所分配的资源进行排他性使用,即在一段时间内某资源只能由一个进程占用,如果此时还有其他进程请求该资源,则请求者只能等待。直至占有该资源的进程用毕释放。
- 请求和保持条件:指进程已经保持了至少一个资源,但是又提出了新的资源请求,而该资源已被其他进程占有,此时请求进程阻塞,但是又对自己获得的其他资源保持不放。
- 不剥夺条件:指进程已获得的资源,在未使用完之前,不能被剥夺,只能在使用完时自己释放。
- 环路等待条件:后一个等待前一个,后一个等待前一个....第一个等待最后一个....
-
处理死锁的基本方法:
- 预防死锁:这是一种较为简单和只管的事先预防的方法,该方法是通过设置某些限制条件,去破坏产生死锁的四个必要条件中的一个或者几个,来预防死锁。预防死锁是一种比较易于实现的方法,已经被广泛使用。但是由于限制条件往往太严格,因而会导致系统资源利用率和系统吞吐量降低。
- 死锁避免:该方法同样是属于事先预防的策略,单是并不是事先采取各种限制措施去破坏死锁的四个必要条件,而是在资源的动态分配中,用某种方法去防止系统进入不安全状态,从而避免死锁。这种方法只需事先施加较弱的限制条件,便可获得较高的资源利用率及系统吞吐量,但在实现上有一定的难度。目前在较完善的系统中常用此方法来避免发生死锁。
- 检测死锁:这种方法并不须事先采取任何限制性措施,也不必检查系统是否已经进入不安全区,而是允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构,及时地检测出死锁的发生,并精确地确定与死锁有关的进程和资源; 然后,采取适当措施,从系统中将已发生的死锁清除掉。
- 解除死锁:这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时,须将进程从死锁状态中解脱出来。常用的实施方法是撤消或挂起一些进程,以便回收一些资源,再将这些资源分配给已处于阻塞状态的进程,使之转为就绪状态,以继续运行。死锁的检测和解除措施有可能使系统获得较好的资源利用率和吞吐量,但在实现上难度也最大
-
银行家算法是死锁避免算法
(其实感觉这部分的知识点比较成体系,很连贯,需要总结的东西也不多)
4.存储器管理
-
高速缓存与寄存器的引入:CPU与外围设备交换的信息一般也依托于主存储器的地址空间,由于主存储器的访问速度远低于CPU执行指令的速度,为了缓和这一矛盾,在计算机系统中引入了寄存器和高速缓存。
- 寄存器:寄存器的访问速度最快,完全可以和CPU协调工作,但是非常昂贵,容量也比较小。
- 高速缓存:访问速度大于主存小于寄存器,容量大于寄存器,小于主存。
- 磁盘缓存:目前的磁盘IO速度远低于对主存的访问速度,因此将频繁使用的一部分磁盘数据和新消息,暂时存放在磁盘缓存中,可以减少访问磁盘的次数。
-
将一个用户源程序变为一个可以在内存中执行的程序:
- 首先要编译:又编译程序将用户源代码编译成若干个目标模块。
- 其次是链接:由链接程序将编译后形成的一组目标模块,以及它们所需要的库函数链接在一起,形成一个完整的装入模块。
- 最后是装入:由装入程序将装入模块装入内存。
-
将一个装入模块装入内存中时,由绝对装入,可重定位装入,动态装入方式。
- 绝对装入:在编译时,如果知道程序将驻留在内存的什么位置,那么,编译程序将产生绝对地址的目标代码。绝对装入程序按照装入模块中的地址,将程序和数据装入内存,装入模块被装入内存后,由于程序中的逻辑地址与实际内存地址完全相同,故不须对程序和数据的地址进行修改。(只适用于单道程序环境)
- 可重定位装入:在多道程序环境下,编译程序不可预知所编译的目标模块应该放在内存的何处,因此,绝对装入方式只适用于单道程序环境。在多道程序环境下,所得到的目标模块的起始地址通常由0开始,程序中的其他地址也都是相对于起始地址计算的。此时应该采用可重定位装入方式,根据内存的当前情况,将装入模块装入到内存中的适当位置。在可重定位装入方式中,装入模块中的逻辑地址与实际地址可能时不同的。(适合多道程序,但是程序运行时不能再内存中移动)
- 动态运行时装入:可重定位装入方式可将装入模块装入到内存中的任何位置,所以可以用于多道环境,但是这种方式不允许程序运行时再内存中移动。但是,实际情况时,再运行过程中的程序可能再内存中的位置可能会经常改变,此时就应该采取动态运行时装入方式。动态运行时装入程序再把装入模块装入内存后,并不立刻把装入模块中的相对地址转换为绝对地址,而是把这种地址转换推迟到程序真正要执行时才进行。因此,装入内存后的所有地址仍是相对地址。为了使地址转换不影响指令的执行速度,这种装入方式需要一个重定位寄存器的支持。
-
程序的链接:源程序经过编译后,可得到一组目标模块,再利用连接程序将这组目标模块链接,形成装入模块,根据链接时的不同,可分为三种:(这一部分教材就是放在装入后介绍的,不过我感觉按照顺序因该是先链接后装入啊.....)
- 静态链接:再程序装入之前,先将个目标模块按照它们所需要的库函数,链接称为一个完整的装入模块,以后不再拆开。我们把这种事先进行链接的方式称为静态链接。
- 装入时动态链接:这是指将用户源程序编译后多得到的一组目标模块,在装入内存时,采用边装入边链接的方式。
- 运行时动态链接:这是指对某些目标模块的链接,是在程序执行中需要该模块时,才对它进行的链接。
-
动态分区分配中的算法:首次适应算法,循环首次适应算法,最佳适应算法,最坏适应算法,快速适应算法。这三种方法属于连续分配的管理方式。
- 首次适应算法:要求空闲分区连的地址按照地址的次序链接,在分配内存时,从链首开始顺序查找,直到找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小,从该分区中划分出一块内存空间分配给请求者,余下的空闲分区仍留在空闲链中。该算法倾向于优先利用内存中低地址部分的空闲分区,从而保留了高地址部分的大空闲分区,这为给提后到达的大作业分配大的内存空间创造了条件。其缺点是低地址部分被不断地划分,会留下很多难以利用,很小地空闲分区,而每一次查找都是从低地址部分开始,这无疑会增加查找可用空闲分区时的开销。
- 循环首次适应算法:该算法从首次适应算法演变而来,再为进程分配内存空间时,不再是从链首部开始查找,而是从上一次找到空闲分区的下一个空闲分区开始查找(注意,是下一个)。直到能找到一个满足要求的空闲分区,从中画出一块请求大小相等的内存空间分配给作业。该算法能使内存中的空闲分区分布的更均匀,从而减少查找空闲分区时的开销,但是这样会缺乏大的空闲分区
- 最佳适应算法:指的是每一次为作业分配内存时,总能把满足要求,又是最小的空闲分区分配给作业,避免大材小用。孤立的看,最佳适应算法似乎是最佳的,但是宏观上来看却不一定,因为每一次分配后,所切割下来的剩余部分总是最小的,这样再存储器中总会留下许多很难利用的小空间。
- 最坏适应算法:和最佳适用算法相反,这个算法每一次都会找出一个最大的分区来分配给作业。这样的优点是剩余的空闲区不至于太小,产生碎片的几率反而是最低的。
- 快速适应算法(王道书中没有涉及):该算法又称为分类搜索法,是将空闲分区根据其容量大小进行分类,对于每一类具有相同容量的所有空闲分区,单独设立一个空闲分区链表,这样,系统中存在多个空闲分区链表,同时在内存中设立一张管理索引表,该表的每一个表项对应了一种空闲分区类型,并记录了该类型空闲分区链表表头的指针。该算法的优点是查找效率高,仅需要根据进程的长度,寻找到能容纳它的最小空闲区链表,并取下第一块进行分配即可。
-
内部碎片和外部碎片:我去,感觉王道书上说的也比较模糊(当然更可能是因为我理解能力太差)。这里按照我的理解说一下:
- 内部碎片:一般在固定分配内存中产生,比如说固定分配100kb的内存块,即使作业实际只用到了1kb的内存,但是也会给该作业分配100kb的内存块。这99kb剩下的空间虽然永远不用,但是不允许其他作业使用,这99kb的内存就是内部碎片。
- 外部碎片:一般在动态分配中产生,比如作业需要用到10kb的内存,系统就会分配正好10kb的内存。这时就完全没有内部碎片了,但是考虑这样的一个情况,现在又三个作业(都是动态分配内存),第一给分配1000kb,第二个分配10kb,第三个分配1000kb(假设内存空间是连续分配)。现在第二个作业运行很快,马上就释放了这10kb的内存,但是因为这一块内存实在是太小了,以后也可能很难利用到,这就形成了外部碎片。
-
基本分页存储管理方式:连续分配方式会形成许多的“碎片”,虽然可以通过“紧凑”方法 将许多碎片拼接成可用的大块空间,但须为之付出很大开销。如果允许将一个进程直接分散地装入到许多不相邻接的分区中,则无须再进行“紧凑”。基于这一思想而产生了离散分配方式。如果离散分配的基本单位是页,则称为分页存储管理方式;如果离散分配的基本单位是段,则称为分段存储管理方式。(这里可以看出,分页管理与刚才的连续管理的”地位”是相同的,都是用来管理为作业分配内存)
在分页存储管理方式中,如果不具备页面对换功能,则称为基本的分页存储管理方式,或称为纯分页存储管理方式,它不具有支持实现虚拟存储器的功能,它要求把每个作业全部装入内存后方能运行。
-
页面和物理块:分页存储管理是将一个进程的逻辑地址空间分为若干个大小相等的片,称为页面或者页,相应的,也把内存空间分分成与页面相同的若干个存储块,称为(物理)块或者页框。由于进程的最后一页经常装不满而形成了不可利用的碎片,称之为“页面碎片”(其实就是刚才说的内部碎片)。
-
分页地址中的地址结构:由两部分组成,分别是页号和偏移量
-
页表:在分页系统中,允许将进程的各页离散的存储在内存中的不同物理块中,但是系统能保证进程正确的运行,即能在内存中找到每个页面所对应的物理块。为此,系统又为每个进程建立了一张页面映像表,简称页表。进程在地址空间中的所有页,依次在页表中有一个页表项。其中记录了相应页在内存中对应的物理块号。可见,页表的作用是实现先从页号到物理块号的地址映射。
-
快表:由于页表使存放在内存中的(书上说通常都是在内存中),这使得CPU在每一次额存取一个数据时,都需要访问两次内存。(第一次访问页表,拼接出来实际地址,第二次通过实际地址来读取数据)这使得计算机处理速度降低近1/2,是得不偿失的。为了提高地址变换速度,引入”快表”。快表是一个有并行查询能力的特殊高速缓冲寄存器。用来存放当前访问的那些页表项(注意,是页表项)。引入快表后,进行地址变换时,首先会访问快表,如果快表有该地址所对应的页表项,就直接拼接地址,没有的话就再访问页表,拼接地址(注意,也有的题目是同时访问页表和快表,这个看具体情况而定),同时再把这个页表项存在页表中。(这里描述的貌似和Cache有点像,但是注意这两个本质上可是不同的,快表是为了加速拼接地址,避免在拼接地址时频繁访存,里面存放的是页号和物理地址的映射关系。Cache里面存放的是一整块数据,为了是在访问数据是避免频繁访存。)
-
两级页表和多级页表:主要是为了解决单个页表过大的问题。现在来说明一下多级页表是怎么节省空间的。现在有逻辑为32位,其中页面偏移量是后12位。
- 在单页表的地址结构中,前20位是页号,每一个进程的页表的页表项有2^20个,在运行该进程时,这个包含着2^20个页表项的超级大页表就会放在内存中,非常占用空间。
- 现在使用二级页表地址结构,逻辑地址的前10位为一级页号,中间10位为二级页号,现在的页表变为:现在又一个一级页表,其中又2^10个“页表项”,记录着每一个一级地址引出的二级页表的地址。而每一个一级页表引出的而二级页表的页表项也有2^10个,其中就记录着拼接出来的页号对应的物理地址。现在运行该进程时,只有在需要时才会将部分页表调入内存,其他的页表还在外存上。(需要调入一个一级页表,在根据需要调入需要的二级页表,这样总共只有2^10+2^10个页表项,比2^20个页表项少了很多)
-
基本分段存储管理方式:为了满足用户和程序员的一系列需求:
- 方便编程:通常,用户把自己的作业按照逻辑划分成若干个段,每一个段都是从0开始编址,并且有自己的名字和长度。因此,希望要访问的逻辑及地址是由段名和段内偏移量决定的。
- 信息共享:实现对程序和数据的共享时,式以信息的逻辑单位为基础的,比如某个例程和函数,分页系统中的也只是存放信息的物理块,没有完整的意义,不利于实现共享。而段是信息的逻辑单位。
- 信息保护:信息保护同样是对信息的逻辑单位进行保护,因此,分段管理方式能有效和方便的实现信息保护。
- 动态增长:在实际应用中,往往有些段,特别是数据段,在使用中会不断地增长,而事先不能直到数据段会增长到多大,前面的存储方式,很难应付这种动态增长的情况。
- 动态链接:动态链接是指在作业运行之前,并不把几个目标程序链接起来,要运行时,陷阱主程序所对应的目标程序装入内存并启动运行,只有当运行过程中需要调用到某些段时,才将该段调入内存并进行链接。可见,动态链接也要求以段作为管理的单位。
-
分段地址的形式:段号+段内地址。 段表:和页表类似,里面记录了从段号到实际物理地址的映射关系,除此以外,还记录了段的长度(因为段的大小都是可能不同的)。
-
段页式存储器:分页系统能有效的提高内存的利用率,分段系统能更好的满足用户的需求,为了结合两种管理方式的优点,引出段页式存储器。段页式系统是分段与分页的相结合,先将用户程序分成若干个段,在把若干个段分成若干个页,并且为每一个段赋予一个段名。简单的说就是先把程序进行分段,而每个段的内部再分页(个人理解:页的大小都是相同的,所以显然段的大小都是页的大小的整数倍,普通的分段存储堆对于段的大小没有特别的要求,所以可能会造成管理的困难,现在的段的大小有了一定的要求,但是)。
-
段页式地址结构:段号+段内页号+页内地址。在段页式存储器中,为了获得一个数据需要访存三次,第一次访问段表,获得页表的地址,第二次访问对应的页表,拼接出来物理地址,第三次才能访问数据。
-
虚拟存储器:前面的各存储器的管理方式有一个共同的特点,就是它们都要求一个作业全部装入内存后才能运行,于是,就出现了下面两种情况:
- 作业很大,已经超过了内存空间中的总容量。作业不能全部装进内存,使该作业无法运行。
- 有大量的作业要运行,但是因为内存的容量不足以容纳所有的作业,只能将少数的作业装入内存让他们先运行,而将其他大量的作业留在外存上等待。
-
常规存储器管理方式的特种:
- 一次性:就是运行作业必须要一次性对的把作业的全部都装入内存。
- 驻留行:作业装入后,便一直的驻留再内存中,直到作业结束。即使是某些进程会因为IO进行长时间的等待,即使是某些模块运行一次后就再也不会被用到。
-
局部性原理:
- 时间局部性:如果某条指令一旦被执行,则不久之后该指令还有可能再次被执行。如果某数据被访问过,则不久后该数据可能被再次访问过。产生时间局部性的典型原因是因为由于程序中有大量的循环操作。
- 空间局部性:一旦程序的某一个存储单元被访问过,在不久后,其附近的存储单元也将再次被访问。在一段时间内所访问的地址,可能集中在一定范围内,其典型情况就是程序的顺序执行。
-
虚拟存储器的实现方法:在虚拟存储器中,允许将一个作业分多次调入内存。
-
分页请求系统:
- 分页请求系统(我去,我记得怎么是请求分页系统? 难道是PDF错了?啊这…不过也都一样):这时在分页系统的基础上,增加了请求调页面和页面置换功能所形成的页式虚拟存储系统,它允许只装入少数页面的程序,便启动运行。以后,再通过调页功能以及页面置换功能,陆续地将把即将要运行地页面调入内存,同时把暂时不运行地内存再调出内存到外存上,置换时以页面为单位。
硬件支持:请求分页的页表机制,缺页中断机构,地址变换机构。
- 分页请求系统(我去,我记得怎么是请求分页系统? 难道是PDF错了?啊这…不过也都一样):这时在分页系统的基础上,增加了请求调页面和页面置换功能所形成的页式虚拟存储系统,它允许只装入少数页面的程序,便启动运行。以后,再通过调页功能以及页面置换功能,陆续地将把即将要运行地页面调入内存,同时把暂时不运行地内存再调出内存到外存上,置换时以页面为单位。
-
分段请求系统:
- 请求分段系统:这是再分段系统的基础上,增加了请求分段以及分段置换功能后所形成的段式虚拟存储系统。它允许只装入少数段的用户和程序,便可以启动。(听起来和分页貌似差不多)。以后在通过调段功能和段的置换功能将暂时不能运行的段调出,同时调入即将运行的段。段的置换是以段为单位进行的。
硬件支持:请求分段的段表机制,缺段中断机构,地址变换结构(听起来貌似和上面也差不多)
- 请求分段系统:这是再分段系统的基础上,增加了请求分段以及分段置换功能后所形成的段式虚拟存储系统。它允许只装入少数段的用户和程序,便可以启动。(听起来和分页貌似差不多)。以后在通过调段功能和段的置换功能将暂时不能运行的段调出,同时调入即将运行的段。段的置换是以段为单位进行的。
-
虚拟存储器的特征:
- 多次性:多次性是指一个作业被分成多次调入内存运行,亦即在作业运行时没有必要将其全部装入,只需将当前要运行的那部分程序和数据装入内存即可;以后每当要运行到尚未调入的那部分程序时,再将它调入。多次性是虚拟存储器最重要的特征,任何其它的存储管理方式都不具有这一特征。因此,我们也可以认为虚拟存储器是具有多次性特征的存储器系统。
- 对换性:对换性是指允许在作业的运行过程中进行换进、换出,亦即,在进程运行期间,允许将那些暂不使用的程序和数据,从内存调至外存的对换区(换出),待以后需要时再将它们从外存调至内存(换进);甚至还允许将暂时不运行的进程调至外存,待它们重又具备运行条件时再调入内存。换进和换出能有效地提高内存利用率。可见,虚拟存储器具有对换性特征。
- 虚拟性:虚拟性是指能够从逻辑上扩充内存容量,使用户所看到的内存容量远大于实际内存容量。这是虚拟存储器所表现出来的最重要的特征,也是实现虚拟存储器的最重要的目标。值得说明的是,虚拟性是以多次性和对换性为基础的,或者说,仅当系统允许将作业分多次调入内存,并能将内存中暂时不运行的程序和数据换至盘上时,才有可能实现虚拟存储器;而多次性和对换性又必须建立在离散分配的基础上。
-
请求分页中的页表机制:
- 在请求分页系统中所需要的主要数据结构是页表,其基本作用仍然是将用户空间中的逻辑地址变成内存中的物理地址。但是还要再加入若干项,供程序在换进,换出时参考。在请求分页系统中的每个页表项如下所示:
- 页号-物理块号-状态位P-访问字段A-修改位M-外存地址
- 状态位P:用于指示该页是否已经调入内存,供程序访问时参考。
- 访问字段A:用来记录本页在一段时间内被访问的次数,或者记录本页最近已经有多长时间未被访问,供选择换出页面时参考。
- 修改为M:表示该字段调入内存后有没有被修改过。
- 外存地址:用于指出该页在外存上的地址,通常是物理块号,供调入该页时参考。
-
缺页中断:在请求分页系统时,每当所要访问的页面不再内存时,便会产生缺页中断,请求OS将所缺的页调入内存。它和一般的中断相比,有明显的区别:
- 在指令执行期间产生和处理的中断信号,通常,CPU都是在一条指令执行完后,才检查是否有中断请求到达。若有,便去响应,否则就继续执行下一条指令。然而,缺页中断时在指令执行期间,发现索要访问的指令或数据不在内存时产生和处理的。
- 一条指令在执行期间,可能会产生多次缺页中断(比如,某一条指令需要处理的数据横跨好几个页面)。
-
物理块的分配策略:
- 固定分配局部置换:为整个进程分配一定数目的物理块,在整个运行期间不再改变。在该策略中,如果进程在运行中发生了缺页,则只能从该进程的n个页面中选择一个页面换出,然后再调入一页,保证分配给该进程的内存空间不变。(按我的理解,这里的固定值得就是物理块的固定,局部置换指的是置换物理块上的数据,而不是置换物理块)
- 可变分配全局置换:先为该进程分配一定数目的物理块,而OS自己也有一个空闲物理块的队列。当某进程发现缺页时,系统会从空闲队列中调出一个空闲物理块给进程,然后把缺的页放入这个新的物理块。只要发生缺页就重复这个过程,直到空闲队列中的物理块用完,再从内存中选择一个页调出。(按照我的理解,这里的可变指的是物理块数目的可变,全局置换指的是一旦缺页,直接加物理块,不再是先把旧的页面调出,再把新的页面调入)
- 可变分配局部置换:首先为进程分配一定数目的物理块,当进程发生缺页时,只允许进程从内存中的页面中换出一页,这样不会影响其他的进程。只有当频繁发生缺页时,才为该进程分配新的物理块。如果这个进程的缺页率特别低,还会收回这个进程的部分物理块。(按照我的理解,这里的可变指的是物理块数目的可变,局部置换指的还是置换物理块上的数据。)
-
页面置换策略:
- 先进先出算法(FIFO):顾名思义,换出最早进入的页面。会产生贝拉迪异常。就是分配的物理块增加,反而缺页率变高了。
- 最近最久未被使用(LRU)算法:换出最久没有被使用过的页面。
- 最少使用置换算法:换出最近时期使用次数最少的页面。
- 简单clock置换算法
- 改进clock置换算法
-
简单/改进clock置换算法:这个算法的描述在教材和王道上面都有,描述起来还是比较复杂的。这里按照我对书上的描述以及我的理解写出一个代码的描述:
//简单clock算法
struct node{
Data//页面中的数据
bool flag;//访问位。如果被访问过,就置为1,如果没有被访问过,就置为0
};
const int maxn=10;//指的是为某个进程固定分配某个数量的物理块
node page[maxn];
void change_algorithm_1(){//简单置换算法
//这个算法一共需要循环的检测两次
for(int i=0;i<maxn;i++){
if(page[i].flag==0){
change(page[i]);//将此页面换出,算法结束
return;
}else{
page[i].flag=0;//否则,将该页的访问位置为0
}
}
for(int i=0;i<maxn;i++){//这一次必有一个页面被换出
if(change==0){
changr(page[i]);
return;
}
}
}
//改进clock算法
struct node{
Data//数据部分
bool A;//访问标志
bool M;//修改标志
};
const int maxn=10;
node page[maxn];
void change_page_algorithm2(){
while(true){//注意,这可不是死循环,这个循环最多执行两次
for(int i=0;i<maxn;i++){
if(page[i].A==0&&page[i].M==0){
change(page[i]);
return ;
}
}
for(int i=0;i<maxn;i++){
if(page[i].A==0&&page[i].M==1){
change(page[i]);
return ;
}else{
page[i].A=0;
}
}
}
}
//还有一个小细节,整个算法的执行过程中,不会改变M(修改标志)的值
-
抖动(教材中貌似没有涉及):在页面置换过程中,一种最糟糕的情况是,刚刚换出的页面马上又要换入主存,刚刚换入的页面马上要放出主存。这种频发的页面调度称为抖动,或者叫颠簸。主要原因是进程频繁访问的页面数多于可用的物理块数。
-
工作集与驻留集(教材上貌似也没有涉及):工作集就是指在某一个时间间隔内,进程要访问的页面集合。驻留集就是系统分配给进程的物理块数。
5 文件管理(这一个章节主要参考了天勤操作系统中的描述)
-
文件的逻辑结构:文件的逻辑结构是从用户观点来看所观察到的文件的组织形式。是用户可以直接处理的数据及其结构。
- 顺序文件:顺序文件又称为连续结构,是最简单的文件结构,其将一个逻辑文件的信息连续存放,以顺序结构存放的文件称为顺序文件或者连续文件。顺序文件的主要优点是顺序存取时速度较快,如果文件时定长记录文件,还可以根据文件的起始地址以及记录的长度随机访问。但是因为文件存储要求连续的存储空间,所以会产生碎片,同时页不利于文件的动态扩充。
- 索引文件:索引结构为一个逻辑文件的信息建立一个索引表,索引表中的表目存放文件记录的长度和所在逻辑文件的起始位置,因此逻辑文件中不再记录的长度信息,索引表本身是一个定长文件,每个逻辑块是可以变长的。索引表和逻辑文件两者构成了索引文件。索引文件的优点是可以随机访问,也利于文件的增删。但是索引表的使用增加了存储空间的开销,另外,索引表的查找策略对文件系统的效率影响很大。
- 索引顺序文件:索引顺序文件是顺序文件和索引文件的结合,索引顺序文件将顺序文件中的所有记录分为若干个组,为顺序文件建立一张索引表,并且为每一组中的第一个(注意,是第一个,不是所有)记录在索引表中建立一个索引项,其中含有该记录的关键字和指向该记录的指针。索引表中包含关键字指针和指针两个数据项,索引表中的索引项按照关键字顺序排列,索引顺序文件的逻辑文件是一个顺序文件,每个分组内部的关键字不必有序排列,但是组与组之间的关键字是有序排列的。
- 直接文件和散列(hash)文件:建立文件的关键字和对应的物理记录之间的关系,也就是说关键字决定其物理地址。这种结构称为直接文件,没有顺序特性。散列文件是一种典型的直接文件,通过散列函数对关键字进行转换,转换的结构直接决定记录的物理位置。散列文件有很高的存取速度,但是因为不同的关键字可能对应相同的散列函数值而引起冲突。
-
文件控制块(FCB):从文件管理的角度来看,文件由文件控制块和文件体两部分组成,文件体就是文件的本身,文件控制块是保存文件属性信息的数据结构。它包含的信息因为操作系统而差异,但是至少包含以下的信息:
- 文件名:该信息用于表示一个文件的符号,每一个文件都具有一个唯一的名字,这样用户可以按照文件名对文件进行操作。
- 文件的结构:该信息说明文件的逻辑结构是记录式文件还是流式文件,若为记录式文件还需要进一步说明记录是否定长,记录长度和个数,说明文件的物理结构是顺序文件还,索引文件,还是顺序索引文件。
- 文件的物理位置:该信息用来指示文件在外存上的存储位置,包括存文件的设备名,文件在外存的存储地址以及文件的长度等
- 存取控制信息:该信息用于只是文件的存取权限,包括文件的拥有者的存取权限以及文件主同组用户的权限和其他一般用户的权限。
- 管理讯息:该信息包括文件的建立日期以及时间,上次存取文件的日期和当前文件的使用状态的信息。
-
索引节点:在检索目录文件的过程中,只用到了文件名,仅当找到了匹配的目录项时,才需要从该目录项中读取出该文件的物理地址。也就是说,在检索目录时,文件的其他描述信息时不会被用到的,因而也不需要调入内存。因此,有些系统采用了文件名与描述信息分开的方法,将文件的描述信息单独形成一个索引节点,简称i节点。文件目录中的每一个目录项仅由文件名和指向给该文件i节点的指针构成。存放在磁盘上的索引节点称为磁盘索引节点,每一个文件都由唯一一个磁盘索引节点,其中主要包括以下内容:
- 文件主标识符:拥有该文件的个人或小组的标识符。
- 文件类型:包括普通文件,目录文件或者特别文件
- 文件的存取权限:各类用户对该文件的存取权限
- 文件的物理地址:每个索引节点间接或者直接的方式给出数据文件所在的盘块的编号。
- 文件长度:以字节为单位的文件长度。
- 文件链接计数:表明在本文件系统中所有指向该文件的文件名的指针数。
- 文件存取时间:本文件醉最近被存取的时间,最近被修改的时间以及索引节最近被修改的时间。
-
当文件比打开时,磁盘索引节点被复制到内存索引节点中,以便使用。存放在内存中的索引节点被称为内存索引节点,其增加了以下的内容
- 索引节点编号:用于标识内存索引节点。
- 状态:指示i是否上锁或者被修改。
- 访问技术:正在访问文件的进程数。
- 逻辑设备号:文件所属文件系统的逻辑设备号
- 链接指针:设置分贝指向空闲链表和散列队列的指针。
-
基于索引节点的共享方式(硬链接):索引节点把FCB中的文件描述信息单独构成一个数据结构,也就是说,物理块的信息在索引节点中。此时,目录项中只有文件名和指向文件索引节点的指针。两个不同的目录项只需要指向相同的索引节点就可以实现共享。在索引节点中再增加一个计数值来统计指向该节点的目录项的个数,这样一来就需要再删除该文件时可以先判断计数值,只有在计数值为1时才能删除该节点。这种方法可以实现文件的异名共享,但是当多个用户共享时,文件的拥有者不能删除该文件。
-
利用符号链接实现的文件共享(软连接):该方法是创建一个称为链接的新目录项,例如,为了使用户b能共享用户c的一个文件,可以由此系统为用户b建立一个指向该文件的新目录项,并放在用户b的目录下。新的目录下个中包含了被共享文件的路径名,可以使绝对路径也可以是相对路径。
- 在利用符号链接方式实现文件共享时,只有文件的拥有者才拥有指向其索引节点的指针。而文件对的共享者和其他用户只有该文的路径名,并不拥有指向其索引节点的指针。这样就不会发生文件拥有者删除共享文件后留下悬空指针的情况。当文件的拥有者把一个共享文件删除后,其他用户试图通过符号链接去访问一个已经被删除的文件时,系统就会因为找不到该文件而访问失败,于是再将符号删除。
- 符号链接方式有一个很大的优点,就是它能够用于链接(通过计算机网络)世界上任何计算机中的文件,此时只需呀提供该文所在机器的网络地址以及文件在该机器中的路径即可。
- 该方法解决了基于索引节点共享方式中文件的拥有者不能删除共享文件的问题,但是其他用户在访问共享的文件式,要逐层查找目录,开销较大。
-
文件保护:
- 访问类型:对文件的保护可以从限制文件的访问类型出发,可以加以控制的访问类型有读,写,执行,添加,列表清单等。此外,还可以对文件的重命名,复制,编辑等加以控制。
- 访问控制:访问控制就是对不同的用户访问同一个文件采取不同的访问类型。根据用户的权限不同,可以把用户分为拥有者,工作组用户,其他用户等。然后对不同的用户组采取不同的访问类型,以防止文件被非法访问。
-
目录的实现:
- 线性表:最为简单的目录实现方法就是使用存储文件名和数据块的线性表。创建新文件时,必须首先搜索目录表以确定没有同名的文件的存在,接着在目录表后增加一个目录项,若是要删除文件,根据给定的文件名搜索目录表,接着释放分配给它的空间,采用链表结构可以减少删除文件的时间,其优点在于实现简单,但是线性表需要采用顺序查找的方法来查找特定的目录项,所以运行比较耗时。
- 散列表:散列表时根据文件名得到一个值,并返回一个指向线性表中元素的指针。这种方法可以大大缩短查找的时间,插入和删除也比较简单,但是要采取一些措施来防止冲突。
-
文件的实现:文件的实现主要是指文件在存储器上的实现,即为文件的物理结构的实现,包括外存的分配方式和文件的存储空间。
-
外存的分配方式-连续分配(注意,这里是物理结构,分配方法和上面说过的逻辑结构不同):连续分配是最简单的磁盘空间分配策略。该方法要求为文件分配连续的磁盘区域,在这种分配算法中,用户必须在分配之前说明待创建文件所需要的存储空间的大小,然后系统查找空闲区的管理表格,查看是否有足够大的空心区供用户使用。如果有,就给文件分配所需要的空间,如果没有。该文件就不能建立,用户进程必须等待。
- 采用连续分配方式时,可以把逻辑文件中的记录 顺序地存储到相邻地物理盘块中,这样所形成地文件结构称为顺序文件结构,此时地物理文件称为顺序文件,这种分配方式保证了逻辑文件中地记录顺序于存储器中地文件占用盘块地顺序一致。
- 连续分配地优点时查找速度比其他方法块(只需要起始盘块号和文件大小)目录中关于文件的物理存储信息也比较简单,但是缺点时容易产生碎片。这种分配方式不适用于文件随时间动态增长和减少的情况。也不适合适合实现不知道文件大小的情况。
-
外存的分配方式-链式分配:对于文件的长度需要动态增长以及用户实现不知到文件的大小的情况,往往采用链式分配。
- 隐式分配:该实现方式用于链接物理的指针隐式的放在每一个物理块中,目录项中有指向索引文件中的第一块和最后一块的指针。此外每个盘块中都有含有指向下一盘块的指针。若是要房屋内某一个盘块,需要从第一个盘块开始一个个盘块都读出指针来(书上就是这么写的,貌似有点不通顺,差不多就是和链表的查找类似)。所以存在随机访问效率低的问题。由于其中任何一个盘块的指针错位都会导致后面的盘块位置丢失,因此这种实现方法的可靠性不高。
- 显示连接:该种方案用于链接物理块的指针显示的放在一张连接表中,每一个磁盘都设置一个连接表。(注意,这个时链接表,存储的是每一个指针指向的信息,可不是索引表)这个表称为文件分配表(FAT)。由于还是链接方式,因此在FAT中找到一个记录的物理块还是要一个一个找,不能随机查找。但是和隐式链接相比,该方案是在内存中查找而不是在硬盘中查找,所以速度快了不少
-
索引分配方式:链式分配存在一些问题,首先就是是随机读取时太慢,而且指针也占用了一定的磁盘空间。
- 在索引分配方式中,系统为每一个文件都分配了一个索引块,索引块中存放者索引表。索引表中的每一个表项对应着分配给文件的一个物理块。索引表不仅支持直接访问,也不会产生外部碎片,文件长度的限制问题也能得到了解决。缺点就是由于索引块的分配,增加了系统存储空间的开销。另外,存取文件需要两次访问外存,第一次时读出索引块中的内容,第二次时访问具体的磁盘块。为了更有效的使用索引表,避免两次访问外存,可以在访问文件时先将索引表调入内存中,这样就只用访问一次外存就可以了。
- 单极索引分配:单极索引分配方法就是将每一个文件对应的盘块号集中放在一起,为每一个文件分配一个索引块,在把分配给该文件的所有盘块号都放在该索引块中。因此,该索引块就是一个包含着多个盘块号的数组。
- 两级索引分配:当文件较大时,一个索引块不能放下所有的文件,可以对索引块在建立索引。这样成立二级索引。
- 混合索引分配:就是把两种索引方式放在一起,索引表上既有直接地址,又有二级索引表的地址,甚至还有更多级索引表的地址。
-
文件的存储空间管理:
- 空闲文件表法:如图所示
序号 第一个空闲块号 空闲块数目 物理块号 1 5 3 (5,6,7) 2 13 5 (13,14,15,16,17) 3 20 6 (20,21,22,23,24,25) 4 … … … - 空闲块链表法:空闲块链表法是将文件存储设备上的所有空闲块都链接在一起,形成一条空闲块链,并设置一个头指针指向空闲链块的第一个物理块。当用户建立文件时,就需要从链收其次取下几个空闲块分配给文件,当撤销文件时,回收其存储空间,并将回收的空闲块一次链入空闲块链表中。
-位图法:位图法就是建立一张位示图(尽管式称其为图,但是实际上是一串二进制位)以反映整个存储空间的分配情况。其中,每一个二进制位都对应着一个物理块,若某位为1,表示物理块已被分配,若某一位为0,表示物理块空闲。
-
组成链接法(UNIX的文件存储空间的管理方法):
- 成组链接方法适用于大型文件系统,该方法将一个文件所有的空闲块按照每组100块分成若干个分组,每一个组的盘块数目和改组的所有盘块号记入到前一个组的第一个盘块中,第一组的盘块数目和第一组的所有盘块号记录到超级块中。这样每一个组的第一个盘块就链接成了一个链表。而组内的多个盘块形成了堆栈,每一组的第一块是存放下一组的块号的堆栈,堆栈是临界资源,每一次只允许一个进程访问。所以系统设置了一把锁来对其互斥访问。
- 分配空闲块的方法:当系统要为文件分配空闲块是,先查找第一组的盘块数,如果不止一块,就将超级快中的空闲磁盘块减1,将栈顶的盘块分配出去,若第一组只剩下一块(就是存放下一组的盘块数和盘块号的那个块,不是空闲块)且栈顶的盘块号不是结束标记0(说明这一组不是最后一组),则先将该块的内容读到超级快中(下一组成了第一组,所以下一组的盘块数和盘块号要读入超级块),然后再将该块分配出去(该块中的信息已经不再有用,这一块成了一个空闲块)。
- 空闲块的回收方法,当系统回收空闲块时,若第一组不满100块,则只要再超级块的空闲盘块的栈顶放入该空闲盘块号,并将其中的空闲盘块数加1即可。若第一组已经有100块了,则先把第一组中的盘块数和空闲盘块号写入该空闲盘块中,然后将”盘块数=1”和”栈顶块还=该空闲盘块号”写入超级块中(该空闲盘块成了新的一组,原本的第一组成了第二组)。
-
磁盘结构的中的信息(我去,这个还真的在大题中考过):
- 引导控制块:通常为分区的第一块,若该分区没有操作系统,则为空。
- 分区控制块:其中包括分区的详情信息,如分区的块数,块的大小,空闲块的数目和指针等。
- 目录结构:采用目录文件组织。
- 文件控制块:其中包含文件的信息,如文件名,拥有者,文件大小和数据块位置等。
-
磁盘的访问时间T:访问时间=寻道时间+旋转时间+传输时间
- 寻道时间:指的是磁盘收到读取指令后,磁头从当前位置移动道目标磁道的位置所需要的时间
- 旋转延迟:一般来说平均旋转时间就是旋转半周所用的时间。
- 传输时间:取决于每次读写的字节数和磁盘的转速。
-
磁盘的调度算法:磁盘是可以被多个进程共享的设备。当有多个进程都要访问磁盘时,用采用一种合适的调度算法。以使得各种进程对磁盘的平均访问时间最短。
- 先来先服务算法FCFS:顾名思义,按照进程到来的先后顺序服务。
- 最短寻道时间优先算法SSTF:优先为距离当前磁头最近的进程服务。该算法的寻道性能比FCFS好,但是肯能会导致某些进程饥饿。但是不能保证平均寻道时间最短。
- 扫描算法SCAN或者电梯调度算法:优先为当前磁头移动方向上举例磁头最近的进程服务。(其实就是从左往右扫描,再从右向左扫描,碰见一个进程就服务一个进程)
- 循环扫描C—SCAN:就是单向的扫描算法。
调度算法 为了解决什么问题引入 优点 缺点 FCFS 公平,简单 未对寻道进行优化,所以平均寻道时间较长,仅适合磁盘请求较少的场合 SSTF 为了解决FCFS的平均寻道时间太长的问题 比FCFS减少了平均寻道时间,有更好的寻道性能 并非最优,而且会导致“饥饿” SCAN 为了解决SSTF算法饥饿现象 兼顾较好的寻道性能和防止饥饿现象广泛用于大中小型计算机和网络中 存在请求刚好被错过而需要等待很久的现象 C-SCAN 解决请求待时间过长的现象 兼顾较好的寻道性能和防止饥饿现象,同时解决了一个请求等待时间过长的问题 可能出现磁臂长期停留再某处而不动的现象 -
磁盘管理(2021年408大题…好吧,当时我脑子里一片空白,果断二战(′▽`〃)):
- 磁盘的格式化:一个新的磁盘只是一个含有磁性记录材料的空白盘,再磁盘能存储数据之前,它必须要分成扇区以便磁盘控制器能够进行读写操作。这个过程称为低级格式化。
- 低级格式化未磁盘的每个扇区采取了独特的数据结构,每个扇区通常由头部,数据区域和尾部组成。头部和尾部包含了一些磁盘控制器所使用的信息。
- 为了使磁盘存储文件,操作系统还需要将自己的数据结构记录磁盘上。将磁盘分为由一个或者多个柱面组成分区(就是常见的C盘和D盘等分区)
- 对物理分区进行逻辑格式化(创建文件系统),操作系统将初始的文件系统数据结构存储道磁盘上,这些数据结构包括空闲和已分配的空间以及一个初始为空的目。
- 引导块:计算机启动时需要一个初始化程序(自举系统),它初始化CPU,寄存器,设备控制器和内存等,接着启动操作系统。为此,该自举程序应找到磁盘上的操作系统内核,装入内存,并转到初始地址,从而开始操作系统的运行。
- 自举程序通常存储在ROM中为了避免自举代码需要改变ROM硬件的问题,只在ROM中保留很小的自举装入程序,而将完整的自举程序保存在磁盘的启动块上。启动块位于磁盘的固定位置,拥有启动分区的磁盘称为启动磁盘或者系统磁盘。
6 IO管理
-
按照信息交换的单位,可以将IO系统分为两类,第一类是块设备,这类设备用于存储信息,由于信息的存取总是以数据块为单位,因此得名。典型代表是磁盘。第二类为字符设备,用于数据的输入和输出,其基本单位是字符,故称为字符设备。代表由打印机,交互终端等。
-
按照设备共享的属性分类:
- 独占设备:指的是在一段时间内只允许一个用户(进程)访问的设备,即临界资源。因而,对于多个并发进程而言,应该互斥的访问这类设备。系统一旦把这类设备分配给某个进程后,便由该进程独占,直到用完释放。独占性设备有可能会引起进程的死锁。(比如打印机)
- 共享设备:这是指一段时间内允许多个进程同时访问的设备。当然,对于每一时刻而言,该类设备仍只允许一个进程访问。显然,共享设备必须是可寻址的和可随机访问的设备,典型代表是盘。共享设备不仅可获得良好的设备利用率。而且也是实现文件系统和数据库系统的物质基础。
- 虚拟设备,这是通过虚拟技术将一台独占设备变为若干台逻辑设备,供若干个用户同时使用
-
三类总线:
- 数据信号线:这类信号线用于在设备和设备控制器之间传信号。
- 控制信号线:这是作为由设备控制器向IO设备发送控制信号时的通路
- 状态信号线:这类信号线用于传送指示设备当前状态的信号。
-
设备控制器是计算机中的一个实体(这个貌似考研没有涉及),其主要职责是控制一个或者多个IO设备,以实现IO设备和计算机之间的数据交换,他是CPU和IO设备之间的接口,它接收从CPU发出来的命令,并且控制IO设备工作,以使处理机从繁杂的设备控制事务中解脱出来。设备控制器是一个可编址的设备,当它仅控制一个设备时,它只有一个唯一的设备地址;若控制器可连接多个设备时,则应含有多个设备地址,并使每一个设备地址对应一个设备。设备控制器的基本功能:接收和识别命令,数据交换,标识和报告设备状态,地址识别,数据缓冲,差错控制。
-
IO通道设备的引入(这个貌似考研也没有涉及):虽然在CPU和IO设备之间加入了设备控制器后,已经大大的减少了CPU对IO的干预,但是当主机所配置的外设很多是,CPU的负担仍然很重,为此,在CPU和设备控制器之间又增设了通道。其主要目的是为了建立独立的IO操作,不仅使得数据的传送能够独立于CPU,而且也希望有关对IO操作的组织,管理异界结束处理尽量独立,以保证CPU有更多的时间来进行数据处理。或者说,其目的是使一些由CPU处理的IO任务由通道来承担,从而把CPU从繁杂的IO任务中解脱出来。在设置了通道后,CPU只要向通道发送一条IO指令,通道在收到IO指令后,便从内存中去除本次需要执行的通道程序,然后执行该通道程序,仅当通道完成了规定的IO任务后,才向CPU发送中断信号。
实际上,IO通道是一种特殊的处理机,它具有执行IO指令的能力,并通过执行通道IO程序来控制IO操作,但是IO通道又于一般对的处理机不同,主要表现在以下两个仿麦呢:一是指令的类型单一,二是通道没有自己的内存,通道所执行的通道程序是放在主机的内存中的。
-
IO控制方式1-程序直接控制方式:在早期的计算机系统中,因为没有中断系统,所以CPU和IO设备进行通信,数据传输时,由于CPU的速度远远块于IO设备,因此CPU需要不断的测试IO设备。这种方式又称为轮询或者忙等。
- 当数据输入时,由处理器向设备控制器发出一条IO指令启动设备进行输入,在设备的输入期间,处理器通过循环执行测试指令不断的检测设备状态寄存器的值,当状态寄存器的值显示设备输入完成时,处理器将数据寄存器中的数据取出并送入内存的指定单元,然后再启动设备去读下一条数据。当用户进程需要向设备输出数据时,也必须同样发出启动命令启动设备输出并等待输出完成操作。
- 优点:程序直接控制方式的工作过程非常简单。
- 缺点:CPU的利用率非常低。因为IO设备速度太慢,跟不上CPU,使得CPU在绝大部分时间都要测试IO设备是否已经完成数据的传输。
-
IO控制方式2-中断控制方式:为了减少程序直接控制方式中的CPU等待时间,提高CPU于设备的并行工作程度,现代计算机系统中广泛采用了中断的控制方式来对IO设备进行控制。
- 当用户进程需要输入数据时,由CPU向设备控制器发出指令启动外设输入数据,在输入数据的同时,CPU可以做其他工作,当输入完成时,设备控制器向CPU发出一个中断信号,CPU收到信号以后,转去执行设备中断处理程序。设备中断处理程序向输入设备的寄存器中的数据传送道某一个特定的内存单元中,供要求输入的进程使用,然后再启动设备去读取下一个数据。
- 优点:与程序直接控制相比,有了中断的硬件支持后,CPU和IO设备之间可以并行工作,CPU只需要再收到中断信号后处理即可,大大提高了CPU的利用率。
- 缺点:这种控制方式仍然存在着一些问题,比如每一台设备输入,输出一个数据,都要中断CPU,中断CPU的次数太多,也会大量消耗CPU的时间。
-
中断程序处理过程(仅指IO完成时发出的中断):
- 唤醒被阻塞的驱动(程序)进程:可用signal操作或者发送信号来唤醒被阻塞的驱动程序。
- 保护被中断进程的CPU环境:将处理器状态字PSW和程序计数器PC压入栈中加以保护,其他需要被压入栈中保护的还有CPU的寄存器等,这些都由应将完成。
- 转入想要的设备处理程序:测试中断源以确定引起中断的设备号
- 中断处理:针对该设备调用相应的中断处理程序。
- 恢复被中断进程的现场,把当时压入栈保护的寄存器等数据弹出,回复当时的CPU执行的上下文。
注意,这里所说的中断仅指由输入,输出引起的中断。
-
IO控制方式3-DMA控制方式:DMA控制方式的基本思想时外设和内存之间开辟直接的数据交换通路。在DMA控制方式中,设备控制器有更强大的功能,在其控制下,设备和内存之间可以成批的交换数据,而不用CPU的干预,这样大大减轻了CPU的负担,这种交换方式一般用于块设备的数据传送。
- 以数据的输入为列,当用户进程需要数据时,CPU将准备存放输入数据的内存的起始地址以及要传输的字节数分别送入DMA控制器中的内存地址寄存器和传送字节数寄存器。在传输数据的同时,CPU可以去做其他事情,输入设备不断地挪用CPU的工作周期,将数据寄存器中的数据源源不断的写入内存,直到要求传输的数据全部传输完毕。DMA控制器在传输完毕时向CPU发出一个中断信号,CPU收到中断信号后转中断处理程序执行,中断结束后返回被中断的程序。
- DMA控制方式的基本特点:数据传输的基本单位是数据块,数据是单项传输,从设备直接送入内存(或者是从内存直接送到数据)。仅在传输一个或者多个数据块的开始和结束时,才需要CPU的干预,整块的数据的传送是在控制器的控制下完成的。
- DMA控制方式和中断方式的主要区别是:中断控制方式在每个数据传输完成后中断CPU,而DMA是在所要求传送的一批数据全部传送结束时才中断CPU。中断控制方式的数据传送时在中断处理时由CPU控制完成的。而DMA控制方式是在DMA控制器控制下完成的。
- DMA控制器中主要有4类寄存器,用于主机和控制器之间的成块数据交换。
- 命令/状态字寄存器(CR):用于接收从CPU发来的IO命令或者有关的控制信息,或者设备的状态。
- 内存地址寄存器(MAR);用于存放数据从设备传送到内存或者从内存到设备的内存地址。
- 数据寄存器(DR):用于暂存从设备到内存或者从内存到设备的数据
- 数据计数器(DC):存放本次要传送的字数。
- 优点:DMA控制下,设备和CPU可以并行工作,同时设备与内存的数据交换速度加快,不需要CPU的干预。
- 缺点:DMA方式在数据传送的方向,存放数据的内存起始地址,和数据长度都需要CPU的控制,并且每一台设备都要有一个DMA控制器,当设备增加时,多个DMA控制器的使用不经济。
-
IO控制方式4-通道控制方式:通道控制方式与DMA控制方式类似,也是一种以内存为中心,实现设备与内存直接交换数据的控制方式。与DMA控制方式相比,通道所需要的CPU干预更少,而且可以做到一个通道控制多台设备,从而减少了CPU的复旦。通道的本质是一个简单的处理器,它独立于CPU,有运算和逻辑控制,有自己的指令系统,也在程序控制下工作,专门负责输入,输出控制,具有执行IO指令的能力,并且通过执行通道IO程序来控制IO操作。
- 与CPU不同的是,通道的指令类型单一,由于通道硬件比较简单,其所能执行的命令主要局限于IO操作的有关指令。通道没有自己的内存,而是与CPU共享内存。
- 优点:通道控制方式解决了IO操作的独立性和各部件工作的并行性,通道把中央处理器从繁琐的输入,输出操作中解放出来,采用通到技术后,不仅能实现CPU和通道的并行操作,而且通道和通道之间也能实现并行操作。各种通道上的设备也能实现并行操作,从而达到提高整个系统效率的根本目的。
- 缺点:需要更多的硬件,成本较高。
- 与DMA方式的区别:DMA方式中需要CPU来控制传输的数据块大小,传输的内存,而通道方式中这些信息都是由通道来控制和管理的。其次,一个DMA控制器对应一台设备与内存传递数据,一个通道可以控制多台设备与内存交换数据。
-
假脱机技术:系统中独占设备的数量有限,往往不能满足多个进程的需要,从而成为系统的瓶颈,使得许多的进程被阻塞。另外,得到独占设备的进程,在整个运行期间往往占有但不经常使用的设备,使得设备的利用率低,为了克服这种缺点,人们通过共享共享设备来虚拟独占设备,将独占设备改造成虚拟设备。从而提高了系统的利用效率,这种技术成为假脱机SPOOLing技术。
-
SPOOLing的技术特点:
- 提高了IO速度,从低速IO设备进行的操作变为了对输入井与输出井的操作。如同脱机一样,提高了IO速度,缓和了CPU与低速IO设备速度不匹配的矛盾。
- 设备并没有分配给任何进程。在输入井与输出井中,分配给进程的是一个存储区和建立一张IO请求表。
- 实现了虚拟设备功能。多个进程同时使用一个独占设备,对于每一个进程而言,都认为自己独占了这个设备,从而实现了设备的虚拟分配。不过,这个设备是逻辑上的设备。
- SPOOLing除了是一种速度匹配技术外,也是一种虚拟设备技术。它用一种物理设备来模拟另一类物理设备。使得各个作业在执行期间只是用虚拟设备,而不是使用物理的独占设备。使得设备的使用率与系统的效率都得到提高。
老哥是考浙大吗
不是。。。。浙大高手太多多多多多了,不敢乱冲......
谢谢老哥
老哥牛逼
o(^▽^)o
里面可能有错的( ´•︵•` )......