计算机操作系统_操作系统考试 在计算机系统中,操作系统是 - CSDN
计算机操作系统 订阅
《计算机操作系统》是2003年8月武汉大学出版社出版的图书,作者是黄水松、黄干平、曾平、李蓉蓉。 [1] 展开全文
《计算机操作系统》是2003年8月武汉大学出版社出版的图书,作者是黄水松、黄干平、曾平、李蓉蓉。 [1]
信息
作    者
黄水松、黄干平、曾平、李蓉蓉
定    价
35元
类    别
计算机与互联网
书    名
计算机操作系统
出版时间
2003年8月
开    本
16
出版社
武汉大学出版社
ISBN
9787307040076
计算机操作系统内容简介
本教材全面系统地介绍了现代计算机操作系统的基本概念、原理和实现方法。全书共分十二章,第一章讲述了现代操作系统的发展概况;第二章至第十章分别阐述了操作系统的基本原理 、概念和实现方法,包括中断技术,进程和线程的管理、进程的同步和通信,存储器管理,虚似存储器,处理机调度,死锁问题,设备管理和文件系统;第十一章介绍了UNIX操作系统,第十三章介绍Windows2000/XP操作系统,并较详细地分析了这两个系统的基本结构、主要的功能模块及其相互之间的关系。本书吸收了国内外近几 年出版的同类教材的优点,内容丰富,既可以作为计算机和相关专业的教材,也可作为从事计算机工作人员的参考书。 [1] 
收起全文
精华内容
参与话题
  • 计算机操作系统是计算机专业必修的专业基础课程,是考研的必考科目。它的特点是概念多、较抽象和涉及面广,所以无论是大学学习还是考研,很多同学都把它当做一块硬骨头,其实只要我们掌握正确的学习方法,操作系统...
  • 计算机操作系统——学习笔记(上)

    万次阅读 多人点赞 2019-02-24 17:20:17
    操作系统OS是配置在计算机硬件上的第一层软件,是对硬件系统的首次扩充。 1. 目标 有效性、方便性、可扩充性、开放性。 2. 作用 作为用户与计算机硬件系统之间的接口 作为计算机系统资源的管理者 实现了对...

    第一章 操作系统引论

    操作系统OS是配置在计算机硬件上的第一层软件,是对硬件系统的首次扩充。

    1. 目标

    有效性、方便性、可扩充性、开放性。

    2. 作用

    • 作为用户与计算机硬件系统之间的接口
    • 作为计算机系统资源的管理者
    • 实现了对计算机资源的抽象

    3.发展过程

    ①人工操作方式:用户独占全机,CPU等待人工操作。
    ②脱机输入输出方式:事先将装有用户程序和数据的纸带装入纸带输入机,在外围机的控制下,把纸带上的数据输入到磁带上(类似于磁盘)。当CPU需要时,从磁带将其高速地调入内存。反之类同。优点:减少了CPU的空闲时间,提高了I/O速度。
    ③单道批处理系统:首先监督程序将磁带第一个作业装入内存,运行控制权在该作业,该作业处理完成时,控制权交回到监督程序,再由监督程序把磁带上的第二个作业调入内存。系统自动对作业成批处理。(内存始终只保持一道作业—单道批处理)。
    缺点:内存浪费,不能充分利用系统资源。
    ④多道批处理系统:用户所提交的作业先存放在外存,排成一个“后备队列”,再由作业调度程序按一定的算法从队列选择若干作业调入内存,使他们共享CPU和系统中的各种资源。
    优缺点:资源利用率提高,系统吞吐量大,平均周转时间长,无交互能力。
    ⑤分时系统:在一台主机上连接了多个带有显示器和键盘的终端,同时允许多个用户通过自己的终端,以交互方式使用计算机,共享主机中的资源。因此,作业直接进入内存,采用轮转运行方式,系统配置一个多路卡(实现分时多路复用),及时接收用户终端命令(数据)。
    特征:多路性、独立性、及时性、交互性。
    ⑥实时系统:系统能及时响应外部事件的请求,在规定的时间内完成对该事件的处理,并控制所有实时任务的协调一致的运行。
    特征:多路性(周期性信息采集,多个对象或执行机构进行控制)、独立性、及时性、交互性、可靠性(多级容错措施)。

    4.基本特征

    ①并发性
    引入进程:提高了系统资源的利用率和系统吞吐量,并改善了系统的性能。
    引入线程:对它的调度所付出的开销比进程小得多,能更高效地提高系统内多个程序间并发执行的程度。
    ②共享性
    互斥共享方式:在一段时间内只允许一个进程访问的资源称为临界资源或独占资源。
    同时访问方式:允许在一段时间内由多个进程同时对它们进行访问。
    ③虚拟技术(通过某种技术把一个物理实体变为若干个逻辑上的对应物)
    (1) 时分复用技术:利用处理机的空闲时间运行其他程序,提高处理机的利用率。
    (2) 空分复用技术:利用存储器的空闲空间存放其他程序,提高内存的利用率。
    ④异步性(进程以不可预知的速度向前推进)。

    5.主要功能

    1. 存储器管理功能
      ①进程控制:创建和撤销进程,分配资源、资源回收,控制进程运行过程中的状态转换。
      ②进程同步:为多个进程运行进行协调。
      进程互斥(为每个临界资源配置一把锁)、进程同步。
      ③进程通信:实现相互合作之间的进程之间的信息交换。
      ④调度:作业调度,进程调度。
    2. 存储器管理功能
      存储器管理的主要任务:为多道程序的运行提供良好的环境,方便用户使用存储器,提高存储器的利用率,并能从逻辑上扩充内存。
      功能:
      ①内存分配:静态分配、动态分配。
      ②内存保护:确保每道用户程序都只在自己的内存空间内运行,彼此互不干扰。一种比较简单的内存保护机制是设置两个界限寄存器。
      ③地址映射:将地址空间中的逻辑地址转换为内存空间中与之对应的物理地址。
      ④内存扩充:借助于虚拟存储技术,逻辑上扩充内存容量。
    3. 设备管理功能:
      设备管理的主要任务:完成用户进程提出的I/O请求,为其分配所需的I/O设备;提高CPU和I/O设备的利用率,提高I/O速度,方便用户使用I/O设备。
      功能:
      ①缓存管理:缓和CPU和I/O设备速度不匹配的矛盾。
      ②设备分配:根据用户进程I/O请求、系统现有资源情况以及按照某种设备的分配策略,为之分配其所需的设备。
      ③设备处理:用于实现CPU和设备控制器之间的通信。
    4. 文件管理功能
      文件管理的主要任务:对用户文件和系统文件进行管理,方便用户使用,并保证文件的安全性。
      ①文件存储空间的管理:为每个文件分配必要的外存空间,提高外存的利用率,并能有助于提高文件系统的存、取速度。
      ②目录管理:为每个文件建立其目录项,并对众多的目录项加以有效的组织,以实现方便的按名存取,即用户只须提供文件名便可对该文件进行存取。
      ③文件的读/写管理和保护
    5. 操作系统与用户之间的接口:用户接口、程序借口

    6.系统调用

    如果一个进程在用户态需要使用内核态的功能,就进行系统调用从而陷入内核,由操作系统代为完成。
    Linux 的系统调用主要有以下这些: 进程控制 fork(); exit(); wait(); 进程通信 pipe(); shmget(); mmap(); 文件操作 open(); read(); write(); 设备操作 ioctl(); read(); write(); 信息维护 getpid(); alarm(); sleep(); 安全 chmod(); umask(); chown()。

    7.OS结构设计

    传统的操作系统结构:无结构操作系统 --> 模块化结构OS --> 分层式结构OS

    • 大内核与微内核
    1. 大内核
      大内核是将操作系统功能作为一个紧密结合的整体放到内核。 由于各模块共享信息,因此有很高的性能。 大内核是将操作系统功能作为一个紧密结合的整体放到内核。 由于各模块共享信息,因此有很高的性能。
    2. 微内核
      由于操作系统不断复杂,因此将一部分操作系统功能移出内核,从而降低内核的复杂性。移出的部分根据分层的原则划分成若干服务,相互独立。 在微内核结构下,操作系统被划分成小的、定义良好的模块,只有微内核这一个模块运行在内核态,其余模块运行在用户态。
    • 微内核OS结构
      ①足够小的内核
      ②基于客户/服务器模式
      ③应用“机制与策略分离”原理
      ④采用面向对象技术

    • 微内核的基本功能
      ①进程(线程)管理
      ②低级存储器管理
      ③中断和陷入处理

    微内核操作系统存在的问题:运行效率降低。
    微内核OS的效率降低的最主要原因:
    频繁地在用户态和核心态之间进行切换。即在完成一次客户对OS提出的服务请求时,需要利用消息实现多次交互和进行用户/内核模式以及上下文的多次切换。
    在这里插入图片描述

    8.中断分类

    • 外中断
      由 CPU 执行指令以外的事件引起,如 I/O 完成中断,表示设备输入/输出处理已经完成,处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。 - 异常 由 CPU 执行指令的内部事件引起,如非法操作码、地址越界、算术溢出等。 - 陷入 在用户程序中使用系统调用。

    第二章 进程管理

    进程的基本概念

    程序的顺序执行:按照某种先后次序顺序执行,仅当前一程序执行完后,才能执行后继操作。
    特征:顺序性、封闭性、可再现性。
    前驱图:描述进程之间执行的前后关系。
    程序的并发执行:
    特征:间断性、失去封闭性、不可再现性

    进程实体:由程序段、相关的数据段和PCB组成,所谓创建和撤销进程实际是对其中的PCB的创建和撤销。(PCB:进程控制块Process Control Block)
    进程的特征:动态性、并发性、独立性、异步性
    进程定义:是进程实体的运行过程,是系统进行资源分配和调度的一个独立单元。
    进程的三种基本状态:就绪状态、执行状态、阻塞状态(阻塞典型事件:请求I/O,申请缓冲空间等)。
    进程的三种基本状态及其转换图。
    在这里插入图片描述

    挂起状态:进程处于静止状态,暂停执行(执行状态下挂起),暂不接受调度(就绪状态下挂起)。
    进程的五种基本状态及其转换图。

    在这里插入图片描述

    具有创建、终止和挂起状态的进程状态图。
    在这里插入图片描述

    进程控制块PCB
    PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。是操作系统中最重要的记录型数据结构。

    进程控制块中的信息:进程标识符、处理机状态、进程调度信息、进程控制信息。
    进程控制块的组织方式:链接方式、索引方式。

    进程控制

    进程控制一般是由OS的内核中的原语来实现的。
    进程的创建
    ①申请空白PCB。
    ②为新进程分配资源。
    ③初始化进程控制块。
    ④将新进程插入就绪队列(如果进程就绪队列能够接纳新进程)。

    进程的终止过程
    ①根据被终止进程的标识符,从 PCB 集合中检索出该进程的 PCB,从中读出该进程的状态。 ②若被终止进程正处于执行状态,应立即终止该进程的执行,并置调度标志为真,用于指示该进程被终止后应重新进行调度。
    ③若该进程还有子孙进程,还应将其所有子孙进程予以终止,以防它们成为不可控的进程。 ④将被终止进程所拥有的全部资源,或者归还给其父进程,或者归还给系统。
    ⑤将被终止进程(PCB)从所在队列(或链表)中移出,等待其他程序来搜集信息。

    进程的阻塞与唤醒
    进程的挂起与激活

    进程同步

    并发进程之间的制约关系
    ①间接相互制约关系。源于资源共享。
    ②直接相互制约关系。源于进程间的合作。

    临界区:每个进程中访问临界资源的那段代码称为临界区。筑进程互斥地进入自己的临界区,便可实现诸进程对临界资源互斥访问。
    为了互斥访问临界资源,每个进程在进入临界区之前,需要先进行检查。
    可把一个访问临界资源的循环进程描述如下:

    同步机制应遵循的规则:空闲让进、忙则等待、有限等待、让权等待。

    • 信号量机制
    1. 整型信号量
      用于表示资源数目的整型量,仅能通过原子操作wait(S)和signal(S)来访问,也就是常见的 P 和 V 操作,执行时不可中断,通常的做法是在执行这些操作的时候屏蔽中断。
    2. 记录型信号量
      不存在“忙等”现象的进程同步机制,遵循了“让权等待”的准则。需要一个用于代表资源数目的整型变量value外,还应增加一个进程链表指针L,用于链接上述的所有等待进程。
      如果信号量的取值只能为0或者1,那么就成为了互斥量(Mutex),0表示临界区已经加锁,1表示临界区解锁。用于进程互斥。
    3. AND型信号量
      将进程在整个运行过程中需要的所有资源,一次性全部分配给进程,待进程使用完后再一起释放。
    4. 信号量集
      AND型信号量基础上,对进程所申请的所有资源以及每类资源不同的资源需求量,在一次P、V原语操作中完成申请或释放。
      信号量的应用
    5. 利用信号量实现进程互斥
      wait(mutex)和signal(mutex)必须成对地出现。
    6. 利用信号量实现前趋关系
    • 管程机制
      虽然信号量机制是一种既方便、又有效的进程同步机制,但每个要访问临界资源的进程都必须自备同步操作wait(S)和signal(S)。这就使大量的同步操作分散在各个进程中。这不仅给系统的管理带来了麻烦,而且还会因同步操作的使用不当而导致系统死锁。
      代表共享资源的数据结构,以及由对该共享数据结构实施操作的一组过程所组成的资源 管理程序,共同构成了一个操作系统的资源管理模块,我们称之为管程。
      管程被请求和释放资源的进程所调用。
      Hansan为管程所下的定义是:“一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作,这组操作能同步进程和改变管程中的数据”。
      管程由四部分组成:
      ①管程的名称。
      ②局部于管程内部的共享数据结构说明。
      ③对该数据结构进行操作的一组过程。
      ④对局部于管程内部的共享数据设置初始值的语句。
      管程相当于围墙,它把共享变量和对它进行操作的若干过程围了起来,所有进程要访问临界资源时,都必须经过管程(相当于通过围墙的门)才能进入,而管程每次只准许一个进程进入管程,从而实现了进程互斥。
    • 条件变量
      对条件变量的操作仅仅是 wait 和 signal,因此条件变量也是一种抽象数据类型,每个条件变量保存了一个链表,用于记录因该条件变量而阻塞的所有进程,同时提供的两个操作即可表示为x.wait和x.signal,其含义为:
      ①x.wait:正在调用管程的进程因x条件需要被阻塞或挂起,则调用x.wait将自己插入到x条件的等待队列上,并释放管程,直到x条件变化。此时其它进程可以使用该管程。
      ②x.signal:正在调用管程的进程发现x条件发生了变化,则调x.signal,重新启动一个因x条件而阻塞或挂起的进程。如果存在多个这样的进程,则选择其中的一个,如果没有,则继续执行原进程,而不产生任何结果。

    经典进程同步问题(使用信号量方法解决)
    生产者-消费者问题
    ①利用记录型信号量
    ②利用AND信号量
    ③利用管程

    哲学家进餐问题
    ①利用记录型信号量
    考虑到如果所有哲学家同时拿起左手边的筷子,那么就无法拿起右手边的筷子,造成死锁。

    为了防止死锁的发生,可以设置两个条件:
    必须同时拿起左右两根筷子;
    只有在两个邻居都没有进餐的情况下才允许进餐。
    ②利用AND信号量机制。

    读者-写者问题
    ①利用记录型信号量
    ②利用信号量集机制

    进程通信

    进程同步与进程通信很容易混淆,它们的区别在于:
    进程同步:控制多个进程按一定顺序执行;
    进程通信:进程之间的信息交换。
    进程通信是一种手段,而进程同步是一种目的。
    也可以说,为了能够达到进程同步的目的,需要让进程进行通信,传输一些进程同步所需要的信息。

    • 进程通信的类型
    1. 共享存储器系统
      因为数据不需要在进程之间复制,所以这是最快的一种 IPC。
      ①基于共享数据结构的通信方式。低效,只适于传递相对少量的数据。
      ②基于共享存储区的通信方式。高级通信方式。
    2. 消息传递系统
      在该机制中,进程间的数据交换是以格式化的消息(message)为单位的;在计算机网络中,又把message称为报文。程序员直接利用操作系统提供的一组通信命令(原语),实现大量数据的传递。
      分为直接通信方式和间接通信方式
    3. 管道通信系统
      “管道”(pipe)是指用于连接一个读进程和一个写进程以实现彼此间通信的一个共享文件,又名pipe文件。
      它具有以下限制: 只支持半双工通信(单向交替传输); 只能在父子进程中使用。
      FIFO也称为命名管道,去除了管道只能在父子进程中使用的限制。
    4. 消息缓冲队列通信机制
      发送进程利用Send原语将消息直接发送给接收进程;接收进程则利用Receive原语接收消息。
      相比于 FIFO,消息队列具有以下优点: 消息队列可以独立于读写进程存在,从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难; 避免了 FIFO 的同步阻塞问题,不需要进程自己提供同步方法; 读进程可以根据消息类型有选择地接收消息,而不像 FIFO 那样只能默认地接收。
    5. 信号量
      它是一个计数器,用于为多个进程提供对共享数据对象的访问。

    线程

    线程与进程的比较
    ①调度
    线程是独立调度的基本单位,在同一进程中,线程的切换不会引起进程切换,从一个进程中的线程切换到另一个进程中的线程时,会引起进程切换。
    ②并发性
    不仅进程之间可以并发执行,而且在一个进程中的多个线程之间亦可并发执行。
    ③拥有资源
    进程都可以拥有资源,是系统中拥有资源的一个基本单位。一般而言,线程自己不拥有系统资源(也有一点必不可少的资源),但它可以访问其隶属进程的资源。
    ④系统开销
    由于创建或撤销进程时,系统都要为之分配或回收资源,如内存空间、I/O 设备等,所付出的开销远大于创建或撤销线程时的开销。类似地,在进行进程切换时,涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置,而线程切换时只需保存和设置少量寄存器内容,开销很小。

    线程间的同步和通信
    互斥锁;
    条件变量;
    信号量机制。
    ①私有信号量:实现同一进程中各线程之间的同步,属于特定的进程所有,OS并不知道私用信号量的存在。
    ②公有信号量:实现不同进程间或不同进程中各线程之间的同步,由OS为它分配空间并进行管理,是一种比较安全的同步机制。

    线程的实现方式
    ①内核支持线程
    在内核的支持下运行的,即无论是用户进程中的线程,还是系统进程中的线程,他们的创建、撤消和切换等也是依靠内核,在内核空间实现的。
    ②用户级线程
    仅存在于用户空间中。对于这种线程的创建、撤消、线程之间的同步与通信等功能,都无须利用系统调用来实现。

    第三章 处理机调度与死锁

    处理机调度的层次

    ①高级调度
    高级调度又称为作业调度或长程调度,其主要功能是根据某种算法,把外存上处于后备队列中的那些作业调入内存,也就是说,它的调度对象是作业。
    作业:通常的程序、数据和作业说明书。
    作业控制块 JCB:保存了系统对作业进行管理和调度所需的全部信息。
    ②低级调度
    通常也把低级调度(Low Level Scheduling)称为进程调度或短程调度(ShortTerm Scheduling),它所调度的对象是进程(或内核级线程)。进程调度是最基本的一种调度,在多道批处理、分时和实时三种类型的 OS 中,都必须配置这级调度。

    低级调度的功能
    保存处理机的现场信息、按某种算法选取进程、把处理机分配给进程

    进程调度中的三个基本机制
    排队器、分派器(分派任务)、上下文切换机制

    进程调度方式

    • 非抢占方式
      实现简单,系统开销小,适用于大多数的批处理系统环境。但它难以满足紧急任务的要求——立即执行,因而可能造成难以预料的后果。显然,在要求比较严格的实时系统中,不宜采用这种调度方式。
    • 抢占方式
      抢占方式的优点是,可以防止一个长进程长时间占用处理机,能为大多数进程提供更公平的服务,特别是能满足对响应时间有着较严格要求的实时任务的需求。但抢占方式比非抢占方式调度所需付出的开销较大。

    进程调度原则
    优先权原则、段作业(进程)优先原则、时间片原则。

    ③中级调度
    中级调度(Intermediate Level Scheduling)又称中程调度(Medium-Term Scheduling)。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。为此,应使那些暂时不能运行的进程不再占用宝贵的内存资源,而将它们调至外存上去等待,把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重新具备运行条件且内存又稍有空闲时,由中级调度来决定把外存上的那些又具备运行条件的就绪进程重新调入内存,并修改其状态为就绪状态,挂在就绪队列上等待进程调度。中级调度实际上就是存储器管理中的对换功能。

    调度队列模型
    ①仅有进程调度的调度队列模型
    ②具有高级和低级调度的调度队列模型
    ③同时具有三级调度的调度队列模型

    选择调度方式和调度算法的若干准则

    1. 面向用户的准则:周转时间短、响应时间快、截止时间的保证、优先权准则
    2. 面向系统的准则:系统吞吐量高、处理机利用率好、各类资源的平衡利用。

    调度算法

    在 OS 中调度的实质是一种资源分配,因而调度算法是指:根据系统的资源分配策略所规定的资源分配算法。
    ①先来先服务调度算法
    FCFS 算法比较有利于长作业(进程),而不利于短作业(进程)。FCFS 调度算法有利于 CPU 繁忙型的作业,而 不利于 I/O 繁忙型的作业(进程)。CPU 繁忙型作业是指该类作业需要大量的 CPU 时间进行 计算,而很少请求 I/O。通常的科学计算便属于 CPU 繁忙型作业。I/O 繁忙型作业是指 CPU 进行处理时需频繁地请求 I/O。目前的大多数事务处理都属于 I/O 繁忙型作业。
    ②短作业(进程)优先调度算法
    SJF 调度算法能有效地降低作业的平均等待时间,提高系统吞吐量。

    ③高优先权优先调度算法

    1. 优先权调度算法的类型
      非抢占式优先权算法
      主要用于批处理系统中;也可用于某些对实时性要求不严的实时系统中。
      抢占式优先权调度算法
      常用于要求比较严格的实时系统中,以及对性能要求较高的批处理和分时系统中。
    2. 优先权的类型
      ①静态优先权
      静态优先权是在创建进程时确定的,且在进程的整个运行期间保持不变
      ②动态优先权
      动态优先权是指在创建进程时所赋予的优先权,是可以随进程的推进或随其等待时间的增加而改变的,以便获得更好的调度性能。
    3. 高响应比优先调度算法
      既照顾了短作业,又考虑了作业到达的先后次序,不会使长作业长期得不到服务。
      Rp优先级 =(等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间

    基于时间片的轮转调度算法

    1. 时间片轮转法
      就绪队列中的所有进程在给定的时间内均能获得一时间片的处理机执行时间。
      时间片大小的确定:时间片略大于一次典型的交互所需要的时间
    2. 多级反馈队列调度算法
      ①应设置多个就绪队列,并为各个队列赋予不同的优先级、不同大小的执行时间片。在优先权愈高的队列中,为每个进程所规定的执行时间片就愈小。
      ②当一个新进程进入内存后,首先将它放入第一队列的末尾,按FCFS原则排队等待调度。
      ③仅当第一队列空闲时,调度程序才调度第二队列中的进程运行。

    实时调度

    实现条件
    ①提供必要的信息
    ②系统处理能力强
    ③采用抢占式调度机制
    ④具有快速切换机制

    分类
    ①非抢占式调度算法
    非抢占式轮转调度算法、非抢占式优先调度算法
    ②抢占式调度算法

    基于时钟中断的抢占式优先权调度算法
    常用的几种实时调度算法

    1. 最早截止时间优先即EDF(Earliest Deadline First)算法
      根据任务的开始截止时间来确定任务的优先级。截止时间愈早,其优先级愈高。具有最早截止时间的任务排在队列的最前面。调度程序在选择任务时,总是选择就绪队列中的第一个任务,为之分配处理机,使之投入运行。
    2. 最低松弛度优先即LLF(Least Laxity First)算法
      根据任务紧急(或松弛)的程度,来确定任务的优先级。任务的紧急程度愈高,为该任务所赋予的优先级就愈高,以使之优先执行。
    • 产生死锁的原因和必要条件

    死锁(Deadlock),是指多个进程在运行 过程中因争夺资源而造成的一种僵局。
    产生死锁的原因可归结为如下两点:
    ①竞争资源。
    ②进程间推进顺序非法。
    产生死锁的必要条件:
    ①互斥条件:指进程对所分配到的资源进行排它性使用,即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求该资源,则请求者只能等待,直至占有该资源 的进程用毕释放。
    ②请求和保持条件:指进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源又已被其它进程占有,此时请求进程阻塞,但又对自己已获得的其它资源保持不放。
    ③不剥夺条件:指进程已获得的资源,在未使用完之前,不能被剥夺,只能在使用完时由自己释放。
    ④环路等待条件:指在发生死锁时,必然存在一个进程——资源的环形链。

    • 处理死锁的基本方法

    ①鸵鸟策略
    因为解决死锁问题的代价很高,因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。 当发生死锁时不会对用户造成多大影响,或发生死锁的概率很低,可以采用鸵鸟策略。 大多数操作系统,包括 Unix,Linux 和 Windows,处理死锁问题的办法仅仅是忽略它。
    ②预防死锁
    通过设置某些限制条件,去破坏产生死锁的四个必要条件中的一个或几个条件,来预防发生死锁。
    ③避免死锁
    在资源的动态分配过程中,用某种方法去防止系统进入不安全状态,从而避免发生死锁。
    ④检测死锁与解除死锁
    检测死锁允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构,及时地检测出死锁的发生,并精确地确定与死锁有关的进程和资源;然后,采取适当措施,从系统中将已发生的死锁清除掉。
    解除死锁常用的实施方法是撤消或挂起一些进程,以便回收一些资源,再将这些资源分配给已处于阻塞状态的进程,使之转为就绪状态,以继续运行。

    • 预防死锁的方法
    1. 预防死锁

    使四个必要条件中的第2、3、4个条件之一不能成立,来避免发生死锁。至于必要条件1,因为它是由设备的固有特性所决定的。
    ①破坏“请求和保持”条件:破坏请求:系统规定所有进程在开始运行之前,都必须一次性地申请其在整个运行过程所需的全部资源。破坏保持:分配资源时,只要有一种资源不能满足某进程的要求,即使其它所需的各资源都空闲,也不分配给该进程,而让该进程等待。
    ②破坏“不可抢占”条件:当一个已经保持了某些资源的进程,再提出新的资源请求而不能立即得到满足时,必须释放它已经保持了的所有资源,待以后需要时再重新申请。
    ③破坏“循环等待”条件:系统将所有资源按类型进行线性排队,并赋予不同的序号。

    1. 系统安全状态

    所谓安全状态,是指系统能按某种进程顺序(P1,P2,…,Pn)(称〈P1,P2,…,Pn〉序 列为安全序列),来为每个进程Pi分配其所需资源,直至满足每个进程对资源的最大需求,使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列,则称系统处于不安全状态。
    避免死锁的实质在于:系统在进行资源分配时,如何使系统不进入不安全状态。
    在这里插入图片描述
    图 a 的第二列 Has 表示已拥有的资源数,第三列 Max 表示总共需要的资源数,Free 表示还有可以使用的资源数。从图 a 开始出发,先让 B 拥有所需的所有资源(图 b),运行结束后释放 B,此时 Free 变为 5(图 c);接着以同样的方式运行 C 和 A,使得所有进程都能成功运行,因此可以称图 a 所示的状态是安全的。 定义:如果没有死锁发生,并且即使所有进程突然请求对资源的最大需求,也仍然存在某种调度次序能够使得每一个进程运行完毕,则称该状态是安全的。 安全状态的检测与死锁的检测类似,因为安全状态必须要求不能发生死锁。下面的银行家算法与死锁检测算法非常类似,可以结合着做参考对比。

    1. 利用银行家算法避免死锁

    上图中有五个进程,四个资源。左边的图表示已经分配的资源,右边的图表示还需要分配的资源。最右边的E、P以及A分别表示:总资源、已分配资源以及可用资源,注意这三个为向量,而不是具体数值,例如 A=(1020),表示4个资源分别还剩下1/0/2/0。 检查一个状态是否安全的算法如下: - 查找右边的矩阵是否存在一行小于等于向量A。如果不存在这样的行,那么系统将会发生死锁,状态是不安全的。 - 假若找到这样一行,将该进程标记为终止,并将其已分配资源加到A中。 - 重复以上两步,直到所有进程都标记为终止,则状态时安全的。 如果一个状态不是安全的,需要拒绝进入这个状态。

    • 死锁的检测与解除

    死锁的检测
    S为死锁状态的充分条件是:当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。
    死锁的解除
    ①剥夺资源。从其它进程剥夺足够数量的资源给死锁进程,以解除死锁状态。
    ②撤销进程。最简单的撤消进程的方法是使全部死锁进程都夭折。

    第四章 存储器管理

    1. 存储器的层次结构

    ①CPU寄存器:寄存器 ②主存(内存):高速缓存、主存储器、磁盘缓存 ③辅存:固定磁盘,可移动存储介质 寄存器和主存储器又被称为可执行存储器。
    操作系统的存储管理,负责对可执行存储器的分配、回收以及提供在存储层次间数据移动的管理机制

    1. 程序的装入和链接

    将一个用户源程序变为一个可在内存中执行的程序,通常都要经过以下几个步骤:
    ①编译,由编译程序将用户源代码编译成若干个目标模块;
    ②链接,由链接程序(Linker)将编译后形成的一组目标模块,以及它们所需要的库函数链接在一起,形成一个完整的装入模块;
    ③装入,由装入程序将装入模块装入内存。

    程序的装入
    ①绝对装入方式(单道程序环境)
    编译时知道程序将驻留在内存的位置,将产生绝对地址(即物理地址)的目标代码。绝对装入程序按照已知地址将装入模块装入内存,不需对地址修改。
    ②可重定位装入方式
    装入时,对目标程序中指令和数据的各地址重定位(虚拟地址到内存地址映射)。(静态重定位)
    ③动态运行时装入方式
    在把装入模块装入内存后,并不立即把装入模块中的相对地址转换为绝对地址,而是把这种地址转换推迟到程序真正要执行时才进行。

    程序的链接
    ①静态链接。在程序运行之前,先将各目标模块及它们所需的库函数,链接成一个完整的装配模块,以后不再拆开。
    ②装入时动态链接。这是指将用户源程序编译后所得到的一组目标模块,在装入内存时,采用边装入边链接的链接方式。
    ③运行时动态链接。这是指对某些目标模块的链接,是在程序执行中需要该(目标)模块时,才对它进行的链接。(可加快程序的装入过程,且可节省大量的内存空间)

    连续分配管理方式
    ①单一连续分配
    (单道程序环境下)将内存分为系统区和用户区,系统区仅供OS使用,用户区仅装用户程序(独占)。
    ②固定分区分配
    (多道程序环境下)将整个用户空间划分为若干个固定大小的区域。被划分几个分区便允许几个程序并发运行而不会互相干扰。
    ③动态分区分配
    根据进程的实际需要,动态地为之分配内存空间。
    数据结构:空闲分区表、空闲分区链。

    分区分配算法
    顺序搜索法
    首次适应算法
    要求空间分区链以地址递增的次序链接。分配内存时,从链首开始顺序查找,直至大小满足要求,按照作业大小从该空闲分区划分内存空间给请求者,余下的空闲空间留在空闲链中。
    循环首次适应算法
    从上次找到的空闲分区的下一个空闲分区开始查找。设置起始查寻指针,用于指示下一次起始查寻的空闲分区,采用循环查找方式。
    最佳适应算法
    要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。(容易形成许多难以利用的碎片)
    最坏适应算法
    扫描整个空闲分区表或链表,挑选一个最大的空闲区,分割一部分存储空间给作业使用。
    快速适应算法(分类搜索法)
    将空闲分区根据其容量大小进行分类,对于每一类具有相同容量的所有空闲分区,单独设立一个空闲分区链表,空闲分区的分类是根据进程常用的空间大小进行划分,
    分区分配操作:分配内存、回收内存。

    ④可重定位分区分配
    系统对内存进行“紧凑”使若干程序移位,用该程序在内存的新起始地址去置换原来的起始地址。(获得新起始地址——动态重定位:系统中增设一个重定位寄存器存放程序和数据在内存的起始地址,程序执行时,真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的)。

    对换
    是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上,以便腾出足够的内存空间,再把已具备运行条件的进程或进程所需要的程序和数据调入内存。
    在具有对换功能的OS中,通常把外存分为文件区和对换区。前者用于存放文件,后者用于存放从内存换出的进程。文件区采取离散分配方式。对换区采用连续分配方式。

    1. 基本分页存储管理方式

    连续分配方式形成的许多“碎片”,不进行“紧凑”,利用离散的方式,将一个进程直接分散地装入到许多不相邻接的分区中。
    ①页面与页表
    分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片,称为页面或页,并为各页加以编号,从 0开始,如第 0 页、第 1 页等。相应地,也把内存空间分成与页面相同大小的若干个存储块,称为(物理)块或页框(frame)。

    地址结构:前一部分为页号P,后一部分为位(偏)移量W(页内地址)。

    系统应能保证进程的正确运行,即能在内存中找到每个页面所对应的物理块。为此,系统又为每个进程建立了一张页面映像表,简称页表。实现从页号到物理块号的地址映射。

    ②地址变换机构
    实现从逻辑地址到物理地址的转换。实际上只是将逻辑地址中的页号,转换为内存中的物理块号。借助于页表来完成。

    • 基本的地址变换机构
      页表大多驻留在内存中。在系统中只设置一个页表寄存器 PTR(Page-Table Register),在其中存放页表在内存的始址和页表的长度。平时,进程未执行时,页表的始址和页表长度存放在本进程的 PCB 中。当调度程序调度到某进程时,才将这两个数据装入页表寄存器中。
    • 具有快表的地址变换机构
      为了提高地址变换速度,可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器,又称为“联想寄存器”(Associative Memory),或称为“快表”,用以存放当前访问的那些页表项。
    1. 基本分段存储管理方式

    ①分段系统的基本原理
    作业的地址空间被划分为若干个段,每个段定义了一组逻辑信息。段的长度由相应的逻辑信息组的长度决定,因而各段长度不等。

    分段地址中的地址结构:段号-段内地址
    段表:记录了该段在内存中的起始地址和段的长度。用于实现从逻辑段到物理内存去的映射。
    地址变换机构

    • 逻辑地址中的段号S与段表长度TL比较。若S>TL,段号太大,访问越界,产生越界中断信号。若S<TL,未越界,根据段表始址和该段段号,计算出该段对应段表项的位置,从中读出该段在内存的起始地址。
    • 检查比较段内地址d和该段的段长SL。若d>SL,发出越界中断信号。若d<SL,未越界,段基址+段内地址=要访问的内存物理地址。

    分页和分段的区别

    • 页是信息的物理单位,分页系统是系统管理的需要。段是信息的逻辑单位,分段系统是为满足用户的需要。
    • 页的大小固定且由系统决定。 段的长度不固定,决定于用户所编写的程序,根据信息的性质划分的。
    • 分页的用户程序地址空间是一维的。分段的用户程序地址空间是二维的。分段是用户的行为,程序员标示一个地址时,既需给出段名,也需给出段内地址。
    • 分页主要用于实现虚拟内存,从而获得更大的地址空间;分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

    分段系统的一个突出优点,是易于实现段的共享,即允许若干个进程共享一个或多个分段,且对段的保护也十分简单易行。

    ②段页式存储管理方式
    分页和分段存储管理方式都各有其优缺点。分页系统能有效地提高内存利用率,而分段系统则能很好地满足用户需要。
    基本原理
    段页式系统的基本原理,是分段和分页原理的结合,程序的地址空间划分成多个拥有独立地址空间的段,每个段上的地址空间划分成大小相同的页,并为每一个段赋予一个段名。这样既拥有分段系统的共享和保护,又拥有分页系统的虚拟内存功能。

    其地址结构由段号、段内 页号及页内地址三部分所组成。

    1. 虚拟存储器的基本概念

    虚拟存储器(内存)的目的是为了让物理内存扩充成更大的逻辑内存,从而让程序获得更多的可用内存。 为了更好的管理内存,操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间,这个地址空间被分割成多个块,每一块称为一页。这些页被映射到物理内存,但不需要映射到连续的物理内存,也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时,由硬件执行必要的映射,将缺失的部分装入物理内存并重新执行失败的指令。 从上面的描述中可以看出,虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存,也就是说一个程序不需要全部调入内存就可以运行,这使得有限的内存运行大程序成为可能。例如有一台计算机可以产生 16 位地址,那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存,虚拟内存技术允许该计算机运行一个 64K 大小的程序。

    局部性原理
    程序在执行时将呈现出局部性规律,即在一较短的时间内,程序的执行仅局限于某个部分;相应地,它所访问的存储空间也局限于某个区域。
    时间局限性
    典型原因是由于在程序中存在着大量的循环操作。
    空间局限性
    典型情况是程序的顺序执行。

    虚拟存储器

    虚拟存储器是指具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定,其运行速度接近于内存速度,而每位的成本却又接近于外存。

    虚拟存储器的特征
    ①多次性
    多次性是指一个作业被分成多次调入内存运行,亦即在作业运行时没有必要将其全部装入,只需将当前要运行的那部分程序和数据装入内存即可;以后每当要运行到尚未调入的那部分程序时,再将它调入。
    ②对换性
    对换性是指允许在作业的运行过程中进行换进、换出,亦即,在进程运行期间,允许将那些暂不使用的程序和数据,从内存调至外存的对换区(换出),待以后需要时再将它们从外存调至内存(换进);甚至还允许将暂时不运行的进程调至外存,待它们重又具备运行条件时再调入内存。换进和换出能有效地提高内存利用率。   
    ③虚拟性
    虚拟性是指能够从逻辑上扩充内存容量,使用户所看到的内存容量远大于实际内存容量。实现小内存运行大作业,改善内存利用率,提高并发程度,增加系统吞吐量。

    虚拟存储器的实现方法
    虚拟存储器的实现,都毫无例外地建立在离散分配的存储管理方式的基础上。
    ①请求分页系统
    硬件支持
    请求分页的页表机制
    请求页表增加四个字段作为请求分页的数据结构。请求分页系统中页表诸项:页号、物理块号、状态位P、访问字段A、修改位M、外存地址。
    缺页中断机构
    每当所要访问的页面不在内存时,便产生一缺页中断,请求OS将所缺之页调入内存。
    地址变换机构
    在分页系统地址变换机构的基础上,再为实现虚拟存储器而增加了某些功能而形成的,如产生和处理缺页中断,以及从内存中换出一页的功能等等。

    实现请求分页的软件:在硬件的支持下,将程序正在运行时所需的页面(尚未在内存中的)调入内存,再将内存中暂时不用的页面从内存置换到磁盘上。
    ②请求分段系统
    硬件支持:请求分段的段表机制、缺段中断机构、地址变换机构

    内存分配策略和分配算法
    ①最小物理块数的确定。
    ②物理块的分配策略

    • 固定分配局部置换
    • 可变分配全局置换
    • 可变分配拒不置换

    ③物理块的分配算法

    • 平均分配算法
    • 按比例分配算法
    • 考虑优先权的分配算法

    调页策略

    ①调入页面的时机

    • 预调页策略
      如果进程的许多页是存放在外存的一个连续区域中,则一次调入若干个相邻的页,会比一次调入一页更高效些。
    • 请求调页策略
      当进程在运行中需要访问某部分程序和数据时,若发现其所在的页面不在内存,便立即提出请求,由OS将其所需页面调入内存。

    ②确定从何处调入页面

    • 全部从对换区调入所需页面
    • 不会被修改的文件都直接从文件区调入,那些可能被修改的部分,从对换区调入。
    • Unix方式。未运行过的页面从文件去调入,曾经运行过但又被换出的页面,从对换区调入。

    页面调入过程
    每当程序所要访问的页面未在内存(存在位为“0”)。
    ①向CPU发缺页中断。
    ②中断处理程序保留CPU环境去分析中断原因。
    ③转入缺页中断处理程序。
    ④通过查找页表得到该页所在外存物理块。
    ⑤若内存未满,启动磁盘I/O,调该缺页入内存,修改页表。
    ⑥若内存已满,置换算法将内存中一页换出,调该缺页入内存,修改页表,置该页面存在位为“1”,页表项写入快表。

    页面置换算法
    在进程运行过程中,若其所要访问的页面不在内存而需把它们调入内存,但内存已无空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应将哪个页面调出,须根据一定的算法来确定。通常,把选择换出页面的算法称为页面置换算法。

    页面置换算法的主要目标是使页面置换频率最低(也可以说缺页率最低)。

    ①最佳置换算法
    其所选择的被淘汰页面,将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法,通常可保证获得最低的缺页率。
    ②先进先出(FIFO)页面置换算法
    该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
    该算法会将那些经常被访问的页面也被换出,从而使缺页率升高。
    ③最近最久未使用(LRU)置换算法
    选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当须淘汰一个页面时,选择现有页面中其t值最大的,即最近最久未使用的页面予以淘汰。
    硬件支持:寄存器和栈。
    ④Clock置换算法
    循环地检查各页面的使用情况。
    ⑤最少使用(LFU)置换算法
    在采用最少使用置换算法时,应为在内存中的每个页面设置一个移位寄存器,用来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面作为淘汰页。
    ⑥页面缓冲算法(PBA)
    将一个被淘汰的页放入两个链表中的一个,即如果页面未被修改,就将它直接放入空闲链表中;否则,便放入已修改页面的链表中。
    当有一个未被修改的页要换出时,实际上并不将它换出内存,而是把该未被修改的页所在的物理块挂在自由页链表的末尾。类似地,在置换一个已修改的页面时,也将其所在的物理块挂在修改页面链表的末尾。利用这种方式可使已被修改的页面和未被修改的页面都仍然保留在内存中。当该进程以后再次访问这些页面时,只需花费较小的开销,使这些页面又返回到该进程的驻留集中。

    请求分段存储管理方式

    硬件支持
    ①段表机制
    段表项中增加了增补位。这是请求分段式管理中所特有的字段,用于表示本段在运行过程中是否做过动态增长。
    ②缺段中断机构
    段不是定长的,这使对缺段中断的处理要比对缺页中断的处理复杂。
    ③地址变换机构
    因为被访问的段并非全在内存,所以在地址变换时,若发现所要访问的段不在内存,必须先将所缺的段调入内存,并修改段表,然后才能再利用段表进行地址变换。

    分段的共享与保护
    ①共享段表
    共享进程计数count、存取控制字段、段号。
    ②共享段的分配与回收
    ③分段保护

    • 越界检查(逻辑地址空间的段号与段表长度进行比较,段内地址与段长进行比较)。
    • 存取控制检查。
    • 环保护机构(一个程序可以访问驻留在相同环或较低特权环中的数据,一个程序可以调用驻留在相同环或较高特权环中的服务)。

    第五章 设备管理

    1. I/O系统

    设备控制器
    设备控制器是计算机中的一个实体,其主要职责是控制一个或多个I/O设备,以实现I/O设备和计算机之间的数据交换。

    设备控制器的基本功能
    ①接收和识别命令:相应的控制寄存器,存放接收的命令和参数,进行译码。 ②数据交换:CPU与控制器之间、控制器与I/O设备之间,数据交换。 ③标识和报告设备的状态:控制器记录设备的状态供CPU了解。 ④地址识别:控制器中配置地址译码器,识别其所控制的设备的地址。 ⑤数据缓区:主机速率高,I/O设备速率低,暂存数据匹配速率再进行数据传送。 ⑥差错控制:I/O设备传来的数据,设备控制器进行差错检测,若错,将差错检测码置位,并向CPU报告,CPU处理,数据作废,重新传送。

    I/O通道
    I/O通道处于CPU和设备控制器之间,是一种特殊的处理机,它具有执行I/O指令的能力,并通过执行通道(I/O)程序来控制I/O操作。指令类型单一、通道与CPU共享内存。
    通道类型
    ①字节多路通道
    按字节交叉方式工作的通道。
    ②数组选择通道
    按数组方式进行数据传送,
    ③数组多路通道
    将数组选择通道传输速率高和字节多路通道能使各子通道(设备)分时并行操作的优点相结合而形成的一种新通道。数据传送是按数组方式进行的。

    总线系统
    在计算机系统中的各部件,如 CPU、存储器以及各种I/O设备之间的联系,都是通过总线来实现的。总线的性能是用总线的时钟频率、带宽和相应的总线传输速率等指标来衡量的。

    1. I/O控制方式

    ①程序I/O方式(不断循环测试状态寄存器中的忙/闲标志busy)
    ②中断驱动I/O控制方式(CPU中断处理,I/O设备可与CPU并行工作)
    ③直接寄存器访问(DMA)I/O控制方式(数据传输的基本单位是数据块,所传送的数据是从设备直接送入内存的或者相反,仅在传送一个或多个数据块的开始和结束时,才需CPU干预,整块数据的传送是在控制器的控制下完成的)
    ④I/O通道控制方式
    DMA方式的发展,进一步减少CPU的干预,把对一个数据块的 读(或写)为单位的干预减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预。实现CPU、通道、I/O设备三者的并行操作。

    1. 缓冲管理

    引入缓冲区的原因
    ①缓和CPU与I/O设备间速度不匹配的矛盾。
    ②减少对CPU的中断频率,放宽对CPU中断响应时间的限制。
    ③提高CPU和I/O设备之间的并行性。

    单缓冲
    在单缓冲情况下,每当用户进程发出一I/O请求时,操作系统便在主存中为之分配一缓冲区。
    双缓冲
    实现双向传输。一个用作发送缓冲区,另一个用作接收缓冲区。
    循环缓冲
    当输入与输出或生产者与消费者的速度相差甚远时,可将多个缓冲组织成循环缓冲形式。使输入进程和计算进程并行执行。可能出现系统受计算限制(输入进程阻塞)和系统受I/O限制(计算进程阻塞)。

    缓冲池
    提高缓冲区的利用率,既可用于输入又可用于输出的公用缓冲池。

    1. I/O软件

    I/O软件的总体设计目标是高效率和通用性。前者是要确保I/O设备与CPU的并发性,以提高资源的利用率;后者则是指尽可能地提供简单抽象、清晰而统一的接口,采用统一标准的方法,来管理所有的设备以及所需的I/O操作。

    I/O系统的层次及功能

    • 用户层软件
      实现与用户交互的接口。
    • 设备独立性软件
      负责实现与设备驱动器的统一接口、设备命名、设备的保护以及设备的分配与释放等,同时为设备管理和数据传送提供必要的存储空间。
    • 设备驱动程序
      与硬件直接相关,负责具体实现系统对设备发出的操作指令,驱动I/O设备工作的驱动程序。
    • 中断处理程序
      用于保存被中断进程的 CPU 环境,转入相应的中断处理程序进行处理,处理完后再恢复被中断进程的现场后返回到被中断进程
    • 硬件
      执行I/O操作。

    中断处理程序的处理过程
    ①唤醒被阻塞的驱动(程序)进程
    ②保护被中断进程的CPU环境 ③转入相应的设备处理程序 ④中断处理
    ⑤恢复CPU的现场并退出中断

    设备驱动程序
    是I/O进程与设备控制器之间的通信程序。
    设备驱动程序的功能
    ①接收由设备独立性软件发来的命令和参数,并将命令中的抽象要求转换为具体要求。
    ②检查用户 I/O 请求的合法性,了解I/O设备的状态,传递有关参数,设置设备的工作方式。
    ③发出I/O命令。如果设备空闲,便立即启动I/O设备去完成指定的I/O操作;如果设备处于忙碌状态,则将请求者的请求块挂在设备队列上等待。
    ④及时响应由控制器或通道发来的中断请求,并根据其中断类型调用相应的中断处理程序进行处理。
    ⑤对于设置有通道的计算机系统,驱动程序还应能够根据用户的I/O请求,自动地构成通道程序。

    设备独立性软件
    设备无关性:应用程序独立于具体使用的物理设备。
    设备独立性软件的主要功能
    ①执行所有设备的公有操作。
    ②向用户层(或文件层)软件提供统一接口。

    1. 设备分配

    设备分配中的数据结构
    设备控制表、控制器控制表、通道控制表和系统设备表
    设备分配时应考虑的因素
    ①设备的固有属性
    对独占、共享、可虚拟三种设备应采取不同的分配策略。
    ②设备分配算法
    先来先服务、优先级高者调用。
    ③设备分配中的安全性
    安全分配方式、不安全分配方式

    SPOOLing技术
    利用一道程序模拟脱机输入时的外围控制机功能,把低速I/O设备的数据传送到高速磁盘上(脱机输入),再利用另一道程序脱机输出时的外围控制机功能,把高速磁盘的数据传送到低速输出设备上(脱机输出)。。这样,便可在主机的直接控制下,实现脱机输入、输出功能。此时的外围操作与CPU对数据的处理同时进行,我们把这种在联机情况下实现的同时外围操作称为 SPOOLing,或称为假脱机操作。

    SPOOLing系统的组成
    ①输入井和输出井
    ②输入缓冲区和输出缓冲区
    ③输入进程SPi和输出进程SPo
    SPOOLing系统的特点
    ①提高了I/O的速度。
    ②将独占设备改造为共享设备。
    ③实现了虚拟设备功能。

    1. 磁盘存储器的管理

    磁盘结构
    盘面(Platter):一个磁盘有多个盘面; 磁道(Track):盘面上的圆形带状区域,一个盘面可以有多个磁道; 扇区(Track Sector):磁道上的一个弧段,一个磁道可以有多个扇区,它是最小的物理储存单位,目前主要有 512 bytes 与 4 K 两种大小; 磁头(Head):与盘面非常接近,能够将盘面上的磁场转换为电信号(读),或者将电信号转换为盘面的磁场(写); 制动手臂(Actuator arm):用于在磁道之间移动磁头; 主轴(Spindle):使整个盘面转动。

    磁盘调度算法

    读写一个磁盘块的时间的影响因素有:
    寻道时间(制动手臂移动,使得磁头移动到适当的磁道上) 旋转时间(主轴转动盘面,使得磁头移动到适当的扇区上) 实际的数据传输时间 其中,寻道时间最长,因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。 ①先来先服务
    这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单,且每个进程的请求都能依次地得到处理,不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化,致使平均寻道时间可能较长。仅适用于请求磁盘I/O的进程数目较少的场合。
    ②最短寻道时间优先
    要求访问的磁道与当前磁头所在的磁道距离最近,以使每次的寻道时间最短。虽然平均寻道时间比较低,但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近,那么在等待的磁道请求会一直等待下去,也就是出现饥饿现象。具体来说,两端的磁道请求更容易出现饥饿现象。
    ③扫描算法
    该算法不仅考虑到欲访问的磁道与当前磁道间的距离,更优先考虑的是磁头当前的移动方向。总是按一个方向来进行磁盘调度,直到该方向上没有未完成的磁盘请求,然后改变方向。因为考虑了移动方向,因此所有的磁盘请求都会被满足,解决了SSTF的饥饿问题。
    ④循环扫描算法
    CSCAN算法规定磁头单向移动。将最小磁道号紧接着最大磁道号构成循环,进行循环扫描。
    ⑤NStepSCAN和FSCAN调度算法
    NStepSCAN算法
    N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列,磁盘调度将按 FCFS算法依次处理这些子队列。而每处理一个队列时又是按SCAN算法,对一个队列处理完后,再处理其他队列。当正在处理某子队列时,如果又出现新的磁盘 I/O请求,便将新请求进程放入其他队列,这样就可避免出现粘着现象。
    FSCAN算法
    FSCAN算法实质上是N步SCAN算法的简化,即FSCAN只将磁盘请求队列分成两个子队列。

    磁盘高速缓存
    磁盘高速缓存的形式
    磁盘高速缓存是指利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息。这里的高速缓存是一组在逻辑上属于磁盘,而物理上是驻留在内存中的盘块。
    数据交付方式
    数据交付是指将磁盘高速缓存中的数据传送给请求者进程。(数据交付、指针交付)。
    置换算法
    最近最久未使用算法LRU、最近未使用算法NRU及最少使用算法LFU。
    除了考虑到最近最久未使用这一原则外,还考虑了以下几点:
    访问频率、可预见性、数据一致性。
    周期性地写回磁盘
    在UNIX系统中专门增设了一个修改(update)程序,使之在后台运行,该程序周期性地调用一个系统调用SYNC。该调用的主要功能是强制性地将所有在高速缓存中已修改的盘块数据写回磁盘。

    提高磁盘I/O速度的其它方法
    ①提前读
    用户(进程)对文件进行访问时,经常采用顺序访问方式,即顺序地访问文件各盘块的数据。在这种情况下,在读当前块时可以预知下一次要读的盘块。因此,可以采取预先读方式,即在读当前块的同时,还要求将下一个盘块(提前读的块)中的数据也读入缓冲区。
    ②延迟写
    延迟写是指在缓冲区A中的数据,本应立即写回磁盘,但考虑到该缓冲区中的数据在不久之后可能还会再被本进程或其它进程访问(共享资源),因而并不立即将该缓冲区 A 中的数据写入磁盘,而是将它挂在空闲缓冲区队列的末尾。当该缓冲区A仍在队列中时,任何访问该数据的进程,都可直接读出其中的数据而不必去访问磁盘。
    ③优化物理块的分布
    使磁头的移动距离最小。
    ④虚拟盘
    所谓虚拟盘,是指利用内存空间去仿真磁盘,又称为RAM盘。虚拟盘的主要问题是:它是易失性存储器。与磁盘高速缓存的主要区别在于: 虚拟盘中的内容完全由用户控制,而高速磁盘缓存中的内容则是由OS控制的。

    廉价磁盘冗余阵列
    它是利用一台磁盘阵列控制器,来统一管理和控制一组(几台到几十台)磁盘驱动器,组成一个高度可靠的、快速的大容量磁盘系统。磁盘阵列采取并行交叉存取。

    展开全文
  • 计算机操作系统 一.操作系统引论 1.操作系统的目标和功能 目标 方便性 有效性 提高系统资源利用率 提高系统吞吐量 可扩充性 开放性 作用 OS作为用户与计算机硬件系统之间的接口 ...

    计算机操作系统

    一.操作系统引论

    1.操作系统的目标和功能

    • 目标
      • 方便性
      • 有效性
        • 提高系统资源利用率
        • 提高系统吞吐量
      • 可扩充性
      • 开放性
    • 作用
      • OS作为用户与计算机硬件系统之间的接口
        • 命令方式
        • 系统调用方式
        • 图标–窗口方式
      • OS实现了对计算机资源的抽象

    2.操作系统的发展过程

    • 未配置操作系统的计算机系统
      • 人工操作方式

          用户独占全机 CPU等待人工操作 严重降低了计算机资源的利用率
        
      • 脱机输入/输出(Off–Line I/O)方式

          减少了CPU的空闲时间 提高了I/O速度 效率仍然不理想
        
    • 单道批处理系统
    • 多道批处理系统
      1.资源利用率高
      2.系统吞吐量大
      3.平均周转时间长
      4.无交互能力
      • (宏观并行,微观串行)
    • 分时系统
      特征:
      1.多路性
      2.独立性
      3.及时性
      4.交互性
    • 实时系统
    • 集群系统–超算~云计算
    • 微机操作系统的发展

    3.操作系统的基本特征

    • 1.并发concurrence
      • 区别并行和并发

          并行性是指两个或多个事件在同一时刻发生→宏观并行,微观并行
          并发性是指两个或多个事件在同一时间间隔内发生→宏观并行,微观串行
        
        • 并发是进程宏观一起运行,微观上交替运行,而并行是指同时运行
      • 引入进程

          进程是指在系统中能独立运行并作为资源分配的基本单位,它是由一组机器指令,数据和堆栈等组成的,是一个能独立运行的活动实体
        
    • 2.共享sharing
      • 1.互斥共享方式
      • 2.同时访问方式
      • 并发和共享是多用户(多任务)OS的两个最基本的特征。它们又是互为存在的条件
    • 3.虚拟virtual
      • 时分复用技术
      • 空分复用技术
    • 4.异步asynchronism

    4.操作系统的主要功能

    • 1.处理机管理功能
      • 进程控制
      • 进程同步
        • 进程互斥方式
        • 进程同步方式(协同)
      • 进程通信
      • 调度
        • 作业调度
        • 进程调度
    • 2.存储器管理功能
      • 内存分配
        • 静态分配
        • 动态分配
      • 内存保护
      • 地址映射
      • 内存扩充
    • 3.设备管理功能
      • 缓冲管理
      • 设备分配
      • 设备处理
        • 设备处理程序又称设备驱动程序
    • 4.文件管理功能
      • 文件存储空间的管理
      • 目录管理
      • 文件的读写管理和保护
    • 5.操作系统与用户之间的接口
      • 用户接口
      • 程序接口
    • 6.现代操作系统的新功能
      • 系统安全
      • 网络的功能和服务
      • 支持多媒体

    5.OS结构设计

    • 传统操作系统结构
      • 无结构操作系统
      • 模块化OS
      • 分层式结构OS
    • 微内核os结构
      • 客户/服务器模式
      • 面对对象的程序设计

    第二章进程的描述与控制

    前驱图和程序执行

    程序并发执行

    • 程序的并发执行
    • 程序并发执行时的特征
      • 间断性
      • 失去封闭性
      • 不可再现性

    进程的描述

    • 进程的定义
      • 进程是程序的一次执行
      • 进程是一个程序及其数据在处理机上顺序执行时所发生的活动
      • 进程是具有独立功能的程序在一个数据集合上运行的过程,它是系统进行资源分配和调度的一个独立单位
    • 进程的特征
      • 动态性
      • 并发性
      • 独立性
      • 异步性
    • 从操作系统角度分类
      • 系统进程
      • 用户进程
    • 进程和程序的区别
      • 进程是动态概念,而程序则是静态概念
      • 程序是指令的有序集合,永远存在;进程强调是程序在数据集上的一次执行,有创建有撤销,存在是暂时的;
      • 进程具有并发性,而程序没有
      • 进程可创建其他进程,而程序并不能形成新的程序
      • 进程是竞争计算机资源的基本单位,程序不是
    • 进程和程序的联系
      • 进程是程序在数据集上的一次执行
      • 程序是构成进程的组成部分,一个程序可对应多个进程,一个进程可包括多个程序
      • 进程的运行目标是执行所对应的程序
      • 从静态看,进程由程序、数据和进程控制块(PCB)组成
    • 进程的基本状态及转换
      • 进程的三种基本状态
        • 就绪状态ready
        • 执行状态running
        • 阻塞状态block
      • 三种基本状态的转换
      • 创建状态和终止状态
        • 五状态进程模型
      • 注意
        • 阻塞态->运行态和就绪态->阻塞态这二种状态转换不可能发生
    • 挂起操作和进程状态的转换
      • 挂起和阻塞的区别
      • 挂起操作的目的
        • 终端用户的需要: 修改、检查进程
        • 父进程的需要:修改、协调子进程
        • 对换的需要:缓和内存
        • 负荷调节的需要:保证实时任务的执行
      • 关键图
    • 进程管理中的数据结构
      • 进程控制块PCB的作用
        • 作为独立运行基本单位的标志
        • 能实现间断性运行方式
        • 提供进程管理所需要的信息
        • 提供进程调度所需要的信息
        • 实现与其他进程的同步与通信
      • 进程控制块的信息
        • 进程标识符
          • 外部标识符PID
          • 内部标识符(端口)
        • 处理机状态
          • 通用寄存器
          • 指令计数器
          • 程序状态字PSW
          • 用户栈指针
        • 进程调度信息
          • 进程状态
          • 进程优先级
          • 进程调度所需的其他信息
          • 事件
        • 进程控制信息
          • 程序和数据的地址
          • 进程同步和通信机制
          • 资源清单
          • 链接指针
        • 进程控制块的组织方式
          • 线性方式
          • 链接方式
          • 索引方式

    进程控制

    • 操作系统内核
      • 两大功能
        • 支撑功能
          • 中断管理
          • 时钟管理
          • 原语操作
            • 进程的管理,由若干原语(primitive)来执行
        • 资源管理功能
          • 进程管理
          • 存储器管理
          • 设备管理
      • 状态
        • 系统态,管态,内核态
        • 用户态,目态
    • 进程的创建
      • 进程的层次结构
        • 父进程
        • 子进程
      • 引起创建进程的事件
        • 用户登录
        • 作业调度
        • 提供服务
        • 应用请求
      • 进程的创建过程
        • 1.申请空白PCB
        • 2.为新进程分配其运行所需的资源
        • 3.初始化进程块PCB
        • 4.如果进程就绪队列能够接纳新进程,便将新进程插入就绪队列
      • 进程的终止
        • 引起进程终止的事件
          • 1.正常结束
          • 2.异常结束
          • 3.外界干预
        • 进程的终止过程
          • 1.根据被终止进程的标识符
      • 进程的阻塞与唤醒
        • 引起进程阻塞和唤醒的事件
          • 请求系统服务而未满足
          • 启动某种操作而阻塞当前进程
          • 新数据尚未到达
          • 无新工作可做:系统进程
        • 进程阻塞过程(自己阻塞自己)
        • 进程唤醒过程(系统或其他进程唤醒自己)
      • 进程的挂起与激活
        • suspend
        • active
    • 进程同步
      • 基本概念
        • 两种形式的制约关系
          • 间接相互制约关系
            • 互斥——竞争
          • 直接相互制约关系
            • 同步——协作
        • 临界资源
        • 分区
          • 进入区enter section
          • 临界区critical section
          • 退出区exit section
          • 剩余区remainder section
        • 同步机制应遵循的规则
          • 1.空闲让进
          • 2.忙则等待
          • 3.有限等待
          • 4.让权等待
      • 进程同步机制
        • 软件同步机制:都没有解决让权等待,而且部分方法还会产生死锁的情况
        • 硬件同步机制
          • 关中断
          • 利用Test-and-Set指令实现互斥
          • 利用swap指令实现进程互斥
        • 信号量机制
          • 整型信号量
          • 记录型信号量
            • 由于整型信号量没有遵循让权等待原则,记录型允许负数,即阻塞链表
          • AND型信号量
          • 信号量集
            • 理解:AND型号量的wait和signal仅能对信号施以加1或减1操作,意味着每次只能对某类临界资源进行一个单位的申请或释放。当一次需要N个单位时,便要进行N次wait操作,这显然是低效的,甚至会增加死锁的概率。此外,在有些情况下,为确保系统的安全性,当所申请的资源数量低于某一下限值时,还必须进行管制,不予以分配。因此,当进程申请某类临界资源时,在每次分配前,都必须测试资源数量,判断是否大于可分配的下限值,决定是否予以分配
            • 操作
              • Swait(S1,t1,d1…Sn,tn,dn)
              • Ssignal(S1,d1…Sn,dn)
            • 特殊情况
      • 经典进程的同步问题
        • 生产者–消费者问题
        • 哲学家进餐问题
        • 读者–写者问题

    进程通信

    • 进程通信是指进程之间的信息交换,又称低级进程通信
    • 进程通信的类型
      • 共享存储器系统
        • 基于共享数据结构的通信方式
          • 生产者和消费者
        • 基于共享存储区的通信方式
          • 高级通信
      • 管道通信系统(pipe)
        • 高级通信
      • 消息传递系统
        • 高级通信
        • 方式分类
          • 直接通信
          • 间接通信
      • 客服机–服务器系统
    • 消息传递通信的实现方式
      • 直接消息传递系统
      • 信箱通信

    线程的基本概念

    • 线程的引入
      • 线程的引入正是为了简化线程间的通信,以小的开销来提高进程内的并发程度
      • 多线程并发的不足
        • 进程的两个基本属性
          • 一个拥有资源的独立单位,可独立分配系统资源
          • 一个可独立调度和分派的基本单位,PCB
        • 程序并发执行所需付出的时空开销
          • 创建进程
          • 撤销进程
          • 进程切换
        • 进程间通信效率低
        • 将分配资源和调度两个属性分开
      • 线程——作为调度和分派的基本单位
        • 进程是系统资源分配的单位,线程是处理器调度的单位
        • 线程表示进程的一个控制点,可以执行一系列的指令。通常,和应用程序的一个函数相对应
        • 进程分解为线程还可以有效利用多处理器和多核计算机
    • 线程与进程的比较
      • 不同点
        • 调度的基本单位
        • 并发性
      • 相似点
        • 状态:运行、阻塞、就绪
        • 线程具有一定的生命期
        • 进程可创建线程,一个线程可创建另一个子线程
        • 多个线程并发执行时仍然存在互斥与同步
    • 线程的实现
      • 线程的实现方式
        • 内核支持线程KST
        • 用户级线程ULT
        • 组合方式
      • 多线程OS中的进程属性
        • 进程是一个可拥有资源的基本单位
        • 多个线程可并发执行
        • 进程已不是可执行的实体
      • 线程的状态和线程控制块
        • 线程运行的三个状态
          • 执行状态
          • 就绪状态
          • 阻塞状态
        • 线程控制块TCB

    第三章:处理机调度与死锁

    处理机调度算法的目标

    • 处理机调度算法的共同目标
      • 资源利用率:CPU的利用率=CPU有效工作时间/(CPU有效工作时间+CPU空闲等待时间)
      • 公平性
      • 平衡性
      • 策略强制执行
    • 批处理系统的目标
      • 平均周转时间短
      • 系统吞吐量高
      • 处理机利用率高
    • 分时系统的目标
      • 响应时间快
      • 均衡性
    • 实时系统目标
      • 截止时间的保证
      • 可预测性
    • 处理机调度的层次
      • 高级调度(作业调度)
        • 分时系统无需作业调度,因为需要交互
        • 批处理系统需要作业调度
      • 中级调度(和挂起有关)
      • 低级调度(进程调度)
        • 进程调度是最基本的调度,任何操作系统都有进程调度。
        • 低级调度的三个基本机制
          • 排队器
          • 分派器
          • 上下文切换
        • 进程调度方式
          • 非抢占方式
          • 抢占方式
            • 优先权原则
            • 短进程优先原则
            • 时间片原则
        • 进程调度的任务
          • 保存处理机的现场信息
          • 按某种算法选取进程
          • 把处理器分配给进程
        • 进程调度的算法
          • 优先级调度算法
            • 优先级调度算法的类型
              • 非抢占式优先级调度算法
                • 等当前进程执行完以后,再执行另一个优先权最高的进程
                • 这种调度算法主要用于批处理系统中;也可用于某些对实时性要求不严的实时系统中。
              • 抢占式优先级调度算法
                • 不等当前进程结束,直接抢处理机
                • 常用于要求比较严格的实时系统中, 以及对性能要求较高的批处理和分时系统中。
            • 优先级的类型
              • 静态优先级
                • 优先权是在创建进程时确定的,且在进程的整个运行期间保持不变。一般地,优先权是利用某一范围内的一个整数来表示的,例如,07或0255中的某一整数, 又把该整数称为优先数。
                • 可以参考BIOS系统中设置boot的优先级
              • 动态优先级
                • 在创建进程时所赋予的优先权,是可以随进程的推进或随其等待时间的增加而改变的,以便获得更好的调度性能。
          • 轮转调度算法
            • 基本原理:在轮转(RR)法中,系统根据FCFS策略,将所有的就绪进程排成一个就绪队列,并可设置每隔一定时间间隔(如30ms)即产生一次中断,激活系统中的进程调度程序,完成一次调度,将CPU分配给队首进程,令其执行
            • 进程切换时机
              • 时间片未用完,进程完成
              • 时间片到,进程未完成
            • 时间片大小的确定
              • 太小利于短作业,增加系统切换开销
              • 太长就退化为FCFS算法
              • 一般选择: q略大于一次交互所需要的时间,使大多数进程在一个时间片内完成
            • 一般来说,平均周转时间将比SJF长,但是有较好的响应时间
          • 多队列调度算法
          • 多级反馈队列调度算法
            • 调度机制
              • 设置多个就绪队列
              • 每个队列都采用FCFS算法
              • 按照队列优先级调度,在第n队列中采取按时间片轮转的方式运行
            • 调度算法的性能
              • 对于终端型用户,由于作业小,感觉满意
              • 对于短批处理作业用户,周转时间也较小
              • 长批处理作业用户,也能够得到执行
          • 基于公平原则的调度算法
            • 保证调度算法
            • 公平分享调度算法

    作业与作业调度

    • 作业
      • 作业不仅包含程序和数据,还配有一份作业说明书,系统根据说明书对程序的运行进行控制。批处理系统是以作业为单位从外存掉入内存的。
    • 作业控制块JCB
      • 为每个作业设置一个JCB,保存了对作业管理调度的全部信息。是作业存在的标志。
    • 作业步
      • 作业步,每个作业都必须经过若干相对独立,有相互关联的顺序步骤才能得到结果。每一个步骤就是一个作业步。
    • 作业运行的三个阶段
      • 收容阶段
      • 运行阶段
      • 完成阶段
    • 作业运行的三个状态
      • 后备状态
      • 运行状态
      • 完成状态
    • 作业调度的主要任务
      • 接纳多少个作业
      • 接纳哪些作业
    • 先来先服务(first–come first–served,FCFS)调度算法
      • 比较有利于长作业,而不利于短作业。
      • 有利于CPU繁忙的作业,而不利于I/O繁忙的作业。
    • 短作业优先(short job first,SJF)的调度算法
      • 优点
        • 比FCFS改善平均周转时间和平均带权周转时间,缩短作业的等待时间;
        • 提高系统的吞吐量;
      • 缺点
        • 必须预知作业的运行时间
        • 对长作业非常不利,长作业的周转时间会明显地增长
        • 在采用SJF算法时,人–机无法实现交互
        • 该调度算法完全未考虑作业的紧迫程度,故不能保证紧迫性作业能得到及时处理
    • 优先级调度算法(priority–scheduling algorithm,PSA)
    • 高响应比优先调度算法(Highest Response Ratio Next,HRRN)
      • 原理
        • 在每次选择作业投入运行时,先计算此时后备作业队列中每个作业的响应比RP然后选择其值最大的作业投入运行
        • 优先权=(等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间=1+等待时间/要求服务时间
      • 特点
        • 如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,因而类似于SJF算法,有利于短作业
        • 当要求服务的时间相同时,作业的优先权又决定于其等待时间,因而该算法又类似于FCFS算法
        • 对于长时间的优先级,可以为随等待时间的增加而提高,当等待时间足够长时,也可获得处理机

    实时调度(HRT和SRT任务)

    • 实现实时调度的基本条件
      • 提供必要信息
        • 就绪时间
        • 开始截止时间和完成截止时间
        • 处理时间
        • 资源要求
        • 优先级
      • 系统处理能力强
        • ∑(Ci/Pi)≤1
        • N个处理机:∑(Ci/Pi)≤N
      • 采用抢占式调度机制
      • 具有快速切换机制
        • 对中断的快速响应能力
        • 快速的任务分派能力
    • 实时调度算法的分类
      • 非抢占式调度算法
        • 非抢占式轮转调度算法
        • 非抢占式优先调度算法
      • 抢占式调度算法
        • 基于时钟中断的抢占式优先级调度算法
        • 立即抢占的优先级调度算法
    • 最早截止时间优先EDF(Earliest Deadline First)算法
      • 根据任务的开始截至时间来确定任务的优先级
        • 截至时间越早,优先级越高
      • 非抢占式调度方式用于非周期实时任务
      • 抢占式调度方式用于周期实时任务
    • 最低松弛度优先LLF(Least Laxity First)算法
      • 类似EDF
      • 算法根据任务紧急(或松弛)的程度,来确定任务的优先级。任务的紧急程度愈高,为该任务所赋予的优先级就愈高, 以使之优先执行。
      • 松弛度例子
        • 例如,一个任务在200ms时必须完成,而它本身所需的运行时间就有100ms,因此,调度程序必须在100 ms之前调度执行,该任务的紧急程度(松弛程度)为100 ms
    • 优先级倒置(Priority inversion problem)
      • 优先级倒置的形成
        • 高优先级进程被低优先级进程延迟或阻塞。
      • 优先级倒置的解决方法
        • 简单的:假如进程P3在进入临界区后P3所占用的处理机就不允许被抢占
        • 实用的:建立在动态优先级继承基础上的

    死锁概述

    • 资源问题
      • 可重用性资源
        • 计算机外设
      • 消耗性资源
        • 数据,消息
      • 可抢占性资源
        • 不引起死锁
        • CPU,内存
      • 不可抢占性资源
        • 光驱,打印机
    • 计算机系统中的死锁
      • 竞争不可抢占性资源引起死锁
      • 竞争可消耗资源引起死锁
      • 进程推进顺序不当引起死锁
    • 死锁的定义,必要条件和处理方法
      • 定义:如果一组进程中的每一个进程都在等待仅由该进程中的其他进程才能引发的事件,那么该组进程是死锁的
      • 产生死锁的必要条件
        • 互斥条件
        • 请求和保存条件
        • 不可抢占条件
        • 循环等待条件
          • 如果每个资源只有一个实例,则环路等待条件是死锁存在的充分必要条件
      • 处理死锁的方法
        • 预防死锁
          • 静态方法,在进程执行前采取的措施,通过设置某些限制条件,去破坏产生死锁的四个条件之一,防止发生死锁。
          • 预防死锁的策略
            • 破坏"请求和保存"条件
              • 第一种协议
                • 所有进程在开始运行之前,必须一次性地申请其在整个运行过程中所需的全部资源
                • 优点:简单,易行,安全
                • 缺点
                  • 资源被严重浪费,严重地恶化了资源的利用率
                  • 使进程经常会发生饥饿现象
              • 第二种协议
                • 它允许一个进程只获得运行初期所需的资源后,便开始运行。进程运行过程中再逐步释放已分配给自己的,且已用毕的全部资源,然后再请求新的所需资源
            • 破坏"不可抢占"条件
              • 当一个已经保存了某些不可被抢占资源的进程,提出新的资源请求而不能得到满足时,它必须释放已经保持的所有资源,待以后需要时再重新申请
            • 破坏"循环等待"条件
              • 对系统所以资源类型进行线性排序,并赋予不同的序号
              • 例如令输入机的序号为1,打印机序号为2,磁盘机序号为3等。所有进程对资源的请求必须严格按资源序号递增的次序提出。
        • 避免死锁
          • 动态的方法,在进程执行过程中采取的措施,不需事先采取限制措施破坏产生死锁的必要条件,而是在进程申请资源时用某种方法去防止系统进入不安全状态,从而避免发生死锁。如银行家算法
          • 避免死锁的策略
            • 系统安全状态
              • 安全状态
                • 某时刻,对于并发执行的n个进程,若系统能够按照某种顺序如<p1,p2…pn>来为每个进程分配所需资源,直至最大需求,从而使每个进程都可顺利完成,则认为该时刻系统处于安全状态,这样的序列为安全序列
              • 安全状态之例
              • 由安全状态向不安全状态的转换
            • 利用银行家算法避免死锁
              • 含义:每一个新进程在进入系统时,它必须申明在运行过程中,可能需要每种资源类型的最大单元数目,其数目不应超过系统所拥有的资源总量。当进程请求一组资源时,系统必须首先确定是否有足够的资源分配给该进程。若有,再进一步计算在将这些资源分配给进程后,是否会使系统处于不安全状态。如果不会,才将资源分配给它,否则让进程等待
              • 银行家算法中的数据结构
                • 可用资源向量 Available[m]:m为系统中资源种类数,Available[j]=k表示系统中第j类资源数为k个。
                • 最大需求矩阵 Max[n,m]:n为系统中进程数,Max[i,j]=k表示进程i对j类资源的最大需求数为中k。
                • 分配矩阵 Allocation[n,m]:它定义了系统中每一类资源当前已分配给每一进程资源数, Allocation[i,j] = k表示进程i已分得j类资源的数目为k个。
                • 需求矩阵 Need[n,m]:它表示每个进程尚需的各类资源数,Need[i,j]=k 表示进程i 还需要j类资源k个。Need[i,j]=Max[i,j] - Allocation[i,j]
              • 银行家算法
              • 安全性算法
              • 银行家算法之例
              • 解题
                • 矩阵
                • 列表
        • 检测死锁
          • 死锁的检测与解除
            • 死锁的检测
              • 资源分配图
                • 简化步骤
                  • 选择一个没有阻塞的进程p
                  • 将p移走,包括它的所有请求边和分配边
                  • 重复步骤1,2,直至不能继续下去
              • 死锁定理
                • 若一系列简化以后不能使所有的进程节点都成为孤立节点
              • 检测时机
                • 当进程等待时检测死锁 (其缺点是系统的开销大)
                • 定时检测
                • 系统资源利用率下降时检测死锁
              • 死锁检测中的数据结构
            • 死锁的解除
              • 抢占资源
              • 终止(或撤销)进程
              • 终止进程的方法
                • 终止所有死锁进程
                • 逐个终止进程
                  • 代价最小
                    • 进程的优先级的大小
                    • 进程已执行了多少时间,还需时间
                    • 进程在运行中已经使用资源的多少,还需多少资源
                    • 进程的性质是交互式还是批处理的
              • 付出代价最小的死锁解除算法
                • 是使用一个有效的挂起和解除机构来挂起一些死锁的进程
        • 解除死锁

    第四章:存储器管理

    存储器的层次结构

    • 多层结构的存储系统
      • 存储器的多层结构
        • CPU寄存器
        • 主存
        • 辅存
      • 可执行存储器
        • 寄存器和主存的总称
        • 访问速度快,进程可以在很少的时钟周期内用一条load或store指令完成存取。
    • 主存储器与寄存器
    • 高速缓存和磁盘缓存

    程序的装入和链接

    • 步骤
      • 编译
        • 源程序 ->目标模块(Object modules)--------Compiler
          • 由编译程序对用户源程序进行编译,形成若干个目标模块
      • 链接
        • 一组目标模块 ->装入模块 (Load Module)----------Linker
          • 由链接程序将编译后形成的一组目标模板以及它们所需要的库函数链接在一起,形成一个完整的装入模块
      • 装入
        • 装入模块 ->内存 --------Loader
          • 由装入程序将装入模块装入内存
    • 程序的装入
      • 绝对装入方式
        • 在编译时,如果知道程序将驻留在内存中指定的位置。编译程序将产生绝对地址的目标代码。
      • 可重定位装入方式
        • 在可执行文件中,列出各个需要重定位的地址单元和相对地址值。当用户程序被装入内存时,一次性实现逻辑地址到物理地址的转换,以后不再转换(一般在装入内存时由软件完成)。
        • 优点:不需硬件支持,可以装入有限多道程序。
        • 缺点:一个程序通常需要占用连续的内存空间,程序装入内存后不能移动。不易实现共享。
      • 动态运行时的装入方式
        • 动态运行时的装入程序在把装入模块装入内存后,并不立即把装入模块中的逻辑地址转换为物理地址,而是把这种地址转换推迟到程序真正要执行时才进行
        • 优点:
          • OS可以将一个程序分散存放于不连续的内存空间,可以移动程序,有利用实现共享。
          • 能够支持程序执行中产生的地址引用,如指针变量(而不仅是生成可执行文件时的地址引用)。
        • 缺点:需要硬件支持,OS实现较复杂。
        • 它是虚拟存储的基础。
    • 程序的链接
      • 静态链接方式(lib)
      • 装入时动态链接
      • 运行时动态链接(dll)

    连续分配存储管理方式

    • 连续分配
      • 单一连续分配(DOS)
      • 固定分区分配(浪费很多空间)
      • 动态分区分配
    • 地址映射和存储保护措施
      • 基址寄存器:程序的最小物理地址
      • 界限寄存器:程序的逻辑地址范围
      • 物理地址 = 逻辑地址 + 基址
    • 内碎片:占用分区之内未被利用的空间
    • 外碎片:占用分区之间难以利用的空闲分区(通常是小空闲分区)
    • 把内存划分为若干个固定大小的连续分区。固定式分区又称为静态分区。
      • 分区大小相等:只适合于多个相同程序的并发执行(处理多个类型相同的对象)。
      • 分区大小不等:多个小分区、适量的中等分区、少量的大分区。根据程序的大小,分配当前空闲的、适当大小的分区。
      • 优点:无外碎片、易实现、开销小。
      • 缺点:
        • 存在内碎片,造成浪费
        • 分区总数固定,限制了并发执行的程序数目。
        • 通用Os很少采用,部分控制系统中采用
    • 动态创建分区:指在作业装入内存时,从可用的内存中划出一块连续的区域分配给它,且分区大小正好等于该作业的大小。可变式分区中分区的大小和分区的个数都是可变的,而且是根据作业的大小和多少动态地划分。
      • 基于顺序搜索的动态分区分配算法
        • 首次适应算法(first fit,FF)
          • 顺序找,找到一个满足的就分配,但是可能存在浪费
          • 这种方法目的在于减少查找时间。
          • 空闲分区表(空闲区链)中的空闲分区要按地址由低到高进行排序
        • 循环首次适应算法(next fit,NF)
          • 相对上面那种,不是顺序,类似哈希算法中左右交叉排序
          • 空闲分区分布得更均匀,查找开销小
          • 从上次找到的空闲区的下一个空闲区开始查找,直到找到第一个能满足要求的的空闲区为止,并从中划出一块与请求大小相等的内存空间分配给作业。
        • 最佳适应算法(best fit,BF)
          • 找到最合适的,但是大区域的访问次数减少
          • 这种方法能使外碎片尽量小。
          • 空闲分区表(空闲区链)中的空闲分区要按大小从小到大进行排序,自表头开始查找到第一个满足要求的自由分区分配。
        • 最坏适应算法(worst fit,WF)
          • 相对于最好而言,找最大的区域下手,导致最大的区域可能很少,也造成许多碎片
          • 空闲分区按大小由大到小排序
      • 基于索引搜索的动态分区分配算法
        • 快速适应算法(quick fit)
        • 伙伴系统(buddy system)
        • 哈希算法
      • 动态可重定位分区分配
        • 紧凑
        • 动态重定位
          • 动态运行时装入,地址转化在指令执行时进行,需获得硬件地址变换机制的支持
          • 内存地址=相对地址+起始地址
        • 动态重定位分区分配算法
          • 1、在某个分区被释放后立即进行紧凑,系统总是只有一个连续的分区而无碎片,此法很花费机时。
          • 2、当“请求分配模块”找不到足够大的自由分区分给用户时再进行紧凑,这样紧缩的次数比上种方法少得多,但管理复杂。采用此法的动态重定位分区分配算法框图如下:
      • 优点:没有内碎片。
      • 缺点:外碎片。

    对换(了解)

    • 系统把所有的作业放在外存,每次只调用一个作业进入内存运行,当时间片用完时,将它调至外存后备队列上等待,在从后备队列调入另一个作业进入内存运行。

    基本分页存储管理方式

    • 分页存储管理的基本方式
      • 页面
        • 将一个进程的逻辑地址空间分成若干个大小相等的片
      • 页框(frame)
        • 内存空间分成与页面相同大小的存储块
      • 由于进程的最后一页经常装不满一块而形成了不可利用的碎片,称之为“页内碎片”
      • 地址结构
        • 页号P+位移量W(0-31)
      • 页表
        • 在分页系统中,允许将进程的各个页离散地存储在内存在内存的任一物理块中,为保证进程仍然能够正确地运行,即能在内存中找到每一个页面所对应的物理块,系统又为每个进程建立了一张页面映像表,简称页表
        • 页表的作用是实现从页面号到物理块号的地址映射
    • 地址变换机构
      • 基本的地址变换机构
        • 要访问两次内存
        • 页表大都驻留在内存中
        • 为了实现地址变换功能,在系统中设置页表寄存器(PTR),用来存放页表的始址和页表的长度。
        • 在进程未执行时,每个进程对应的页表的始址和长度存放在进程的PCB中,当该进程被调度时,就将它们装入页表寄存器。
      • 具有快表的地址变换机构
        • 提高了效率,此处会有计算题
        • 如果页表存放在内存中,则每次访问内存时,都要先访问内存中的页表,然后根据所形成的物理地址再访问内存。这样CPU存一个数据必须访问两次内存,从而使计算机的处理速度降低了1/2。
        • 为了提高地址变换的速度,在地址变换机构中增设了一个具有并行查询功能的特殊的高速缓冲存储器,称为“联想存储器”或“快表”,用以存放当前访问的那些页表项。
        • 地址变换过程为:
          • 1、CPU给出有效地址
          • 2、地址变换机构自动地将页号送入高速缓存,确定所需要的页是否在快表中。
          • 3、若是,则直接读出该页所对应的物理块号,送入物理地址寄存器;
          • 4、若快表中未找到对应的页表项,则需再访问内存中的页表
          • 5、找到后,把从页表中读出的页表项存入快表中的一个寄存器单元中,以取代一个旧的页表项。
    • 两级和多级页表
      • 主要是有的时候页表太多了,要化简
      • 格式:外层页号P1+外层页内地址P2+页内地址d
      • 基本方法:将页表进行分页,每个页面的大小与内存物理块的大小相同,并为它们进行编号,可以离散地将各个页面分别存放在不同的物理块中。
    • 反置页表
      • 反置页表为每一个物理块(页框)设置一个页表项,并按物理块排序,其内容则是页号和其所属进程的标识。
    • 优点:
      • 没有外碎片,每个内碎片不超过页大小。
      • 一个程序不必连续存放。
      • 便于改变程序占用空间的大小。即随着程序运行而动态生成的数据增多,地址空间可相应增长。
    • 缺点:程序全部装入内存。

    分段存储管理方式

    • 引入
      • 方便编程
      • 信息共享
      • 动态增长
      • 动态链接
    • 在分段存储管理方式中,作业的地址空间被划分为若干个段,每个段是一组完整的逻辑信息,每个段都有自己的名字,都是从零开始编址的一段连续的地址空间,各段长度是不等的。
    • 内存空间被动态的划分为若干个长度不相同的区域,称为物理段,每个物理段由起始地址和长度确定
    • 分段系统的基本原理
      • 分段
        • 格式:段号+段内地址
      • 段表
        • 段表实现了从逻辑段到物理内存区的映射。
      • 地址变换机构
    • 和分页的区别
      • 页是信息的物理单位
      • 页的大小固定且由系统固定
      • 分页的用户程序地址空间是一维的
      • 通常段比页大,因而段表比页表短,可以缩短查找时间,提高访问速度。
      • 分页是系统管理的需要,分段是用户应用的需要。一条指令或一个操作数可能会跨越两个页的分界处,而不会跨越两个段的分界处。
    • 信息共享
      • 这是分段最重要的优点
    • 段页式存储管理方式
      • 基本原理
        • 格式:段号(S)+段内页号(P)+页内地址(W)
      • 地址变换过程
        • 需要三次访问过程
      • 在段页式系统中,为了获得一条指令或数据,需三次访问内存:第一次访问内存中的段表,从中取得页表始址;第二次访问内存中的页表,从中取出该页所在的物理块号,并将该块号与页内地址一起形成指令或数据的物理地址;第三次访问才是真正根据所得的物理地址取出指令或数据。

    第五章:虚拟存储器

    常规存储管理方式的特征

    • 一次性
    • 驻留性

    局部性原理

    • 程序在执行时将呈现出局部性特征,即在一较短的时间内,程序的执行仅局限于某个部分,相应地,它所访问的存储空间也局限于某个区域
    • 时间局限性
      • 如果程序中的某条指令一旦执行, 则不久以后该指令可能再次执行;如果某数据被访问过, 则不久以后该数据可能再次被访问。产生时间局限性的典型原因,是由于在程序中存在着大量的循环操作
    • 空间局限性
      • 一旦程序访问了某个存储单元,在不久之后,其附近的存储单元也将被访问,即程序在一段时间内所访问的地址,可能集中在一定的范围之内,其典型情况便是程序的顺序执行。

    定义

    • 指具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储器系统

    优点

    • 大程序:可在较小的可用内存中执行较大的用户程序;
    • 大的用户空间:提供给用户可用的虚拟内存空间通常大于物理内存(real memory)
    • 并发:可在内存中容纳更多程序并发执行;
    • 易于开发:不必影响编程时的程序结构
    • 以CPU时间和外存空间换取昂贵内存空间,这是操作系统中的资源转换技术

    特征

    • 离散性
      • 指在内存分配时采用离散的分配方式,它是虚拟存储器的实现的基础
    • 多次性
      • 指一个作业被分成多次调入内存运行,即在作业运行时没有必要将其全部装入,只须将当前要运行的那部分程序和数据装入内存即可。多次性是虚拟存储器最重要的特征
    • 对换性
      • 指允许在作业的运行过程中在内存和外存的对换区之间换进、换出。
    • 虚拟性
      • 指能够从逻辑上扩充内存容量,使用户所看到的内存容量远大于实际内存容量。

    虚拟存储器的实现方式

    • 请求分页存储管理方式
      • 硬件
        • 请求页表机制
          • 格式:页号+物理块号+状态位P+访问字段A+修改位M+外存地址
        • 缺页中断机构
        • 地址变换机构(过程图很关键)
      • 请求分页中的内存分配
        • 最小物理块数
          • 即能保证进程正常运行所需的最小物理块数
        • 内存分配策略
          • 固定分配局部置换(国王的大儿子)
          • 可变分配全局置换(国王的二儿子)
          • 可变分配局部置换(国王的小儿子)
      • 物理块分配算法
        • 平均分配算法
        • 按比例分配算法
        • 考虑优先权的分配算法
      • 页面调入策略
        • 系统应在何时调入所需页面
          • 预调页策略(不能实现)
          • 请求调页策略(需要才给)
        • 系统应该从何处调入这些页面
          • 对换区
          • 文件区
        • 页面调入过程
        • 缺页率(出计算题)
    • 请求分段系统
      • 硬件
        • 请求分段的段表机构
        • 缺段中断机构
        • 地址变换机构

    页面置换算法

    • 抖动的概念
      • 即刚被换出的页很快又要被访问,需要将它重新调入,此时又需要再选一页调出
    • 最佳置换算法(需要预知后面进程,所以不能实现)
    • 先进先出页面置换算法(FIFO)
      • 选择在内存中驻留时间最久的页面予以淘汰
    • 最近最久未使用置换算法(LRU)Recently
      • 寄存器支持
      • 特殊的栈结构
    • 最少使用置换算法(LFU)Frequently
    • clock置换算法(对访问位A的判断)
      • 改进型——增加对修改位M思维判断
    • 页面缓冲算法(PBA,page buffering algorithm)
      • 空闲页面链表
      • 修改页面链表

    第六章:输入输出系统

    I/O系统的功能,模型和接口

    • I/O系统管理的对象是I/O设备和相应的设备控制器。
    • I/O系统的基本功能
      • 隐藏物理设备的细节
      • 与设备的无关性
      • 提高处理机和I/O设备的利用率
      • 对I/O设备进行控制
      • 确保对设备的正确共享
      • 错误处理
    • I/O软件的层次结构
      • 用户层I/O软件
      • 设备独立性软件
      • 设备驱动程序(厂家开发)
      • 中断处理程序
      • 硬件
    • I/O系统的分层
      • 中断处理程序
      • 设备驱动程序
      • 设备独立性软件
    • I/O系统接口
      • 块设备接口
        • 指以数据块为单位来组织和传送数据信息的设备
        • 典型的块设备是磁盘、光盘
        • 块设备的基本特征
          • ①传输速率较高,通常每秒钟为几兆位;
          • ②它是可寻址的,即可随机地读/写任意一块;
          • ③磁盘设备的I/O采用DMA方式。
      • 流设备接口
        • 又称字符设备指以单个字符为单位来传送数据信息的设备
        • 这类设备一般用于数据的输入和输出,有交互式终端、打印机
        • 字符设备的基本特征
          • ①传输速率较低;
          • ②不可寻址,即不能指定输入时的源地址或输出时的目标地址;
          • ③字符设备的I/O常采用中断驱动方式。
      • 网络通信接口
        • 提供网络接入功能,使计算机能通过网络与其他计算机进行通信或上网浏览。

    I/O设备和设备控制器

    • 分类
      • 使用特性分
        • 存储设备
        • I/O设备
      • 传输速率分
        • 低速设备(几字节——几百字节)
          • 典型的设备有键盘、鼠标、语音的输入
        • 中速设备(数千——数万字节)
          • 典型的设备有行式打印机、激光打印机
        • 高速设备(数十万——千兆字节)
          • 典型的设备有磁带机、磁盘机、光盘机
    • 设备并不是直接与CPU进行通信,而是与设备控制器通信。在设备与设备控制器之间应该有一个接口。
      • 数据信号:控制器 ← 设备 ← 控制器
        • 传送数据信号,输入、输出bit
      • 控制信号: 控制器 → 设备
        • 执行读、写操作的信号
      • 状态信号:设备当前使用状态
    • 设备控制器
      • 主要功能:控制一个或多个I/O设备,以实现I/O设备和计算机之间的数据交换
      • 基本功能
        • 接收和识别命令
          • 控制寄存器、命令译码器
        • 数据交换
          • 实现CPU与控制器,控制器与设备间的数据交换
        • 标识和报告设备的状态
        • 地址识别
          • 配置地址译码器,识别不同的设备
        • 数据缓冲区
        • 差错控制
      • 设备控制器的组成
        • 设备控制器与处理机(CPU)的接口
          • 实现CPU与设备控制器之间的通信
        • 设备控制器与设备的接口
          • 控制器可连接多个设备
        • I/O逻辑
          • 实现对设备的控制
          • CPU利用该逻辑向控制器发送I/O命令
          • 命令、地址译码
    • 内存映像I/O
      • 驱动程序将抽象I/O命令转换出的一系列具体的命令,参数等数据装入设备控制器的相应寄存器,由控制器来执行这些命令,具体实施对I/O设备的操作
    • I/O通道
      • 目的:建立独立的I/O操作(组织, 管理和结束),使由CPU处理的I/O工作转由通道完成(解放CPU,实现并行)

      • 什么是I/O通道?

        • 是一种特殊的处理机,具有通过执行通道程序完成I/O操作的指令
        • 特点:指令单一(局限于与I/O操作相关的指令),与CPU共享内存
      • 基本过程:

        • CPU向通道发出I/O指令->通道接收指令->从内存取出通道程序处理I/O->向CPU发出中断
      • 通道类型

        • 字节多路通道
          • 低中速连接子通道时间片轮转方式共享主通道
          • 字节多路通道不适于连接高速设备,这推动了按数组方式进行数据传送的数组选择通道的形成。
        • 数组选择通道
          • 这种通道可以连接多台高速设备,但只含有一个分配型子通道,在一段时间内只能执行一道通道程序, 控制一台设备进行数据传送, 直至该设备传送完毕释放该通道。这种通道的利用率很低。
        • 数组多路通道
          • 含有多个非分配型子通道,前两种通道的组合,通道利用率较好
      • 瓶颈问题

        • 原因;通道不足
        • 解决办法:增加设备到主机间的通路,而不增加通道(结果类似RS触发器)

    中断机构和中断处理程序

    • 中断
      • 分类
        • 中断(外部触发)
          • 对外部I/O设备发出的中断信号的响应
        • 陷入(内部原因:除0)
          • 由CPU内部事件引起的中断
      • 中断向量表(类比51单片机)
        • 中断程序的入口地址表
      • 中断优先级
        • 对紧急程度不同的中断处理方式
      • 对多中断源的处理方式
        • 屏蔽中断
        • 嵌套中断
    • 中断处理程序
      • 测定是否有未响应的中断信号
      • 保护被中断进程的CPU环境
      • 转入相应的设备处理程序
      • 中断处理
      • 恢复CPU 的现场并退出中断

    设备驱动程序

    • 是I/O进程与设备控制器之间的通信程序,又由于它常以进程的形式存在,故以后就简称为设备驱动进程
    • 主要任务是接受来自它上一层的与设备无关软件的抽象请求,并执行这个请求。
    • 功能
        1. 接收由I/O进程发来的命令和参数, 并将命令中的抽象要求转换为具体要求。例如,将磁盘块号转换为磁盘的盘面、 磁道号及扇区号。
        1. 检查用户I/O请求的合法性,了解I/O设备的状态,传递有关参数,设置设备的工作方式。
        1. 发出I/O命令,如果设备空闲,便立即启动I/O设备去完成指定的I/O操作;如果设备处于忙碌状态,则将请求者的请求块挂在设备队列上等待。
        1. 及时响应由控制器或通道发来的中断请求,并根据其中断类型调用相应的中断处理程序进行处理。
        1. 对于设置有通道的计算机系统,驱动程序还应能够根据用户的I/O请求,自动地构成通道程序。
    • 设备驱动程序的处理过程
      • 将用户和上层软件对设备控制的抽象要求转换成对设备的具体要求,如对抽象要求的盘块号转换为磁盘的盘面、磁道及扇区。
      • 检查I/O请求的合理性。
      • 读出和检查设备的状态,确保设备处于就绪态。
      • 传送必要的参数,如传送的字节数,数据在主存的首址等。
      • 工作方式的设置。
      • 启动I/O设备,并检查启动是否成功,如成功则将控制返回给I/O控制系统,在I/O设备忙于传送数据时,该用户进程把自己阻塞,直至中断到来才将它唤醒,而CPU可干别的事。
    • 对I/O设备的控制方式
      • I/O控制的宗旨
        • 减少CPU对I/O控制的干预
        • 充分利用CPU完成数据处理工作
      • I/O 控制方式
        • 轮询的可编程I/O方式
        • 中断驱动I/O方式
        • DMA控制方式
        • I/O通道控制方式
    • DMA控制器组成
      • 主机与DMA控制器的接口
      • DMA控制器与块设备的接口
      • I/O控制逻辑

    与设备无关的I/O软件

    • 基本概念
      • 含义: 应用程序独立于具体使用的物理设备。
      • 驱动程序是一个与硬件(或设备)紧密相关的软件。为实现设备独立性,须在驱动程序上设置一层软件,称为设备独立性软件。
      • 设备独立性(Device Independence)的优点
        • 以物理设备名使用设备
        • 引入了逻辑设备名
        • 逻辑设备名称到物理设备名称的转换(易于实现I/O重定向)
    • 与设备无关的软件
      • 设备驱动程序的统一接口
      • 缓存管理
      • 差错控制
      • 对独立设备的分配与回收
      • 独立于设备的逻辑数据块
    • 设备分配中的数据结构
      • 设备控制表DCT
      • 控制器控制表COCT
      • 通道控制表CHCT
      • 显然,在有通道的系统中,一个进程只有获得了通道,控制器和所需设备三者之后,才具备了进行I/O操作的物理条件
      • 系统设备表SDT
      • 逻辑设备表LUT
      • 分配的流程,从资源多的到资源紧张的:LUT->SDT->DCT->COCT->CHCT
      • 在申请设备的过程中,根据用户请求的I/O设备的逻辑名,查找逻辑设备和物理设备的映射表;以物理设备为索引,查找SDT,找到该设备所连接的DCT;继续查找与该设备连接的COCT和CHCT,就找到了一条通路。

    用户层的I/O软件

    • 系统调用与库函数
      • OS向用户提供的所有功能,用户进程都必须通过系统调用来获取
      • 在C语言以及UNIX系统中,系统调用(如read)与各系统调用所使用的库函数(如read)之间几乎是一一对应的。而微软的叫Win32API
    • 假脱机系统(spooling)
      • spooling技术是对脱机输入/输出系统的模拟
      • 主要组成
        • 输入/输出井
        • 输入/输出缓冲区
        • 输入/输出进程
        • 井管理程序
      • 特点(体现操作系统的虚拟性)
        • 提高了I/O的速度
          • 对数据所进行的I/O操作,已从对低速设备演变为对输入井或输出井中的数据存取。
        • 将独占设备改造为共享设备
          • 实际分给用户进程的不是打印设备,而是共享输出井中的存储区域
        • 实现了虚拟设备功能
          • 将独占设备变成多台独占的虚拟设备。

    缓冲区管理

    • 缓冲的引入(原因)
      • 缓和CPU与I/O设备间速度不匹配的矛盾
      • 减少对CPU的中断频率,放宽对CPU中断响应时间的限制
      • 提高CPU和I/O设备之间的并行性
      • 解决数据粒度不匹配的问题
    • 单缓冲区
      • 即在CPU计算的时候,将数据数据输入到缓冲区(大小取决与T和C的大小)
    • 双缓冲区
      • 即允许CPU连续工作(T不断)
    • 环形缓冲区(专为生产者和消费者打造)
      • 组成
        • 多个缓冲区
        • 多个指针
      • 使用
        • Getbuf过程
        • Releasebuf过程
      • 同步问题
    • 缓冲池(理解为更大的缓冲区)
      • 组成
        • 空白缓冲队列(emq)
          • 由空缓冲区链接而成F(emq),L(emq)分别指向该队列首尾缓冲区
        • 输入队列(inq)
          • 由装满输入数据的缓冲区链接而成F(inq),L(inq)分别指向该队列首尾缓冲区
        • 输出队列(outq)
          • 由装满输出数据的缓冲区链接而成F(outq), L(outq)分别指向该队列首尾缓冲
      • Getbuf和Putbuf过程
        • 收容:缓冲池接收外界数据
        • 提取:外界从缓冲池获得数据
      • 缓冲区工作方式(从缓冲区的角度来看)
        • 收容输入
        • 提取输入
        • 收容输出
        • 提取输出

    磁盘存储器的性能和调度

    • 数据的组织和格式
    • 磁盘的类型
      • 固定头磁盘(贵)
      • 移动头磁盘
    • 磁盘访问的时间(关键)
      • 寻道时间Ts=m*n+s
      • 旋转延迟时间Tr
      • 传输时间Tt=b/rN
      • 总时间Ta=Ts+1/2r+b/rN
    • 磁盘的调度算法(掌握图表)
      • 先来先服务(FCFS)
        • 优点:公平,简单
        • 缺点:可能导致某些进程的请求长期得不到满足
      • 最短寻道时间优先(SSTF)
        • 说明:要求访问的磁道和当前磁头所在的磁道距离最近,以使每次的寻道时间最短
      • 扫描算法(SCAN)
        • 扫描算法不仅考虑到欲访问的磁道与当前磁道间的距离,更优先考虑的是磁道当前的移动方向
        • 联想电梯的运行
        • 可防止低优先级进程出现“饥饿”的现象
      • 循环扫描算法(CSCAN)
        • 算法规定磁头单向移动,例如,只是自里向外移动,当磁头移到最外的磁道并访问后,磁头立即返回到最里的欲访问磁道,亦即将最小磁道号紧接着最大磁道号构成循环,进行循环扫描
      • NStepScan算法
        • N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列,磁盘调度将按FCFS算法依次这些子队列。
      • FSCAN算法
        • 是Nstepscan算法的简化,将磁盘请求队列分成两个子队列

    第七章:文件管理

    数据项

    • 基本数据项
    • 组合数据项

    记录

    • 记录是一组相关数据项的集合,用于描述一个对象在某个方面的属性

    文件

    • 文件类型
    • 文件长度
    • 文件的物理位置
    • 文件的建立时间

    文件操作

    • 创建文件
    • 删除文件
    • 读文件
    • 写文件
    • 设置文件读写的位置

    文件的逻辑结构

    • 顺序文件
    • 记录寻址
    • 索引文件
    • 索引顺序文件
    • 直接文件和哈希文件

    文件目录

    • 文件控制块(FCB)
      • 文件名+inode(属性)
    • 简单的文件目录
      • 单级文件目录
        • 查找慢
        • 不允许重名
        • 不便于实现文件共享
      • 两级文件目录
        • 提高检索速度,从M*N到M+N
    • 树形结构目录
      • 路径名
        • “…”是父目录
        • “/”是根目录
        • 区别绝对路径和相对路径(…/…/…/1/2/3/)

    文件共享

    • 有向无循环图(DAG)
    • 利用符号链接实现文件共享
      • 实际上就是“快捷方式”

    文件保护

    操作系统思维导图图片

    思维导图下载地址

    github:希望大家可以给一个star,谢谢支持

    码云:希望大家可以给一个star,谢谢支持

    展开全文
  • 本资源是计算机操作系统(第四版)汤小丹著,第四版 欢迎下载
  • 计算机操作系统知识梳理

    千次阅读 多人点赞 2018-04-02 00:28:34
    1、进程和线程以及它们的区别(1)进程是对运行时程序的封装,是系统进行资源调度和分配的基本单位,实现操作系统的并发。(2)线程是进程的子任务,是CPU调度和分派的基本单位,用于保证程序的实时性,实现进程内部的...

    1、进程和线程以及它们的区别

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

    (2)线程是进程的子任务,是CPU调度和分派的基本单位,用于保证程序的实时性,实现进程内部并发。

    (3)一个程序至少有一个进程,一个进程至少有一个线程,线程依赖进程的存在。

    (4)进程执行过程中拥有独立的内存单元,而多个线程共享进程的内存。

    2、进程间的通信的几种方式

    (1)管道(pipe)及命名管道(named pipe:管道可用于具有亲缘关系的父子进程间通信,命名管道除了具有管道所具有功能外,还允许无亲缘关系进程的通信。

    (2)信号signal):是一种比较复杂的通信方式,用于通知接收进程某个事件已经发生。

    (3)消息队列:是消息的链接表,克服上两种通信方式中信号量有限的缺点,具有写权限的进程可以按照一定规则向消息队列中添加新信息;对消息队列有读权限得进程则可以从消息队列中读取信息。

    (4)共享内存:最有用的进程间通信方式。它使得多个进程可以访问同一块内存空间,不同进程可以及时看到对方进程中对共享内存中数据的更新。这种方式需要依靠某种同步操作,如互斥锁和信号量等。

    (5)信号量:主要作为进程之间及同一种进程的不同线程之间的同步和互斥手段。

    (6)套接字:这是一致性更为一般进程间通信机制,它可用网络中不同机器之间进程间通信,应用非常广泛。

    3、线程同步的方式

    1互斥量Synchronized/lock:采用互斥对象机制,只有拥有互斥对象的线程才有访问公共资源的权限,因为互斥对象只有一个,所以可以保证公共资源不会被多个线程同时访问。

    2)信号量Semaphore它允许同一时刻多个线程访问同一资源,但需要控制同一时刻访问此资源的最大线程数。

    3)事件(信号),Wait/Notify:通过通知操作的方式来保存多线程同步,还可以方便的实现多线程优先级比较操作。

    4、什么是死锁?死锁产生的条件?

    4.1死锁的概念:

    在两个或者多个并发进程中,如果每个进程持有某种资源而又等待其它进程释放它或它们现在保持着的资源,在未改变这种状态之前都不能向前推进,称这一组进程产生了死锁。通俗讲,就是两个或者多个进程无限期的阻塞、相互等待的一种状态。

    4.2死锁产生的四个必要条件

    1)互斥:至少有一个资源必须属于非共享模式,即一次只能被一个进程使用;若其他申请使用该资源,那么申请进程必须等到该资源被释放为止;

    2)占用并等待:一个进程必须占有至少一个资源,并等待另一个资源,而该资源为其他进程所占有;

    3)非抢占;进程不能被抢占,即资源只能被进程在完成任务后资源释放。

    4)循环等待:若干进程之间形成一种头尾相接的环形等待资源关系。

    4.3死锁处理的基本策略和常用方法

    解决死锁的基本方法主要有:预防死锁,避免死锁,检测死锁,解除死锁等思想。

    (1)死锁预防

    死锁预防基本思想:只要确保死锁发生的四个必要条件至少有一个不成立,就能预防死锁。

    ①打破互斥条件:允许进程同时访问某些资源。但是,有些资源是不能被多个进程所共享的,这是由资源本身属性所决定的,因此,这种办法通常并无实用价值。

    ②打破占用并等待条件:可以实行资源预先分配策略(进程在运行前一次性向系统申请它所需要的全部资源,若所需全部资源得不到满足,则不分配任何资源,此进程暂不运行;只有当系统能满足当前进程所需的全部资源时,才一次性将所申请资源全部分配给该线程)或者只允许进程在没有占用资源时才可以申请资源(一个进程可申请一些资源并使用它们,但是在当前进程申请更多资源之前,它必须全部释放当前所占有的资源)。但是这种策略也存在一些缺点:在很多情况下,无法预知一个进程执行前所需的全部资源,因为进程是动态执行的,不可预知的;同时,会降低资源利用率,导致降低了进程的并发性。

    ③打破非枪占条件:允许进程强行从占有者哪里夺取某些资源,也就是说,但一个进程占有了一部分资源,在其申请新的资源且得不到满足时,它必须释放所有占有的资源以便让其它线程使用。这种预防死锁的方式实现起来困难会降低系统性能。

    ④打破循环等待条件:实行资源有序分配策略。对所有资源排序编号,所有进程对资源的请求必须严格按资源序号递增的顺序提出,即只有占用了小号资源才能申请大号资源,这样就不回产生环路,预防死锁的发生。

    (2)死锁避免

    死锁避免的基本思想是动态检测资源分配状态,以确保循环等待条件不成立,从而确保系统处于安全状态。所谓安全状态是指:如果系统能按某个顺序为每个进程分配资源(不超过其最大值),那么系统状态是安全的,换句话说就是,如果存在一个安全序列,那么系统处于安全状态。资源分配图算法和银行家算法是两种经典的死锁避免的算法,其可以确保系统始终处于安全状态。其中,资源分配图算法应用场景为每种资源类型只有一个实例(申请边,分配边,需求边,不形成环才允许分配),而银行家算法应用于每种资源类型可以有多个实例的场景。

    (3)死锁解除

    死锁解除的两种常用方法为进程终止和资源抢占。所谓进程终止是指简单地终止一个或多个进程以打破循环等待,分终止所有死锁进程、一次只终止一个进程直到取消死锁循环为止。所谓资源抢占就是指从一个或多个死锁进程哪里抢占一个或多个资源,此时需考虑三问题

    ①选择一个牺牲品。

    ②回滚到安全状态

    ③饥饿(在代价因素中加上回滚次数,回归的越多则越不可能作为牺牲品,避免一个进程总是被回滚)。

    5、进程有哪几种状态?

    1)就绪状态:进程已获得除处理机以外的所需资源,等待分配处理机资源;

    2)运行状态:占用处理机资源运行,处于此状态的进程数小于等于CPU数;

    3)阻塞状态:进程等待某种条件,在条件满足之前无法执行;

     

    6、线程有几种状态?

    Java虚拟机 中,线程从最初的创建到最终的消亡,要经历若干个状态:创建(new)、就绪(runnable/start)、运行(running)、阻塞(blocked)、等待(waiting)、时间等待(time waiting) 和 消亡(dead/terminated)。

     

     


    7、分页和分段有什么区别(内存管理)?

    段式存储管理是一种符合用户视角的内存分配管理方案。在段式存储管理中,将程序的地址空间划分为若干段(segment),如代码段,数据段,堆栈段;这样每个进程有一个二维地址空间,相互独立,互不干扰。段式管理的优点是:没有内碎片(因为段大小可变,改变段大小来消除内碎片)。但段换入换出时,会产生外碎片(比如4k的段换5k的段,会产生1k的外碎片)。

    页式存储管理方案是一种用户视角内存与物理内存相分离的内存分配管理方案。在页式存储管理中,将程序的逻辑地址划分为固定大小的页(page),而物理内存划分为同样大小的帧,程序加载时,可以将任意一页放入内存中任意一个帧,这些帧不必连续,从而实现了离散分离。页式存储管理的优点是:没有外碎片(因为页的大小固定),但会产生内碎片(一个页可能填充不满)。

    两者不同:

    (1)目的不同:分页是由于系统管理的需要而不是用户的需要,它是信息的物理单位;分段的目的是为了能更好地满足用户的需要,它是信息的逻辑单位,它含有一组其意义相对完整的信息;

    (2)大小不同:页的大小固定且由系统决定,而段的长度却不固定,由其所完成的功能决定

    (3)地址空间不同:段向用户提供二维地址空间;页向用户提供的是一维地址空间;

    (4)信息共享:段是信息的逻辑单位,便于存储保护和信息的共享,页的保护和共享受到限制;

    (5)内存碎片:页式存储管理的优点是没有外碎片(因为页的大小固定),但会产生内碎片(一个页可能填充不满);而段式管理的优点是没有内碎片(因为段大小可变,改变段大小来消除内碎片)。但段换入换出时,会产生外碎片(比如4k的段换5k的段,会产生1k的外碎片)。

    8、操作系统中进程调度策略有哪几种?

    (1)FCFS(先来先服务,队列实现,非抢占的):先请求CPU的进程先分配到CPU

    (2)SJF(最短作业优先调度算法):平均等待时间最短,但难以知道下一个CPU区间长度

    (3)优先级调度算法:优先级越高越先分配到CPU,相同优先级先到先服务,存在的主要问题是:低优先级进程无穷等待CPU,会导致无穷阻塞或饥饿;解决方案:老化

    (4)时间片轮转调度算法(可抢占的):队列中没有进程被分配超过一个时间片的CPU时间,除非它是唯一可运行的进程。如果进程的CPU区间超过了一个时间片,那么该进程就被抢占并放回就绪队列。

    (5)多级队列调度算法:将就绪队列分成多个独立的队列,每个队列都有自己的调度算法,队列之间采用固定优先级抢占调度。其中,一个进程根据自身属性被永久地分配到一个队列中。

    (6)多级反馈队列调度算法:与多级队列调度算法相比,其允许进程在队列之间移动:若进程使用过多CPU时间,那么它会被转移到更低的优先级队列;在较低优先级队列等待时间过长的进程会被转移到更高优先级队列,以防止饥饿发生。

    9、说一说进程同步有哪几种机制

    原子操作、信号量机制、自旋锁管程、会合、分布式系统

    10、什么是虚拟内存?

    10.1内存发展历程

    没有内存抽象(单进程,除去操作系统所用的内存之外,全部给用户程序使用) —>有内存抽象(多进程,进程独立的地址空间,交换技术(内存大小不可能容纳下所有并发执行的进程)—> 连续内存分配(固定大小分区(多道程序的程度受限),可变分区(首次适应,最佳适应,最差适应),碎片)—> 不连续内存分配(分段,分页,段页式,虚拟内存)

    10.2虚拟内存

    虚拟内存允许执行进程不必完全在内存中。虚拟内存的基本思想是:每个进程拥有独立的地址空间,这个空间被分为大小相等的多个块,称为页(Page),每个页都是一段连续的地址。这些页被映射到物理内存,但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时,由硬件立刻进行必要的映射;当程序引用到一部分不在物理内存中的地址空间时,由操作系统负责将缺失的部分装入物理内存并重新执行失败的命令。这样,对于进程而言,逻辑上似乎有很大的内存空间,实际上其中一部分对应物理内存上的一块(称为帧,通常页和帧大小相等),还有一些没加载在内存中的对应在硬盘上,如图所示。

     

    由图可以看出,虚拟内存实际上可以比物理内存大。当访问虚拟内存时,会访问MMU(内存管理单元)去匹配对应的物理地址(比如图5的0,1,2)。如果虚拟内存的页并不存在于物理内存中(如图5的3,4),会产生缺页中断,从磁盘中取得缺的页放入内存,如果内存已满,还会根据某种算法将磁盘中的页换出。

    10.3页面置换算法

    1)FIFO先进先出算法:在操作系统中经常被用到,比如作业调度(主要实现简单,很容易想到);

    2)LRU(Least recently use)最近最少使用算法:根据使用时间到现在的长短来判断;

    3)LFU(Least frequently use)最少使用次数算法:根据使用次数来判断;

    4)OPT(Optimal replacement)最优置换算法:理论的最优,理论;就是要保证置换出去的是不再被使用的页,或者是在实际内存中最晚使用的算法。

    10.4虚拟内存应用及优点

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

    好处:

    (1)在内存中可以保留多个进程,系统并发度提高

    (2)解除了用户与内存之间的紧密约束,进程可以比内存的全部空间还大

    11、颠簸

    颠簸本质上是指频繁的页调度行为,具体来讲,进程发生缺页中断,这时,必须置换某一页。然而,其他所有的页都在使用,它置换一个页,但又立刻再次需要这个页。因此,会不断产生缺页中断,导致整个系统的效率急剧下降,这种现象称为颠簸(抖动)。

    解决策略包括:

    (1)如果是因为页面替换策略失误,可以修改替换算法来解决这个问题;

    (2)如果是因为运行的程序太多,造成程序无法同时将所有频繁访问的页面调入内存,则要降低多道程序的数量;

    (3)否则,还剩下两个办法:终止该进程或增加物理内存容量。

    12、局部性原理

    1时间上的局部性:最近被访问的页在不久的将来还会被访问;

    2空间上的局部性:内存中被访问的页周围的页也很可能被访问。

    参考博客:https://blog.csdn.net/justloveyou_/article/details/78304294

    展开全文
  • 基于文件系统的概念,可以把数据组成分为数据项、记录和文件三级。 文件类型 按用途分类: ①系统文件:由系统软件构成。 ②用户文件:用户的文件。 ③库文件:标准子例程及常用的例程。 按文件中数据的形式...

    第六章 文件管理

    基于文件系统的概念,可以把数据组成分为数据项、记录和文件三级。
    文件类型
    按用途分类:
    ①系统文件:由系统软件构成。
    ②用户文件:用户的文件。
    ③库文件:标准子例程及常用的例程。
    按文件中数据的形式分类: ①源文件:由源程序和数据构成的。
    ②目标文件:源程序经过编译,尚未链接的目标代码“.obj” ③可执行文件:目标代码经过链接后的文件“.exe”。
    按存取控制属性分类:
    ①只执行文件 ②只读文件 ③读写文件
    按组织形式和处理方式分类:
    ①普通文件:由ASCII码或二进制码组成的字符文件
    ②目录文件:由文件目录组成的文件(检索执行下属文件)
    ③特殊文件:系统中的各类I/O设备

    文件系统模型

    最底层是对象及其属性;中间层是对对象进行操纵和管理的软件集合;最高层是文件系统提供给用户的接口。
    ①对象及其属性:文件、目录、磁盘存储空间。
    ②对对象操纵和管理的软件集合(核心)。
    ③文件系统的接口:命令接口、程序接口。

    文件操作
    ①最基本的文件操作:创建、删除、读、写文件、截断文件、设置文件的读/写位置
    ②文件的“打开”和“关闭”操作
    所谓“打开”,是指系统将指名文件的属性(包括该文件在外存上的物理位置)从外存拷贝到内存打开文件表的一个表目中,并将该表目的编号(或称为索引)返回给用户。以后,当用户再要求对该文件进行相应的操作时,便可利用系统所返回的索引号向系统提出操作请求。系统这时便可直接利用该索引号到打开文件表中去查找,从而避免了对该文件的再次检素。如果用户已不再需要对该文件实施相应的操作时,可利用“关闭”(close)系统调用来关闭此文件,OS 将会把该文件从打开文件表中的表目上删除掉。
    ③其他文件操作
    允许用户直接设置和获得文件的属性、有关目录的操作、实现文件共享的系统调用和用于对文件系统进行操作的系统调用等。

    文件的逻辑结构:从用户观点出发所观察到的文件组织形式。
    文件的物理结构:又称为文件的存储结构,是指文件在外存上的存储组织形式。

    文件逻辑结构的类型

    有结构文件
    组织方式:
    ①顺序文件:由一系列记录按某种顺序排列所形成的文件。可以按照不同的顺序进行排列:串结构、顺序结构。
    最佳应用场合是在对诸记录进行批量存取。
    ②索引文件:建立一张索引表,并为每个记录设置一个表项。 可为变长记录文件建立一张索引表,对主文件中的每个记录,在索引表中设有一个相应的表项,用于记录该记录的长度L及指向该记录的指针。索引表本身是一个定长记录的顺序文件。
    主要用于对信息处理的及时性要求较高的场合。
    ③索引顺序文件:为顺序文件建立一张索引表,在索引表中为每组中的第一个记录建立一个索引项,其中含有该记录的键值和指向该记录的指针。有效地克服了变长记录文件不便于直接存取的缺点,而且所付出的代价也不算太大。

    无结构文件
    即流式文件。其长度以字节为单位。对流式文件的访问,则是采用读/写指针来指出下一个要访问的字符。

    直接文件和哈希文件
    对于直接文件,则可根据给定的记录键值,直接获得指定记录的物理地址。换言之,记录键值本身就决定了记录的物理地址。
    哈希文件是目前应用最为广泛的一种直接文件。它利用Hash 函数(或称散列函数),可将记录键值转换为相应记录的地址。但为了能实现文件存储空间的动态分配,通常由Hash 函数所 求得的并非是相应记录的地址,而是指向一目录表相应表目的指针,该表目的内容指向相应记录所在的物理块。

    外存分配方式

    ①连续分配
    连续分配要求为每一个文件分配一组相邻接的盘块。一组盘块的地址定义了磁盘上的一段线性地址。在采用连续分配方式时,可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中。此时的物理文件称为顺序文件。
    利用紧凑的方法,将盘上所有的文件紧靠在一起,把所有的碎片拼接成一大片连续的存储空间。
    优点:顺序访问容易,顺序访问速度快。
    缺点:要求有连续的存储空间,必须事先知道文件的长度。

    ②链接分配
    在采用链接分配方式时,可通过在每个盘块上的链接指针,将同属于一个文件的多个离散的盘块链接成一个链表,把这样形成的物理文件称为链接文件。
    优点:离散分配,消除了外部碎片,提高了外存空间的利用率;当文件动态增长时,可动态地再为它分配盘块,故而无需事先知道文件的大小。此外,对文件的增、删、改也十分方便。
    缺点:不能支持高效的直接存取,文件分配表(FAT)需占用较大的内存空间。

    ③索引分配
    单级索引分配
    为每个文件分配一个索引块(表),再把分配给该文件的所有盘块号都记录在该索引块中,因而该索引块就是一个含有许多盘块号的数组。
    优点:支持直接访问,不会产生外部碎片。
    缺点:花费较多的外存空间。对于小文件采用索引分配方式时,其索引块的利用率将是极低的。

    多级索引分配
    当文件太大,应为索引块再建立一级索引,称为第一级索引,即系统再分配一个索引块,作为第一级索引的索引块,将第一块、第二块……等索引块的盘块号填入到此索引表中,这样便形成了两级索引分配方式。如果文件非常大时,还可用三级、四级索引分配方式。

    混合索引分配方式
    将多种索引分配方式相结合,系统既采用了直接地址,又采用了一级索引分配方式,或两级索引分配方式,甚至还采用了三级索引分配方式。

    目录管理

    文件目录也是一种数据结构,用于标识系统中的文件及其物理地址,供检索时使用。
    文件控制块:基本信息、存取控制信息及使用信息。
    索引结点
    在有的系统中,如UNIX系统,便采用了把文件名与文 件描述信息分开的办法,亦即,使文件描述信息单独形成一个称为索引结点的数据结构, 简称为i结点。在文件目录中的每个目录项仅由文件名和指向该文件所对应的i结点的指针所构成。
    磁盘索引结点
    这是存放在磁盘上的索引结点。每个文件有惟一的一个磁盘索引结点。
    内存索引结点
    这是存放在内存中的索引结点。当文件被打开时,要将磁盘索引结点拷贝到内存的索引结点中,便于以后使用。

    目录结构
    单级目录结构
    这是最简单的目录结构。在整个文件系统中只建立一张目录表,每个文件占一个目录项,目录项中含文件名、文件扩展名、文件长度、文件类型、文件物理地址以及其它文件属性。
    优点
    简单且能实现目录管理的基本功能——按名存取。
    缺点
    查找速度慢、不允许重名、不便于实现文件共享(只适用于单用户环境)。

    两级目录
    可以为每一个用户建立一个单独的用户文件目录UFD。这些文件目录具有相似的结构,它由用户所有文件的文件控制块组成。此外,在系统中再建立一个主文件目录MFD;在主文件目录中,每个用户目录文件都占有一个目录项,其目录项中包括用户名和指向该用户目录文件的指针。
    优点:克服了单机目录的缺点,并且提高了检索目录的速度;在不同的用户目录中,可以使用相同的文件名;不同用户还可使用不同的文件名来访问系统中的同一个共享文件。

    多级目录结构
    多级目录结构又称为树型目录结构,主目录在这里被称为根目录,把数据文件称为树叶,其它的目录均作为树的结点。
    路径名
    在该路径上从树的根(即主目录)开始,把全部目录文件名与数据文件名依次地用“/”连接起来,构成该数据文件的唯一路径名。
    当前目录:进程当前访问的工作目录
    相对路径名:从当前目录开始直到数据文件为止所构成的路径名。
    绝对路径名:从树根开始的路径名称为绝对路径名。
    优点
    查询速度更快,同时层次结构更加清晰,能够更加有效地进行文件的管理和保护。在多级目录中,不同性质、不同用户的文件可以构成不同的目录子树,不同层次、不同用户的文件分别呈现在系统目录树中的不同层次或不同子树中,可以容易地赋予不同的存取权限。
    缺点
    在多级目录中查找一个文件,需要按路径名逐级访问中间节点,这就增加了磁盘 访问次数,无疑将影响查询速度。

    目录查询技术
    线性检索法(顺序检索法)
    Hash方法
    系统利用用户提供的文件名并将它变换为文件目录的索引值,再利用该索引值到目录中去查找,这将显著地提高检索速度。对于使用了通配符的文件名,系统此时便无法利用Hash方法检索目录,因此,这时系统还是需要利用线性查找法查找目录。

    文件存储空间的管理

    ①空闲表法
    空闲表法属于连续分配方式,它与内存的动态分配方式雷同,它为每个文件分配一块连续的存储空间,即系统也为外存上的所有空闲区建立一张空闲表,每个空闲区对应于一个空闲表项。
    空闲盘区的分配与内存的动态分配类似,同样是采用首次适应算法、循环首次适应算法等。系统在对用户所释放的存储空间进行回收时,也采取类似于内存回收的方法,即要考虑回收区是否与空闲表中插入点的前区和后区相邻接,对相邻接者应予以合并。
    ②空闲链表法
    空闲盘块链
    这是将磁盘上的所有空闲空间,以盘块为单位拉成一条链。当用户因创建文件而请求分配存储空间时,系统从链首开始,依次摘下适当数目的空闲盘块分配给用户。当用户因删除文件而释放存储空间时,系统将回收的盘块依次插入空闲盘块链的末尾。
    空闲盘区链
    这是将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外,还应有能指明本盘区大小(盘块数)的信息。分配盘区的方法与内存的动态分区分配类似,通常采用首次适应算法。在回收盘区时,同样也要将回收区与相邻接的空闲盘区相合并。在采用首次适应算法时,为了提高对空闲盘区的检索速度,可以采用显式链接方法,亦即,在内存中为空闲盘区建立一张链表。
    ③位示图法
    位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为“0”时,表示对应的盘块空闲;为“1”时,表示已分配。
    优点
    从位示图中很容易找到一个或一组相邻接的空闲盘块。位示图很小,占用空间少,因而可将它保存在内存中,从而节省了许多磁盘的启动操作。
    ④成组链接法
    在UNIX系统中采用的是成组链接法,这是将上述两种方法相结合而形成的一种空闲盘块管理方法,它兼备了上述两种方法的优点而克服了两种方法均有的表太长的缺点。

    空闲盘块的组织
    空闲盘块号栈用来存放当前可用的一组空闲盘块的盘块号(最多含100个号),以及栈中尚有的空闲盘块号数N。

    空闲盘块的分配
    首先检查空闲盘块号栈是否上锁,如未上锁,便从栈顶取出一空闲盘块号,将与之对应的盘块分配给用户,然后将栈顶指针下移一格。若该盘块号已是栈底,即 S.free(0),这是当前栈中最 后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号,因此,须调用磁盘读过程,将栈底盘块号所对应盘块的内容读入栈中,作为新的盘块号栈的内容,并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。然后,再分配一相应的缓冲区(作为该盘块的缓冲区)。最后,把栈中的空闲盘块数减1并返回。

    空闲盘块的回收
    将回收盘块的盘块号记入空闲盘块号栈的顶部,并执行空闲盘块数加1操作。当栈中空闲盘块号数目已达100 时,表示栈已满,便将现有栈中的100个盘块号记入新回收的盘块中,再将其盘块号作为新栈底。

    文件共享与文件保护

    ①基于索引结点的共享方式
    文件的物理地址及其它的文件属性等信息放在索引结点中,在文件目录中只设置文件名及指向相应索引结点的指针。由任何用户对文件进行Append操作或修改, 所引起的相应结点内容的改变,都是其他用户可见的,从而也就能提供给其他用户来共享。
    ②利用符号链实现文件共享
    在新文件中只包含被链接文件F的路径名。这样的链接方法被称为符号链接。新文件中的路径名则只被看作是符号链,当B要访问被链接的文件F且正要读LINK 类新文件时,此要求将被OS截获,OS根据新文件中的路径名去读该文件,于是就实现了用户B对文件F的共享。
    磁盘容错技术
    影响文件安全的因素:人为、系统、自然。
    措施
    ①通过存取控制机制来防止由人为因素所造成的文件不安全性。
    ②通过磁盘容错技术来防止由磁盘部分的故障所造成的文件不安全性。
    ③通过“后备系统”来防止由自然因素所造成的不安全性。
    第一级容错技术 SFT-Ⅰ
    用于防止因磁盘表面缺陷所造成的数据丢失。它包含双份目录、双份文件分配表及热修复重定向和写后读校验等措施。
    第二级容错技术 SFT-Ⅱ
    用于防止由磁盘驱动器和磁盘控制器故障所导致的系统不能正常工作,它具体又可分为磁盘镜像和磁盘双工。
    基于集群技术的容错功能
    主要工作模式有三种:①热备份模式;②互为备份模式;③公用磁盘模式。

    数据一致性

    事务
    事务是用于访问和修改各种数据项的一个程序单位。
    事务记录
    用来记录在事务运行时数据项修改的全部信息。

    恢复算法可利用以下两个过程::
    ①undo〈Ti〉。该过程把所有被事务 Ti修改过的数据恢复为修改前的值。
    ②redo〈Ti〉。该过程把所有被事务 Ti修改过的数据设置为新值。

    引入检查点的主要目的,是使对事务记录表中事务记录的清理工作经常化。在发生故障后,并不需要对事务记录表中的所有事务记录进行处理,而只需对最后一个检查点之后的事务记录进行处理。

    并发控制
    利用互斥锁、共享锁实现顺序性。

    重复数据的数据一致性问题
    第一种方法是当一个文件被修改后,可查找文件目录,以得到其它几个拷贝的索引结点号,再从这些索引结点中找 到各拷贝的物理位置,然后对这些拷贝做同样的修改;第二种方法是为新修改的文件建立几个拷贝,并用新拷贝去取代原来的文件拷贝。
    盘块号一致性的检查
    利用软件方法构成一个计数器表,每个盘块号占一个表项,可有0,…,N-1项,N为盘块总数。每一个表项中包含两个计数器,分别用作空闲盘块号计数器和数据盘块号计数器。如果情况正常,则两组计数器中对应的一对(计数器中的)数据应该互补。
    链接数一致性检查
    配置一张计数器表,此时应是为每个文建立一个表项,其中含有该索引结点号的计数值。在进行检查时,从根目录开始查找,每当在目录中遇到该索引结点号时,便在该计数器表中相应文件的表项上加1。当把所有目录都检查完后,便可将该计数器表中每个表项中的索引结点号计数值与该文件索引结点中的链接计数 count 值加以比较,如果两者一致,表示是正确的;否则,便是产生了链接数据不一致的错误。

    第七章 操作系统接口

    1. 联机用户接口

    操作系统是用户与计算机硬件系统之间的接口,两类接口:用户接口、程序接口。
    用户接口分为两类:联机用户接口、脱机用户接口。
    联机用户接口:字符显示式用户界面、图形化用户界面。
    字符显示式用户界面:命令行方式、批命令方式(.BAT文件、Shell文件)。
    联机命令的类型
    ①系统访问类;②磁盘操作类;③文件操作类;④目录操作类;⑤通信类;⑥其他命令。
    键盘终端处理程序
    ①字符接收功能:面向字符方式、面向行方式。
    ②字符缓冲功能:专用缓冲区方式、公用缓冲池方式。
    ③回送显示。
    ④屏幕编辑。
    ⑤特殊字符处理。

    命令解释程序
    主要功能是先对用户输入的命令进行解释,然后转入相应命令的处理程序去执行。
    命令解释程序的作用
    在屏幕上给出提示符,请用户键入命令,然后读入该命令识别命令,再转到相应命令处理程序的入口地址,把控制权交给该处理程序去执行,并将处理结果送屏幕上显示。
    MS-DOS命令解释程序的组成
    常驻部分、初始化部分、暂存部分。

    1. Shell命令语言

    UNIX的Shell是作为操作系统的最外层,也称为外壳。它可以作为命令语言,为用户提供使用操作系统的接口,用户利用该接口与机器交互。
    简单命令
    所谓简单命令,实际上是一个能完成某种功能的目标程序的名字。命令可带有参数表,用于给出执行命令时的附加信息。命令名与参数表之间还可使用一种称为选项的自变量,用破折号开始,后跟一个或多个字母、数字。
    ①进入与退出系统
    用户的进入与退出过程,实际上是由系统直接调用Login及Logout程序完成的。
    ②文件操作命令
    显示文件内容命令cat,复制文件副本的命令cp,对已有文件改名的命令mv,撤消文件的命令rm,确定文件类型的命令file。
    ③目录操作命令
    建立目录的命令mkdir,撤消目录的命令rmdir,改变工作目录的命令cd,改变对文件的存取方式的命令chmod。
    ④系统询问命令
    访问当前日期和时间命令date,询问系统当前用户的命令who,显示当前目录路径名的命令pwd。

    重定向与管道命令
    重定向:用于改变输入、输出设备的手段。
    用重定向符“<”和“>”分别表示输入转向与输出转向。
    在做输出转向时,若上述的文件file2并不存在,则先创建它;若已存在,则认为它是空白的,执行上述输出转向命令时,是用命令的输出数据去重写该文件;如果文件file2事先已有内容,则命令执行结果将用文件file1的内容去更新文件 file2的原有内容。现在,如果又要求把file4的内容附加到现有的文件file2的末尾,则应使用另一个输出转向符“>>”。

    管道命令:用符号“|”来连接两条命令,使其前一条命令的输出作为后一条命令的输入。
    由UNIX系统来 “缓冲”第一条命令的输出,并作为第二条命令的输入。在用管道线所连接的命令之间,实现单向、同步运行。

    通信命令
    ①信箱通信命令mail
    mail命令被作为在UNIX的各用户之间进行非交互式通信的工具。
    ②对话通信命令write
    用这条命令可以使用户与当前在系统中的其他用户直接进行联机通信。
    ③允许或拒绝接收消息命令mesg
    选项n表示拒绝对方的写许可(即拒绝接收消息);选项y指示恢复对方的写许可,仅在此时,双方才可联机通信。

    后台命令
    用户可以在这种命令后面再加上“&”号,以告诉Shell将该命令放在后台执行,以便用户在前台继续键入其它命令。

    1. 系统调用

    为了保证系统程序不被应用程序有意或无意地破坏,为计算机设置了两种状态:系统态(也称为管态或核心态) 和用户态(也称为目态)。操作系统在系统态运行,而应用程序只能在用户态运行。在实际运行过程中,处理机会在系统态和用户态间切换。相应地,现代多数操作系统将CPU的指令集分为特权指令和非特权指令两类。
    特权指令
    在系统态时运行的指令,是关系到系统全局的指令。
    非特权指令
    在用户态时运行的指令。一般应用程序所使用的都是非特权指令。

    系统调用
    由操作系统捕获到该命令后,便将CPU的状态从用户态转换到系统态,然后执行操作系统中相应的子程序(例程),完成所需的功能。执行完成后,系统又将CPU 状态从系统态转换到用户态,再继续执行应用程序。
    系统调用在本质上是应用程序请求OS内核完成某功能时的一种过程调用。但它 是一种特殊的过程调用,它与一般的过程调用有下述几方面的明显差别:
    ①运行在不同的系统状态。
    ②状态的转换通过软中断进入。
    ③返回问题。
    ④嵌套调用。

    中断机制
    系统调用是通过中断机制实现的,并且一个操作系统的所有系统调用都通过同一个中断入口来实现。

    系统调用的类型
    ①进程控制类系统调用
    创建和终止进程的系统调用、获得和设置进程属性的系统调用、等待某事件出现的系统调用。
    ②文件操纵类系统调用
    创建和删除文件、打开和关闭文件、读和写文件。
    ③进程通信类系统调用
    消息传递方式和共享存储区方式。
    ④设备管理类系统调用
    主要用于实现申请设备、释放设备、设备I/O和重定向、获得和设置设备属性、逻辑上连接和释放设备等功能
    ⑤信息维护类系统调用
    主要用来获得包括有关系统和文件的时间、日期信息、操作系统版本、当前用户以及有关空闲内存和磁盘空间大小等多方面的信息。

    POSIX(基于UNIX的可移植操作系统接口)标准
    POSIX定义了标准应用程序接口(API),用于保证编制的应用程序可以在源代码一级上在多种操作系统上移植运行。只有符合这一标准的应用程序,才有可能完全兼容多种操作系统,即在多种操作系统下都能够运行。
    POSIX标准定义了一组过程,这组过程是构造系统调用所必须的。通过调用这些过程所提供的服务,确定了一系列系统调用的功能。

    系统调用的实现
    ①中断和陷入硬件机构
    把中断分为外中断和内中断。所谓外中断,是指由于外部设备事件所引起的中断,内中断则是指由于CPU内部事件所引起的中断。内中断(trap)也被译为“捕获”或“陷入”。通常,陷入是由于执行了现行指令所引起的;而中断则是由于系统中某事件引起的,该事件与现行指令无关。由于系统调用引起的中断属于内中断,因此把由于系统调用引起中断的指令称为陷入指令。
    不同的系统调用对应不同的陷入向量,在进行陷入处理时,根据陷入指令中的陷入向量,转入实现相应的系统调用功能的子程序,即陷入处理程序。

    系统调用号和参数的设置
    如何将系统调用的参数传递给陷入处理机构和系统内部的子程序(过程),常用的实现方式有以下几种:
    陷入指令自带方式
    直接将参数送入相应的寄存器
    参数表方式(当前大多数的 OS 中,如 UNIX 系统和 Linux 系统采用)

    系统调用的处理步骤
    ①将处理机状态由用户态转为系统态;
    ②由硬件和内核程序进行系统调用的一般性处理;
    ③将用户定义的参数传送到指定的地址保存起来;
    ④分析系统调用类型,转入相应的系统调用处理子程序;
    ⑤恢复被中断的或设置新进程的CPU现场, 然后返回被中断进程或新进程,继续往下执行。
    系统调用的功能主要是由系统调用子程序来完成的。

    1. UNIX系统调用

    UNIX系统调用的类型
    ①进程控制
    创建进程(fork)、终止进程(exit)、等待子进程结束(wait)、执行一个文件(exec)、获得进程ID、获得用户ID、进程暂停(pause)。
    ②文件操纵
    创建文件(create)、打开文件(open)、关闭文件(close)、读和写文件read和write、连接和去连接(link和unlink)
    ③进程间的通信
    在UNIX系统中提供了一个用于进程间通信的软件包,简称IPC。它由消息机制、共享存储器机制和信号量机制三部分组成。
    ④信息维护
    设置和获取时间、获得进程和子进程时间(times)、设置文件访问和修改时间(utime)、获取当前UNIX系统的名称(uname)。

    被中断进程的环境保护
    在中断和陷入发生后,是先经硬件陷入机构予以处理,再进入 trap.S, 然后再调用 trap.C 继续处理。
    在UNIX系统Ⅴ的内核程序中,有一个trap.S文件,它是中断和陷入总控程序。该程序用于中断和陷入的一般性处理。
    系统调用陷入后需处理的公共问题
    ①确定系统调用号
    ②参数传送
    ③利用系统调用定义表转入相应的处理程序
    ④系统调用返回前的公共处理

    1. 图形用户接口GUI

    Windows操作系统为例,在系统初始化后,操作系统为终端用户生成了一个运行explorer.exe的进程,它运行一个具有窗口界面的命令解释程序,该窗口为一个特殊的窗口,即桌面。采用的是事件驱动控制方式,用户通过动作来产生事件以驱动程序工作。事件实质就是发送给应用程序的一个消息,用户按键或点击鼠标等动作都会产生一个事件,通过中断系统引出事件驱动控制程序工作,对事件进行接收、分析、处理和清除。

    第八章 网络操作系统

    计算机网络概述

    计算机网络的拓扑结构
    ①星形和树形网络拓扑结构
    ②公用总线形和环形网络拓扑结构
    ③网状形网络拓扑结构
    在广域网中最广泛采用的是网状形网络拓扑结构。它是通过点—点的连接方式,将分布在不同地点的、用于实现数据通信的分组交换设备PSE(Packet Switch Equipment)连接在一起,形成一个不规则的网状形网络。在逻辑上可分为通信子网和资源子网两部分。
    网络拓扑结构的主要特点是它具有分布性。减少了网络中的信息流量,提高了可靠性,改善了网络的可扩充性。

    • 计算机广域网络

    (1)公用交换电话网
    交换是指在两个或多个结点之间建立暂时通信线路(或链路)的操作。建立链路的操作是由交换中心完成的。两个结点在通信之前,须先建立链接,然后源结点把信息通过该链路发送给交换中心,再由交换中心把信息转发到目标结点,通信结束后便拆除该链接。
    (2)分组交换网
    报文交换方式
    基于“存储—转发”方式进行报文交换的,即数字式报文交换中心先将各用户发来的电报接收下来,存储在报文缓冲区中,经过适当的处理(如判别目标地址、报文优先级等)后,为该报文选择一条转发路由,并将它送至该路由的输出队列中排队,再依次将该队列中各报文转发出去。
    分组交换方式
    分组交换方式对报文交换方式的一种改进,它同样是基于“存储—转发”方式来传 输信息的。为了提高传输效率而将不定长的报分解成定长的(报文)分组(packet),然后以分组为单位进行传输。这种方式的好处是:简化了对缓冲区的管理,加速了对信息的传输,减少了传输出错率以及重发信息量。
    分组交换网
    以分组作为传输的基本单位。一个分组由分组头和正文两部分组成。正文是用户要传送的信息,而分组头则是用于控制该分组在网络中传输所必需的(控制)信息。
    (3)帧中继网
    ①帧交换方式的帧中继网
    帧交换方式中传输的基本单位是帧,其长度是可变的,它们同样都采用“存储—转发”方式。
    信元交换方式的帧中继网
    网络中所传输和交换的基本单位是具有固定长度的“信元” 。当源帧交换器收到用户设备发来的帧后,便将之分割为多个定长的信元,在整个帧中继网络中传输和交换时,都是以信元为基本单位,直至它们到达目标帧交换器后,才被重新组装成帧。
    (4)异步传输模式(ATM)
    ATM 是以信元(Cell)为基本传输单位的,在每个时间片中传输一个信元。由于信元的发送无固定的周期,因而将这种传输方式称为异步传输方式。
    在 ATM 交换方式中,主要提供的是面向连接的方式。特点:按时间片交换,定长交换,硬件实现(这无疑是ATM能获得极高传输速率的重要原因)。

    • 计算机局域网络

    (1)基本型局域网
    ①以太网
    采用的是公用总线型网络拓扑结构,采用了带有冲突检测的载波侦听多重访问控制规程,亦即 CSMA/CD 规程。
    ②令牌环网
    采用的是环形网络拓扑结构。
    可通过两种途径来扩展LAN站点的平均带宽。其一是提高LAN的传输速率; 另一途径是减少每个网段上的站点数目。
    (2)快速局域网
    快速LAN是试图通过提高LAN的传输速率来增加每个站点的带宽的。
    FDDI光纤环网、快速以太网 100 BASE-T。
    (3)交换式LAN
    交换式LAN是通过减少每个局域网段上的站点数目的方法,来增加站点的平均带宽。构建交换式局域网要比构建快速局域网更方便、经济。
    (4)千兆以太网
    千兆位以太网仍采用CSMA/CD规程。在传输介质上,主要利用光纤系统。
    (5)10 Gb/s以太网
    10 Gb/s以太网仍采用CSMA/CD规程,只能工作在全双工方式,因而不存在争用总线问题。

    网络互连
    (1)网桥
    网桥是用于连接同构LAN的网络互连设备。同构LAN是指从应用层到逻辑链路控制子层这几个层次中,相对应的层次采用相同的协议。
    网桥所实现的功能应属于MAC子层和物理层。从网桥的工作原理中不难得知网桥应具有以下功能:
    ①帧的发送和接收;②缓冲管理;③协议转换。
    (2)路由器
    路由器是在网络层上实现的互连,它能识别不同的网络层协议,如IP、IPX协议等,因而具有更强的互连能力。路由器的功能涉及到物理层、数据链路层和网络层,其主要功能如下:
    ①拆包和打包功能;②路由选择功能;③进行协议转换;④分段和重新组装。
    (3)网关
    网关用于互连异构型网络。所谓互连异构型网络,一般是指不同类型的网络。在网关中至少要进行网络层、数据链路层及物理层的协议转换,目前对异构型网络的互连,通常是在网络层或传输层上实现的。
    异构型网络的互连:异构型LAN互连、LAN与WAN互连、WAN与WAN互连、LAN与主机互连。

    网络体系结构

    网络体系结构的基本概念
    所谓网络体系结构,就是计算机网络的层次及其协议的集合。具体地说,网络体系结构是关于计算机网络应设置哪几层,每个层次又应提供哪些协议的精确定义。至于这些功能应如何实现,则不属于网络体系结构部分。

    开放系统互连参考模型OSI/RM
    开放系统(OSI)的内容
    ①开放系统之间的信息交换,这是每一个单独的开放系统的内部行为;
    ②开放系统之间相互合作去完成一项共同任务。
    OSI/RM的组成
    ①开放系统;②应用实体;③连接;④物理介质。

    分层
    每个系统可被看成是由有序的一组子系统所组成。一个系统被分成若干个层次,其中第N层是由若干个处于第N层的子系统所组成。(N)子系统又包括了若干个(N)实体。在同一层中的实体为对等实体。除最高层外,分布在(N)层中的(N)实体相互合作,向(N+1)层的实体提供(N)服务。

    网络协议
    (N)实体之间的合作,是受一个或几个(N)协议支配的。(N)协议精确地规定了(N)实体如 何利用(N-1)服务协同工作去实现(N)功能。

    数据单元
    OSI把对等实体之间所传送的信息称为(N)协议数据单元(N)-PDU,由两部分组成:
    ①(N)协议控制信息(N)-PCI,用它来协调两个实体之间的连接操作;
    ②(N)服务数据单元(N)-SDU,其中存放由(N+1)实体提供的数据。

    OSI七层模型
    物理层、数据链路层、网络层、传输层、会话层、表示层、应用层。
    其中低三层即物理层、数据链路层和网络层用于实现通信子网中的信息传输,或者说,它们是面向通信的(一般称之为通信子网);最高三层即会话层、表示层和应用层向应用进程提供资源子网功能的服务,因此它是面向应用的;中间层即传输层,它是在高三层和低三层之间起桥梁作用。

    • 物理层

    它建立在通信介质(它不在OSI七层之内)的基础上实现系统和通信介质的接口功能,为数据链路实体之间透明的传输比特流提供服务。
    功能:物理链接的建立与拆除;物理服务数据单元传输;物理层管理。

    • 数据链路层

    在相邻两系统的网络实体之间建立、维持和释放数据链路连接,以及正确无误地传输数据链路服务数据单元。功能:数据链路连接的建立和释放;数据链路协议数据单元的形成;定界和同步;顺序和流量控制;差错的检测和恢复。

    • 网络层

    主要涉及通信子网及与主机的接口。网络层提供建立、维持和释放网络连接的手段,以实现两个端系统中传输实体间的通信。功能:
    网络连接服务;路径选择;网络连接多路复用;分组与组段;有序传送和流量控制;差错的检测和恢复。
    网络层提供的数据传输服务:无连接服务和面向连接的服务,亦把它们称为数据报服务和虚电路服务。

    • 传输层

    传输层在低三层和高三层间起桥梁作用。该层消除了OSI高层所要求的服务与各类网络层所提供的服务之间的差异。具体表现在以下三方面:传输出错率和建立连接的失败率;数据传输速率、吞吐量和传输时延;分段和组段功能。

    • 会话层

    对基本的传输连接服务进行“增值”,以提供一个能满足多方面要求的会晤连接服务。会话层的“增值”是基于下述几种应用要求的:半双工通信、更有效的差错纠正机制、允许暂停发送消息。

    • 表示层

    对不同系统的表示方法进行转换,消除网内各应用实体之间的语言差异,以实现不同系统之间的数据交换。

    • 应用层

    为应用进程访问OSI环境提供了手段,并直接为应用进程服务,其它各层也都通过应用层向应用进程提供服务。应用层所提供的服务可分为两类:公共应用服务元素(CASE)、特定应用服务元素(SAEA)

    TCP/IP网络体系结构
    TCP/IP模型
    TCP/IP是一个协议族,其中包含了多种协议,由这些协议构成了TCP/IP的网络体系结构。

    • 网络访问层

    主要关注的是两个端系统之间的数据通信,以及两个端系统借以通信的网络类型。所使用的网络可能是电路交换网、分组交换网、ATM网或者以太网等。

    • 网络互连层

    TCP/IP模型中最重要的层次,其中的IP协议主要用于异构型网络之间的相互连接和路由选择。IP所提供的是面向无连接的、不可靠的传输服务。

    • 传输层

    最主要的协议是传输控制协议TCP,它所提供的是面向连接的、可靠的端到端通信机制。

    • 应用层

    提供了许多用于支持各种应用程序的网络服务,相应地,在应用层就有许多应用层协议。

    互联网协议IP V4和IP V6
    IP V4协议
    IP V4 协议主要应解决三个问题,即寻址、数据报的分段和重新组装、路由选择。
    IP V6协议
    修改:扩大了地址空间、增设了安全机制、提高了路由的转发效率、增强了协议的可扩充性。

    传输层协议TCP和UDP
    传输控制协议TCP
    TCP提供了面向连接的、可靠的端到端通信机制。所谓面向连接,是指在端系统要传送数据前,应先进行端到端之间的连接;在数据传送完后,应拆除连接。而所谓可靠是指,即使网络层(通信子网)出现了差错,TCP协议采用了确认和重发措施,仍能正确地控制连接的建立、数据的传输和连接的释放。

    用户数据报协议UDP
    UDP协议是一种无连接的、不可靠的协议。它不要求网络中的端系统在数据传送之前先建立端到端之间的连接;同样,在数据传送结束后,也不要拆除连接。在数据传送过程中,无需对传送的数据进行差错检测,也不必对丢失的数据进行重发等。

    LAN网络体系结构
    局域网参考模型LAN/RM
    将数据链路层分为两个子层:逻辑链路控制子层LLC和介质(媒体)访问控制子层 MAC。
    LLC子层是数据链路层的顶部子层,其主要功能是在任何一个源LLC实体和目标实体之间进行信息传输。在LLC子层中提供了两种类型的链路操作,其中类型1操作提供的是无连接服务,类型2操作提供的是面向连接的服务。
    介质访问控制MAC子层
    推荐标准:CSMA/CD、令牌传送。

    Internet与Intranet

    Internet的特征:广域性、广泛性、高速性和综合性。
    IP地址
    IP地址是在Internet中主机的地址标识。IP地址共有32位二进制数,可以表示为4个十进制数,在各十进制数之间均用小数点隔开。每个主机的IP地址都是由网络标识和主机标识两部分组成,可分为A、B、C三类。
    在这里插入图片描述
    域名
    如果说,IP地址是面向网络的主机标识符,域名则是面向用户的主机标识符。每个域名通常由几个部分(段)组成,我们把域名中的每个段称为一个子域,各子域之间用小数点分隔开。

    Internet提供的传统信息服务
    电子邮件(E-mail)服务、文件传输服务(FTP)、远程登录服务TELNET、电子公告板系统BBS。

    Web服务
    WWW的基本概念
    WWW(Word Wide Web)称为环球网或Web。它是当前最为流行的信息服务类型。Web是一种信息检索工具。

    超文本标识语言HTML
    HTML是用于创建超文本文件的编程语言。可用该语言向普通文件中添加一些特殊的标识符,使在所生成的文件中,含有其它多种类型的文件,如声音,图像等,我们把这种文件称为超文本文件。特点:通用性、简易性、可扩充性、平台无关性。

    超文本传输协议HTTP
    HTTP是一个通用的、面向对象的客户(Web浏览器)/服务器(Web服务器)协议。该协议属于TCP/IP协议族中的应用层通信协议, 是建立在TCP协议基础上的,依赖于TCP协议来确保传输的正确性。
    WWW的基本特征
    对信息资源访问的分布性、信息形式的多样性、用户界面的统一性、Web服务应用的广泛性。

    客户/服务器模式

    两层结构客户/服务器模式的局限性
    不能适应应用不断增多的情况;需要在客户机与服务器上安装特定的高层(表示层和应用层)网络软件。
    只适用于较小规模的信息系统和网络中。

    三层结构的客户/服务器模式
    在客户机与服务器之间,增设一中间实体,用该实体把客户机与服务器隔开。通常把这个中间实体称为应用服务器或中间层服务。把两层客户/服务器模式客户机中的大部分应用软件和接口移到应用服务器上,从而简化客户机。
    应用服务器的组成:与客户机交互的接口、与数据(库)服务器交互的接口和事务逻辑。
    事物逻辑的主要功能有两个:功能一是将用户的请求包转换为对数据(库)服务器访问的请求包,功能二是将数据(库)服务器返回的响应包转换为对客户机的响应包。
    优点:①增加了系统的灵活性和可扩充性;②简化了客户机,降低了整个系统的费用;③使客户机的安装、配置和维护更为方便。
    缺点:①开发难度大,开发周期长;②访问效率低。
    当信息系统的规模较小时,最好采用两层客户/服务器模式;对于大型信息系统,通常都采用三层客户/服务器模式。

    浏览器/服务器模式
    在基于Internet的Internet内部网络中,在Internet中再增加一个Web服务器,它相当于前面所介绍的应用服务器,此时的客户机不是直接去访问Internet中的(数据库)服务器,而是访问Web服务器,再由Web服务器代理客户机去访问某个(些)(数据库)服务器。
    Web浏览器、Web服务器和数据库服务器三层的客户/服务器模式。通常把这种三层结构的模式称为浏览器/服务器模式。

    网络操作系统的功能

    1. 数据通信功能

    ①连接的建立和拆除;②报文的分解与组装;③传输控制:发送——等待方式、连续发送方式;④流量控制;⑤差错的检错与纠正

    1. 网络资源共享功能

    ①硬盘共享:以虚拟软盘方式实现硬盘共享、以文件服务方式实现硬盘共享。
    ②网络打印
    在LAN中以假脱机方式实现共享打印的原理。
    共享打印模式:客户/服务器模式、对等模式。

    1. 分布式文件系统DFS

    先利用DFS工具来建立一个共享目录,称之为DFS根目录; 再在此根目录下建立若干个子目录,这些子目录既可以是常规的本地子目录,也可以是一个个连接点。令这些连接点指向一些其它计算机系统上的共享目录和文件,这样,就把人们感兴趣的所有有关的共享目录和文件与DFS根目录下的分布式文件系统建立了连接。

    应用互操作功能
    ①信息的“互通性”
    所谓信息的“互通性”,是指在不同网络的结点之间能实现通信。而妨碍信息“互通性”的主要因素,是各个网络使用了各不相同的传输协议。
    在完成了网络之间物理上的连接之后,应再采取措施实现信息的互通。实现信 息的互通的一种有效方法是为互连网络中的所有各网站,都配置同一类型的传输协议。目前主要是利用TCP/IP来实现信息的“互通性”。
    ②信息的“互用性”
    所谓信息的“互用性”是指,在不同的网络中的站点之间能实现信息的互用,亦即一个网络中的用户能够去访问另一个网络文件系统(或数据库系 统)中的文件(数据)。
    网络文件系统协议NFS
    NFS(Network File System)是一种用于TCP/IP网络上的客户/服务器协议。在NFS 协议中包括一系列的命令和服务,这些命令和服务涉及到客户访问文件服务器上的文件系统、共享打印机,以及文件传输等,客户还可利用NFS命令去控制和访问远程文件系统;服务器则是根据请求者的请求做相应的处理,并将结果返回给请求者。NFS在提供这些服务时,要利用外部数据表示协议XDR(和远程过程调用 RPC。
    外部数据表示协议XDR
    XDR是处于OSI/RM中的表示层,主要用于处理在不同体系结构中的计算机之间的数据表示不一致时所出现的问题。
    远程过程调用 RPC
    远程过程调用是将单机环境下的过程调用延伸到分布式系统环境。

    网络管理
    网络管理的目标:①增强网络的可用性;②提高网络的运行质量;③提高网络的资源利用率;④保障网络数据的安全性;⑤提高网络的社会和经济效益。
    网络管理的功能:①配置管理;②故障管理;③性能管理;④安全管理;⑤计费管理。
    网络管理模型
    在现代网络中,普遍采用管理者/代理者模型。管理者是指驻留在管理系统中的,用于发出管理命令和接收代理者发来的通知的软件;代理者是指驻留在受管对象系统中,用于接收并执行管理者发来的命令,提供受管对象的视图并发出用于反映受管对象行为的通知的软件。

    网络操作系统提供的服务

    域名系统(DNS)
    域名系统同样也采用倒树形结构,它对应于域名的层次。在DNS的顶部是根服务器,下面是若干个顶级域名服务器,再下面是二级域名服务器……。由上级域名服务器管理属于它的下一级域名服务器。

    域名解析
    在域名系统中的每台本地域名服务器,都配置了一个域名解析器软件。所谓域名解析,是指将主机域名转换为对应的IP地址。
    DNS是基于客户/服务器模式的系统,因此在查询IP时,通常需要经过多次客户和服务器之间的交互。
    提升解析效率:在每个域名服务器中配置一个高速缓存,服务器应定期更新缓存中的数据。
    域名解析过程中客户与服务器的交互过程。
    在这里插入图片描述

    目录服务
    目录服务管理的对象:
    ①物理设备。通常为物理设备建立一张目录表,表中的每个目录项中可以包括物 理设备的标识符、设备类型。
    ②网络服务。
    ③用户。

    目录服务的功能:
    ①用户管理。保证核准用户能够方便地访问各种网络服务,禁止非核准用户的访问。
    ②分区和复制功能。将一个庞大的目录库分成若干个分区,再将这些分区的目录 库分别复制到多台服务器中,且使每个分区被复制的位置尽量靠近最常使用这些对象的用户,在有的目录服务中还允许在一台服务器上存放多个不同分区的拷贝。
    ③创建、扩充和继承功能。一些目录服务采用了面向对象的结构。
    ④多平台支持功能。对于一个大型企业网络,通常可能包含多种类型的网络工作站和网络服务器,因而其目录服务也存在着在管理对象上的差异。这就要求目录服务具有跨越平台的能力。

    目录服务带来的好处:
    ①简化了网络管理。只需为新服务器在网络的目录树上建立一个新的目录结点(项),这样,网络上的所有用户便都可以访问该新服务器。
    ②方便用户入网和访问。实现一个用户一个账户的单一登录性,也允许用户从网络中的任一结点对网络中的各个服务器进行访问。
    ③提高了网络的可用性。在目录中都有所有重要设备和所提供的服务的目录项;当网络中有某个(些)服务器发生故障时,目录服务可以及时发现,并可将用户对该服务器的访问请求转送到其它服务器上。

    支持Internet 提供的服务
    所谓支持Internet的功能是指,用户能从客户机上到Internet网上去浏览,并能取得Internet所提供的多种服务。

    必须在客户机和服务器上都配置相应的软件:
    ①Web浏览器软件和Web服务器软件。
    浏览器的基本功能是向 Web 服务器提出服务请求,并显示由 Web 服务器制作的显示信息。服务器软件向Web浏览器提供Web服务的,由此形成了浏览器/服务器模式。
    ②安装E-mail、FTP等多种服务软件
    近几年来所推出的新的浏览器软件,已不是单纯地实现浏览器功能,还包括许多其它的服务功能,如 E-mail服务、FTP服务、Telnet服务等。通常把这样的浏览器软件称为浏览器套件。在近几年所推出的Web服务器软件中,除了能提供Web 服务,同样也包括了许多其它的服务功能。
    ③在客户机上配置TCP/IP协议软件。原因是实现信息互通,建立在TCP/IP基础上的Internet。

    第九章 系统安全性

    系统安全的基本概念

    系统安全性的内容:物理安全、逻辑安全和安全管理。
    逻辑安全是指系统中信息资源的安全:数据机密性、数据完整性和系统可用性。
    系统安全的性质:多面性、动态性、层次性、适度性。
    系统安全威胁的类型:假冒用户身份、数据截取、拒绝服务、修改信息、伪造信息、否认操作、中断传输、通信量分析。
    信息技术安全评价公共准则(CC)
    CC 的组成:信息技术产品的安全功能需求定义,这是面向用户的;安全保证需求定义,这是面向厂商的。

    数据加密技术
    数据加密技术是对系统中所有存储和传输的数据进行加密,使之成为密文。
    数据加密技术包括这样几方面的内容:数据加密、数据解密、数字签名、签名识别以及数字证明等。

    数字加密模型
    组成:明文、密文、加密(解密)算法E(D)、密钥K。
    类型:
    ①按其对称性分类:
    对称加密算法。
    在这种方式中,在加密算法和解密算法之间存在着一定的相依关系,即加密和解密算法往往使用相同的密钥;或者在知道了加密密钥Ke后,就很容易推导出解 密密钥Kd。
    非对称加密算法。
    这种方式的加密密钥Ke和解密密钥Kd不同,而且难以从Ke推导出Kd来。可以将其中的一个密钥公开而成为公开密钥,因而把该算法称为公开密钥算法。用公开密钥加密后,能用另一把专用密钥解密;反之亦然。
    ②按所变换明文的单位分类
    序列机密算法、分组加密算法。

    基本加密方法
    ①易位法:按照一定的规则,重新安排明文中的比特或字符的顺序来形成密文,而字符本身保持不变。
    比特易位、字符易位。
    ②置换法:按照一定的规则,用一个字符去置换(替代)另一个字符来形成密文。比较好的置换算法是进行映像。

    对称加密算法和非对称加密算法

    • 对称加密算法

    最有代表性的对称加密算法是数据加密标准DES。
    在DES中所使用的密钥长度为64位,它由两部分组成,一部分是实际密钥,占56位;另一部分是8位奇偶校验码。DES属于分组加密算法,它将明文按64位一组分成若干个明文组,每次利用56位密钥对64位的二进制明文数据进行加密,产生64位密文数据。
    DES加密算法属于对称加密算法。加密和解密所使用的密钥是相同的。DES的保密性 主要取决于对密钥的保密程度。加密者必须用非常安全的方法(如通过个人信使)将密钥送给接收者(解密者)。如果通过计算机网络传送密钥,则必须先对密钥本身予以加密后再传送,通常把这种算法称为对称保密密钥算法。

    • 非对称加密算法

    在对数据进行加密和解密时,使用不同的密钥。每个用户都保存着一对密钥,每个人的公开密钥都对外公开。假如某用户要与另一用户通信,他可用公开密钥对数据进行加密,而 收信者则用自己的私用密钥进行解密。这样就可以保证信息不会外泄。
    由于对称加密算法和非对称加密算法各有优缺点,即非对称加密算法要比对称加密算法处理速度慢,但密钥管理简单,因而在当前新推出的许多新的安全协议中,都同时应用了这两种加密技术。
    一种常用的方法是利用公开密钥技术传递对称密码,而用对称密钥技术来对实际传输的数据进行加密和解密。例如,由发送者先产生一个随机数,此即对称密钥,用它来对欲传送的数据进行加密;然后再由接收者的公开密钥对对称密钥进行加密。接收者收到数据后,先用私用密钥对对称密钥进行解密,然后再用对称密钥对所收到的数据进行解密。

    数字签名
    在利用计算机网络传送报文时,可将公开密钥法用于电子(数字)签名来代替传统的签名。
    数字证明书
    由一个大家都信得过的认证机构CA为公开密钥发放一份公开密钥证明书,又把该公开密钥证明书称为数字证明书,用于证明通信请求者的身份。

    网络加密技术
    ①链路加密
    链路加密,是对在网络相邻结点之间通信线路上传输的数据进行加密。链路加密常采用序列加密算法,它能有效地防止由搭线窃听所造成的威胁。两个数据加密设备分别置于通信线路的两端,它们使用相同的数据加密密钥。
    在链路加密方式中,不仅对正文做了加密,而且对所有各层的控制信息也进行了加密。
    在链路加密方式中,在相邻结点间的物理信道上传输的报文是密文,而在所有中间结点中的报文则是明文,这给攻击者造成了可乘之机,使其可从中间结点上对传输中的信息进行攻击。这就要求能对所有各中间结点进行有效的保护。
    ②端到端加密
    端到端加密方式是在源主机或前端机FEP中的高层(从传输层到应用层)对所传输的数据进行加密。在整个网络的传输过程中,不论是在物理信道上,还是在中间结点中,报文的正文始终是密文,直至信息到达目标主机后才被译成明文,因而这样可以保证在中间结点不会出现明文。在这种加密方式中,不能对报头中的控制信息(如目标地址、路由信息等)进行加密。
    上述两种加密方式各有优缺点。一种比较好的网络加密方式是,同时采用链路加密和端到端加密,以取长补短。如利用端到端加密方式来使用户数据以密文形式穿越各个中间结点,以保障用户数据的安全;而利用链路加密方式则可使报头中的控制信息以密文形式在通信信道中传输,使之不易受到攻击。

    认证技术

    认证又称为鉴别或验证。它是指证被认证的对象(包括人和事)是否名符其实或者是否有效的一种过程。
    身份认证目前主要依据下述三个方面的信息来确定:所知、所有、个人特征。

    ①基于口令的身份认证
    利用口令确认用户的身份是当前最常用的认证技术。
    对口令机制的基本要求:口令长度适中、自动断开连接、隐蔽回送显示、记录和报告。
    一次性口令
    口令被使用一次后,就换另一个口令。在采用该机制时,用户必须提供记录有一系列口令的一张表,并将该表保存在系统中。系统为该表设置一指针用于指示下次用户登录时所应使用的口令。
    口令文件
    口令文件用于保存合法用户的口令和与口令相联系的特权。
    保证口令文件安全性的最有效的方法是,利用加密技术。选择一个函数来对口令进行加密,该函数f(x)具有这样的特性:在给定了x值后,很容易算出f(x);然而,如果给定了f(x)的值,却不能算出x的值。利用f(x)函数去编码(即加密)所有 的口令,再将加密后的口令存入口令文件中。当某用户输入一个口令时,系统利用函数f(x)对该口令进行编码,然后将编码(加密)后的口令与存储在口令文件中的已编码的口令进行比较,如果两者相匹配,便认为是合法用户。
    挑战——响应验证

    ②基于物理标志的认证技术
    基于磁卡的认证技术
    磁卡是基于磁性原理来记录数据的,在磁卡上所存储的信息,可利用磁卡读写器将之读出。
    基于IC卡的认证技术
    在IC卡中可装入CPU和存储器芯片,使该卡具有一定的智能。CPU用于对内部数据的访问和与外部数据进行交换,还可利用加密算法对数据处理。
    根据在磁卡中所装入芯片的不同可把IC卡分为以下三种类型:
    存储器卡:
    只有一个E2PROM(可电擦、可编程只读存储器)芯片,不具有安全功能,只能作为储值卡。
    微处理器卡:
    它除具有E2PROM 外,还增加了一个微处理器。已具有一定的加密设施,被广泛用作信用卡。
    密码卡:
    又增加了加密运算协处理器和RAM。能支持非对称加密体质RSA,专门用于确保安全的智能卡,在卡中存储了一个很长的用户专门密钥和数字证明书。
    将IC卡用于身份识别的方法明显地优于磁卡,是因为:IC 卡具有更好的安全性、防伪性、保密性,且存储容量大得多。

    ③基于生物标志的认证技术
    常用于身份识别的生理标志:指纹、视网膜、声音、手指长度。
    生物识别系统的要求:识别系统的性能必须满足要求;能被用户接受;系统成本适当。
    生物识别系统的组成:注册部分、识别部分。

    ④基于公开密钥的认证技术

    1. 申请数字证书:服务器申请数字证书;客户申请书证书。
    2. SSL握手协议:身份认证、协商加密算法、协商加密密钥。
    3. 数字加密和检查数据的完整性。

    控制访问技术

    保护域:进程对一组对象访问权的集合。它规定了进程所能访问的对象和能执行的操作。
    进程和域间的静态联系方式
    在进程和域之间,可以一一对应,即一个进程只联系着一个域。在进程的整个生命期中,其可用资源是固定的,我们把这种域称为“静态域”。
    进程和域间的动态联系方式
    在进程和域之间,也可以是一对多的关系,即一个进程可以联系着多个域。在此情况下,可将进程的运行分为若干个阶段,其每个阶段联系着一个域,这样便可根据运行的实际需要,来规定在进程运行的每个阶段中所能访问的对象。

    访问矩阵
    利用一个矩阵来描述系统的访问控制。访问矩阵中的行代表域,列代表对象,矩阵中的每一项是由一组访问权组成的。

    具有域切换权的访问矩阵
    为了能对进程进行控制,同样应将切换作为一种权力,仅当进程有切换权时,才能进行这种切换。

    访问矩阵的修改:拷贝权、所有权、控制权。
    拷贝权和所有权都是用于改变矩阵内同一列的各项访问权的,或者说,是用于改变在不同域中运行的进程对同一对象的访问权。控制权则可用于改变矩阵内同一行中(域中)的各项访问权,亦即,用于改变在某个域中运行进程对不同对象的访问权。

    访问控制矩阵的实现
    访问控制表
    对访问矩阵按列(对象)划分,为每一列建立一张访问控制表ACL。在该表中, 已把矩阵中属于该列的所有空项删除,此时的访问控制表是由一有序对(域,权集)所组成的。
    域是一个抽象的概念,每个用户是一个域,也可以每个进程是一个域。
    访问控制表也可用于定义缺省的访问权集。

    访问权限表
    把访问矩阵按行(即域)划分,便可由每一行构成一张访问权限表。换言之,这是由一个域对每一个对象可以执行的一组操作所构成的表。
    访问权限表不能允许直接被用户(进程)所访问。
    大多数系统都同时采用访问控制表和访问权限表,在系统中为每个对象配置一 张访问控制表。当一个进程第一次试图去访问一个对象时,必须先检查访问控制表,检查进程是否具有对该对象的访问权。如果无权访问,便由系统来拒绝进程的访问,并构成一例外(异常)事件;否则(有权访问),便允许进程对该对象进行访问,并为该进程建立一访问权限,将之连接到该进程。以后,该进程便可直接利用这一返回的权限去访问该对象,这样,便可快速地验证其访问的合法性。当进程不再需要对该对象进行访问时,便可撤消该访问权限。

    计算机病毒

    计算机病毒的基本概念
    计算机病毒是一段程序,它能不断地进行复制和感染其它程序,无需人为介入便能由被感染的程序和系统传播出去。
    计算机病毒的危害:
    占用系统空间、占用处理机时间、对文件造成破坏、使机器运行异常。
    计算机病毒的特征:
    寄生性、传染性、隐蔽性、破坏性

    计算机病毒的类型
    ①文件型病毒
    现在大多数病毒都采用寄生的方法,把自己附着在正常程序上。
    大多数病毒是被从程序的后面装入的,并把文件头中起始地址指向病毒的始端。病毒也可以被放在文件的中间,即充斥在程序里的空闲空间中。当受感染的程序执行时,病毒将寻找其它可执行文件继续散播。
    ②内存驻留病毒
    该病毒一旦执行,自己便占据内存驻留区,通常选择占据在内存的上端或下端的中断变量中(通常不会使用的数百个字节的内存区域)。为了能使自己频繁地执行,通常内存驻留病毒会把陷阱或中断向量的内容复制到其它地方去,而把自己的地址放入其中,使中断或陷阱指向病毒程序的入口。
    ③引导扇区病毒
    病毒也会寄生于磁盘上用于引导系统的引导区。这样,当系统开机时,病毒便借助于 引导过程进入系统。
    ④宏病毒
    宏病毒可利用软件提供的宏功能将病毒插入到带宏的doc文件或dot文件中。
    ⑤电子邮件病毒
    电子邮件病毒嵌入到电子邮件中,只要接收者打开含有该病毒的电子邮件,病毒就会被激活。由于电子邮件病毒是通过Internet传播的,因此使病毒的传播速度显著加快。

    病毒的隐藏方式
    ①伪装:通过压缩伪装;通过修改日期或时间来伪装。
    ②隐藏:隐藏于目录和注册表空间;隐藏于程序的页内零头。
    ③更改用于磁盘分配的数据结构。
    ④更改坏扇区列表。

    常用的产生多态病毒的方法如下:插入多余的指令;对病毒程序进行加密。

    基于病毒数据库的病毒检测方法
    ①建立病毒数据库
    首先应当采集病毒的样本。
    ②扫描硬盘上的可执行文件
    采取将硬盘上的可执行文件与病毒数据库中的病毒样本严格匹配的方式,可能会漏掉许多多形态病毒。 解决这一问题的方法是采用模糊查询软件。

    基于文件改变的病毒检测方法:通过被感染文件的长度或者日期和时间的改变来发泄病毒。

    完整性检测方法:首先扫描硬盘,检查是否有病毒,当确信硬盘是干净的后,它才正式工作。它首先计算每个文件的检查和(或称校验和),然后再计算目录中所有相关文件的检查和,将所有这些检查和都写入一个检查和文件中,利用它们来对文件是否被病毒感染进行检查。等到下一次检测病毒时,完整性检测程序将重新计算所有文件的检查和,并分别与原来文件的检查和进行比较,若不匹配,就表明该文件已发生改变,由此可以认定该文件已被感染上病毒。
    更好的方法是对检查和文件进行加密,而且可以采用智能卡技术,将加密密钥直接做在芯片上。

    第十章 UNIX系统内核结构

    UNIX系统概述

    UNIX系统的特征
    ①开放性
    ②多用户、多任务环境
    ③功能强大且高效
    ④丰富的网络功能
    ⑤支持多处理器功能

    UNIX系统的内核结构
    UNIX核心的框图。
    在这里插入图片描述
    OS核心分成两大部分:进程控制子系统、文件子系统。
    进程控制子系统:负责对四大资源中的两大资源——处理机和存储器进行管理。
    功能:
    ①进程控制。
    ②进程通信。
    ③存储器管理。用于为进程分配物理存储空间。
    ③进程调度。采用的是动态优先数轮转调度算法。

    进程的描述和控制

    在UNIX系统Ⅴ中,采用了段页式存储管理方式。在该系统中把段称为区——Region。

    进程控制块
    在 UNIX 系统Ⅴ中,把进程控制块(PCB)分为四部分:
    ①进程表项
    其中包括最常用的核心数据。为了提高对这些信息访问的效率,系统设计者将常被访问的信息放在进程表项中,又称之为Proc表或Proc结构,使之常驻内存。
    ②U区
    用于存放用户进程表项的一些扩充数据。这部分数据并非常驻内存。
    ③系统区表
    存放各个区在物理存储器中的地址信息等。
    ④进程区表
    用于存放各区的起始虚地址及指向系统区表中对应区表项的指针。
    核心可通过查找进程区表和系统区表,将区的逻辑地址变换为物理地址。

    进程状态
    进程的状态转换图。
    在这里插入图片描述
    (1)执行状态。
    处于用户态执行时,进程所能访问的内存空间和对象受到限制,其所占有的处理机是可被抢占的;而处于核心态执行中的进程,则能访问所有的内存空间和对象,且所占用的处理机是不允许被抢占的。
    (2)就绪状态。
    这是指进程处于一种只需再获得处理机便可执行的状态。由于UNIX内核提供了对换功能,因而又可把就绪状态分为“内存中就绪”和“就绪且换出”两种状态。
    (3)睡眠状态。
    由于对换功能的原因又可将睡眠状态分为“内存睡眠”状态和“睡眠且换出”状态。当内存紧张时,在内存中睡眠的进程可被内核换出到外存上,相应地,此时进程的状态便由“内存睡眠”状态转换为“睡眠且换出”状态。
    (4)“创建”与“僵死”状态。
    创建状态是指利用fork系统调用来创建子进程时,被创建的新进程所处的状态;僵死状态是在进程执行了exit系统调用后所处的状态,此时该进程实际上已不存在,但还留下一些信息供父进程搜集。
    (5)被抢占状态。
    当正在核心态执行的进程要从核心态返回到用户态执行时,如果此时已有一优先级更高的进程在等待处理机,则此时内核可以抢占(剥夺)已分配给正在执行进程的处理机,去调度该优先级更高的进程执行。

    进程映像
    进程是进程映像(Process Image)的执行过程;或者说,进程映像也就 是正在运行进程的实体,它由三部分组成:
    ①用户级上下文
    用户级上下文的主要成分是用户程序。它在系统中可分为正文区和数据区两部分。
    ②寄存器上下文
    寄存器上下文主要是由CPU中的一些寄存器的内容所组成的。主要的寄存器有:程序寄存器、处理机状态寄存器(PSR)、栈指针、通用寄存器。
    ③系统级上下文
    系统级上下文包括OS为管理该进程所用的信息,可分为静态和动态两部分。

    进程控制
    ①fork系统调用
    在UNIX的内核中设置了一个0进程,它是惟一一个在系统引导时被创建的进程。系统中除0进程外的所有进程都是用fork创建的。
    核心需为 fork 完成下列操作:为新进程分配一个进程表项和进程标识符;检查同时运行的进程数目;拷贝进程表项中的数据;子进程继承父进程的所有文件;为子进程创建进程上下文;子进程执行。
    ②exec系统调用
    用于将一个可执行的二进制文件覆盖在新进程的用户级上下文的存储空间上,以更新新进程的用户级上下文。
    execⅤ系统调用所要完成的操作:对可执行文件进行检查;回收内存空间;分配存储空间;采纳数拷贝。
    ③exit系统调用
    UNIX内核利用exit来实现进程的自我终止。
    内核需为exit完成以下操作:关闭软中断;回收资源;写记账信息;置进程为“僵死”状态。
    ④wait系统调用
    wait系统调用用于将调用进程挂起,直至其子进程因暂停或终止而发来软中断信号为止。

    进程调度与切换
    UNIX系统是单纯的分时系统,未设置高级调度——作业调度,只设置了中级调度——进程对换和低级调度——进程调度。
    引起进程调度的原因
    ①UNIX系统是分时系统,因而其时钟中断处理程序须每隔一定时间便对要求进程调度程序进行调度的标志runrun予以置位,以引起调度程序重新调度。
    ②当进程执行了wait、exit及sleep等系统调用后要放弃处理机时,也会引起调度程序重新进行调度。
    ③当进程执行完系统调用功能而从核心态返回到用户态时,如果系统中又出现了 更高优先级的进程在等待处理机时,内核应抢占当前进程的处理机,这也会引起调度。

    调度算法
    采用动态优先数轮转调度算法进行进程调度。

    进程优先级的分类
    核心优先级。又可进一步把它分为可中断和不可中断两种。
    用户优先级。又被分成n+1级,其中第0级为最高优先级,第n级的优先级最低。

    进程优先数的计算
    优先数 = 最近使用CPU的时间 / 2 + 基本用户优先数

    进程切换
    在进程调度之后,内核所应执行的是进程上下文的切换,即内核是把当前进程的上下文保存起来,而所恢复的则是进程调度程序所选中的进程的上下文,以使该进程能恢复执行。

    进程的同步与通信

    ①sleep与wakeu同步机制
    sleep过程
    进入sleep过程后,核心首先保存进入睡眠时的处理机运行级,再提高处理机的运行优先级来屏蔽所有的中断,接着将该进程置为“睡眠”状态,将睡眠地址(对应着某个睡眠事件)保存在进程表项中,并将该进程放入睡眠队列中。如果进程的睡眠是不可中断的,做了进程上下文的切换后,进程便可安稳地睡眠。当进程被唤醒并被调度执行时,将恢复处理 机的运行级为进入睡眠时的值,此时允许中断处理机。
    wakeup过程
    主要功能是唤醒在指定事件队列上睡眠的所有进程,并将它们放入可被调度的进程队列中。

    ②信号机制
    信号机制主要是作为在同一用户的诸进程之间通信的简单工具,是对硬中断的一种模拟。
    信号机制与中断机制之间的相似之处表现为:
    信号和中断都同样采用异步通信方式,在检测出有信号或有中断请求时,两者都是暂停正在执行的程序而转去执行相应的处理程序,处理完后都再返回到原来的断点;再有就是两者对信号或中断都可加以屏蔽。
    信号与中断两机制之间的差异是:
    中断有优先级,而信号机制则没有,即所有的信号都是平等的;再者是信号处理程序是在用户态下运行的,而中断处理程序则是在核心态下运行;还有,中断响应是及时的,而对信号的响应通常都有较长的时间延迟。

    信号机制的功能:
    发送信号;设制对信号的处理方式(可利用系统调用signal(sig, func)来预置对信号的处理方式);对信号的处理。

    管道机制
    所谓管道,是指能够连接一个写进程和一个读进程、并允许它们以生产者——消费者方式进行通信的一个共享文件,又称为pipe文件。由写进程从管道的入端将数据写入管道,而读进程则从管道的出端读出数据。
    管道的类型:
    无名管道:这是个临时文件,当这些进程不再需要此管道时,由核心收回其索引结点。
    有名管道:利用mknod系统调用建立的、可以在文件 统中长期存在的、具有路径名的文件,因而其它进程可以感知它的存在,并能利用该路径名来访问该文件。

    对无名管道的读写:
    ①对pipe文件大小的限制。
    核心将索引结点中的直接地址项作为一个循环队列来管理,为它设置一个读指针和一个写指针,按先进先出顺序读写。
    ②进程互斥。
    ③进程写管道。
    如果管道中有足够的空间能存放要写的数据,在每写完一(盘)块后,核心便自动增加地址项的大小。当写完i-addr(9)地址项中所指示的盘块时,便又向i-addr(0)地址项所指示的盘块中写数据,全部写完后,核心修改索引结点中的写指针,并唤醒因该管道空而睡眠等待的进程。如果管道中无足够的空间来存放要写入的数据,核心将对该索引结点做出标志,然后让写进程睡眠等待,直到读进程将数据从管道中读出后,才唤醒等待写进程。
    ④进程读管道。
    当进程从管道中读数据时,也同样会有两种可能:如果管道中已有足够的数据供进程读,读进程便根据读指针的初始值去读数据。每读出一块后,便增加地址项的大小。读完时,核心修改索引结点中的读指针,并唤醒所有等待的写进程。如果进程所要读的数据比管道中的数据多,则可令读进程把管道中已有数据读完后,暂时进入睡眠状态等待,直至写进程又将数据写入管道后,再将读进程唤醒。

    消息机制
    消息
    消息是一个格式化的、可变长度的信息单元。为便于管理而把消息分为消息首部和消息数据区两部分。
    消息队列
    每个消息队列有一个称为关键字key的名称,它是由用户指定的。每个消息队列还有一个消息队列描述符。
    消息队列的建立
    利用系统调用msgget( )先建立一个指名的消息队列。
    消息队列的操纵
    利用msgctl( )系统调用对指定的消息队列进行操纵:用于查询有关消息队列的情况的命令;用于设置和改变有关消息队列的属性的命令;消除消息队列的标识符。

    消息的发送
    可利用msgsnd( )系统调用来发送消息。
    消息的接收
    可利用msgrcv( )系统调用,从指定消息队列中读一个消息。

    共享存储区机制
    共享存储区机制是UNIX系统中通信速度最高的一种通信机制。
    当进程间欲利用共享存储区进行通信时,须首先在主存中建立一个共享存储区,然后将该区附接到自己的虚地址空间上。此后,进程之间便可通过对共享存储区中数据的读和写来实现直接通信。

    共享存储区的建立
    利用系统调用shmget( )建立一块共享存储区,并提供该共享存储区的名字key和共享存储区以字节为单位的长度size等参数。
    共享存储区的操纵
    用 shmctl( )系统调用对共享存储区的状态信息进行查询;对共享存储区加锁或解锁;修改共享存储区标识符等。

    共享存储区的附接与断开
    利用系统调用shmat( )将该共享存储区附接到用户给定的某个进程的虚地址 shmaddr上,并指定该存储区的访问属性。
    当进程不再需要该共享存储区时,再利用系统调用shmdt( )把该区与进程断开。

    信号量集机制
    信号量
    在UNIX系统中规定,每个信号量有一个可用来表示某类资源数目的信号量值和一个操作值,该操作值可为正整数、零或负整数三种情况之一。
    信号量集
    在一个信号量集中,通常都包含有若干个信号量。对这组信号量的操作方式应当是原子操作方式。
    信号量集的数据结构
    信号量表:是信号量的结构数组。
    信号量集表:是信号量集的索引结构数组,其中的每一个元素都对应于一个信号量集。

    系统调用
    semget( )系统调用:用户可利用该系统调用来建立信号量集。
    semop( )系统调用:该系统调用可用来对信号量集进行操作。

    存储器管理

    请求调页管理的数据结构
    ①页表和磁盘描述表
    页表
    UNIX系统Ⅴ将进程的每个区分为若干个虚页,可把这些虚页分配到不相邻接的页框中,为此而设置了一张页表。在其每个表项中,记录了每个虚页和页框间的对照关系。
    磁盘块描述表
    在请求调页机制中,若发现缺页,系统应将所缺页调入内存。
    引入了磁盘块描述表,用它来记录进程在不同 时候的每个虚页在硬盘中的盘块号。这样,当进程在运行中发现缺页时,可通过查找该页表的方法来找到所需调入页面的位置。
    一个进程的每一页对应一个磁盘描述表项,它描述了每一个虚页的磁盘拷贝。

    ②页框数据表和对换使用表
    页框数据表
    每个页框数据表项描述了内存的一个物理页。
    对换使用表
    对换设备上的每一页都占有对换使用表的一个表项,表项中含有一个引用计数,其数值表示有多少页表项指向该页。

    换页进程
    在UNIX系统的核心中,专门设置了一个换页进程,即0进程。其主要任务是:每隔一定时间,对内存中的所有有效页的年龄加1,以及当有效页的年龄达到规定值后,便将它换出。
    ①增加有效页的年龄
    每当内存中的空闲页面数低于某规定的低限时,核心便唤醒换页进程,由换页进程去检查内存中的每一个活动的、非上锁的区, 对所有有效页的年龄字段加 1。对于那些其年龄已增至最大的页,将它们换出。如果这种页已被进程访问过,便将其年龄域中的年龄降为 0。

    ②对换出页的几种处理方式
    (1)若在对换设备上已有被换出页的拷贝,且该页的内容未被修改,此时,核心只需将该页页表项中的有效位清零,并将页框数据表项中的引用计数减1,最后将该页框数据表项放入空闲页链表中。
    (2)若在对换设备上没有被换出页的拷贝,则换出进程应将该页写到对换设备上。但为了提高对换效率,对换进程并不是随有随换,而是先将所有要换出的页链入到一个要换出的页面链上。当换出页面链上的页面数达到某一规定值时,比如64个页,核心才真正将这些页面写到对换区中。
    (3)虽然在对换设备上已有换出页的副本,但该页的内容已被修改过,此时核心应将该页在对换设备上原来占有的空间释放,再重新将该页拷贝到对换设备上,使在对换设备上的拷贝内容总是最新的。

    ③将换出页面写到对换设备上
    当在换出页面链表中的页面数已达到规定值时,核心应将它们换出。为此,应首先为它们分配一个连续的对换空间,以便一起将它们换出;但如果在对换设备上没有足够大的连续空间,而其空闲存储空间的总和又大于 64KB 时,核心可采取每次换出一页的方式将它们换出。

    请求调页
    如何将所缺之页调入内存,这将与所缺页面应从何处调入有关,这又可分成以下三种情况:
    ①缺页在可执行文件上
    根据该文件所对应的系统区表项中的索引结点指针,找到该文件的索引结点,即可把从磁盘块描述表项中得到的该页的逻辑块号作为偏移量,查找索引结点中的磁盘块号表,便可找到该页的磁盘块号,再将该页调入内存。

    ②缺页在对换设备上
    核心先为该缺页分配一个内存页,修改该页页表,使之指向内存页,并将页框数据表项放入相应的散列队列中,然后把该页从对换设备上调入内存。

    ③缺页在内存页面缓冲区中
    只需适当地修改页面表项等数据结构中的信息。

    设备管理

    1. 字符设备缓冲区管理

    ①空闲字符缓冲区队列
    所有的空闲字符缓冲区都通过各自的链接指针C-next链接成一个空闲字符缓冲区队列,由队列头标中的队首指针cfreelist指向其第一个缓冲区。
    空闲缓冲区队列实际上是一个栈。

    ②空闲字符缓冲区的分配与回收
    内核可利用getcf过程从空闲字符缓冲区队列中取得一个空闲缓冲区。
    空闲缓冲区队列属于临界资源。
    调用 putcf 过程释放缓冲区。

    ③设备的字符缓冲区队列
    当字符设备工作时,通常都拥有一个至几个不同的字符缓冲区队列,所有的队列都由一个称为clist结构的信息块加以控制。
    getc过程:从一个clist结构的队首指针所指示的字符缓冲队列中取出为首的字符,然后修改该队列的可用字符计数和队首指针。
    putc过程:将一个字符C放入设备的指定字符缓冲区队列的末尾。
    getcb过程:从指定的设备字符缓冲区队列中取出第一个缓冲区,并将该队列的可用字符计数减去第一个缓冲区中的字符数,然后返回指向该缓冲区的指针bp。
    putcb过程:将由bp所指向的缓冲区放入指定的设备字符缓冲区队列的末尾。

    1. 块设备缓冲区管理

    盘块缓冲区及其首部
    每一个盘块缓冲区均由两部分组成:一部分用于存放数据本身,即数据缓冲区;另一部分是缓冲控制块,也称缓冲首部,用于存放对应缓冲区的管理信息。

    盘块缓冲池结构
    ①空闲链表。
    为了对缓冲区进行管理,在核心中设置了一个双向链接的空闲链表。
    ②散列队列。
    为了加速对缓冲区的查找,系统把所有的缓冲区逐个设备地、按其块号所计算的散列值的不同,组织成多个队列,每个散列队列仍是一个双向链,其中缓冲区的 数目不断地变化,各块的散列值用散列函数计算。

    盘块缓冲区的分配
    ①getblk( )过程。该过程用于从空闲缓冲区队列中获得任一空闲缓冲区。
    ②getblk(dev, blkno)过程。该过程用于为指定设备dev和盘块号为blkno的盘块申请一个缓冲区。

    盘块缓冲区的回收
    调用brelse过程将之收回。释放者进程唤醒等待进程,若在所释放的缓冲区中数据是有效的,可将该缓冲区链入空闲链表的末尾;否则(缓冲区中数据无效),应将它链入空闲队列的头部。空闲链表属于临界资源,UNIX系统通过提高处理机的运行级对中断加以屏蔽的方法来实现。

    内核与驱动程序接口
    在UNIX系统中,每类设备都有一个驱动程序,用来控制该类设备。

    设备开关表的作用:
    系统为每类设备提供了一个设备开关,其中含有各函数的入口地址。设备开关表是核心与驱动程序间的接口,系统调用通过设备开关表转向相应驱动程序的函数。

    块设备开关表
    打开函数的入口地址、关闭函数的入口地址、策略函数的入口地址。

    字符设备开关表
    打开特定字符设备的函数入口地址、关闭特定字符设备的函数入口地址、读特定字符设备的函数入口地址、写特定字符设备的函数入口地址、预置该设备参数的函数及读取该设备预置参数的函数等的入口地址。

    磁盘驱动程序
    ①打开磁盘驱动器的过程gdopen
    再调用gdtimer过程启动对应的控制器和设备短期时钟闹钟,用于控制磁盘驱动器的执行时间。
    ②启动磁盘控制器的过程gdstart
    在进行磁盘的读、写之前,应首先装配磁盘控制器中的各个寄存器,然后再启动磁盘控制器。
    gdstartegy过程的主要功能则是把指定的缓冲首部排在磁盘控制器I/O队列的末尾,并启动磁盘控制器。
    ③磁盘中断处理过程gdintr
    先检查磁盘是否已经启动,若尚未启动,程序便不予理睬即返回;若已启动,则还须先通过对状态寄存器的检查,来了解本次传送是否出错。若已出错,做好重新执行的准备,然后再传送。仅当重试多次都失败且超过规定的执行时间时,才设置出错标志。如未出错,则继续传送下一个缓冲区中的数据。

    磁盘的读/写程序
    ①读方式
    一般读方式:只把盘块中的信息读入缓冲区,由bread过程完成。
    提前读方式:当一个进程要顺序地读一个文件所在的各个盘块时,可要求提前将下一个盘块(提前块)中的信息读入缓冲区。可缩短读这块数据的时间,从而改善了系统性能。提前读功能由breada过程完成。
    ②写方式
    一般写方式:这种方式是真正地把缓冲区中的数据写到磁盘上,且进程须等待写操作完成,由bwrite过程完成。
    异步写方式: 进程无需等待写操作完成便可返回,异步写过程是bawrite。
    延迟写方式: 该方式并不真正启动磁盘,而只是在缓冲首部设置延迟写标志,然后便释放该缓冲区,并将之链入空闲链表的末尾。以后,当有进程申请到该缓冲区时,才将其内容写入磁盘。引入延迟写的目的是为了减少不必要的磁盘I/O。延迟写方式由过程bdwrite完成。

    文件管理

    UNIX文件系统的特点
    ①文件系统的组织是分级树形结构形式。
    ②文件的物理结构为混合索引式文件结构。
    ③采用了成组链接法管理空闲盘块。
    ④引入了索引结点的概念。

    文件系统结构
    文件名和文件属性(说明)分开存放,由文件属性构成文件的索引结点。
    UNIX文件系统结构图。
    在这里插入图片描述

    文件系统的资源管理
    当文件处于“未打开”状态时,文件需占用三种资源:
    (1)一个目录项,用以记录文件的名称和对应索引结点的编号。
    (2)一个磁盘索引结点项,用以记录文件的属性和说明信息,这些都驻留在磁盘上。
    (3)若干个盘块,用以保存文件本身。
    当文件被引用或“打开”时,须再增加三种资源:
    (1)一个内存索引结点项,该项驻留在内存中。
    (2)文件表中的一个登记项。
    (3)用户文件描述符表中的一个登记项。

    文件的物理结构
    采用一种混合索引文件结构,这是将文件所占用盘块的盘块号直接或间接地存放在该文件索引结点的13个地址项之一项中。在查找文件时,只须找到文件的索引结点,便可用直接或间接的寻址方式获得指定文件的盘块。
    寻址方式
    ①直接寻址
    在索引结点中建立了10个地址项i-addr(0)~i-addr(9),在每个地址项中直接置入该文件占用盘块的编号。这相当于单级索引文件的寻址方式。
    ②一次间接寻址
    在i-addr(10)地址项中,存放的不再是存放文件的一个物理盘块号,而是将存放了直接地址的1~256个物理盘块号的盘块的编号放于其中,这相当于两级索引文件中的寻址方式。
    ③多次间接寻址
    使用的地址项分别为索引结点中的i-addr(11)和i-addr(12)。二次间址相当于三级索引文件中的寻址方式。

    地址转换
    ①将字节偏移量转换为文件逻辑块号。
    在每次读、写时,都要先把字节偏移量转换为文件的逻辑块号和块内位移量。
    ②把文件逻辑块号转换为物理盘块号。
    直接寻址:
    首先,将文件的逻辑块号转换为索引结点中地址项的下标;其次,从该下标所指的地址项中,即可获得物理盘块号。
    一次间址:
    第一步,由于一次间址的地址项下标为10,所以可以从i-addr(10)中得到一次间址盘块号,由bread过程读间址块。
    第二步,计算一次间址中文件的逻辑块号,即将文件的逻辑块号减10,根据一次间址中的逻辑块号得到间址块号中地址项的下标,再从相应下标的地址项中得到物理盘块号。
    ③多次间址。

    索引结点的管理
    超级块:专门用于记录文件系统中盘块和磁盘索引结点使用情况的一个盘块。
    磁盘索引结点的分配与回收
    ①分配过程ialloc
    每当核心创建一个新文件。都要为之分配一个空闲磁盘i结点。若分配成功,便再分配一内存i结点。
    ②回收过程ifree
    当一个文件已不再被任何进程需要时,应将该文件从磁盘上删除,回收其所占用的盘块及相应的磁盘i结点。
    内存索引结点的分配与回收
    ①分配过程iget
    在打开文件时,为之分配内存i结点。由于允许文件被共享,因此 ,如 果一文 件早已被其他用户打开并有了内存i结点,此时便只需将该i结点中的引用计数加1;如果文件尚未被其他用户打开,则由iget过程为该文件分配一个内存i结点,并调用bread 过程将其磁盘i结点的内容拷贝到内存i结点中,同时进行初始化。
    ②回收过程iput
    每当进程要关闭某文件时,须调用iput过程先对该文件的内存i结点中的引用计数做减1操作。若结果为0,便回收该内存i结点,再判断其磁盘的i结点的联接计数,若其结果也为 0,便删除此文件,并回收分配给该文件的盘块和磁盘 i 结点。

    空闲磁盘空间的管理
    ①文件卷的组织
    0#块一般用于系统引导或空闲;1#块为超级块,用于存放文件卷的资源管理信息;从2#块起存放磁盘索引结点,直到K#块。
    ②空闲盘块的组织
    采用了成组链接法。将若干个空闲盘块划归为一个组,将每一组中的所有盘块号存放在前一组的第一个空闲盘块中,而仅把第一组中的所有空闲盘块号放入超级块的空闲盘块号栈中。
    ③空闲盘块的分配与回收
    空闲盘块的分配
    空闲盘块的分配是由alloc过程完成的,该过程的主要功能是从空闲盘块号栈中获得一空闲盘块号。
    空闲盘块的回收
    空闲盘块的回收是由free过程完成的。

    用户文件描述符表的管理
    ①用户文件描述符表
    在UNIX系统Ⅴ中,在每个进程的U区中都设置了一张用户文件描述符表。核心先对其打开请求做仔细检查后,便在该进程的用户文件描述符表中分配一个空项,取其在该表中的位移量作为文件描述符fd返回给用户。以后,当用户再访问该文件时,只需提供该文件描述符fd,系统根据fd便可找到相应文件的内存索引结点。
    ②ufalloc过程
    首先是从用户文件描述符表中查找一个空项,若找到,便将该表项的序号fd作为文件描述符写入进程的U区,然 后返回;否则,置出错标志后返回“NULL”。

    文件表的管理
    文件表
    系统为了对文件进行读/写,设置了一个确定读/写位置偏移量的读/写指针。
    除了读/写偏移量f-offset外,还设置了文件引用计数f-count,用于指示正在利用 该文件表项的进程数目,以及用于指向对应内存索引结点的指针f-inode和读/写标志f-flag。
    falloc过程
    该过程的功能是分配文件表项。调用 ufalloc 过程分配用户文件描述符表项,若找到空闲文件表项,便将该项的始址置入用户文件描述符表项中。在设置完文件描述符表项的初始值后便返回(fp)。若未找到空闲文件表表项,则返回 NULL。

    目录管理
    ①构造目录项
    构造目录的任务是由过程makenode完成的。在创建一个新文件时,由系统调用creat过程来为文件构造一个目录项,makenode 过程首先调用ialloc过程为新文 件分配一个磁盘i结点及内存i结点。当分配成功时,须先设内存i结点的初值(含拷贝),然后又调写目录过程wdir,将用户提供的文件名与分配给该文件的磁盘i结点号一起,构成一个新目录项,再将它记入其父目录文件中。
    ②删除目录项
    对于一个只由某用户独享的文件,在该用户不再需要它时,应将它从文件系统中删除,以便及时腾出存储空间。
    对于一个可供若干个用户(进程)共享的文件,内核将利用link系统调用为各用户分别建立一个与该文件的联接,并设置联接计数nlink,使之等于要共享该文件的进程数目。仅当所有联接到该文件上的用户都不再需要该文件时,其nlink值必为0,系统才执行删除此共享文件的操作。相应地,将此文件的最后一个目录项从其文件目录中删除。
    ③检索目录
    用户在第一次访问某文件时,系统按路径名去检索文件目录,得到该文件的磁盘索引结点,且返回给用户一个文件描述符。以后,用户便利用该文件描述符来访问该文件,这时系统不再去检索文件目录。
    检索目录的过程namei是根据用户给出的文件路径名,从高层到低层顺序地查找各级文件目录,寻找指定文件的索引结点号。
    链接

    链接

    编译系统

    以下是一个 hello.c 程序:

    #include <stdio.h>
    
    int main()
    {
        printf("hello, world\n");
        return 0;
    }
    

    在 Unix 系统上,由编译器把源文件转换为目标文件。
    gcc -o hello hello.c
    这个过程大致如下:
    在这里插入图片描述

    • 预处理阶段:处理以#开头的预处理命令;
    • 编译阶段:翻译成汇编文件;
    • 汇编阶段:将汇编文件翻译成可重定向目标文件;
    • 链接阶段:将可重定向目标文件和 printf.o 等单独预编译好的目标文件进行合并,得到最终的可执行目标文件。

    静态链接

    静态链接器以一组可重定向目标文件为输入,生成一个完全链接的可执行目标文件作为输出。链接器主要完成以下两个任务:

    • 符号解析:每个符号对应于一个函数、一个全局变量或一个静态变量,符号解析的目的是将每个符号引用与一个符号定义关联起来。
    • 重定位:链接器通过把每个符号定义与一个内存位置关联起来,然后修改所有对这些符号的引用,使得它们指向这个内存位置。
      在这里插入图片描述

    目标文件

    可执行目标文件:可以直接在内存中执行;
    可重定向目标文件:可与其它可重定向目标文件在链接阶段合并,创建一个可执行目标文件;
    共享目标文件:这是一种特殊的可重定向目标文件,可以在运行时被动态加载进内存并链接。

    动态链接

    静态库有以下两个问题:

    • 当静态库更新时那么整个程序都要重新进行链接;
    • 对于 printf 这种标准函数库,如果每个程序都要有代码,这会极大浪费资源。
      共享库是为了解决静态库的这两个问题而设计的,在Linux系统中通常用.so后缀来表示Windows系统上它们被称为DLL。它具有以下特点:
    • 在给定的文件系统中一个库只有一个文件,所有引用该库的可执行目标文件都共享这个文件,它不会被复制到引用它的可执行文件中;
    • 在内存中,一个共享库的.text节(已编译程序的机器代码)的一个副本可以被不同的正在运行的进程共享。
      在这里插入图片描述
    展开全文
  • 计算机操作系统_内存管理

    千次阅读 2019-03-04 10:11:09
    假定系统的内存共640K,初始状态为操作系统本身占用40K。 t1 时刻,为作业A、B、C分配80K、60K、100K、的内存空间; t2 时刻作业B完成; t3 时刻为作业D分配50K的内存空间; t4 时刻作业C、A完成; ...
  • 计算机操作系统-操作系统的定义

    千次阅读 2019-01-15 09:31:20
    操作系统层往两侧看:负责管理协调硬件、软件等计算机资源的工作 从上往下看:为上层的应用程序和用户提供简单易用的服务 从下往上看:操作系统系统软件,而不是硬件 定义 Operating System是指控制和管理整个...
  • 计算机操作系统课后习题答案

    千次阅读 2019-04-14 17:16:19
    计算机操作系统(第四版)课后习题答案(完整版) 第一章 1.设计现代OS的主要目标是什么? 答:(1)有效性 (2)方便性 (3)可扩充性 (4)开放性 2.OS的作用可表现在哪几个方面? 答:(1)OS作为用户与计算机...
  • 计算机操作系统原理

    千次阅读 2019-09-23 09:04:31
    最近准备i面试,抽时间回顾一下计算机操作系统原理. -2018.10.1 1、硬件基础 计算机的构成: 处理器(CPU):主要包括运算器、控制器 内存(主存储器) 输入输出设备 详细的讲,CPU内部包括: 存储器地址寄存器...
  • 操作系统基础知识复习总结

    万次阅读 多人点赞 2019-08-17 20:59:38
    操作系统 操作系统概述 操作系统作用 存储管理 处理机管理 设备管理 文件管理 用户接口 操作系统的定义 是管理和控制计算机系统中各种硬件和软件资源、合理地组织计算机工作流程的...
  • 计算机操作系统知识点汇总(三)

    千次阅读 2018-10-03 21:03:16
    操作系统 一、概述 1、基本特征 (1)并发:并发是指宏观上在一段时间内能同时运行多个程序,而并行则指同一时刻能运行多个指令。操作系统通过引入进程和线程使得程序能够并发运行; (2)共享:共享是指系统中...
  • 计算机操作系统_银行家算法

    万次阅读 多人点赞 2020-04-18 00:52:33
    银行家算法
  • 操作系统作为用户与计算机硬件系统之间的接口,用户可通过三种方式使用计算机:命令方式、系统调用方式、图标-窗口方式 1.命令方式:典型的命令行方式有DOS系统和Unix系统等 2.系统调用方式:(system call)为了...
  •  网络操作系统计算机网络中的各台计算机有机地结合起来,提供一种统一、经济而有效的使用各台计算机的方法,实现各个计算机之间的互相传送数据。网络操作系统最主要的特点是网络中各种资源的共享以及各台计算机...
  • 本文分享配套的课件和课后习题答案。 计算机操作系统课后习题答案(第四版) 汤小丹、梁红兵、哲凤屏、汤子瀛编著 西安电子科技大学出版社出版
  • 电脑有时候会出现一些小问题,这里描述了本次操作由于这台计算机的限制而被取消.请与您的系统管理员联系问题的解决办法。
  • 计算机操作系统原理与设计.pdf 下载
  •  1、操作系统计算机硬件设备进行操作,如控制声卡发出声音,控制显卡绘制图形等。  2、操作系统可以感受到用户对输入设备的操作,如鼠标的移动,键盘的按键被按下等,并且可以知道鼠标移动的位置,被按下键盘的...
1 2 3 4 5 ... 20
收藏数 953,322
精华内容 381,328
关键字:

计算机操作系统