计算机操作系统原理笔记

1 操作系统绪论

1.1 操作系统概念

定义：操作系统是计算机系统中的一个系统软件，操作系统是管理和控制计算机操作系统中的硬件和软件资源，利用这些资源来组织计算机的工作流程，为用户提供一个足够功能、使用方法、可扩展、可管理、安全的工作环境，是用户和计算机之间的一个接口。

特征：并发、共享、虚拟、异步。

1.2 操作系统发展历程

手工操作(无操作系统)—单道批处理—多道批处理—分时系统—实时系统—微机操作系统的发展。

1.2.1单道批处理

原理：计算机自动的一个接一个的处理作业，直到磁带上所有的作业都完成，虽然对作业的处理是成批的，但是内存中只有一个作业。

特征：内存中一道程序数目、独占CPU、没有作业和进程调度、程序次序严格对应。

1.2.2多道批处理

原理：用户提交的作业存放在外存上，并排成一个队列，作业调度程序根据一定的算法，选择若干的作业调入内存，使它们共享CPU和内存资源。

特征：内存中多道程序、交替占用CPU、需要作业和进程调度、程序次序不严格对应。

1.2.3分时系统

特征：多路性、独立性、及时性、交互性。

1.2.4实时系统

特征：多路性、独立性、及时性、交互性、可靠性。

2 操作系统用户界面

2.1 作业

定义：分用户和系统角度去理解

a) 用户：在一次应用处理过程中，从输入到输出结束，用户要求计算机所作有关该次业务处理的全部工作称为一个作业；

b) 系统：作业=程序+数据(作业体)+作业说明书(作业控制语言JCL)

2.2 一般用户输入输出方式

2.2.1联机输入输出方式

2.2.2脱机输入输出方式

2.2.3直接耦合方式

2.2.4Spooling系统

原理：todo。

特点：系统把作业处理的全过程分为相对独立的三部分—输入流、处理流、输出流。

2.2.5网络联机方式

2.3 系统调用

定义：系统调用是操作系统留给编程人员的唯一接口。

原理：todo

2.3.1系统调用指令

int和trap指令进行系统调用。

call和jmp指令进入普通过程调用(子调用)。

3 进程管理

3.1 进程的概念

组成：进程=程序+数据+进程控制块(进程状态信息PCB)

定义：进程是程序的一次执行活动，一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。

目的：对应的虚拟处理机、虚拟存储器和虚拟外设等资源的分配和回收；反映了系统中程序执行的并发性、随机性和共享性；

优缺点：引用了多线程，提高了对硬件资源的利用率，但又带来了额外的空间和时间开销，增加了os的复杂性。

3.2 进程和程序的区别

a) 进程是动态的，程序是静态的；

b) 进程是暂时的，程序是永久的；

c) 组成不同，进程的组成包括程序；

d) 对应关系不同，通过多次执行，一个程序可对应多个进程，通过调用关系，一个进程可包含多个程序；

e) 进程可以并行，具有独立性、异步性。

f) 进程是竞争计算机资源的基本单位。

3.3 进程控制块(PCB)

进程控制块包含了有关进程的以下4个信息，是进程动态特征的集中反映。

3.3.1描述信息

3.3.2控制信息

3.3.3资源管理信息

3.3.4CPU保护现场结构

3.4 进程上下文切换

原因：进程中断、超时、进程调用。

步骤：

a) 保存被切换进程的正文部分到有关存储区。

b) 进程有关调度和资源分配程序执行，选取新的进程。

c) 新进程正文部分从存储区取出，激活选中进程执行。

3.5 进程的状态和进程转换

3.5.1进程状态

初始态、执行状态、等待状态、就绪状态、终止状态(例子转转火锅：想吃(创建)、流动的菜(就绪)、吃(执行)、拿太多(等待)，吃完(终止))

3.5.2进程状态转换

3.6 进程控制

3.6.1进程创建和撤销

3.6.2进程阻塞和唤醒

3.6.3进程的挂起和激活

3.7 进程互斥和同步

3.7.1临界区和临界资源

临界资源是一次仅允许一个进程使用的共享资源。

临界区是每个进程访问临界资源的那段代码。

3.7.2信号量和PV原语

信号量是一种卓有成效的进程同步工具，可以用信号量实现互斥。

信号量的数值仅能由P、V原语操作改变。

3.7.3互斥的概念

定义：不允许俩个以上的共享该资源的并发进程同时进入临界区称为互斥。

3.7.4同步的概念

定义：对相关进程执行次序进行协调后，按照一定规则允许进程共享资源的并发进程称为同步。

3.8 进程通信

Todo

3.9 死锁问题

3.9.1死锁的概念

定义： 如果一组进程中每个进程都在等待由该进程中的其他进程才能引发的事件，那么该组进程就是死锁的。

起因：并发进程的资源竞争

条件：同时具备互斥条件、不剥夺条件、部分分配、环路条件。

3.9.2死锁的解决方案

3.9.2.1 死锁预防

3.9.2.2 死锁避免

最具代表性的避免算法-银行家算法

3.9.2.3 死锁的检测和恢复

3.10 线程

3.10.1 线程的基本概念

定义：引入线程后，线程是操作系统调度和分配的基本单位。

组成：线程=？+线程控制块(TCB)

3.10.2 线程状态和线程控制块(TCB)

线程状态：执行状态、就绪状态、阻塞(等待)状态

线程控制块数据结构包括：

a) 线程标识符

b) 一组寄存器

c) 线程执行状态

d) 优先级

e) 线程专有存储区

f) 信号屏蔽

g) 堆栈指针

3.10.3 线程和进程的区别

从以下六点讨论

a) 调度性：在传统OS中，拥有资源的基本单位，独立调度和分派的基本单位都是进程。在引入线程的OS中，把线程作为调度和分派的基本单位，进程只是拥有资源的基本单位。

b) 并发性：在引入进程的OS中，不仅线程间可以并发执行，而且在一个进程内的多线程间，也可以并发执行。

c) 拥有资源：拥有资源的基本单位一直是进程，线程除了一点在运行中必不可少的资源，本身不拥有系统资源，但它可以共享其隶属进程的资源。

d) 独立性：每个进程都能独立申请资源和独立运行，但是同一进程的多个线程则共享进程的内存地址空间和其他资源，他们之间独立性要比进程之间独立性低。

e) 系统开销：在创建或者撤销进程时，系统都要为之分配和回收进程控制块（PCB）以及其他资源，进程切换时所要保存和设置的现场信息也要明显多于线程。由于隶属于一个进程的多个线程共享同一地址空间，线程间的同步与通讯也比进程简单。

f) 支持多处理机系统：传统的进程只能运行在一个处理机上，多线程的进程，则可以将进程中的多个线程分配到多个处理机上，从而获得更好的并发执行效果。

4 处理机调度

4.1 调度层级

一个作业提交后，往往会经历三种层级（加线程四种）

4.1.1作业调度

又叫宏观调度或者高级调度，用于决定把外存后备队列中的哪些作业调入内存，为他们创建进程，同时作业调度根据他的周转时间等方式来衡量优劣。

4.1.1.1 周转时间相关

周转时间=作业完成时间-作业提交时间=作业等待时间+作业执行时间

平均周转时间=所有作业周转时间之和/总作业数

带权周转时间=作业周转时间/作业执行时间

平均带权周转时间=所有带权作业周转时间之和/总作业数

4.1.1.2 响应时间，截止时间和系统吞吐量

响应时间是提交请求和返回该请求的响应之间使用的时间
截止时间是某任务必须开始执行或者必须完成的最迟时间
吞吐量是对单位时间内完成的工作量的量度

4.1.2交换调度

又称内存调度或中级调度，它按一定算法将外存中已具备运行条件的进程换入内存，将内存中处于阻塞状态的某些进程换至外存

4.1.3进程调度

又叫微观调度或者低级调度，用来决定就绪列表哪个进程获得处理机，并将处理机分配给选择进程，具体有俩种方式

4.1.3.1 非抢占方式

一旦进程获得CPU，它将一直执行，直到改进程完成或者发生阻塞时才会把CPU让出来。

4.1.3.2 抢占方式

系统可以根据某种原则让一正在执行的进程暂停，并将已分配给他的处理机重新分配给另一个进程

a) 优先权原则：就绪的高优先权进程有权抢占低优先权进程的CPU

b) 短作业优先原则：就绪的短进程有权抢占长进程的CPU

c) 时间片原则：一个时间片用完后，系统重新进行进程调度

4.1.4线程调度

Todo

4.2 作业和进程的关系

系统必须为一个作业创建一个根进程；再根据任务要求，系统或者根进程创建相应的子进程；然后为子进程分配资源和任务。

4.3 调度算法

宏观调度：先来先服务调度算法、最短作业优先算法、最高响应比优先法。

​ 微观调度：轮转法、优先级法、多级反馈轮转法。

5 存储管理

5.1 存储器结构

由内存量由大到小、由访问速度由小到大分别是磁盘缓存、主存输器、高速缓存、寄存器，其中，除寄存器外，其他三者属于主存，而还有相应的辅存，固定磁盘、可移动存储介质。

5.1.1寄存器

寄存器具有与处理机相同的速度，对寄存器的访问速度最快，完全能与CPU协作。寄存器主要用于存放处理机运行时数据，加速存储器访问速度。

5.1.2高速缓存

它是介于寄存器和存储器之间的存储器，主要用于备份主存中比较常见的数据，减少处理机对主存储器的访问次数。

5.1.3主存输器

简称内存或主存，用于保存进程运行时的程序和数据，也叫执行存储器，通常处理机都是从主存储器中取得指令和数据的，并将指令放入指令寄存器中，数据放入数据寄存器中。

5.1.4磁盘缓存

目前磁盘I/O远低于对主存的访问速度，为了缓和两者之间在速度上不匹配，设置了磁盘缓存。主要用于暂时存放频繁使用的一部分磁盘数据和信息。

5.2 程序的处理阶段

主要有编译，链接，装入，下面主要讲链接和装入。

5.2.1程序的链接

源程序经过编译后，可得到一组目标模块。链接程序的功能是将这组目标模块以及它们所需要的库函数装配成一个完整的装入模块。
链接又可分为静态链接，装入时动态链接，运行时动态链接。

5.2.2程序的装入

分为绝对装入方式，可重定位装入方式，动态运行时的装入方式。

5.3 地址变换

5.3.1静态地址重定向

原理：Todo这里还没懂，但是静态地址重定向是程序执行之前完成的地址映射工作，静态重定位不需要硬件支持。

5.3.2动态地址重定位

关系：MA(物理地址)=BR(基址地址)+VR(虚拟地址)。

原理：动态地址重定向是在程序执行过程中，在CPU访问内存之前，将程序或数据地址转换成内存地址，动态重定向依靠硬件地址变换机构完成。

5.4 分区存储管理

分区管理把内存划分成若干大小不等的区域，除操作系统占用一个区域，其余由多道环境下的各并发进程共享，分区管理是满足多道程序设计的一种最简单的存储器方法。

5.4.1固态分区法

原理：把内存固定地划分为若干个大小不一的区域，分区规则由系统操作员和操作系统决定，分区一旦划分，在整个执行过程中每个分区的长度和内存的总分区个数将保持不变。

优点:易于实现，开销小。

缺点：内碎片造成浪费；分区总数生成时确定，限制并发执行的程序数目。

5.4.2动态分区法

原理：动态分区法在作业执行前不建立分区，在作业的处理过程中随作业或进程对内存的要求而改变。

优点：没有内碎片；

缺点：有外碎片；

算法：根据情况有以下俩种，着重介绍三种

a) 基于顺序搜索的动态分区分配：最先适应算法，最佳适应算法，最坏适应算法，循环最先适应算法

b) 基于索引搜索的动态分区分配：快速适应算法，伙伴系统，哈希算法

5.4.2.2 最先适应法

5.4.2.3 最佳适应法

5.4.2.4 最坏适应法

5.4.3页式管理（离散分配）

基本思想：各进程的虚拟空间被划分成若干长度相等的页，同时把内存空间也按页的大小划分为片或者页，大致分为静态页式管理和动态页式管理。

5.4.3.1 静态页式管理

原理：在作业或者进程执行之前，把该作业或进程的程序段和数据全部装入各个也页面种，并通过页表和硬件地址变换机构实现虚拟地址到内存物理地址的地址映射。

5.4.3.2 动态页式管理

5.4.4段式和段页式管理

基本思想：todo

5.4.4.1 段式管理

原理：todo

5.4.4.2 段页式管理

原理：todo

5.4.5覆盖和交换技术

5.5 虚拟存输器

5.5.1虚拟存储的实现方式

虚拟内存的实现都是建立在离散（动态）分配存储管理方式的基础上。主要有两种实现方式：

5.5.1.1 分页请求系统

在分页系统基础上增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许用户程序只装入少数界面的程序（及数据）即可启动运行，以后再通过调页功能及页面置换功能陆续将即将运行的页面调入内存，同时把不用的页面再换出到外存上。
硬件支持：请求分页的页表机制，缺页中断结构，地址变换机构实现请求分页的软件：包括用于实现请求调页的软件和实现页面置换的软件，在硬件支持下，将程序正在运行时所需的页面（尚未在内存中）调入内存，再将内存中暂时不用的页面从内存置换到磁盘上

5.5.1.2 请求分段系统

在分段系统基础上增加了请求调段功能和分段置换功能所形成的段式虚拟存储系统，具体实现原理同分页请求系统，不过载体是“段”不是“页”

5.5.2页面置换算法

5.5.2.1 随机淘汰算法

随机地选择某个用户地页面并将其换出。

5.5.2.2 最佳置换算法（理想型淘汰算法OPT）

其所选择被淘汰的页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面，但是因为未来不可预知，所以该算法不能实现。

5.5.2.3 先进先出置换算法（FIFO）

总是先淘汰最先进入内存的页面。

5.5.2.4 最近最久未使用算法（LRU）

选择最近最久未使用内存页面进行淘汰。需要较多硬件支持。

5.5.2.5 最少使用置换算法（LFU）

在内存为每个页面设置一个移位寄存器记录该页面被访问频率，选择最近时期使用最少的页面作为淘汰页。

5.5.2.6 Clock置换算法

是一种LRU算法
每页设置一个访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列；
当某个页面被访问时，其访问位置1。淘汰时，检查其访问位，如果是0，就换出；若为1，则重新将它置0；
再按FIFO算法检查下一个页面，到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首再去检查第一个页面；

6 文件系统

6.1 文件系统基本概念

目的：文件系统地出现是为了更好地管理软件资源

文件系统的定义：操作系统中与管理文件有关的软件和数据称为文件系统

文件的定义：文件时一段程序和数据的集合

文件的分类：按文件性质分为系统文件、库文件、用户文件，按组织形式分普通文件、目录文件、特殊文件。

6.2 文件的逻辑结构和存取方式

6.2.1逻辑结构

字符流的无结构文件：管理简单，但是查找困难，对基本信息单位操作不多的使用于采用这种方式，例如源程序文件、目标代码文件。

记录式的有结构文件：把文件的记录按不同的方式排列，构成不同的逻辑结构，以便于增删改查和管理，常见的有以下四种。

6.2.1.1 连续结构

6.2.1.2 多重结构

6.2.1.3 转置结构

6.2.1.4 顺序结构

6.2.2逻辑存储方法

6.2.2.1 顺序存输方法

6.2.2.2 随机存输方法

6.2.2.3 按关键字存输方法

多用于复杂文件系统。

6.2.3逻辑搜索方式

文件的获取是要找到文件内容所在的逻辑地址

6.2.3.1 线性搜索法

6.2.3.2 散列法

6.2.3.3 二分搜索法

6.3 文件的物理结构和存储设备

6.3.1文件物理结构

6.3.1.1 连续文件

连续文件采用连续分配方式：

特点：为每一个文件分配一组相邻接的盘块;把逻辑文件中的记录顺序地存储到邻接的各物理盘块中;这样形成的文件结构称为顺序文件结构,物理文件称为顺序文件。
优点：顺序访问容易; 顺序访问速度快;
缺点：要求有连续的存储空间; 必须事先知道文件的长度;

6.3.1.2 串联文件

串联文件采用链接分配

特点：文件的信息存放在若干不连续的物理块中；各块之间通过指针连接，前一个物理块指向下一个物理块；可分为隐式链接和显式链接；
优点：没有外部碎片，空闲空间列表的任何块可以用于满足请求。当创建文件时，并不需要说明文件的大小只，要有可用的空闲块，文件就可以继续增长。因此，无需合并磁盘空间。
缺点：存取速度慢，不适于随机存取;可靠性问题，如指针出错;更多的寻道次数和寻道时间;链接指针占用一定的空间;

6.3.1.3 索引文件

索引文件采用索引分配

特点：每个文件都有自己的索引块，这是一个磁盘块地址的数组。

6.3.2文件存储设备

存储设备有磁盘、光盘、磁带，磁盘分为硬盘和软盘，但近年软盘逐渐被光盘和优盘取代，下面介绍以磁带为代表的顺序存取存储设备和以磁盘为代表的直接存取存储设备。

6.3.2.1 顺序存取存储设备—磁带

特点：只有前面的被存取，才能对后面的进行存取；访问时间与记录到磁头的距离成正比；随机存取、关键字存取效率低，但是顺序存储速度块；容量大。

影响因素：信息密度（字符数/英寸）、磁带带速（英寸/秒）、快间间隙。

6.3.2.2 直接存取存储设备—磁盘

6.4 文件存储空间管理

文件存储空间的管理实质是对空闲块的组织和管理问题，有以下三种空闲管理方式。

6.4.1空闲目录管理

6.4.2空闲链块法

6.4.3位示图

6.5 文件目录管理

从文件管理角度看，一个文件包括文件说明和文件体。

6.5.1文件目录的种类

6.5.1.1 单级文件目录

在整个文件系统中只建立一张目录表，每个文件占一个目录项，目录项中含有文件名、文件扩展名、文件长度、文件类型、文件物理地址以及其他文件属性。

6.5.1.2 两级文件目录

目录分为两级：一级称为主文件目录MFD，每个用户目录文件都占有一个目录项，包含用户名和指向该用户子目录的指针；二级称为用户文件目录UFD(又称用户子目录)，给出该用户所有文件的FCB；

6.5.1.3 树形结构目录

多级目录结构又称为树型目录结构；
主目录称为根目录，数据文件称为树叶，其他目录均作为树的结点；

6.5.2文件目录的共享

从系统管理的方式来看，有三种方法可以实现文件共享

6.5.2.1 绕道法

6.5.2.2 链接法

6.5.2.3 基本文件目录表（BFD）

6.5.3目录管理

文件目录管理应该存放在磁盘，其他的没理解todo

6.6 文件存取控制

用户对文件的存取权限有读、写、执行的许可问题，而验证的方式有以下四种。

6.6.1存取控制矩阵

6.6.2存取控制表

6.6.3口令方式

6.6.4密码方式

密码方式是保密性最好的验证方式。

7 设备管理

7.1 设备的分类

在计算机系统中，除了CPU和内存，其他大部分称为外部设备，它们包括外存设备、输入输出设备、终端设备。

7.2 数据传输控制方式

设备管理的主要任务之一是控制设备和内存或CPU之间进行数据传输,常用的数据传输方式有以下四种。

7.2.1程序直接控制方式

由用户进程来直接控制内存或者CPU和外围设备之间的信息传送。

7.2.2中断方式

I/O操作由程序发起，在操作完成时，由外设向CPU发起中断，通知该程序。数据每次读写通过CPU。

7.2.3DMA方式

在外围设备和内存之间开辟直接的数据交换通道。

7.2.4通道控制方式

以内存为中心，实现设备和内存直接交换数据的控制的方式。

7.3 中断技术

原理：中断是指系统发生紧急事件使CPU暂时中断当前执行程序转而执行相应事件处理，处理完毕后又返回中断处或者调度新进行。

过程：判断中断响应条件—关中断—保存被中断现场—分析中断原因转中断处理子程序—执行中断和处理子程序—恢复现场—开中断—返回中断点

7.3.1中断技术的分类

中断一般分为硬中断和软中断，而硬中断又分为外中断和内中断。

7.3.1.1 外中断

一般是来自处理机和内存外部的中断

7.3.1.2 内中断（陷阱）

一般是来自处理机和内存内部的中断

7.3.1.3 软中断

是通信进程之间模拟硬中断的一种信号通信方式

7.4 缓冲技术

目的：缓冲的引用时为了解决外围设备和处理机速度不匹配的问题。

分类：缓存技术分为单缓冲、双缓冲、多缓冲以及缓冲池。

7.4.1缓冲池的结构

缓冲池由多个缓冲区组成，而一个缓冲区由俩部分组成，一部分用来标识该缓冲器和用来管理管冲首部，一部分用来存放数据的缓冲体。

7.4.2缓冲池管理

Todo