操作系统 第2章 处理机管理 (学习笔记)
第2章 处理机管理
2.1概述
2.1.1多用户
(1)多用户: 多用户同时通过终端连接到计算机主机
(2)宏观:在同一个时间范围内独立地使用计算机系统
(3)微观:各用户程序并没有同时使用计算机的资源,共享只能是时间上的分割
2.1.2程序
(1)程序: 计算机处理的一系列的指令，按照一定的逻辑要求被划分成多个相关模块，这些模块必须顺序地执行
(2)程序顺序执行的特征:顺序性,封闭性,可再现性
(3)程序的并发执行的特征:间断性,失去封闭性,不可再现性
(5)并发程序三个特点：动态性,制约性,并行性
(6)并发程序:逻辑上并行，物理上串行
1)物理上的串行:CPU串行地执行着一定大小的程序片断
2)逻辑上的并行 :从宏观上看，在一个时间范围内，每一个程序都获得了运行
2.1.4Linux中的描述
(1)任务：Linux是一个多任务系统，程序的并行就是任务的并行，任务作为一个实体具有申请、占有、释放和抢占资源的资格
(2)进程：进程之间有一种隶属关系，除隶属关系外它们又是相互独立的，可以产生，也可以消亡
2.2进程及其状态
2.2.1进程的定义
(1)进程的引入:由于多道程序的特点，程序具有了并行、制约和动态的特征，就使得原来程序的概念已难以刻划和反映系统中的情况了
(2)定义:
1)进程是并发程序的一次执行过程
2)进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动
(3)进程：程序在并发环境下的执行过程
(4)本质:
1)进程的存在必然需要程序的存在
2)进程是系统中独立存在的实体
3)并发特性通过对资源的竞争来体现动态特性通过状态来描述
4)进程和数据相关
(5)进程与程序的主要区别：
1)程序是永存的，进程是暂时的
2)程序是静态的观念，进程是动态的观念
3)进程由三部分组成：程序+数据+进程控制块PCB（描述进程活动情况的数据结构）
4)进程和程序不是一一对应的:一个程序可对应多个进程即多个进程可执行同一程序 一个进程可以执行一个或几个程序
5)进程是一个独立的运行单位，能与其它进程并发(并行)执行。而程序则不可以并发执行。
6)进程是进行计算机资源分配的基本单位，也是进行处理机调度的基本单位
(6)进程特征：动态性、并发性、调度性、异步性、结构性
(7)进程的分类
系统进程：是执行操作系统核心代码的进程，起到对系统资源的管理和控制作用。
用户进程：主要是执行用户程序的进程。
系统进程和用户进程的区别：
1)系统进程可以独占分配给它们的资源，也能以最高优先级运行；而用户进程需要通过系 统服务请求(系统调用)的方式来竞争使用系统资源。
2)用户进程不能直接执行I/O操作，而系统进程可以。
3)系统进程在内核态(管态)下活动，而用户进程则是在用户态(目态)下活动。
2.2.2进程的状态及其转换
(1)进程基本状态:
1)运行态（Running）：进程正在占用CPU；
2)就绪态（Ready）：进程具备运行条件，但尚未占用CPU；
3)阻塞态（Blocked）：进程由于等待某一事件不能享用CPU。
(2)进程状态的转换:
1)就绪态->运行态 2)运行态->就绪态 3)运行态->阻塞态 4)阻塞态->就绪态
(3) UNIX进程状态及转换
创建状态：进程刚被建立还没有被**
内存就绪：进程的数据区处于内存并被**
外存就绪：进程的数据区处于外存并被**
核心运行：从内存就绪队列中调度一进程运行，处理机运行系统程序
用户运行： 当前运行的是用户程序
内存睡眠：处于核心运行态的进程申请某种资源而不能获得时，进程就变为内存睡眠状态
外存睡眠：进程处于睡眠状态并且数据区处于外存
被抢先：进程正从核心运行态向用户运行态转换时发生进程调度，它将处于被抢先状态
僵死状态：进程完成了它的所有任务将被撤销之前
(3) Linux进程状态及转换
2.2.3进程描述机构和进程实体
2.2.3.1进程控制块
(1)进程控制块PCB（Process Control Block）:描述进程的数据结构,一个进程和其它进程以及系统资源的关系，记录了进程在各个不同时期所处的状态
(2)进程控制块的作用：进程控制块是进程组成中最关键的部分。
1)每个进程有唯一的PCB。
2)操作系统根据PCB对进程实施控制和管理。
3)进程的动态、并发等特征是利用PCB表现出来的。
4)PCB是进程存在的唯一标志。
2.2.3.2进程实体
(1)进程实体由三部分构成：由程序段、数据段、进程控制块PCB
(2)进程实体的三种表现形式：
1)程序段、数据段、PCB
2)数据段、PCB
3)数据段、PCB
2.2.3.3PCB的组织
(1)PCB的组织:为了统一管理、控制和调度进程，操作系统将进程控制块集中组织
(2)PCB组织方式:线性队列、链接表、索引表
(3)典型的形式
PCB表：系统中专门开辟依次存放所有进程的PCB的一个区域
进程队列：将不同状态进程分别组成队列的形式
2.2.3.4进程上下文
(1)进程上下文:进程物理实体和支持进程运行的环境
(2)进程上下文包括三个组成部分：
用户级上下文：由用户程序段、用户数据段（含共享数据块）和用户堆栈组成的进程地址空间。
系统级上下文：包括静态部分如PCB和资源表格，以及动态部分如核心栈、现场信息和控制信息、进程环境块、以及系统堆栈等组成的进程地址空间。
寄存器上下文：由程序状态字寄存器和各类控制寄存器、地址寄存器、通用寄存器组成
2.2.3.4进程虚空间
进程的虚拟空间:将进程的PCB、用户堆栈、用户私有地址空间、共享地址空间等内容组合在一个具有一定逻辑顺序的空间
2.3进程控制
(1)进程从产生到消亡的整个过程都由操作系统来控制的，而操作系统只不过是一系列的
能够独立运行、具有特定功能的程序
(2)操作系统拥有某些特权，它是被称为系统调用或者原语的程序
(3)在操作系统中，和计算机硬件直接打交道的程序被组织在一起，称为操作系统的内核
(4)内核是通过执行各种原语操作来实现各种控制和管理功能
2.3.1原语
(1)原语:执行过程中不可中断的、实现某种独立功能的、可被其他程序调用的程序
2.3.2进程控制原语
(1)进程控制原语:对进程的行为进行控制
(2)最基本的进程控制原语：进程建立、进程调度、进程等待、进程唤醒、进程撤消
(3)进程建立中, 父进程在调用创建原语之前必须准备的参数：进程标识符、进程优先级以及进程程序的起始地址
2.3.3Linux中的进程控制
(1)进程建立fork()函数
(2)进程等待wait()函数
(3)进程自我终止exit()函数
(4)进程删除kill()函数
(5)信号signal()函数（可以用来终止进程）
(6)获取进程的IDgetpid（ ）函数
(7)获取进程之父进程IDgetppid（ ）函数
2.3.4Windows中的进程控制
(1)Windows提供的系统调用称为应用程序编程接口 (API)，它是应用程序用来请求和完成计算机操作系统执行的低级服务的一组例程
CreateProcess()：进程的初始化，建立进程与可执行文件之间的关系，标志进程状态，配置进程的输入输出
GetGuiResources()：对进程GUI资源的查看，它返回打开的GUI对象的数目，也可返回 指定进程中打开的USER对象的数目
GetProcessVersion()：进程版本查看
SetProcessPriorityBoost()：进程优先级提升
ExitProcess()和TerninateProcess()：两个终止进程函数，前者先完成对进程资源的关 闭,再调用后者实现进程本身的终止
(2)线程:进程中的逻辑小块，它具有挂起自身和被挂起的能力，因此线程的状态是可以变化的
线程创建CreateThread():它为线程分配空间，指定线程的起始地址等
线程挂起SuspendThread()
线程恢复ResumeThread()
(3)在Windows中由微内核来管理线程的执行
(4)微内核将CPU的时间划分成小的时间片，当线程获得一个时间片时就得以运行
(5)线程的引入对系统的并行和提高效率带来了极大的好处：
1)省去了资源申请环节，创建一个新线程花费时间少
2)由于线程上下文只包含和CPU相关的内容，两个线程切换时花费时间少
3)同一进程内的线程共享所有资源，之间相互通信无须调用内核
(6)进程和线程的区别和联系:
1)进程是拥有应用程序所有资源的对象
2)线程是进程中一个独立的执行路径
3)一个进程至少要有一个线程，这个线程被叫做主线程
4)一个进程的线程越多，该进程获得的CPU时间就越多，进程的运行时间就越快
5)所有线程参与对CPU时间片的竞争
6)线程运行时共享其对应进程所拥有的资源
2.4进程同步
2.4.1互斥关系
同步：是进程间共同完成一项任务时直接发生相互作用的关系(进程之间的一种协调配合关系)
2.4.2同步关系
互斥：若干进程竞争进入临界段时，相互之间所形成的排它性关系(从广义上讲它也属于同步关系的范畴)
2.4.3临界区实现方法
(1)临界资源（critical resource）：是一次只能被一个进程使用的资源
(2)临界段/临界区(critical section)：是使用临界资源的程序段
(3)互斥进入临界区的准则:
1)每次至多只允许一个进程处于临界段中。
2)对于请求进入临界段的多个进程，在有限时间内只让一个进入。
3)进程只应在临界段中停留有限时间。
4)如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。
(4)临界区实现方法
对于互斥，可以统一描述为：
临界区入口手段；
临界区；
临界区出口手段；
(5)临界区本身无须改变，关键是设计出有效的出入口方案，来实现临界区原则
最简单的软件算法
Dekker算法
Peterson算法
硬件指令“测试并设置（TS）”
中断屏蔽方法
2.4.4用P、V操作实现互斥与同步
(1)信号量: 是一个数据结构
1)信号量定义：信号量（信号灯）=＜信号量的整型变量值S，指向PCB的指针Q＞
2)信号量的物理意义：
1.初始化时，整型变量S为一非负整数
当S变量的值为负数时，该值的绝对值代表Q指针所指向的进程控制块PCB的数目，被该指针所指向的进程处于等待状态
当S变量的值不为负数时，Q指针指向空
2.信号量初值为非负的整数变量，代表资源数。
3.信号量值可变，但仅能由Ｐ、Ｖ操作来改变。
(2)P操作原语P(S)
1)P操作一次，S值减１，即S＝S－１（请求分配一资源）；
2)如果S≥0，则该进程继续执行；如果S＜0表示无资源，则该进程的状态置为阻塞态，把相应的PCB连入该信号量队列的末尾，并放弃处理机，进行等待（直至另一个进程执行V(S)操作）。
(3)V操作原语（荷兰语的等待）V(S)
1)V操作一次，S值加1，即S＝S+１（释放一单位量资源）；
2)如果S＞0，表示有资源，则该进程继续执行；如果S≤0，则释放信号量队列上的第一个PCB所对应的进程（阻塞态改为就绪态），执行V操作的进程继续执行。
(4)进程间简单同步与互斥的实现
1)用P，V原语实现互斥的一般模型:设互斥信号量mutex初值为1
2)用P、V原语实现简单同步的例子:S1缓冲区是否空（0表示不空，1表示空），初值S1=0； S2缓冲区是否满（0表示不满，1表示满），初值S2=0；
3)生产者——消费者问题（OS典型例子）：mutex互斥信号量，初值为1；full满缓冲区数，初值为0；empty空缓冲区数，初值为N；
4) 实现计数: 设有M个进程都要以独享的方式用到某一种资源，且一次只申请一个资源，该种资源的数目为N, 当前有| N-M |个进程在等待资源
(5)Windows中的互斥与同步
1)互锁函数Interlock用来实现线程间一个长整数的读写，保证当一个线程正在修改该长整数值时，另一个有同样企图的线程被锁定等待
2)对临界段CriticalSection的操作
3)事件Event允许一个线程对其受信状态进行直接的控制
4) 互斥体Mutexes引导对共享资源的访问
5)信号量Semaphores用来记录可访问某一资源的最大线程数
2.5进程通信
进程通信:进程之间的信息交换
通信方式有：消息通信,管道
2.5.1消息通信
(1)进程间的数据交换以消息为单位
(2)用户直接利用系统中提供的一组通信命令（原语）进行通信
(3)消息msg通常由消息头和消息正文构成：
1)消息头
msgsender消息发送者
msgreceiver消息接收者
msgnext下一个消息的链指针
msgsize整个消息的字节数
2)消息正文
msgtext消息正文
(4)消息通信分类：
1)直接通信方式
2)间接通信方式
发送进程使用发送原语直接将消息发送到某种中间实体（邮箱）中，接收进程使用接收原语从该中间实体中取出消息,也称为邮箱通信
2.5.2管道
(1)在两个进程的执行过程中，如果一个进程的输出是另一个进程的输入，可以使用管道文件
(2)在Linux系统中，使用符号“|”来表示已建立管道文件
(3)管道通信
输入进程：从进程A的输出区读数据，写入管道文件
管道文件；这是一个临时文件，输入进程向它写信息，输出进程从它读信息
输出进程：将管道文件的数据读出，写入进程B的输入区
(4)管道通信的关系
互斥关系——输出和输入进程不可能同时读或者写
同步关系——当管道文件为空时，输出进程等待输入进程
当管道文件为满时，输入进程等待输出进程
(4)管道:是数据流，它既可以是单向的，也可以是两个进程间双向的,又被分为匿名管道和命名管道
2.5.3Windows中的进程通信
邮件位——是单向机制，一个进程留下消息，等待另一个进程接收
对邮件位的操作：
创建邮件位CreateMailslot()
读取邮件位信息GetMailslotInfo()
改变邮件位信息SetMailslotInfo()
对于邮件位中的数据，windows是通过对文件的操作来实现数据的读写的
2.5.4Linux中的进程通信
信号（Signals）属于Linux系统的低级通信，主要用于在进程之间传递控制信号
管道（Pipes）是UNIX操作系统传统的进程通信技术，包括无名管道和有名管道两种，通过文件系统来实现
消息队列（Message Queues）允许一个或多个进程写消息，一个或多个进程读取消息
信号灯（Semaphores）最简单的形式就是内存中一个位置，它的取值可以由多个进程检验和设置
共享内存方式可以使不同进程共同访问一块虚拟存储空间，通过对该存储区的共同操作来实现数据传递
2.6死锁
2.6.1死锁定义
(1)死锁: 是若干进程都无知地等待对方释放资源而处于无休止的等待状态
(2)产生死锁的根本原因：资源有限且操作不当。
2.6.2死锁发生的必要条件
(1)死锁产生的必要条件：资源的互斥使用,资源不可抢占,资源的部分分配,循环等待
2.6.3对抗死锁
解决死锁的三种方法：运行前预防,运行中避免,运行后解除 (检测与恢复)
2.6.3.1运行前预防
死锁预防的基本思想和可行的解决办法
1.死锁预防的基本思想：打破产生死锁的四个必要条件的一个或几个。
2.预防死锁的策略：资源预先分配策略、资源有序分配策略。
1)资源预先分配策略：打破占有且申请条件，进程在运行前一次性地向系统申请它所需要的全部资源，如果所序言的全部资源得不到满足，则不分配任何资源，此进程暂不运行。
2)资源有序分配策略(***升序或减序)：打破循环等待条件，把资源事先分类编号，按序分配，使进程在申请、占用资源时不会形成环路.
什么是进程的安全序列，死锁与安全序列的关系
1.安全序列的定义：所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列{P1，P2，…，Pn}就是安全序列。
2.安全序列{P1，P2，…，Pn}是这样组成的：若对于每一个进程Pi(1≤i≤n)，它需要的附加资源可以被系统中当前可用资源加上所有进程Pj(j<i)d当前占有资源之和所满足，则{P1，P2，…，Pn}为一个安全序列。
3.安全序列与死锁的关系：虽然存在安全序列一定不会有死锁发生，但是系统进入不安全状态（四个死锁的必要条件同时发生）也未必会产生死锁，当然，产生死锁后，系统一定处于不安全状态。
2.6.3.2运行中避免
死锁的避免与银行家算法
1.避免死锁的方法：银行家算法。
2.银行家算法的基本思想：分配资源之前，判断系统是否是安全的；若是，才分配。
2.6.3.3运行后解除
死锁检测
1. 死锁的检测算法：是当进程进行资源请求时检查并发进程组是否构成资源的请求和占用环路。如果不存在这一环路，则系统中一定没有死锁。
2. 总之：如果资源分配图中不存在环路，则系统不存在死锁；反之如果资源分配图中存在环路，则系统可能存在死锁，也可能不存在死锁。
死锁恢复:
1.死锁的恢复思想：一旦在死锁检测时发现死锁，就要消除死锁，使系统从死锁中恢复过来。 2.死锁的恢复方法：
1)系统重新启动
2)撤消进程、剥夺资源
2.7实用系统中的进程
2.7.1任务和进程
任务和进程是对同一实体在不同时期的不同称呼
任务表现为用户使用的可执行的单元
在任务没有被启用时，它只是存在于辅助存储器上的一组程序和数据，它们被记录在Windows的注册表中
通过鼠标对任务图标的点击，任务被装入内存中，并且开始运行，这时它就被称为进程
此时进程拥有系统资源和私有资源，在进程运行终止时资源被释放或者关闭
在基于进程的多任务环境下，两个或者多个进程可以并发执行
2.7.2线程
线程表示进程中可以并发执行的程序段，它是可执行代码的不可拆散的单位
一个进程必须具有至少一个线程，多个线程可并行地运行于同一个进程中
一个进程内的所有线程都共享进程的虚拟地址空间，因此，可以访问对应进程拥有的全局变量和资源
线程是时间片的竞争者，线程一旦**，就正常运行直到时间片用完，此时操作系统选择另一线程进行运行
线程的状态分为执行和挂起，改变线程状态的函数有线程挂起SuspendThread()和线程恢复执行ResumeThread()
由于一个进程中的线程可以并发执行，系统中可独立执行的实体远远多于进程数目，因此，执行效率得以提高
2.7.3 Windows支持的同步对象
互锁函数：用来实现线程间一个长整数的读写
临界段：用来控制对特殊代码段的访问权
事件：是一个线程将二进制的状态通知给另外的线程的工具
互斥体：其目的是引导对共享资源的访问
信号量：用来记录可访问某一资源的最大线程数