计算机系统

计算机是如何工作的？（采用“存储程序”工作方式）

程序在执行前：

数据和指令事先存放在存储器中，每条指令和每个数据都有地址，指令按序存放，指令由OP、ADDR字段组成，程序起始地址置pc

开始执行程序：

第一步：根据pc取指令

第二步：指令译码

第三步：取操作数

第四步：指令执行

第五步：回写结果

第六步：修改pc的值

继续执行下一条指令

程序启动前，指令和数据都存放在储存器中，形式上没有差别，都是0/1序列

采用“存储程序”工作方式：程序由指令组成，程序被启动后，计算机能自动取出一条一条指令执行，在执行过程中无需人的干预。

指令中需给出的信息：

操作性质（操作码）

源操作数1或/和源操作数2（立即数、寄存器编号、存储地址）

目的操作数地址（寄存器编号、存储地址）

存储地址的描述与操作数的数据结构有关

汇编指令：用助记符和标号来表示的指令（与机器指令一一对应）

指令：包含操作码和操作数或其他地址码（机器指令用二进制表示，汇编指令用符号表示）

高级语言转换为机器语言程序：

两种转换方式：“编译”和“解释”

编译程序：将高级语言源程序转换为机器级目标程序，执行时只要启动目标程序即可。

解释程序：将高级语言语句逐条翻译成机器指令并执行，不生成目标文件。

一、操作系统的特征（并发、共享、虚拟、异步）

并发：指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。

并行：指两个或多个事件在同一时刻发生。

操作系统的并发性指计算机系统中同时存在着多个运行着的程序。

共享即资源共享，是指系统中的资源可供内存中多个并发执行的进程共同使用。

两种资源共享方式：

互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源。

同时共享方式：允许一个时间段内多个进程“同时”对它们进行访问。（交替地对资源进行访问）

并发性指计算机系统中同时存在着多个运行着的程序。

共享性是指系统中的资源可供内存中多个并发执行的进程共同使用。

虚拟是指一个物理上的实体变为若干个逻辑上的对应物。物理实体（前者）是实际存在的，而逻辑上对应物（后者）是用户感受到的。

虚拟技术：空分复用技术，时分复用技术。

异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停的，以不可预知的速度向前推进，这就是进程的异步性。（只有系统拥有了并发性，才有可能导致异步性）

二、操作系统的发展与分类

手工操作阶段

主要缺点：用户独占全机、人机速度矛盾导致资源利用率极低。

单道批处理系统

主要优点：缓解了一定程度的人机速度矛盾，资源利用率有所提升。

主要缺点：内存中仅能一道程序运行，只有该程序运行结束后才能调入下一道程序。CPU有大量的时间是在空闲等待I/O完成，资源利用率依然很低。

多道批处理系统：

主要优点：多道程序并发执行，共享计算机资源。资源利用率大幅提升，CPU和其他资源保持“忙碌”状态，系统吞吐量增大。

主要缺点：用户响应时间长，没有人机交互功能（用户提交自己的作业之后就只能等待计算机处理完成，中间不能控制自己的作业执行）

实时操作系统

主要优点：能够优先响应一些紧急任务，某些紧急任务不需要时间片排队。

在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完事件。实时操作系统的特点是及时性和可靠性。

硬实时操作系统：必须在绝对严格的规定时间内完成处理。

软实时操作系统：能接受偶尔违反时间规定。

三、操作系统的运行机制和体系结构

指令（特权指令、非特权指令）

两种处理器状态

用户态（目态）：此时CPU只能执行非特权指令。

核心态（管态）：特权指令、非特权指令都可执行。

两种程序

内核程序：操作系统的内核程序是管理者，既可以执行特权指令，也可以执行非特权指令，运行在核心态。

应用程序：为了保证系统能安全运行，普通应用程序只能执行非特权指令，运行在用户态。

内核（时钟管理、中断处理、原语、对系统资源进行管理的功能）

内核时计算机上配置的底层软件，是操作系统最基本、最核心的部分。

实现操作系统内核功能的那些程序就是内核程序。

时钟管理：实现计时功能。

中断处理：负责实现中断机制。

原语：是一种特殊的程序，处于操作系统最底层，是最接近硬件的部分，这种程序的运行具有原子性——其运行只能一气呵成，不可中断，运行时间较短、调用频繁。

对系统资源进行管理的功能：进程管理、存储器管理、设备管理。

操作系统的体系结构（大内核、微内核）

大内核：将操作系统的主要功能模块都作为系统内核，运行在核内心。

优点：高性能

缺点：内核代码庞大，结构混乱，难以维护。

微内核：只把最基本的功能保留在内核

优点：内核功能少，结构清晰，维护方便。

缺点：需要频繁地在核心态和用户态之间切换，性能低。

四、中断、异常

本质：发生中断意味着需要操作系统的介入，开展管理工作。由于操作系统的管理工作需要使用特权指令，因此CPU要从用户态转为核心态。中断可以使CPU从用户态切换为核心态，使操作系统获得计算机的控制权。有了中断才能实现多道程序并发执行。

用户态——》核心态是通过中断实现的，并且中断时唯一的途径。

中断的分类

内中断（异常、例外、陷入）：自愿中断（指令中断）、强迫中断（硬件故障、软件故障）。

信号的来源：CPU内部与当前执行的指令有关。

外中断：外设请求、人工干预。

信号的来源：CPU外部与当前执行的指令无关。

五、系统调用

操作系统作为用户和计算机硬件之间的接口，需要向上提供一些简单易用的服务。主要包括命令接口和程序接口。其中，程序接口由一组系统调用组成。

系统调用相关处理涉及对系统资源的管理、对进程的控制，这些功能需要执行一些特权指令才能完成，因此系统调用的相关处理需要在核心态下进行。

系统调用的背后过程:

传递系统调用参数->执行陷入指令（用户态）->执行系统调用相应服务程序（核心态）->返回用户程序

注意：1.陷入指令是在用户态执行的，执行陷入指令之后立即引发一个内中断，从而CPU进入核心态。

2.发出系统调用请求是在用户态，而对系统调用的相应处理在核心态下进行。

3.陷入指令是唯一一个只能在用户态执行，而不可在核心态执行的指令。

凡是与资源有关的操作、会直接影响到其他进程的操作，一定需要操作系统的介入，即需要通过系统调用来实现。

系统调用发生在用户态，对系统调用的处理发生在核心态。

执行陷入指令会产生内中断，使处理器从用户态进入核心态。

六、进程

PCB：称为进程控制块，系统为每个运行的程序配置一个数据结构，用来描述进程的各种信息（如程序代码存放位置）。

进程的定义：程序段、数据段、PCB三部分组成了进程实体。一般情况下，我们把进程实体就简称为进程。注意：PCB是进程存在的唯一标志。

1.进程是程序的一次执行过程。

2.进程是一个程序及其数据在处理机上顺序执行时所发生的活动。

3.进程时具有独立功能的程序在数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

程序段：程序代码存放的地方。

数据段：程序运行时、产生的运算数据，就存放在数据段内。

PCB：操作系统通过PCB来管理进程，因此PCB中应该包含操作系统对其进行管理所需的各种信息。

进程的组织：

链接方式：按照进程状态将PCB分为多个队列，操作系统持有指向各个队列的指针。

索引方式：根据进程状态的不同，建立几张索引表。操作系统持有指向各个索引表的指针。

进程的特征：动态性、并发性、独立性、异步性、结构性。

七、进程的状态

进程的三种基本状态：

运行态：占有CPU，并在CPU上运行。

就绪态：已经具备运行条件，但由于没有空闲的CPU，而暂时不能运行。

阻塞态:因等待某一事件而暂时不能运行。

进程的另外两种状态：

创建态：进程正在被创建，操作系统为进程分配资源、初始化PCB。

终止态：进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销PCB。

八、进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。

用原语实现进程控制。原语的特点是执行期间不允许中断，这种不能被中断的操作即原子操作。

原语的功能：

1.更新PCB中的信息。

2.将PCB插入合适的队列。

3.分配/回收资源。

相关原语：进程的创建、进程的终止、进程的阻塞、进程的唤醒、进程的切换。

九、进程通信（共享存储、管道通信、消息传递）

共享存储

两个进程对共享空间的访问必须是互斥的（互斥访问通过操作系统提供的工具实现）。

共享存储的两种方式：基于数据结构的共享、基于存储区的共享

基于数据结构的共享：这种共享方式速度慢、限制多，是一种低级通信方式。

基于存储区的共享：在内存中画出一块共享存储区，数据的形式、存放位置都由进程控制，而不是操作系统。相比之下这种共享方式速度更快，是一种高级通信方式。

管道通信

“管道”是指用于连接读写进程的一个共享文件，其实就是在内存中开辟一个固定的缓冲区。

1.管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。

2.各进程要互斥的访问管道。

3.数据以字符流的形式写入管道，当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read()系统调用将被阻塞。

4.如果没写满，就不允许读。如果没读空，就不允许写。

5.数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况。

消息传递

进程间的数据交换以格式化的消息为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。

消息传递的两种方式：直接通信方式、间接通信方式

直接通信方式：消息直接挂到接收进程的消息缓冲队列上。

间接通信方式：消息要先发送到中间实体（信箱）中。

九、线程概念多线程模型

线程的概念：线程是一个基本的CPU执行单元，也是程序执行流的最小单位。引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得进程内可以并发处理各种任务。引入线程后，进程只作为除CPU之外的系统资源的分配单元。

线程的属性：

1.线程是处理机调度的单位。

2.多CPU计算机中，各线程可占有不同的CPU。

3.每个线程都有一个线程ID、线程控制块（TCB）

4.线程也有就绪、阻塞、运行三种基本状态。

5.线程几乎不拥有系统资源。

6.同一进程的不同线程之间共享进程的资源。

7.由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预。

8.同一进程中线程的切换，不会引起进程的切换。

9.不同进程中线程的切换，会引起进程切换。

10.切换同进程内的线程，系统开销很小。

11.切换进程，系统开销较大。

线程的实现方式：

用户级线程：由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责，用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。

内核级线程：由操作系统内核完成管理工作，线程的调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。

十、处理机调度（高级调度、中级调度、低级调度）

高级调度：

按一定的原则从外存上处于后备队列的作业中挑选一个（或多个）作业，给它们分配内存等必要资源，并建立相应的进程（建立PCB），以使它们获得竞争处理机的权利。

高级调度是外存和内存之间的调度。每个作业只调入一次，调出一次。作业调入时会建立相应的PCB，作业调出时才撤销PCB。高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出。

中级调度：

引入虚拟存储技术后，可将暂时不能运行的进程调至外存等待，等它重新具备了运行条件且内存稍有空间时，再重新调入内存（可以提高内存利用率和系统吞吐量）暂时调到外存等待进程状态为挂起状态。PCB并不会一起调到外存，而是会常驻内存。PCB中会记录进程数据再外存中的存放位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控、管理。被挂起的进程PCB会被放到挂起队列中。中级调度就是要决定将哪个处于挂起状态的进程重新调入内存。

低级调度:（进程调度）

其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。

进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。

十一、进程调度（低级调度）的时机切换与过程调度方式

进程调度（低级调度）：就是按照某种算法从就绪队列中选择一个进程为其分配处理机。

不能进行进程调度与切换的情况：

1.在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。

2.进程在操作系统内核程序临界区中。

3.在原子操作过程中（原语)。原子操作不可中断，要一气呵成。

进程调度的方式：

非剥夺调度方式：又称非抢占方式，只允许进程主动放弃处理机，在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。

剥夺调度方式：又称抢占方式，当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，即立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

进程切换与过程：

进程调度是指从就绪队列中选中一个要运行的进程。（这个进程可以是刚刚被暂停执行的进程，也可能是另外一个进程，后一种情况就需要进程切换）

进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。

进程切换的过程主要完成了：

1.对原来运行的进程各种数据的保存。

2.对新的进程各种数据的恢复。

注意：进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在进程切换上，而真正用于执行进程的时间减少。

十二、调度算法的评价指标

CPU利用率：

利用率=忙碌时间/总时间

系统吞吐量：单位时间内完成作业的数量。

周转时间：是指作业被交给系统开始，到作业完成为止的这段时间间隔。它包括四个部分：作业在外存后备队列上等待作业调度（高级调度）的时间、进程在就绪队列上等待进程调度（低级调度）的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。后三项在一个作业整个处理过程中，可能发生多次。

等待时间：指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。

对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。

对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。

响应时间：指从用户提交请求到首次产生响应所用的时间。