操作系统课堂笔记_操作系统笔记

第一章概述

操作系统（Operating System, OS）是计算机系统中最重要的系统软件，它统一管理计算机系统的硬件资源与信息资源，控制与调度上层软件的执行并为其提供易于使用的接口。

1.1计算机系统

操作系统在计算机系统中的地位：操作系统是硬件系统之上安装的第一层系统软件，是与硬件结合最紧密的一种系统软件，也是用户使用计算机的接口。

计算机软件系统包括系统软件、支撑软件和应用软件三大组成部分。

• 实用程序是为了方便用户使用所设置的操作系统外围的扩展程序，包括文本编辑工具、调试工具等。
• 支撑软件用来支持用户操作计算机的环境，提供软件开发工具，包括接口软件、工具软件、环境数据库等。
• 应用软件是用户按其需要自行编写的专用程序。
• 系统软件是指控制和协调计算机及外部设备，支持应用软件开发和运行的系统，是无需用户干预的各种程序的集合，主要功能是调度，监控和维护计算机系统；负责管理计算机系统中各种独立的硬件，使得它们可以协调工作。系统软件使得计算机使用者和其他软件将计算机当作一个整体而不需要顾及到底层每个硬件是如何工作的。

系统调用：它们屏蔽了程序访问硬件的细节。系统调用加上允许用户使用的机器指令子集，构成了一个扩展的机器指令集。

计算机硬件系统：机器语言操作系统之资源管理：机器语言+广义指令（扩充了硬件资源管理）

操作系统之文件系统：机器语言+系统调用（扩充了信息资源管理）

数据库管理系统：+数据库语言（扩充了功能更强的信息资源管理）

语言处理程序：面向问题的语言

计算机程序的解释执行过程：

1.2计算机操作系统

操作系统的定义：操作系统（Operating System, OS）是计算机系统中最基础的系统软件，它统一管理软硬件资源，控制程序执行，改善人机界面，合理组织计算机工作流程，为用户使用计算机提供良好的运行环境。

计算机系统的特征：并发性、共享性、异步性、虚拟性

• 并发性是指两个或两个以上的活动或事件在同一时间间隔内发生。（时间段）并行性是指两个或两个以上的活动或事件在同一时刻发生。（时间点）并发性的实质是对有限的物理资源强行复用，供多用户共享以提高效率
• 共享指计算机系统中的资源可被多个并发执行的进程共同使用，而不是被某个进程独占。 资源共享的方式可分成两种：透明资源共享和独占资源共享。
• 异步性，又称随机性，是指在多道程序环境中，允许多个进程并发执行，并发活动会导致随机事件的发生，由于系统资源有限而程序众多，在多数情况下，每个进程的执行并非连贯的，而是“走走停停”。因此，并发进程是以异步方式运行的，即系统中的进程何时执行？何时暂停？以什么样的速度向前推进？进程总共要花多少时间才能执行完？这些都是不可预知的。
• 虚拟性是把物理上的一个实体变成逻辑上的多个对应物，或把物理上的多个实体变成逻辑上的一个对应物的技术。

1.3深入观察操作系统

1.3.1操作系统资源管理技术

资源复用：多个进程共享物理资源，空分复用共享；时分复用共享

资源虚化：是对资源进行转化、模拟或整合，把一个或多个物理资源转变成一个或多个逻辑上的对应物的一类技术，以达到多用户共享一套物理资源的目的。

资源抽象：资源抽象是指通过编制软件来屏蔽硬件资源物理特性和实现细节，简化对硬件资源的操作、控制和使用，即不考虑物理细节而对资源执行操作的技术。

1.3.2程序控制的角度

多道程序设计思想，是指允许多个程序同时进入计算机系统的主存，通过竞争处理器资源获得交替执行。

（宏观并发，微观串行），PPT上例题求单道和多道的处理器利用率

求解某个数据问题，要求从输入机输入500个字符，用时78ms；经计算处理52ms后，花费20ms将结果存储到磁带上，如此反复，直至所有数据处理完毕。

单道程序运行：

处理器利用率：52 / (78+52+20) ≈ 35%

多道程序运行：

处理器利用率： (52+42)/(78+52+20) ≈ 63%

优点：

• • • 提高CPU、主存和设备的利用率
    • 提高系统吞吐率（即单位时间内系统运行完的作业数目和资源利用率）
    • 充分发挥系统的并行性，使得设备与设备之间，CPU与设备之间均可并行工作。

缺点：

延长了作业周转时间，即单个作业的运行时间增长。

多道程序设计的实现要点：

• • • 如何使用资源：调用操作系统提供的服务例程（如陷入机制）；
    • 如何复用CPU：调度程序（在CPU空闲时让其他程序运行）；
    • 如何使CPU与I/O设备充分并行：设备控制器与通道（专用的I/O处理器）；
    • 如何让正在运行的程序让出CPU：中断（中断正在执行的程序，引入OS处理）。

用户接口

操作系统为用户提供的接口有两类：程序接口与操作接口

• • • • 程序接口（系统调用）：是操作系统对外提供服务和功能的手段，有一组系统调用组成，获得操作系统的低层服务，访问或使用系统管理的各种软硬件资源。
      • 操作接口（作业级接口）：是操作系统为用户提供的组织和控制作业/应用程序执行的手段，由一组操作控制命令、图形用户界面或作业控制语言组成。

• • • • • 联机作业控制接口——操作控制命令
        • 脱机作业控制接口——作业控制语言（JCL）

1.3.3操作控制计算机的角度

命令解释程序，是接受和执行一条用户命令并对作业加工处理的程序包。

1.3.5程序接口的角度

系统调用：现代操作系统内核提供的一些列具有预定功能的服务例程。（系统调用把应用程序的访问请求传送至内核，调用相应的服务例程完成所需处理，再将处理结果返回给应用程序。根本原因是对系统进行“保护”，在逻辑上相互隔离）

系统调用的作用：

①内核可以基于权限和规则对资源访问进行裁决，保证系统的安全性；

②系统调用对资源进行抽象，提供一致性接口，避免用户在使用资源时发生错误，且使编程效率大大提高。

系统调用大致可分为六大类：进程控制、文件管理、设备管理、信息维护、通信 、保护。

系统调用是应用程序获得操作系统服务的唯一途径，是操作系统提供给编程人员的唯一接口。

操作系统实现系统调用功能的机制称为系统陷阱或系统异常处理机制。

①陷入指令（trap）/访管指令（ supervisor）是指由于系统调用而引起处理器中断的机器指令，它是非特权指令，在用户态下执行时会产生CPU模式切换，即由用户态转换到内核态。

每个系统调用都事先规定编号，称为功能号。

②系统调用的实现要点

• 编写系统调用服务例程
• 设计系统调用入口地址表
• 陷阱处理机制

处理机的状态：内核态（核心态、管态；处理器运行系统程序）与用户态（目态、普通态；处理器运行用户程序）

特权指令（内核时，启动I/O设备、设置时钟、控制中断屏蔽位、清内存、建立存储键、加载PSW等敏感性操作）非特权指令（内核态与用户态）

系统调用与函数调用之间的区别：

• 调用形式不同：函数按转向地址调用，系统调用按功能号调用。
• 实现方式不同：函数代码在用户态执行，可由用户自己编制或库函数提供，使用用户栈；系统调用代码则在内核态执行，由操作系统提供，要通过系统陷阱机制从用户态转换到内核态，使用核心栈。
• 被调用代码的位置不同：函数调用是静态调用，调用程序和被调用代码处于同一程序内，经链接后是目标代码的一部分，当函数升级或修改时必须重新编译和链接；系统调用是动态调用，系统调用的服务例程位于操作系统中，是系统级程序，当系统调用的服务例程升级或修改时与调用程序无关。
• 提供方式不同：函数调用通常由编程语言提供，不同语言所提供的函数功能、类型和数量可以不同；系统调用由操作系统提供，一旦操作系统设计好，系统调用的功能、类型和数量便固定不变。
• 像函数调用一样，系统调用也允许嵌套调用。

构件：组成操作系统的基本单位（主要有内核，进程，线程，类程和管程）

内核：是一组中断驱动的程序模块，作为可信软件来提供支持进程并发执行的基本功能和基本操作，它驻留在内核空间，运行于内核态，具有执行特权指令、直接访问硬件设备和所有主存空间的权限，且不可被其他进程抢占。

作业:

1. 思考题 （3）、（4）、（6）、（8）、（13）和（14）。 修改（8）为：什么是系统调用？简述其处理过程及其和函数调用的区别。

2. 应用题 （3）etg

操作系统功能：

1）设备管理：主要负责内核和外围设备的数据交互，实质是对硬件设备的管理，包括输入输出设备的分配、初始化、维护和回收等等。

2）作业管理：负责人机交互、图形界面或系统任务的管理。

3）文件管理：涉及文件的逻辑组织和物理组织、目录结构和管理等等。从操作系统的角度来看，文件系统是系统对文件存储器的存储空间进行分配、维护、回收，同时负责文件的索引、共享和权限保护.从用户的角度来说，文件系统是按照文件目录和文件名来进行存取的。

4）进程管理：说明一个进程存在的唯一标志是PCB(进程控制块)，负责维护进程的信息和状态。进程管理的实质是系统采取某些进程调度算法来是处理合理的分配给每个任务使用。

5）存储管理：数据的存储方式和组织结构。

第二章处理器管理

处理器管理是操作系统的重要组成部分，负责管理、调度和分配计算机系统的处理器资源，并控制程序的执行。

2.1处理器

中央处理器CPU

寄存器分为用户程序可见寄存器（通用寄存器，地址寄存器）、控制与状态寄存器（程序计数器，指令寄存器，条件码，标志位）两种。

机器指令是计算机系统执行的基本命令，是中央处理器执行的基本单位。

指令由一个或多个字节组成，包括操作码字段、一个或多个操作数地址字段，以及一些表征机器状态的状态字以及特征码。

特权指令：仅在内核态下才能使用的指令（启动I/O设备、设置时钟、控制中断屏蔽位、清内存、建立存储键、加载PSW等敏感性操作）

非特权指令：在内核态与用户态下都能使用的指令。

内核态，是操作系统管理程序运行时所处的状态，可认为处理器正在运行可信系统软件，此时全部机器指令都被允许在处理器上执行，程序可访问所有主存单元和系统资源，并具有改变处理器状态的能力。

用户态，是指处理器正在运行非可信系统软件/用户程序时所处的状态此时无法执行特权指令，且访问仅限于当前正在处理器上执行程序所在的地址空间。

处理器模式的切换（模式切换）：包括“用户模式一内核模式和“内核模式一用户模式”的转换。

• 中断、异常或系统异常等事件导致用户程序向OS内核切换触发:用户模式一内核模式，如:程序请求操作系统服务、程序运行时发生异常、程序运行时发生并响应中断。
• OS内核处理完成后，调用中断返回指令(如Intel的iret)，触发:内核模式一用户模式

每个进程被创建时捆绑一个核心栈，具有可读、可写、不可执行的属性。

用户栈是操作系统在用户进程空间中开辟的一块区域。

用于保存应用程序的子程序 (函数)间相互调用的参数、返回值、返回点以及子程序的局部变量。

核心栈也叫系统栈或内核栈，是主存中属于操作系统内核空间的一块区域。

其用途包括

• 保存中断现场
• 保存操作系统程序 (函数)间相互调用的参数、返回值、返回点以及程序局部变量。

2.2中断

中断，是指在程序执行过程中，遇到急需处理的事件时，暂时中止现行程序在CPU上的运行，转去执行相应的事件处理程序，待处理完成后再返回断点或调度其他程序执行的过程。

中断向量:是指中断服务程序入口地址的偏移量与段基值，一个中断向量占据4字节空间。

·操作系统是由“中断驱动”的;换言之，中断是激活操作系统的唯一方式。

中断有广义和狭义之分，上述中断是指广义的中断。

• 狭义的中断指来源于处理器之外的中断事件，即与当前运行指令无关的中断事件，如I/O中断、时钟中断、外部信号中断等。
• 异常指当前运行指令引起的中断事件，如地址异常、算术异常处理器硬件故障等。
• 系统异常指执行陷入指令而触发系统调用引起的中断事件，如请求设备、请求I/O、创建进程

终端装置：计算机系统中发现并响应中断、异常的硬件装置。

中断处理程序是操作系统中处理中断事件的控制程序，主要任务是处理中断事件和恢复正常操作。

中断处理过程为:

1保护处理器现场。

2分析被中断进程的PSW中断码字段，识别中断源

3根据中断源对中断事件进行具体处理

4恢复正常操作。包括两种情况:

• • 情况一:对于某些能够被快速处理的中断，处理完毕后直接返回刚刚被中断的进程。
  • 情况二:对于其他中断，需要中断当前进程的运行，调整进程队列，启动进程调度，选择下一个执行的进程并恢复其执行.

• 

中断屏蔽是指禁止CPU响应中断或者禁止产生中断。

2.3进程管理

引入进程的两个主要目的:

• 刻画运行程序之间的并发性。引入进程，能较好地刻画系统内部程序的并发执行。
• 解决资源的共享性，提高资源利用率。

“可再入”程序:是指能够被多个程序同时调用的程序。（可重入代码，纯代码）

进程的概念从操作系统实现者的观点出发，一个进程包括五个实体部分:

• (OS管理运行程序的)数据结构P
• (运行程序的)主存或虚拟主存代码C
• (运行程序的)主存或虚拟主存数据D
• (运行程序的)通用寄存器信息R
• (OS控制程序执行的)程序状态字信息 PSW

进程的定义：进程是具有独立功能的程序在某个数据集合上的一次活动，也是操作系统进行资源分配和保护的基本单位。

列车更具有一般意义，火车只是特例。

进程特征：

• 动态性：动态性是指进程是程序在数据集合上的一次动态执行过程，是动态的概念。

同时，它还有生命周期，由创建而产生，由调度而执行，由撤销而消亡。

• 并发性：同一时间段或同一时间点内发生的两个及两个以上的活动或事件
• 异步性：进程执行不连贯
• 共享性：多个进程可以共享相同程序，进程与程序并不是一一对应的
• 独立性：每个进程是操作系统中的一个独立实体，有自己的虚存空间，程序寄存器和内部状态等。

进程的状态

• 三态模型：

1. 1. 运行态 (running进程占有处理器正在运行的状态。
   2. 就绪态进程具备运行条件，等待系统分配处理器以便( ready) :运行的状态。
   3. 等待态 (waiting) : 又称阻塞态、睡眠态，指进程不具备运行条件，等待某个事件完成的状态

通常，进程在创建后处于就绪态

• 五态模型：加入新建态，终止态
• 具有挂起状态的模型

• • 性能低和死锁原因：运行资源不足。
  • 解决办法:剥夺某些进程的内存及其他资源，调入OS管理的对换区，不参加进程调度，待适当时候再调入内存、恢复资源、参与运行，这就是进程挂起。
  • 挂起态与等待态有着本质区别，后者占有已申请到的资源处于等待；前者没有任何资源。

进程控制块：PCB是操作系统管理进程建立的数据结构，是进程存在的唯一标志，用来记录和刻画进程状态及环境信息，是进程动态特征的汇集，也是操作系统掌握进程的唯一资料结构和管理进程的主要依据。

进程控制块与进程一一对应，是系统感知进程存在的唯一标识。

PCB包括进程执行时的情况以及进程让出处理器后所处的状态、断点等信息，一般包含三种信息：

• 标识信息。用于唯一地标识一个进程。
• 现场信息。用于保留进程在运行时存放在处理器现场中的各种信息。
• 控制信息。用于管理和调度进程

进程映像：由于进程状态在不断发生变化，某时刻进程的内容及其状态集合。包括以下组成部分:

1. 进程控制块:与进程一一对应。用来存储进程标识号、处理器状态信息和进程控制信息。
2. 进程数据块:是组成进程的各种私有数据，用户栈也在数据块中开辟，用于在函数调用时存放栈帧、局部变量和返回地址等。
3. 进程核心栈:每个进程捆绑一个，进程在内核态工作时使用，用来保存中断/异常现场，保存内核函数调用的参数、局部变量和返回地址等。

进程上下文：在操作系统中，进程物理实体和支持进程运行的环境 。

进程在其当前上下文中运行，当系统调度新进程占有处理器时，新老进程随之发生上下文切换。

它由三个部分组成:

1. 用户级上下文:由程序块、数据块、共享内存区、用户栈组成，占用进程的虚存空间。
2. 寄存器上下文:由处理器状态寄存器、指令计数器、栈指针、通用寄存器等组成。
3. 系统级上下文:由进程控制块、主存管理信息、核心栈等操作系统管理进程所需要的信息组成。

关键的进程管理程序：

系统调用/中断/异常处理程序

队列管理程序:管理PCB

进程控制程序:用于控制进程创建与状态转换

进程调度程序(独立进程居多):用于处理器调度

进程通信程序(多个程序包)

终端登录与作业控制程序、性能监控程序、审计程序等外围程序

进程控制程序中，原语是由若干条指令构成的完成某种特定功能的程序，执行上具有不可分割性。

进程切换指从正在运行的进程中收回处理器，让待运行进程来占有处理器运行。实质上就是被中断运行进程与待运行进程的上下文切换。

模式切换：处理器状态切换：正向模式切换（用户态-》内核态），逆向模式切换（内核态-》用户态）

服务器进程：把操作系统服务例程组织为在用户态工作的系统进程。

2.4多线程技术

线程的定义：线程是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。

线程的优点：（比起进程）

• 线程切换速度快速
• 通信易于实现
• 减少管理开销
• 并发程度提高

作业

1.思考题

（3）（7）（8） (11)~ (17)和(19)

2.应用题

（1）（7）（9）(14) 、(15) 、(18) 和 (21)

第三章存储管理

存储管理负责管理计算机系统的主存

存储管理的目的:提高内存的利用率为多道程序的运行提供良好的环境从逻辑上扩充内存

主存空间一般分为两部分

(1)系统区: 用于存放操作系统内核程序和数据结构等

(2)用户区: 用于存放应用程序和数据

3.1存储管理基础

逻辑地址空间:也叫程序地址空间，是指用户编程所使用的地址空间。

逻辑地址:又称相对地址，是指程序地址空间中的地址。它总是相对某个基准(通常为0)开始连续编号。

逻辑地址有两种形式:

• 一维逻辑地址(地址)
• 二维逻辑地址 (段号:段内地址)

段式程序设计：把一个程序设计成多段：代码段，数据段，堆栈段

段覆盖技术：是指用户在程序设计时包括主程序段，堆栈段，多个子程序段和数据段，执行程序时只调入主程序段，堆栈段和需要的子程序段与数据段，并根据执行需要，由程序设计者预先设计代码决定哪些段调入内存。

处理器执行指令和处理数据时是按照物理地址访问主存的。

物理地址: 又称绝对地址，是物理主存的存储单元从统一的基地址0开始顺序编号的地址。

物理地址空间：主存中所有存储单元所限定的地址范围，即物理地址的集合。

物理地址空间是由存储器地址总线扫描出来的空间，其大小取决于实际安装的内存容量。

主存的复用方式

多道程序设计需要复用内存，即多个进程划分使用主存，主存复用有分区服用，页框复用。

分区复用:将主存划分为多个固定或可变尺寸的分区，一个程序或程序段占用一个分区。

页框复用:将主存划分成多个固定大小的页框(也叫页架或主存物理块)，一个程序或程序段根据页框大小自动划分成页面，进而占用多个页框。

存储管理的基本模式

• 单连续分区存储管理:一维逻辑地址空间的程序占用一个主存的固定分区或可变分区。
• 页式存储管理:一维逻辑地址空间的程序，占用多个主存页框区。
• 段式存储管理:段式二维逻辑地址空间的程序，占用多个主存可变分区，一个段占用一个单连续的主存分区。
• 段页式存储管理:段式二维逻辑地址空间的程序，占用多个主存页框区。

地址转换：重定位，静态地址重定位，动态地址重定位。

虚拟存储器

虚拟存储器的定义:在计算机系统的层次式存储器中，自动实现部分装入和部分替换功能，在逻辑上为用户提供一个比物理主存容量大得多的、可寻址的“主存储器”虚拟存储器的容量与物理主存大小无关，但受限于计算机地址结构和可用的磁盘容量。虚拟地址空间等同于实际物理主存加部分硬盘区域所组成的存储空间

(1)为什么要引入虚拟存储器?

实存管理，必须为进程分配足够的主存空间，装入其全部信息。由于进程的全部信息装入主存后，实际上并非同时使用，会降低主存利用率。

(2)实现虚拟存储器的基本思路（实现方式 ）

部分装入，进程的程序和数据只需装入一部分即可运行，其余部分当需要运行时才从磁盘装入内存。

部分替换，当装入程序时内存没有足够的空间时，系统可将内存中暂时不用的信息移至磁盘。

程序局部性原理一一虚拟存储器实现的理论依据

程序局部性原理，指程序在执行过程中的一个较短时间内，所执行的指令地址或操作数地址分别局限于一定的存储区域中。它可细分为时间局部性和空间局部性。

• 时间局部性:一条指令被执行了，则在不久的将来它可能再被执行。
• 空间局部性:若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用。

作业：

1. 思考题

（2）、（4）、（5）、（11）、 （13）、 （16）和（18）。

2. 应用题

（4）、（9）、（12）、（13）、（15）、（16）、（21）（加OPT和CLOCK页面调度算法）和（25）。

• 在页式存储管理中，决定页面大小的主要因素是什么？

页面的大小取决于存储器分块的大小，即取决于地址结构，取决于内存块号和字长，与系统硬件有着重要关系。

• 试述缺页中断与一般中断之间的区别。

两种中断产生的时刻不同，前者在执行一条指令中间同时产生并立即转去处理，而后者则在一条指令执行完毕后，当硬件终端装置发现有中断请求后才去响应。

两种中断处理完后的归属不同，前者返回原指令重新执行，后者重新调度或执行下一条指令。

• 可变分区空闲块分配算法

• • 最先适配算法：从头到尾遍历，第一个放得下的即可。
  • 最优适配算法：放得下的最小的那个，实现方法，按大小，从小到大排序，从头遍历。
  • 最坏适配算法：按大小，从大到小排，每次挑最大的
  • 下次适配算法：第一次从头开始遍历，第一个放得下的即可，剩下的都接上上一次寻找的位置接着往下找。

大题：

（15）有误，（内存）1024kb = 220

4KB = 212 （页内地址数）B 20 - 12 = 8, 8位页号。

• 最近最少使用算法（LRU）对占用的页面计数，优先替换掉使用次数最小的页面
• 先进先出算法（FIFO）
• 最佳页面替换算法（OPT）优先替换掉最晚会被调用的页面

请求分页式管理

• 主要功能：当需要执行某条指令而发现它不在内存时或当某条指令需要访问其他的数据或指令时，这些指令和数据不在内存，从而发生缺页中断，于是系统将外存中相应的页面调入内存
• 优点：按需访问，只有被访问的页面的才会进入内存，节省了内存空间
• 缺点：处理缺页中断次数过多和调页的系统开销较大，由于每次仅调入一页，增加了磁盘I/O次数

程序的链接有以下三种方式：

• 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的可执行程序，以后不再拆开。
• 装入时动态链接：将用户源程序编译后所得到的一组目标模块，在装入内存时，釆用边装入边链接的链接方式。
• 运行时动态链接：对某些目标模块的链接，是在程序执行中需要该目标模块时，才对它进行的链接。其优点是便于修改和更新，便于实现对目标模块的共享。

分页存储管理的基本原理：
操作系统以页框为单位为各个进程分配内存空间。系统自动地将作业的地址空间分页，将系统的主存空间分块，页与块等大小，在作业运行时，一次性把作业的全部页面装入内存，各个页所占的内存块可以不连续，也不必按先后顺序，可以放到不相邻的各个页框中。这实际是个把作业从地址空间映射到存储空间的过程

第四章设备管理

4.1设备管理基础

设备管理的对象：输入/输出设备。

设备管理手段：操作系统通常将设备抽象成设备文件，赋予文件属性，以类似于文件操作的方式提供对设备的访问和保护接口，并按照分层的思想实现设备管理。

设备管理目的：对设备进行抽象，屏蔽设备的物理细节和操作过程，配置统一的驱动程序，提供统一的人机交互界面。解决设备与设备之间，设备和CPU之间处理速度不匹配的问题，使得CPU和设备能够充分并行工作，提高CPU和设备的利用率，以此提高计算机系统的整体性能。

设备管理的功能：设备中断处理，缓冲区管理 ，设备分配与去配，设备驱动调度 ，实现虚拟设备

1.I/O设备

• I/O设备又称为外围设备或外部设备，简称外设，用于计算机系统与外部世界（如用户、其它计算机或电子设备等）进行信息交换与存储。
• I/O系统：I/O设备及其接口线路、控制部件、通道和管理软件的总称。
• I/O操作：计算机的主存和 I/O设备之间的信息传送操作。

2. I/O设备分类

按照I/O信息交换单位及设备管理实现方式分类：字符设备和块设备。

• 字符设备是指计算机与设备之间以字符为单位进行信息交换，即一次交换一个或若干个字节。
• 字符设备的基本特征是：传输速率较低；不可寻址（即不能指定输入时的源地址及输出时的目标地址）；字符设备在I/O时，常采用中断驱动方式。
• 块是存储介质上由连续信息组成的一个区域。
• 块设备，是指计算机与设备之间以块为单位进行信息交换，例如磁盘、磁带等存储型设备。
• 块设备的基本特征是：传输速率较高，通常每秒钟为几兆位；可寻址，即随机的读/写任意一块；块设备在I/O时，常采用DMA方式。

I/O设备控制方式： I/O设备必须通过设备控制器才能与CPU交换数据。

设备控制器是CPU和设备之间的一个接口，它接收从CPU发来的命令，控制I/O设备操作，实现主存和设备之间的数据传输。

I/O 控制宗旨：尽量减少主机对I/O控制的干预，把主机从繁杂的I/O控制事物中解脱出来，以更多的去完成其数据处理任务。

I/O设备的控制方式分为四类：轮询方式、中断方式、DMA方式和通道方式。主要差别在于：中央处理器和外围设备并行工作的方式不同，并行工作的程度不同。

• 轮询方式:处理器向控制器发送一个I/O 命令如果设备未就绪，则重复测试过程，直至设备就绪执行数据交换等待I/O操作完成后，才可以继续其它操作。特点：轮询：处理器循环检查设备的状态是否就绪；顺序：CPU和设备只能串行工作，效率低下。

• 中断方式 :处理器向控制器发出一个I/O命令，然后继续执行后续指令如果该进程不需要等待I/O完成，后续指令可以仍是该进程中的指令否则，该进程在这个中断上挂起，处理器执行其他工作控制器检查设备状态，就绪后发起中断CPU响应中断，转向中断处理程序中断处理程序执行数据读写操作 恢复执行原先的程序.特点：响应中断后会终止原程序的执行CPU不需要等待I/O设备就绪CPU需要参与数据传送 CPU和设备部分并行操作，效率有所提高

• DMA方式:CPU和设备能并行工作。DMA模块模仿处理器来控制主存和设备控制器之间的数据交换。处理器向DMA模块发出 I/O命令 处理器继续执行其它工作，DMA模块负责传送全部数据数据传送结束后，DMA 中断处理器.特点：CPU不会终止原程序的执行CPU只在数据传送的开始和结束时参与， CPU与设备并行工作。开始时，CPU需要对DMA模块进行初始化结束时，CPU响应中断，但不必保存现场.

• 通道方式 流程：CPU遇到I/O请求，启动指定通道 一旦启动成功，通道开始控制I/O设备进行操作,CPU执行其他任务I/O操作完成后，I/O通道发出中断，CPU停止当前工作，转向处理I/O操作结束事件.特点：CPU、通道和设备之间并行工作。

4.2 设备管理软件

(1) I/O 软件的总体设计目标高效率：改善设备效率，尤其是磁盘I/O操作的效率。 通用性：用统一的标准来管理所有设备。

(2)设计思路把软件组织成层次结构，低层软件用来屏蔽硬件细节，高层软件向用户提供简洁、友善的界面。

(3) I/O 软件设计需要考虑的问题 设备无关性：程序员编写程序时与具体的物理设备无关。出错处理：低层软件能处理的错误不让高层软件感知。同步/异步传输：支持阻塞和中断驱动两种工作方式。缓冲技术：建立数据缓冲区，提高吞吐率。

2. I/O软件的分层结构

I/O软件自底向上依次组织成4个层次：I/O中断处理程序、 I/O设备驱动程序、独立于设备的I/O软件和用户空间的I/O软件。

4.2.3I/O缓冲技术

(1) 引入缓冲的目的：

• 解决CPU与设备之间速度不匹配的矛盾；
• 协调逻辑记录大小和物理记录大小不一致的问题；
• 提高CPU和设备的并行性；
• 减少I/O操作对CPU的中断次数，放宽对CPU 中断响应时间的要求。

(2) 缓冲区的概念缓冲区，是在内存中开辟的存储区，专门用于临时存放I/O操作的数据。

(3) 实现缓冲技术的基本思想

• 写操作：将数据送至缓冲区，直到装满，进程继续计算，同时系统将缓冲区的内容写到设备上。
• 读操作：系统将设备上的物理记录读至缓冲区，根据要求将当前所需要的数据从缓冲区中读出并传送给进程。

(4)缓冲区

• 单缓冲
• 双缓冲
• 循环缓冲

4.3独占性外围设备的的分配

设备独立性：是指应用程序独立于具体使用的物理设备的特性。

• 为了实现设备独立性，引入了逻辑设备和物理设备两个概念。在应用程序中，使用逻辑设备名来请求使用某类设备；而系统在实际执行时，使用物理设备名。系统必须具有将逻辑设备名转换成对应的物理设备名的功能，通常是通过对照表来实现转换。
• 逻辑设备表LUT（Logical Unit Table）：该表的每一个表目中包含了三项：逻辑设备名、物理设备名和设备驱动程序的入口地址。当以后进程再利用逻辑设备名来请求I/O设备时，系统通过查找LUT，即可找到物理设备和驱动程序。
• 设备独立性的优点：①应用程序与具体物理设备无关，系统增减或变更设备时不需要修改源程序；②易于应对I/O设备故障，提高系统可靠性；③增加设备分配的灵活性，更有效地利用设备资源，实现多道程序设计。

独占型外设的分配：

(1) 根据设备的物理特性将外围设备分为三类：

独占设备：是指在一段时间内只允许一个用户（进程）访问的设备。系统一旦把这类设备分配给某个进程后，便由该进程独占，直至用完释放。卡片机、打印机、用户终端等大多数低速输入、输出设备都是独占设备。

共享设备：是指在一段时间内允许多个进程同时访问的设备。设备交替地为进程进行信息的读或写操作。共享设备必须是可寻址的和可随机访问的设备。典型的共享设备是磁盘。对共享设备不仅可获得良好的设备利用率，而且是实现文件系统和数据库系统的物质基础。

虚拟设备：是指通过虚拟技术将一台独占设备变换成若干台逻辑设备，供若干个用户（进程）同时使用的设备。

(2) 分配方式

静态分配：在作业执行之前将所要使用的设备全部分配给它，当作业在执行过程中不再需要使用这类设备或作业执行结束将要撤离时，再收回设备。静态分配实现简单，能防止系统发生死锁，但会降低设备利用率。

动态分配：在作业执行过程中需要设备时提出申请，系统分配成功后使用，用完回收。可以提高设备利用率，但会出现死锁问题。例如打印机。对于磁盘等共享设备，一般不必进行分配，设备管理的主要工作是驱动调度和实施驱动。

(3) 分配算法

常用的有先请求先服务，优先级高者先服务等分配算法。此外，在多进程请求I/O设备分配时，应预先进行检查，防止因循环等待对方所占用的设备而产生死锁。

(1) 设备类表系统中拥有一张设备类表，每类设备对应于表中一栏，包括内容有：设备类、总台数、空闲台数和设备表起始地址等。

(2) 设备表每类设备都有各自的设备表，用来登记这类设备中的每台物理设备，包括：物理设备名（号），逻辑设备名（号），占有设备的进程号、已分配/未分配、好/坏标志等。

4.4共享型外围设备的驱动

• 1. 顺序存取存储设备：顺序存取存储设备是严格依赖信息的物理位置进行定位和读写的存储设备。它具有存储容量大、稳定可靠、卷可装卸和便于保存等优点。
• 2. 直接存取存储设备:磁盘是一种直接（随机）存取存储设备。每个物理记录有确定的位置和唯一的地址，存取任何一个物理块所需的时间几乎不依赖于此信息的位置。 为了访问磁盘上的一条物理记录，必须给出三个参数： 柱面号、磁头号、扇区号

• 

读写数据时，磁头必须定位到指定磁道上指定扇区的开始处。

过程：寻道时间：控制移动臂到达指定柱面，选择磁头号

旋转延迟时间：等待要读写的扇区旋转到磁头下

数据传送时间

2. 磁盘读写时间

磁盘完成数据读写所需要的时间是寻道时间、旋转延迟、传送时间的总和。

存取时间 = 寻道时间 + 平均旋转等待时间 + 平均传输时间

r：磁盘旋转的角速度（单位：转/秒）b：要传送的字节数N：每个磁道中的字节数

磁盘的驱动调度包括移臂调度和旋转调度。

1. 磁盘移臂调度

目的：驱动调度首先要使移动臂的移动时间尽可能短，从而节省处理多个访问请求的寻道总时间。

移臂调度的算法主要有：

(1) “先来先服务”算法 FCFS 调度策略：优先调度先发出的访问请求。

缺点：磁盘臂随机移动，不考虑各I/O请求之间的相对次序和移动臂当前的位置，进程等待I/O请求的时间会很长，寻道性能较差。

(2) “最短查找时间优先”算法调度策略：总是先执行查找时间最短的访问请求。较先来先服务算法有较好的寻道性能。

缺点：存在“饥饿”现象。

(3) 扫描算法·单向扫描移动臂总向一个方向扫描，顺序处理I/O请求，在归途中不提供服务。适用于不断有大量柱面均匀分布的请求情形。

(3) 扫描算法·双向扫描：移动臂每次向一个方向移动，遇到最近的I/O请求便进行处理，到达最后一个柱面后再向相反方向移动，继续处理请求，如此循环往复。

缺点：对最近扫描所跨越区域的请求响应较慢。·

（4）电梯调度：无请求时移动臂停止不动，有请求时按电梯规律移动。每次选择沿移动臂的移动方向最近的柱面，如果当前移动方向上没有但相反方向有请求时，改变移动方向。

2. 旋转调度

目的：旋转调度需要在最少的旋转圈数之内解决该柱面上的全部数据访问请求，使得旋转延迟的总时间最少。

循环排序:通过优化I/O请求排序，在最少旋转圈数内完成位于同一柱面的访问请求。旋转位置测定硬件和多磁头同时读写技术有利于提高旋转调度的效率。

优化分布：通过信息在存储空间的排列位置优化来减少旋转延迟。交叉

按柱面而非盘面进行数据读写：连续记录数据时，先记录在同一柱面的不同磁道上，然后再更换柱面，可以减少数据读写时的移臂操作。

交叉因子:因此，对扇区编号时会间隔编号，例如交叉因子为2:1表示相邻编号之间会间隔1个扇区，3:1表示会间隔2个扇区。

4.5 虚拟设备

虚拟设备是用一类物理设备模拟另一类物理设备的技术，可以将独占型设备变为共享型设备。是通过虚拟技术将一台独占设备变换为若干台逻辑设备供若干用户或进程同时使用的设备。

主要条件：1）大容量缓冲区 2）软件配有预输入和缓输出程序并能管理程序。

SPOOLing，联机同时外围设备操作，又称作假脱机操作，是使独占设备虚拟为共享设备的一种技术。为了模拟脱机外围设备操作，需要提供“预输入”和“缓输出”功能。

作业

1. 思考题 （3）、（4）、（8）、（9）、（13）和（18）。

2. 应用题 （3） 、（4）和（12）。

第五章文件管理

文件逻辑结构可分为字符流式无结构文件和记录式有结构文件

1.文件组织：文件组织指文件中信息的配置和构造方式，应该从文件的逻辑结构和组织以及文件的物理结构和组织两方面考虑。

2.文件的逻辑结构：文件的逻辑结构和组织是从用户观点出发，研究用户概念中抽象的信息组织方式，这是用户能观察到的，可加以处理的数据集合。由于数据可独立于物理环境构造，故称为逻辑结构，相关数据的集合构成逻辑文件。

3.文件的物理结构：和组织是指逻辑文件在物理存储空间中的存放方法和组织关系。这时的文件看做物理文件，即相关物理块的集合。

文件的存储结构涉及: 块的划分、记录的排列、索引的组织、信息的搜索等许多问题，其优劣直接影响文件系统的性能。构造文件物理结构的方法有计算法和指针法。

4.关系：存储设备的物理特性会影响到数据的逻辑组织和所采用的存取方法。

5.存取方法：

顺序存取法：顺序存取按照文件的逻辑地址顺序存取
例子:若当前读取的记录为Ri，则下一次读取的记录被自动地确定为Ri的下一个相邻记录Ri+1。
特点:在无结构字符流文件中，顺序存取反映当前读写指针的变化。在存取完一段信息之后，读写指针自动加或减去该段信息长度，指出下次存取时的位置。大多数操作系统采用顺序存取和随机存取方法。

随机存取法(直接存取法)：随机存取法允许用户根据记录编号存取文件的任一记录，或者是根据存取命令把读写指针移到指定读写处进行读写。大多数操作系统采用顺序存取和随机存取方法。

索引存取法：按关键字存取法通常用于复杂文件系统，特别是数据库管理系统。根据给定的关键字或记录名进行文件的存取。首先搜索待存取记录的逻辑位置，再将其转换到相应的物理地址后进行存取。

按关键字存取法对文件的搜索包括两种：关键字搜索和记录搜索。

关键字搜索：关键字搜索是在用户给定要搜索的关键字和记录之后，确定该关键字在文件中的位置

记录搜索：记录搜索是在搜索到要查找的关键字之后，在含有该关键字的所有记录中查找出需要的记录。

三种搜索算法

线性搜索法(linear search)；

线性搜索法(linear search)；

二分搜索法(binary search algorithm)。

第六章并发程序设计

多进程的关系：

进程并发运行的环境中，多个进程之间存在如下竞争和协作的关系：

- 进程中的资源争用(间接作用)

当并发进程竞争使用同一个资源时，它们之间就会发生冲突。为了避免冲突，当一个进程获得资源时，另一个进程必须等待。这种情况需要通过互斥机制来解决。

- 进程间通过共享的合作(间接作用)

一个进程等待另一个进程的执行，并以另一个进程的执行结果作为本进程的执行条件，就形成了同步机制

- 进程间通过通信的合作(直接作用)

进程间还可以通过通信进行合作，同性提供了同步和协调各种活动的方法。如操作系统提供的通信功能。

PV操作

PV原语的含义
P操作和V操作是不可中断的程序段，称为原语。PV原语及信号量的概念都是由荷兰科学家E.W.Dijkstra提出的。信号量sem是一整数，sem大于等于零时代表可供并发进程使用的资源实体数，但sem小于零时则表示正在等待使用临界区的进程数。

P原语操作的动作是：
（1） sem减1；
（2） 若sem减1后仍大于或等于零，则进程继续执行；
（3） 若sem减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度。
V原语操作的动作是：
（1） sem加1；
（2） 若相加结果大于零，则进程继续执行；
（3） 若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。

由于用于互斥的信号量sem与所有的并发进程有关，所以称之为公有信号量。公有信号量的值反映了公有资源的数量。只要把临界区置于P(sem) 和V(sem)之间，即可实现进程间的互斥。

利用PV原语实现进程同步的方法是：首先判断进程间的关系为同步的，且为各并发进程设置私有信号量，然后为私有信号量赋初值，最后利用PV原语和私有信号量规定各进程的执行顺序。下面我们将例1增添一个条件，使其成为进程间是同步的。

死锁

死锁是指一组进程中的各个进程均占有不会释放的资源，但因互相申请被其它进程所占用不会释放的资源而处于的一种永久等待状态。

死锁的四个必要条件

• • 互斥条件：进程互斥使用临界资源。一个资源每次只能被一个执行流使用；
  • 占用和等待条件：申请新资源时，不释放已占有资源。一个执行流因请求资源而阻塞时，对已获得的资源保持不放；
  • 不可剥夺条件：一个进程不能抢占其他进程占有的资源。一个执行流已获得的资源，在未使用完之前，不能强行剥夺；
  • 循坏等待条件：存在一组进程循环等待资源。若干执行流之间形成一种头尾相接的循环等待资源的关系；

避免死锁

• • 破坏死锁的四个必要条件；
  • 加锁顺序；
  • 避免锁未释放的场景；
  • 资源一次性分配

银行家算法

它提出的思想是：把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

执行步骤:

设Request i是进程Pi的请求向量，如果Request i[j]=K，表示进程P i需要K个R j类型的资源。当P i发出资源请求后，系统按下述步骤进行检查：

　　(1) 如果Request i[j]≤Need[i,j]，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

　　(2) 如果Request i[j]≤Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。

　　(3) 系统试探着把资源分配给进程P i，并修改下面数据结构中的数值：

Available[j]:= Available[j]-Request i[j]；

Allocation[i,j]:= Allocation[i,j]+Request i[j]；

Need[i,j]:= Need[i,j]-Request i[j]；

　　(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

安全性算法设计

系统所执行的安全性算法可描述如下：

　　(1) 设置两个向量：

　　 ① 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work:=Available。

　　 ② Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]:=false；当有足够资源分配给进程时，再令Finish[i]:=true。

　　(2) 从进程集合中找到一个能满足下述条件的进程：

　　 ① Finish[i]=false；

　　 ② Need[i,j]≤Work[j]；若找到，执行步骤(3)，否则，执行步骤(4)。

　　(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work[j]:= Work[j]+Allocation[i,j]；

Finish[i]:=true；

go to step （2）；

　　(4) 如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

生产者与消费者问题描述如下:

假设有n个生产者和m个消费者共享一个容量为k的缓冲器。一个生产者一次只能将一个产品放入空缓冲器中，个消费者一次只能从满的缓冲器中取出一个产品消费解: 生产者和消费者之间是同步的;生产者之间、消费者之间是互斥的，即进程对缓冲器的使用是互斥的。信号量定义为:

mutex:互斥信号量，初值为1，实现进程的互斥:empty:生产者信号量，初值为k;full:消费者信号量，初值为0。

PV操作描述如下

item B[k]；
semaphore empty; empty=k；
semaphore full; full=0；
int in=0;
int out=0
Cobegin
	Process producer i( ) //i=1,2,..
	begin
    	while(true)
    		begin
        		produce( );
        		P(empty);
        		P(mutex);
        		append to B[in];
        		in=(in+1)% k;
        		V(mutex);
        		V(ful1);
        	end;
     end;

Process consumer_j()
	begin
		while(true)
			begin
                P(ful1);
				P(mutex);
				take( ) from B[out];
				out=(out+1) % k;
				V(mutex);
				V(empty);
				consume()
       		 end;
	end;
C;

注意: 两个P操作的次序不能颠倒，互斥信号量的P操作必须放在同步信号量的P操作之后，否则，会死锁。而两个V操作的次序任意。

读者与写者问题描述如下

有一个数据文件(或记录) ，可被多个进程共享。其中有些进程要求读一-读进程，有些进程要求写或修改一一写进程。系统允许多个读进程同时访问这个文件，但不允许一个写进程和其它读进程或写进程同时访问这个文件可见该问题保证了一个写进程必须与其它进程互斥地访问共享文件。

解:设置一个整型变量readcount，用作计数器，表示正在读的进程数目。信号量定义为:mutex: 互斥信号量，表示对计数器readcount的操作是互斥的，初始值为1。

writeblock: 写互斥信号量，表示是否允许写，初始值为1。

int readcount=0.
semaphor writeblock,emutex;
writeblock=1;mutex=1;
Cobegin
    Process reader_i()
    	Begin
    		P(mutex);
			readcount++;
			If (readcount==1)
                P(writeblock);
			V(mutex);
			读文件;
			P(mutex);
			readcount--;
			If(readcount==0)
                V(writeblock);
			V(mutex);
		End;
	Process writer_j()
		Begin
			P(writeblock);
			写文件;
			V(writeblock)
		End;
Coend

理发师问题描述如下:理发店里有一位理发师、一把理发椅和 n 把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉;当一个顾客到来时，它必须叫醒理发师。如果理发师正在理发时又有顾客来到，那么，如果有空椅子可坐，顾客就坐下来等待，否则就离开理发店

解:给出的解法引入3个信号量和1个控制变量:控制变量waiting 用来记录等候理发的顾客数，初值为0;

信号量 customers 用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为 0 ;

信号量 barbers 用来记录正在等候顾客的理发师数，并用作阻寒顾客进程，初值为 0 ;

信号量 mutex 用于互斥，初值为 1 。

int waiting=0;/*等候理发的顾客数 */
int CHAIRS=N/*为顾客准备的椅子数 */
semaphore customers,barbers,mutex;
customers:=0;barbers:= 0;
waiting:=0;
mutex:=1;
cobegin
	process barber( )
    begin
		while(TRUE)//理完一人，还有顾客吗?
			begin
				P(customers)//若无顾客，理发师睡眠
            	P(mutex);//若有顾客，进入临界区
				waiting--;//等候顾客数减1
				V(barbers);//理发师准备为顾客理发
				V(mutex);//退出临界区
				cut_hair( )://理发师正在理发(非临界区)
			end;
	end;
procedure customer_i( )
	begin
		P(mutex);//进入临界区
		if (waiting<CHAIRS)//判断是否有没有空椅子
            begin
                waiting++;//等候顾客数加1
				V(customers);//唤醒理发师
				V(mutex);//退出临界区
				P(barbers);//理发师忙，顾客坐着等待
                get_haircut( ); //否则，顾客可以理发
			end;
		else V(mutex)//人满了，顾客离开
	end;
coend