《现代操作系统》读书笔记
第二章 进程与线程
一、进程
1. 进程的概念
- 程序:为了完成特定功能的一系列指令的有序集合
- 进程:一个具有一定独立功能的程序在数据集合上的一次动态执行过程
- 每个进程都有自己的状态
- 每个进程都有自己的虚拟地址空间
- 进程是操作系统分配资源的基本单位
-
- 伪并行:CPU在任何多道程序设计系统中,由一个进程快速切换至另一个进程,使每个进程运行几十或几百毫秒,某一瞬间CPU只运行一个进程,但1秒内CPU可运行多个进程,该过程称为伪并行
- 注意:若一个程序运行了两遍,则算作两个进程
- 进程实现了将一个CPU变换为多个虚拟的CPU,可以理解为每一个进程都拥有它自己的虚拟CPU,而实际上真正的CPU是在各个进程之间来回切换。
-
- 进程组:UNIX中进程和他所有的子进程组成一个进程组;window中没有进程组,但父进程有一个特别的令牌(称为句柄)可以用来控制子进程2、进程的创建
- 进程可分为前台进程和后台进程(守护进程),在UNIX、Linux系统中可用ps程序列出正在运行的进程、window中可用任务管理器列出
- 4种导致进程的创建的主要事件:
- 系统初始化
- 用户请求创建一个新进程
- 正在运行的进程执行了创建进程的系统调用
- 一个批处理作业的初始化
-
- UNIX系统进程的创建:
- UNIX系统中只有一个系统调用fork可以用来创建新进程,该系统调用会创建一个与调用进程相同的副本,这两个进程(父进程和子进程)拥有相同的内存印象、环境字符串、打开文件等,通常子进程接着执行execve等系统调用以修改内存映像并运行一个新程序。
-
- window系统进程的创建*window系统中约有100个函数用于处理进程的管理、同步等相关事务,如CreatProcess函数既处理进程的创建也负责将正确的程序装入新的进程,该函数有10个参数,其中包含优先级信息、该进程所需创建的窗口规格等。
3、进程的终止
- 4种导致进程终止的主要事件:
- 正常退出(自愿)
- 出错退出(自愿)exit(unix) ExitProcess(window)
- 严重错误(非自愿)
- 被其他进程杀死(非自愿)kill(unix) TerminateProcess(window)
-
4、进程的状态
- 进程生命周期的划分:进程创建、进程执行、进程等待、进程抢占、进程唤醒、进程结束
- 创建 -> 就绪 -> 运行 -> 等待
- 挂起(Suspend):把一个进程从内存转到外存
- 激活(Activate):把一个进程从外存转到内存
-
5、进程的组织管理
- 通过进程控制块PCB的组织管理来实现进程的组织管理
进程控制块
- 进程标识信息
- 处理机现场保存(进程交替运行时需要保存)
- 进程控制信息
- 调度和状态信息
- 进程间通信信息
- 存储管理信息
- 进程占用资源
- 有关数据结构连接信息
-
二、线程
1、线程存在的必要性
2、线程的优点
- 一个进程可同时拥有多个线程,线程之间可并发执行
- 当大量计算和I/O处理时,多线程可重叠交互进行,加快了程序执行速度
- 各线程之间可共享地址空间和文件等资源
- 线程比进程更轻量级,更容易创建也更容易撤销
3、线程的缺点
- 当cpu资源不够用时,线程分解会造成额外的开销
- 线程之间缺乏保护,可能造成数据混乱
- 缺乏访问控制,线程调用系统函数时会影响整个进程
- eg:一个线程调用exit函数则整个进程会退出
-
- 编程难度提高(需要考虑更多控制减少线程缺点的影响)
3、线程与进程的比较
进程 | 线程 |
操作系统分配资源的基本单位 | CPU调度的基本单位 |
私有完整的资源平台 | 只独享指令流执行的必要资源(寄存器和栈等) |
安全性高 | 线程可减少并发执行的时间和空间开销 |
4、单线程和多线程
- 线程表仅仅记录各个线程的属性,如每个线程的程序计数器、堆栈指针、寄存器和状态等
(1)单线程
- 每个进程都有一个线程,每个线程都在不同的地址空间运行
(2)多线程
- 用来描述在同一个进程中允许多个线程的情形
- 一个进程中有三个线程,三个线程在相同的地址空间运行
线程共享 | 线程独享 |
地址空间 | 程序计数器 |
全局变量 | 寄存器 |
打开文件 | 堆栈 |
子进程 | 状态 |
即将发生的定时器 | 特殊:errno(全局变量) |
信号与信号处理程序 | 信号屏蔽字 |
账户信息 | 调度优先级 |
线程ID |
- 每一个线程拥有自己的堆栈很重要,每个线程的堆栈有一帧供各个被调用但是还没有从中返回的过程使用。在该栈帧中存放了相应的过程的局部变量以及过程调用完成后使用的返回地址。
- 线程之间数据共享,若共享栈会引起栈混乱
- 数据共享引起数据恶意性 (线程互斥)
线程调用 | 描述 |
pthread_create | 创建线程 |
pthread_exit | 结束调用的线程,并释放栈 |
pthreat_join | 等待一个特定的线程退出,特定线程的标识符以参数形式给出 |
pthreat_yield | 释放CPU来运行另一个线程 |
pthreat_attr_init | 创建并初始化一个线程的属性结构 |
pthreat_attr_destroy | 删除一个线程的属性结构,释放其占用的内存 |
5、线程的三种实现方式
(1)用户线程
POSIX Pthreads ,Mach C -thread ,Solaris threads
概念:由一组用户级的线程库函数来完成线程的管理
优点:
- 不依赖于操作系统内核
- 内核不了解用户线程的存在
- 可用于不支持线程的多进程操作系统
-
- 在用户空间实现的线程机制
- 每个进程私有的线程控制块(TCB)列表
- TCB由线程库函数维护
-
- 同一进程内用户线程切换速度快
- 无需用户态/核心态切换
-
- 允许每个进程拥有自己的线程调度算法
缺点:
- 线程发起系统调用而阻塞时,整个进程进入等待
- 不支持基于线程的处理机抢占
- 只能按照进程分配CPU时间
(2)内核线程
Windows , Solaris , Linux
概念:进程由内核通过系统调用实现的线程机制,由内核完成线程的创建、终止和管理()
- 由内和维护PCB和TCB
- 线程执行系统调用而被阻塞不影响其他线程
- 线程的创建、终止和切换相对较大
- 以线程为单位进行CPU时间分配(多线程的进程可获得更多CPU的时间)
(3)轻权进程
Solaris (LightWeight Process)
概念:内核支持的用户线程,一个进程可有一个或多个轻量级进程,每个轻权进程有一个单独的内核线程来支持
(4)用户线程与内核新城的对应关系
一对一
多队一
多对多
三、进程间通信
1、实现进程间通信要考虑的三个问题
- 如何把信息传递给另一个进程
- 如何确保两个或多个进程活动中不会交叉
- 如何使其以正确的顺序传输
2、竞争条件
概念:两个或多个进程读写某些共享数据,最终结果取决于进程运行的精准时序
3、临界区
概念:对共享内存进行访问的程序片段
为避免竞争条件,需满足以下4点
- 任何两个进程不能同时处于任何临界区
- 不应对CPU的速度和数量做任何假设
- 临界区外运行的程序不得阻塞其他进程
- 不得使进程无限期等待进入临界区
4、集中实现互斥的方案
(1)忙等待的互斥
- 屏蔽中断
- 使每个进程刚刚进入临界区后立即屏蔽所有中断
- 缺点:
- 屏蔽中断权交给用户后,若进程屏蔽中断后不再打开中断,系统可能会因此终止
- 对于多处理器系统,屏蔽中断仅对执行该指令的CPU有效,其他CPU仍可访问共享内存
-
-
- 锁变量
- 使用一个共享锁变量,初值为0,当进程进入临界区前测试锁变量是否为0,为0则进程将其设为1并进入临界区
- 缺点:
- 进程读到锁变量为0,在其将锁变量改为1前另一个进程被调度运行,将锁变量改为1,当第一个进程再次进去时锁变量为1,两个进程同时进入临界区
-
-
- 严格轮换法
- turn初值为0用于检查或更新共享内存。开始时进程0检查turn值为0,进入临界区,进程1发现其值为0,进入等待循环不断监测turn的值。
- 忙等待:不断测试一个变量直到某个值出现为止称为忙等待
- 在一个进程比另一个进程慢很多的情况下,严格轮换法存在很大缺陷
-
while(TURE)
{
while(turn!=0)
{
critical_region();
turn=1;
noncritical_region();
}
}
while(TURE)
{
while(turn!=1)
{
critical_region();
turn=0;
noncritical_region();
}
}
- Peterson解法
#define FALSE 0
#define TRUE 1
#define N 2
int turn; //现在轮到谁
int interestde[N] //所有值初始化为0(FALSE)
void enter_region(int process)
{
int other;
other = 1 - process;
interested[process] = TURE;
turn = process;
while(turn==process&&interested[other])
}
void leave_region(int process)
{
interested[process]=FALSE;
}
- 各进程使用进程号作为函数的参数,通过设置数组元素以及turn的值表示是否想进入临界区,当两个进程同时想进入临界区时,后来的进程会覆盖掉前面进程修改的turn值,使前面的进程循环0次进入临界区,而后来的进程不断循环不能进入临界区,直到前面的进程退出临界区。
- TSL指令
enter_region:
TSL REGISTER,LOCK //复制锁到寄存器并将锁设为1
CMP REGISTER ,#0 //判断锁是否为0
JNE enter_region //若不为0,则循环
RET //返回调用者进入临界区
leave_region:
MOVE LOCK ,#0 //在锁中存入0
RET //返回调用者
- XCHG指令
enter_region:
TSL REGISTER,#1 //在寄存器中放入1
XCHG REGISTER,LOCK //交换寄存器与锁变量内容
CMP REGISTER ,#0 //判断锁是否为0
JNE enter_region //若不为0,则循环
RET //返回调用者进入临界区
leave_region:
MOVE LOCK ,#0 //在锁中存入0
RET //返回调用者
- Peterson解法、TSL、XCHG解法都有忙等待的缺点。他们本质上都是当一个进程想进入临界区时,先检查是否允许进入,若不允许则等待,直到允许为止
- 若考虑一台机器有两个进程,H进程优先级高,L进程优先级低,当L处于临界区时,若H处于就绪态,由于L优先级低,不会被调度,无法离开临界区,H进程将一直处于忙等待状态
(2)生产者与消费者问题
- 生产者与消费者问题也称有界缓冲区问题,两个进程共享一个固定大小的缓冲区,生产者放入信息,消费者拿出信息,当缓冲区已满时,生产者睡眠,待消费者取出时再唤醒生产者;当缓冲区为空时,消费者睡眠,待生产者放入数据时再唤醒它
- 该方案依旧存在竞争条件问题,当缓冲区为空时,消费者读取到count=0,此时生产者乱入放入数据修改count=1,并发现进入时count=0,则发送wakeup信号给消费者,而消费者此时并未睡眠,这将导致wakeup信号丢失,此时,消费者再次进入缓冲区由于前面检测count=0因此消费者进入睡眠状态,生产者也终将填满缓冲区进入睡眠,这样两个进程都将永久睡眠。
- 解决竞争条件问题可加上一个唤醒等待位,当wakeup信号发送给一个清醒的进程时,将唤醒等待位置为1,当进程进入睡眠时,若唤醒等待位为1则将该位清除且依旧保持清醒。但当进程更多时唤醒等待位就不够使用了,该方法并未根本解决竞争问题
-
-
5、信号量
- 信号量由一个整型sem和两个原子操作组成
- 原子操作P( )
- sem减1
- 若sem<1,进入等待,否则继续
-
- 原子操作V( )
- sem加1
- 若sem<=0,唤醒一个等待进程
-
-
- 原子操作:指一组相关联的操作要么不间断地执行,要么都不执行,由操作系统实现PV操作的原子性
6、互斥量
- 互斥量是一个可以处于两态之间的变量:解锁和加锁,与PV操作不同它只需要一个二进制位来表示它,当一个线程需要访问临界区时,调用mutex_lock,如果该互斥量是解锁的调用成功可进入临界区;如果该进程已加锁则调用线程被阻塞;如果多个进程被阻塞,将随机选择一个线程并使之允许调用锁变量。
- 该方法与TSL、XHG解法基本一样,但该方法由于系统时钟超时作用不会出现忙等待现象,取锁失败时,TSL、XCHG方***进入忙等待而该方法则调用thread_yield将CPU释放给另一个线程
- 前面所说的所有方法都忽略了一个条件,进程至少可以访问一些共享内存,若不能前面提到的方法都无法实现;解决方法有两种,一是信号量等共享数据可以存在内核中,并通过系统调用来实现;二是让进程共享一部分地址空间,最坏情况时,可通过共享文件来实现
7、管程
- PV操作需要注意其执行顺序是否正确,一旦倒序或顺序有误就会出现死锁问题
- 管程可用于解决该问题,一个管程是由过程、变量及数据结构组成的集合
- 管程是一个编程语言,编译器必须要识别管程并对互斥做出安排,而多数语言没有管程,互斥问题无法解决
8、消息传递
- 消息传递是一种系统调用
- 为了防止信号的丢失,采取一旦接收方收到信号则立即回送一条特殊的确认信息,若发送方在一定时间间隔未接收到确认消息,则重新发送,接收方通过接收消息的序号识别消息是否重复,序号一致则接收消息重复可忽略。
9、屏障
- 用屏障来实现所有进程都进入就绪状态时才能进入下一个阶段这一情形
- 在每一阶段的结尾安置屏障,当进程到达屏障时就被屏障阻拦,知道所有进程都到达该屏障为止,屏障可用于一组进程的同步
四、调度
1、调度简介
进程切换:CPU资源当前占用者的切换
- 保存当前进程在PCB中执行上下文(CPU状态)
- 恢复下一个进程的上下文
- 处理机调度
- 从就绪队列中挑选下一个占用CPU资源的进程
- 从多个CPU中挑选就绪进程可以使用的CPU资源
-
- 调度程序
- 挑选就绪进程的内核函数
-
- 调度时机
- 进程从运行状态切换到了等待状态
- 进程被终结
- 非抢占系统:当前进程主动放弃CPU
- 抢占系统:中断请求被服务例程响应完成时或当前进程被抢占时(时间片用完、进程从等待切换到就绪)
-
- 调度算法的准则
- CPU使用率:CPU处于忙状态的时间百分比
- 吞吐量:单位时间内完成的进程数量
- 周转时间:进程从初始化到结束的总时间(包含等待时间)
- 等待时间:进程在就绪队列中的总时间
- 响应时间:从提交到产生相应话费的总时间
-
- 调度策略
- 减少响应时间
- 减少平均响应时间的波动
- 增加系统的吞吐量
- 减少等待时间
- 保证相对的公平性
-
2、批处理系统中的调度
- 先来先服务
- 按照进程进入就绪队列的顺序来执行
- 优点:简单
- 缺点:平均等待时间波动大、I/O资源和CPU利用率较低、
-
- 最短作业优先
- 就绪队列按照预期时间来排序
- 缺点
- 可能导致饥饿:连续短进程会使长进程无法获得CPU资源
- 需要预知未来:需与预知下一个CPU计算的执行时间
-
-
- 最短剩余时间优先
- 该进程比当前执行进程剩余时间更短则优先执行该进程
-
3、交互式系统中的调度
- 时间片:分配处理机资源的基本时间单元
- 轮转调度
- 时间片结束时按照先来先服务算法切换到下一个就绪进程
- 缺点:额外的上下文切换(时钟切换)、时间片过小大量上下文切换影响系统吞吐量、时间片过长平均等待时间波动大
-
- 优先级调度
- 就绪队列按照进程的优先级进行排序
- 为防止高优先级进程无休止运行调度程序会加入时钟中断降低该进程的优先级或赋予进程最大时间片
- 优先级可静态赋予也可系统动态确定
-
- 多级队列
- 就绪队列分成多个子队列且相互独立
- 每个队列拥有自己的调度策略
- 队列间的调度
- 固定优先级:可能导致饥饿
-
-
- 最短进程优先
- 首先运行最短作业时间的进程来使响应时间最短
- 可根据进程历史行为推测运行时间最短的进程
-
4、实时系统中的调度
- 实时系统通常可分为硬实时和软实时
- 硬实时:必须满足绝对的截止时间
- 软实时:不希望错失截止时间但可以容忍
-
- 实时系统按照响应度可分为周期性事件和非周期性时间
- 周期性事件:以规则的时间间隔发生
- 非周期性事件:发生时间不可预知
-