Background

面向期末考试的快速复习罢了

Chapter 1.

什么是操作系统，他有什么功能？作用
操作系统是管理计算机硬件与软件资源的计算机程序，所以 是个系统软件
主要目标
方便 有效 可扩充 开放
操作系统功能
处理机管理功能：进程控制、进程同步、进程通信、调度（作业调度、进程调度）
存储器管理功能：内存分配、内存保护、存储扩充、地址映射
设备管理功能：缓冲管理、设备分配、设备处理
文件管理功能：文件存储空间的管理、目录管理、文件的读 /写管理和保护
操作系统与用户之间的接口：命令接口、程序接口、图形接口
操作系统的发展历史
从一开始的单道批处理到多道批处理，分时系统,实时系统
原理
单道批处理
作业自动运行，无需干预
磁带上的各个作业按顺序地进入内存，先调入先完成
内存中仅有一道程序运行，可以看成是串行的
外设和CPU交替空闲和忙碌，CPU和外设利用效率低
作业运行过程中若发生IO请求，高速的CPU要等待低速的I/O操作完成，导致CPU资源利用率和系统吞吐量降低。
多道批处理
计算机内存中同时存放多道相互独立的程序 优点是利用率高 吞吐量大 缺点是周转时间长，没有人机交互能力
分时系统
分时系统是指在一台主机上连接多个带有显示器和键盘的终端，同时允许多个用户通过自己的键盘，以交互的方式使用计算机，共享主机中的资源。 把处理器的运行时间分成很短的时间片 优点是改善了周转时间 缺点是 对长作业非常不利,可能长时间得不到执行
并且有时候需要比时间片更短的时间
实时系统
能实时进行交互
操作系统的基本特征
并发
并发是指在内存中放多道作业， 在一个时间段上来看，每一道作业都能不同程度地向前推进。但在任何一个时间点上只能有一道占用CPU。
系统中的资源可供多个并发的进程共同使用。
共享
根据资源属性的不同，有两种资源共享方式：

互斥共享方式（临界/独占资源）
同时访问方式

虚拟
通过某种技术将一个物理实体映射为若干个逻辑上对应物（如CPU；一个屏幕可看成多个屏幕-窗口）。或将多个物理实体映射为一个逻辑实体（如虚拟存储是内存和外存的虚拟）
异步
不确定性：什么时候开始，执行多久时间，终止时间

Chapter 2

进程的描述
进程是指进程实体的运行过程，是系统进行资源分配和调度的独立单位。
进程实体（简称进程）：程序块、相关的数据、进程控制块PCB
进程特征
动态、独立、异步、并发
进程和程序的区别
程序是静态的，进程是动态的
程序是永久的，进程是暂时的；
进程是由程序和数据、进程控制块PCB三部分组成的；
进程具有创建其他进程的功能，而程序没有
同一程序可对应多个进程
进程的三种状态 就绪阻塞运行
1C6D4D855C30F7613DC7CF6141F619A5.png
就绪状态（Ready R态）：存在于处理机调度队列中的所有进程，它们已经准备就绪，一旦得到CPU，就立即可以运行。这些进程所处的状态为就绪状态。
运行状态（Running  E态）：正在运行的进程所处的状态为运行状态。
等待/阻塞/睡眠状态（Wait/Blocked   B态）：若一进程正在等待某一事件发生（如等待输入输出工作完成），这时，即使给它CPU，它也无法运行，称该进程处于等待状态（阻塞、 睡眠、封锁状态）。
阻塞队列：根据阻塞原因可以设置多个队列。
进程控制块PCB
将一个不能独立运行的程序变成一个可以独立运行的基本单位，一个能与其他进程并发执行的进程。
PCB组成
进程标识符(process ID)：唯一，通常是一个整数
处理机状态
进程调度信息
进程控制信息

进程同步
间接相互制约关系：系统资源竞争，进程间彼此无关
直接相互制约关系：进程间合作，彼此相关
临界资源(Critical Resource/CR)：一段时间内一次仅允许一个进程访问的资源。
临界区(Critical Section/CS)：临界段，在每个程序中，访问临界资源的那段程序。
临界区是对每一个不同的临界资源来规定的 不同临界资源的临界区不互斥
同步遵循的规则
空闲让进
忙则等待
有限等待（有限时间等待，以免“死等”）
让权等待（不能进入自己的临界区时，应及时释放处理机，以免进程陷入“忙等”）
信号量机制
整形信号量
记录型信号量
and型信号量
pv操作题目
线程的引进
引入进程的目的是为了使多个程序更好的并发执行，改善资源利用率、提高系统效率。
引入线程则是为了减少并发执行时所付出的时空开销，使并发粒度更细、并发性更好
线程是程序执行中一个单一的顺序控制流程，是程序执行流的最小单元，是处理器调度和分派的基本单位。一个进程可以有一个或
多个线程，各个线程之间共享程序的内存空间(也就是所在进程的内存空间)

Chapter 3

处理机调度的目的，内存中多个程序争夺虚拟机
处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程并发
处理机调度三个层次
高级 中级 低级
高级调度即作业调度 决定位于外存中的作业进入内存 创建进程分配资源
作业调度的问题
接纳多少作业？ 取决于多道程序度
接纳哪些作业？ 取决于所采用的调度算法，如先来先服务调度算法、短作业有限调度算法等
中级调度（又称中程调度）：涉及进程在内、外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间。ctrl+z（挂起)暂时不需要的进程 等到后来由中级调度决定调回进程
低级调度（也称进程调度、微观调度、短程调度）：用来决定就绪队列中哪个进程应获得处理机，再有分派程序执行把处理机分配给各个进程
进程调度的两种方式：
非抢占式：不允许某进程抢占已经分配出去的处理机
抢占方式：允许调度程序根据某种原则，暂停正在执行的进程，将处理机重新分配给另一进程
抢占原则：优先权原则、短作业（进程）优先原则、时间片原则
进程调度解决问题:
按什么原则分配CPU ——调度算法
何时分配CPU——调度的时机
如何分配CPU——CPU调度过程
进程调度时机
a、一个进程运行完毕，或因某种错误而终止运行
 b、当一个进程在运行时变为等待状态（等待I/O）
 c、分时系统中时间片到
 d、当有一个优先级更高的进程就绪（抢占式）
例：新创建一个进程；一个等待进程变成就绪
e、在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语）

调度算法 FCFS(先来先服务) SJF(短作业优先( 高响应比调度算法（HRRN）——响应比Rp = 1 +（作业等待时间 / 作业处理时间）

死锁四个必要条件
互斥，不可抢占，请求和保持 环路

银行家算法题目

chapter4

EDB2EF39-E231-4902-823E-336CFD6C66D5.png
1、连续分配存储管理方式
单一连续分配——最简单，适用于单用户、单任务的OS。
优点：
    易于管理。
缺点：
   对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占用内存。
固定分区分配——把内存划分为个数固定、大小相等或不等的多个区域。分区的划分由计算机的操作员或者由操作系统给出，并给出分区说明表。
        优点：易于实现，开销小。
        缺点：
            内存碎片（零头）造成浪费
            分区总数固定，限制了并发执行的程序数目。
            可以和覆盖、交换技术配合使用。

动态分区分配——指在系统运行的过程中建立分区，并使分区的大小刚好与作业的大小相等。这种存储管理的方法解决了固定分区严重浪费内存的问题。是一种较为实用的存储管理方法。
首次适应法（FF）：要求空闲分区按首址递增的次序组织空闲。 分区表（队列）。 

               注意：每次分配和回收后空闲分区表或空闲 分区队列都要按首址递增的次序排序。

        下次适应法(NF)（循环首次适应算法）：按分区的先后次序，从上次分配的分区起查找（到最后分区时再回到开头），找到符合要求的第一个分区。

        最佳适应法(BF) ：要求按空闲区大小递增的次序组成空闲分区表（队列）。

               注意：分配和回收后要对空闲区表(队列)重新排序

             优点：
               在系统中若存在一个与申请分区大小相等的空闲区，必定会被选中，而首次适应法则不一定。

            若系统中不存在与申请分区大小相等的空闲区，则选中的空闲区是满足要求的最小空闲区，而不致于毁掉较大的空闲区。

            缺点：
                空闲区的大小一般与申请分区大小不相等，因此将其一分为二，留下来的空闲区一般情况下是很小的，以致无法使用。随着时间的推移，系统中的小空闲区会越来越多，从而造成存储区的大量浪费

        最坏适应法(WF)：要求空闲区按大小递减的顺序组织空闲区表（或队列）

2、非连续分配管理:基本分页存储管理方式——把用户程序按逻辑页划分成大小相等的部分，称为页（page） 。从0开始编页号，页内地址是相对于0编址
页表包含以下几个表项：

页号：登记程序地址空间的页号。
块号：登记相应的页所对应的内存块号。
其它：登记与存储信息保护有关的信息

586900C3-D71F-461A-8617-2D21802FFD4A.png

分段存储管理 段号S 端内位移W
分页对于用户来说是没什么逻辑意义的，分页是为了完成离散存储，所有的页面大小都一样，对程序员来说这就像碎纸机一样，出来的东西没有完整意义。但是分段不一样，分段不定长，分页由系统完成，分段有时在编译过程中会指定划分，因此可以保留部分逻辑特征，容易实现分段共享。

段页式存储管理

chapter 5

虚拟存储器具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统
1、交换技术

1.1、选择原则

即：将哪个进程换出内存？

1.2、选择时机

  只要不用（或很少再用）就换出；

  只在内存空间不够或有不够的危险时换出；

1.3、交换时需要做哪些工作？

    换出和换入过程，需要一个磁盘交换区：
    必须足够大以存放用户程序内存映像的拷贝；

    必须对这些内存映像直接存取。

1.4、换回内存时位置的确定
2、虚拟存储的实现方法

    2.1、请求分页系统

        在分页系统的基础上增加请求调页功能和置换功能所形成的页式虚拟存储器系统。
        硬件支持：请求分页的页表机制、缺页中断机构、地址变换机构。
        软件支持

    2.2、请求分段系统

        请求分段的段表机制、缺段中断机构、地址变换机构

3、请求分业存储管理方式

   在进程开始运行之前，不是装入全部页面，而是装入几个或零个页，之后根据进程运行的需要，动态装入其它页；

  在进程开始运行之前，不是装入全部页面，而是装入几个或零个页，之后根据进程运行的需要，动态装入其它页；
3.1页表机制
状态位：表示该页是否装入内存；
访问位：此页在一段时间被访问的次数，可用来决定淘汰哪页（由不同的算法决定）；
修改位：查看此页是否在内存中被修改过；
外存地址：该页在外存上的位置。
页号
块号

页面置换算法
OPT(最佳置换) FIFO(先进先出) 最近最少使用(LRU)

Belady异常 缺页率随着分配物理块增加而增加

内存管理计算中地址的处理

至少需要几级页表
虚拟内存 增加进程并发数说明利用率不高
位示图基本运算
与内存操作，是虚拟一个页的概念来作为最小单位。与硬盘打交道，就是以块为最小单位

页式存储管理中，访问指令或数据时，首先要访问内存中的页表，查找到指令或数据所在页面对应的页表项，然后再根据页表项查找访问指令或数据所在的内存页面。需要访问内存两次。
段式存储管理同理，需要访问内存两次。
段页式存储管理，首先要访问内存中的段表，然后再访问内存中的页表，最后访问指令或数据所在的内存页面。需要访问内存三次。

分配给用户的物理空间等于总空间减去页表或段表长度
固定大小分配的会产生内部碎片 其余的会产生外部碎片
分段大小并不固定

Chapter 6

第六章：输入输出系统

1、I/O系统的结构

 

微机型I/O系统—I/O设备通过设备控制器链接到总线上，CPU通过设备控制器与相应设备进行通信
主机型I/O系统（带通道的I/O系统）—具有通道的I/O系统结构：I/O设备、设备控制器、I/O通道、处理器。
 

2、设备控制器—是一个可编址设备，分为字符设备控制器和块设备控制器，是CPU与设备间的接口。

 

功能：
 

             接收和识别命令
             数据交换
             设备状态的了解和报告
             地址识别
             数据缓冲、差错控制

 

 

 

设备控制器的组成（三部分）
设备控制器与处理机的接口（数据线（数据寄存器、控制/状态寄存器）、地址线、控制线）
设备控制器与设备的接口（数据信号、状态信号、控制信号）
I/O逻辑：实现对设备的控制
 

3、设备管理功能

 

监视系统中所有设备的状态
设备的分配（相关数据结构、设备分配策略、分配的方式、分配技术和算法等。）
I/O控制（设备驱动处理（块设备）和设备中断处理（字符设备）。）
 

4、I/O控制方式

 

循环测试I/O方式
I/O中断方式
 

        优点：
　　    CPU利用率大大提高。（相对于忙等待方式）
        缺点：
            每台设备每输入/出一个字（节）的数据都有一次中断。如果设备较多时，中断次数会很多，使CPU的计算时间大大减少。
            不适合块设备。中断次数多，效率极低。
            为减少中断对CPU造成的影响，可采用DMA方式和通道方式。

 

DMA方式—控制器功能更强，除有中断功能外，还有一个DMA控制器（DMAC）。
 

          在DMAC的控制下，设备同主存之间可成批交换数据，不用CPU干预。

         DMAC由三部分组成：主机与DMAC的接口、DMAC与块设备的接口、I/O控制逻辑。

 

PS：中断方式与DMA方式区别

    中断方式是在数据缓冲寄存器满后，发中断请求，CPU进行中断处理；DMA方式则是在所要求传送的数据块全部传送结束时要求CPU进行中断处理； ——大大减少了CPU进行中断处理的次数。

   中断方式的数据传送是由CPU控制完成的；DMA方式则是在DMAC的控制下完成的。

通道方式
 

         为使CPU从繁忙的I/O处理中摆脱出来，现代大、中型计算机系统中设置了专门处理I/O操作的处理机，并把这种处理机称为通道。通道=I/O处理机

 

5、缓冲技术

5.1、缓冲技术的实现

提出用缓冲技术来匹配CPU与设备的速度的差异和负荷的不均匀，从而提高处理机与外设的并行程度。
引入缓冲可缓和CPU与外设的速度差异。

凡是数据到达和离去速度不匹配的地方均可采用缓冲技术。

硬件缓冲器，在设备控制器中有硬件缓冲器，通常容量较小。
软件缓冲技术是广泛应用的一种缓冲技术，它由缓冲区和对缓冲区的管理两部分组成。
 

5.2、常用的缓冲技术

 

单缓冲 —最简单的一种缓冲形式。当进程发出一I/O请求时，OS在内存中为之分配一缓冲区
 

双缓冲—设置两个缓冲区buf1和buf2。交替使用两个缓冲区，使CPU和设备的并行操作的程度进一步提高。

环形缓冲 —环形缓冲技术是在主存中分配一组大小相等的存储区作为缓冲区，并将这些缓冲区链接起来。
缓冲池—环形缓冲区一般用于特定的进程，属于专用缓冲区，当系统较大时，将会有许多这样的环形缓冲区，这不仅要消耗大量的内存空间，利用率也不高。

hin、sin、hout、sout为指针

 

5.3、引入缓冲技术的原因

  提出用缓冲技术来匹配CPU与设备的速度的差异和负荷的不均匀，从而提高处理机与外设的并行程度。
引入缓冲可缓和CPU与外设的速度差异。

凡是数据到达和离去速度不匹配的地方均可采用缓冲技术。

6、设备分配

 

设备分配中的数据结构
设备分配方式
静态分配
 

        在作业级进行的，当一个作业运行之前由系统一次分配满足需要的全部设备，这些设备一直为该作业占用，直到作业撤消。
        设备的利用效率较低

 

        不会出现死锁

    2.  动态分配  

    在进程运行的过程中进行的，当进程需要使用设备时，通过系统调用命令向系统提出设备请求，系统按一定的分配策略给进程分配所需设备，一旦使用完毕立即释放。
    有利于提高设备的使用效率
    会出现死锁，应力求避免

 设备分配算法
先请求先服务
优先级高的优先服务
 设备分配技术
独享分配（打印机、键盘、显示器。磁带机可作为独占设备，也可作为共享设备。）
共享分配（磁盘，磁带和磁鼓）
虚拟分配（为提高计算机系统的效率，提出了在高速共享设备上模拟低速设备功能的技术，称为虚拟设备技术。）
7、假脱机（SPOOLing）系统特点

 

提高了I/O速度
将独占设备改造为共享设备
实现了虚拟设备功能