第二章 进程的描述与执行
2.1 前趋图和程序执行
2.1.1 前趋图
是一个有向无环图，表征了程序执行的先后顺序
2.1.2 程序顺序执行
1、程序的顺序执行
2、顺序执行的特征
- 顺序性
- 封闭性
- 可再现性
2.1.3 程序并发执行
1、程序的并发执行
2、并发执行的特征
- 间断性
- 失去封闭性
- 不可再现性
2.2 进程的描述
2.2.1 进程的定义和特征
1、进程的定义
进程控制块PCB，由程序段、数据段和PCB三者组成了进程实体，又叫进程映像；
所谓创建进程就是指创建进程的PCB，撤销进程就是指撤销进程的PCB
进程是进程实体的运行过程，是进行资源分配和调度的独立单位
2、进程的定义
动态性，并发性，异步性，独立性
2.2.2 进程的基本状态及转换
1、进程的三种基本状态
（1）就绪：就绪队列
（2）执行：已获得CPU，正在执行的
（3）阻塞：阻塞队列
2、三种基本状态的转换
就绪➡️运行：处理机调度
运行➡️就绪：时间片用完
运行➡️阻塞：I/O操作或其他资源不能满足
阻塞➡️就绪：需要的资源得到了满足，或者I/O完成了
3、创建状态和终止状态
2.2.3 挂起操作和进程状态的转换
有活动就绪、静止就绪、挂起、执行、阻塞和创建，终止七个阶段
2.2.4 进程管理中的数据结构
1、定义
进程表；OS系统中还有内存表，文件表和设备表，分别实现内存管理，文件管理和设备管理
进程表又被称为进程控制块PCB
文件表又被称为文件控制块FCB
设备表又被称为
2、进程控制块PCB的作用
进程控制块PCB描述进程的当前状况以及管理进程运行的全部信息，是操作系统总最重要的记录型数据结构
（1）作为独立运行基本单位的标志
（2）能实现间断性运行方式
（3）提供进程管理所需要的信息
（4）提供进程调度所需要的信息
（5）实现与其他进程的同步与通信
3、PCB中的信息
（1）进程标识符（PID——Program Identity ）：用于唯一的标识一个进程
（2）处理机状态：就是处理机的上下文，主要是由处理机的各种寄存器中的内容组成的，包括：通用寄存器，指令计数器PC，程序状态字寄存器PSW，用户栈指针
（3）进程调度信息：进程状态、优先级、阻塞原因等
（4）进程控制信息：程序和数据的地址、进程同步和通信机制，资源清单，链接指针等
4、PCB的组织方式
（1）线性方式
（2）链接方式
（3）索引方式，根据不同类型的PCB，建立几张索引表
2.3 进程控制
进程控制一般是由OS的内核中的原语来实现的
2.3.1 操作系统内核
系统态：又叫管态；
1、支撑功能
时钟管理、中断处理、原语操作
2、资源管理功能
进程管理，内存管理，I/O设备管理。而文件管理不需要内核态，用户态的守护程序可以完成这个功能
用户态：又叫目态
2.3.2 进程的创建
子进程可以继承父进程的资源
3、引起进程创建的事件
（1）用户登录
（2）作业调度
（3）提供系统服务
（4）应用请求：是用户进程自己创建新进程，上述三个都是系统内核为用户创建一个新进程
4、新进程的创建
（1）申请空白的PCB
（2）分配必要的资源
（3）初始化PCB
（4）插入就绪队列
2.3.3 进程的终止
1、引起进程终止的事件
（1）正常结束
（2）异常错误
（3）外界干预
2、进程的终止过程
2.3.4 进程的阻塞与唤醒
1、引起进程阻塞的事件
2、进程的阻塞过程block
3、进程的唤醒过程wakeup
区分挂起与激活！
2.3.5 进程的挂起suspend与激活active
2.4 进程同步
2.5 经典进程的同步问题
2.6 进程通信
2.6.1 进程通信的类型
1、共享存储器系统
（1）低级方式的共享是基于数据结构的共享，高级方式的共享则是基于存储区的共享
用户进程一般都是独立的，进程运行期间一般不能访问其他进程的空间，要想实现共享存储，必须通过特殊的系统调用来实现；而进程中的线程是自然共享进程空间的
（2）特点：慢，灵活性差
2、管道（pipe）通信系统
（1）先进先出的，pipe文件：用于连接一个读进程和一个写进程以实现它们之间的通信
（2）管道只能使用半双工通信，是数据流的形式，只要管道非空就可以读，只要管道非满就可以写
3、消息传递系统
（1）直接通信
（2）间接通信：信箱通信（电子邮件系统）
4、客户机-服务器系统
（1）套接字（Socket）
（2）远程过程调用和远程方法调用
2.6.2 消息传递通信的实现方式
1、直接消息传递系统（直接通信）
（1）直接通信原语
A.对称寻址方式
send(receiver,message)
receive(sender,message)
B.非对称寻址方式
send(P,message)
receive(id,message)
（2）消息的格式
有定长的消息格式和变长的消息格式
（3）进程的同步方式
①发送进程阻塞，接收进程阻塞
②发送进程不阻塞，接收进程阻塞
③发送进程不阻塞，接收进程不阻塞
（4）通信链路
建立方式有两种，一种是发送进程使用建立连接原语，一种是发送进程直接发送，OS自动建立一条通信链路
建立的链路可以分为两种，单向通信链路和双向通信链路
2、信箱通信（间接通信）
（1）信箱的结构
分为信箱头和信箱体
（2）信箱的通信原语
①信箱的创建和撤销
②消息的接收和发送
send(mailbox,message)
receive(mailbox,message)
（3）信箱的类型
①私用邮箱：用户进程自己创建，只有用户进程可以receive邮箱中的信息，是单向通信链路
②公用邮箱：OS创建，核准进程都可以用，双向通信链路
③共享邮箱：进程创建，共享进程可以用
2.6.3 直接消息传递系统实例
消息缓冲队列通信机制
1、消息缓冲队列通信机制中的数据结构
（1）缓冲区
（2）PCB中增加消息队列队首指针和消息队列 互斥信号量和资源信号量
2、发送原语
3、接收原语
2.7 线程(Threads)的基本概念
2.7.1 线程的引入
1、进程的两个基本属性
①是一个拥有资源的独立单位
②是调度和分派的基本单位
但引入线程之后，进程只作为除了CPU外的系统资源的分配单元，而线程则作为处理机的分配单元
2、程序并发执行所需付出的时空开销
①创建进程：要给进程分配资源，建立相应的PCB
②撤销进程：回收资源，撤销PCB
③进程切换：保留CPU环境，设置新CPU环境
3、线程——作为调度和分派的基本单位
2.7.2 线程与进程的比较
1、调度的基本单位
2、并发性
3、拥有资源
4、独立性：每个线程有唯一的标识符和一个线程控制块
5、系统开销：引入线程之后系统开销小了很多
6、支持多处理机系统
2.7.3 线程的状态和线程控制块
1、线程运行的三个状态
执行、就绪、阻塞（与进程的三个状态一样）
2、线程控制块TCB
包含以下几个组成部分
①线程标识符
②一组寄存器
③状态标识符
④优先级
⑤线程专有存储区
⑥信号屏蔽
⑦堆栈指针
3、多线程OS中的进程属性
（1）进程仍是拥有资源的基本单位
（2）多个线程可以并发执行
（3）进程不再是可执行的实体，而线程作为独立运行（调度）的基本单位
4、线程的属性
（1）每个线程有唯一的标识符和线程控制块
（2）不同的线程可以执行相同的程序
（3）同一进程的各个线程共享该进程所拥有的资源
2.8 线程的实现
2.8.1 线程的实现方式
1、内核支持线程KST（kernel support threads）
线程的创建、阻塞、撤销和切换在内核空间实现；
调度以线程为单位
2、用户级线程ULT（user level threads）
线程的创建、阻塞、撤销和切换在用户空间中实现，内核意识不到线程的实现
调度以进程为单位
3、组合方式
（1）多对一模型
（2）一对一模型
（3）多对多模型
2.8.2 线程的实现
1、内核支持线程的实现
在创建一个新进程时，就分配一个任务数据区PTDA；每次进程要创建一个线程时，就为这个线程分配一个TCB
2、用户级线程的实现
用户级线程都运行在一个中间系统上，两种方式实现中间系统
（1）运行时系统
实质上是指用于管理和控制线程的函数（过程）的集合
（2）内核控制线程
又称为轻型进程LWP（light weight process），就是组合方式的线程实现方式。
用户级线程会很多，但不能设置太多的LWP，就把一些LWP做成一个缓冲池，称作“线程池”
通过LWP把用户级线程和内核线程连接起来。
2.8.1 线程的创建和终止
1、线程的创建
初始化线程执行线程创建函数（或系统调用），创建完成后返回线程的标识符
2、线程的终止
终止线程执行相应的函数（或系统调用）对他执行终止操作
第三章 处理机调度与死锁
3.1 处理机调度的层次和调度算法的目标
3.1.1 处理机调度的层次
1、高级调度
又称长程调度或作业调度，运行频率最低；调度对象是作业；仅用于多道批处理系统中。
决定外存上处于后备队列的哪些作业被调入内存，为他们创建进程，分配必要的存储空间。
2、低级调度
又称短程调度或进程调度，运行频率最高；调度对象是进程（或内核级线程）；
决定哪个进程获得处理机
3、中级调度
又称内存调度；调度对象是进程；实际上就是存储器管理中的对换功能；
引入目的是提高内存利用率和系统吞吐量。
3.1.2 处理机调度算法的目标
1、处理机调度算法的共同目标
（1）提高资源利用率（处理机资源利用率）
（2）公平性
（3）平衡性
（4）策略强制执行
2、批处理系统的目标
（1）平均周转时间短
平均周转时间、带权的平均周转时间
（2）系统吞吐量大（单位时间处理的作业数量多）
（3）处理机利用率高
3、分时系统的目标
（1）响应时间快
（2）均衡性
4、实时系统的目标
（1）截止时间的保证
（2）可预测性
3.2 作业与作业调度
3.2.1 批处理系统中的作业
1、作业和作业步
（1）作业
（2）作业控制块（JCB）
2、作业控制块
3、作业运行的三个阶段和三种状态
（1）收容阶段：后备状态
（2）运行阶段：运行状态
（3）完成阶段：完成状态
3.2.2 作业调度的主要任务
作业调度又称为接纳调度
1、接纳多少个作业
根据多道程序度（即允许多少个作业同时在内存中运行）
2、接纳哪些作业
取决于采用的调度算法
对于分时系统和实时系统，要做到及时响应，所以收到的命令或者数据是直接送入内存的，因此
不需要作业调度算法，但是必须有一定的接纳控制措施，保证系统的正常运行。
3.2.3 先来先服务（FCFS）和短作业优先（SJF）调度算法
1、先来先服务（first-come first-served FCFS）调度算法
2、短作业优先（short job first SJF）的调度算法
（1）短作业优先算法：以作业的长短来决定优先级
（2）缺点：①必须预知作业的运行时间 ②对长作业非常不利，使周转时间明显增长
③无法实现人机交互 ④完全不考虑作业的紧迫程度
3.2.4 优先级调度算法和高响应比优先调度算法
1、优先级调度算法
根据作业的紧迫程度来决定作业的优先级
2、高响应比优先调度算法
既考虑作业的等待时间，又考虑作业运行时间
引入了一个动态优先级，这个优先级随着等待时间的增长而增大
Rp=
=
京公网安备 11010502036488号