操作系统——第二章（线程进程管理）

62 阅读 0 评论 41 点赞

我是靠谱客的博主欣喜金毛，最近开发中收集的这篇文章主要介绍操作系统——第二章（线程进程管理），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

进程

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

（2）进程的组成：程序段、数据段、PCB三部分组成了进程实体，进程实体简称为进程。

（3）进程的组织方式：

链接方式：按照进程状态将PCB分为多个队列，操作系统持有指向各个队列的指针
索引方式：根据进程状态不同，建立几张索引表，操作系统持有指向各个索引表的指针

（4）进程的特性：动态性、并发性、独立性、异步性、结构性

（5）进程的状态：

运行态：单核情况下只有一个进程处于运行态
就绪态：处于就绪态的进程拥有了除了处理机之外所有需要的资源，一旦获得处理机，即可立即进入运行态开始运行，万事俱备，只欠CPU
阻塞态：因等待某一事件而暂时不能运行，比如等待打印机
创建态：进程正在被创建，操作系统为进程分配资源、初始化PCB
终止态：进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销PCB

在这里插入图片描述
（6）进程控制：用原语实现各种进程状态的转换。原语采用关中断和开中断指令实现原子操作，关中断后外部中断信号无法打断当前操作，因此关中断是只能在核心态下执行的特权指令。

（7）进程通信：
概念：指的就是进程间的信息交换，进程是分配系统资源的单位，因此各个进程拥有的内存空间相互独立

共享存储：两个进程对共享空间的访问是互斥的，分为基于数据结构的共享（低级）和基于存储区的共享（高级）
管道通信：进程一将数据写入管道，进程二从管道读取数据，是半双工的通信。写进程写满读进程才能读，写满后不能再写，读空时不能再读
消息传递：进程间的数据交换以格式化的消息为单位，分为直接通信方式和间接通信方式

线程

可以理解为轻量级的进程，是CPU执行的最小单元。

（1）线程属性：

线程是处理机调度的单位
多CPU计算机中，各个线程可占用不同的CPU
每个线程都有一个线程ID，线程控制块
线程也有就绪、阻塞、运行三种基本状态
线程几乎不拥有系统资源
同一进程的不同线程间共享进程的资源
由于共享内存地址空间，统一进程中线程的通信甚至无需系统干预
同一进程的线程切换不会引起进程切换，不同进程的线程切换会引起进程切换
切换进程内的线程系统开销很小，切换进程的系统开销很大

（2）线程实现方式

用户级线程：从用户的视角可以看到的线程，用户态下即可以完成，无需操作系统干预
内核级线程：从操作系统角度可以看到的线程，内核级线程才是处理机分配的单位，管理工作由操作系统内核完成，核心态下才能完成

（3）多线程模型

多对一模型：多个用户级线程对应一个内核级线程，每个用户进程只对应一个内核级线程。优点是不同线程的切换在用户态即可完成，缺点是当一个用户进程被阻塞的话那么整个进程都被阻塞，并发度不高
一对一模型：一个用户级线程对应一个内核级线程，优点是并发能力强，缺点是一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理成本高，开销大。
多对多：n个用户线程对应m个内核级线程，克服了上述两者的一些缺点

（4）进程调度
处理机调度：就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给他运行，以实现进程的并发执行

高级调度：按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程
中级调度：可将暂时不能运行的进程调至外存等待（PCB不会被调出内存），被挂起的PCB会被放到挂起队列，等它从新具备了运行条件且内存有空闲时，重新调入内存。目的是提高内存利用率和系统吞吐量，暂时调到外存等待的进程状态为挂起状态。
低级调度：按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。进程调度是最基本的一种调度，在一般的操作系统中必须配置该调度

需要进行进程调度的情况

主动：进程正常终止、运行过程中发生异常而终止、进程主动请求阻塞如IO
被动：分给进程的时间片用完、更紧急的事需要处理比如IO中断、有更高优先级的进行进入就绪队列

不能进行进程调度的情况

在处理中断的过程中
进程在操作系统内核临界区中（可能会影响到内核的管理工作）
在原子操作过程中进程不可断

（5）调度算法评价指标

CPU利用率：忙碌时间/总时间
系统吞吐量：总共完成的作业/总共花的时间
周转时间：指从作业提交到完成的这段时间间隔
等待时间：处于等待处理机状态时间之和
响应时间：从用户提出请求到首次响应的时间

（6）调度算法

先来先服务（FSFS）：非抢占式，优点公平、算法实现简单，缺点对长作业有利，对短作业不利。不会导致饥饿
短作业优先（SJF）：分为抢占式和非抢占式（默认），最短的作业优先得到服务，会产生作业饥饿（一直得不到服务）
高响应比优先（HRRN）：非抢占式，通过计算各个任务的响应比来选择响应比最小的来执行。响应比=（等待时间+要求服务时间）/要求服务时间。不会导致饥饿。
时间片轮转（RB）：抢占式的算法，该算法用于进程调度，公平、轮流的为各个进程服务，让每个进程在一定时间段内可以得到响应，时间片到了之后会重新进入就绪队列。如果时间片过大，那么会退化为先来先服务算法，时间片太小的话切换进程的开销会很大。不会导致饥饿。
优先级调度算法：分为抢占式和非抢占式，为每个任务设置优先级，调度时选择优先级最高的作业，可能会产生饥饿问题。通常系统进程的优先级高于用户进程，前台进程优先级高于后台进程，操作系统更偏好IO型进程
多级反馈队列调度算法：抢占式算法，各个进程进来后都会被优先处理，可能会导致饥饿，优点是集合了其他各类算法的优势

进程同步、互斥

（1）基本定义

进程同步：在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。比如各个进程的执行可能存在顺序关系
进程互斥：临界资源在同一时刻只允许一个进程访问，多个进程对临界资源的访问会产生进程互斥。对临界资源的访问可以分为四个部分，进入区、临界区、退出区和剩余区。其中临界区是访问临界资源的代码，进入区和退出区是负责实现互斥的代码（可以理解为上锁解锁的过程）

（2）进程互斥需要遵循的原则

空闲让进：临界区空闲时，允许一个进程访问
忙则等待：临界区正在被访问时，试图访问临界区的进程需要等待
有限等待：等待的时间是有限的，保证不会饥饿
让权等待：进不了临界区的进程，要释放处理机，防止忙等

（3）进程互斥的软件实现方法

单标志法：每个进程访问完临界区会将使用临界区的权限转让给另一个进程，该方法会违背“空闲让进”原则
双标志先检查法：设置一个布尔型数组用来标记各个进程想进入临界区的意愿，违背了“忙则等待”原则，当一个进程访问临界区时另一个进程也有可能在访问。
双标志后检查法：先上锁再检查，仍然存在异步问题，违背了“空闲让进”和“有限等待”原则
Peterson算法：继续改进，其中一个进程主动让对方先使用临界区，但仍然不遵循“让权等待”原则

（4）进程互斥的硬件实现方法

中断屏蔽方法：某进程访问临界区资源时关闭中断
TestAndSet指令：TSL指令用硬件实现，执行过程不允许被打断，优点是实现简单，适用于多处理机环境
Swap指令：与TSL相似

信号量机制

（1）信号量简介

信号量其实就是一个变量，可以用信号量表示系统中某种资源的数量，比如打印机只有一台，那么将其信号量置为1，分为整型信号量和记录型信号量。

整型信号量：用一个整数型变量作为信号值，数值表示某种资源，存在的问题是不满足让权等待原则
记录型信号量：用一个结构体，value表示资源数，L表示指向等待该资源的队列，可以用记录型信号量实现系统资源的申请和释放，也可实现进程互斥、进程同步

（2）信号量实现进程互斥

分析并发进程的关键活动，划分临界区
设置互斥信号量，初值为1
在临界区之前执行P（mutex）
在临界区之后执行V（mutex）

（3）信号量实现进程同步

分析什么地方需要进程同步
设置同步信号量S，初始为0
在“前操作”之后执行V（mutex），表示前一个已经执行完
在“后操作”之前执行P（mutex），表示后一个开始执行

（4）生产者消费者问题

生产者、消费者共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能将产品放入缓冲区，否则必须等待，只有缓冲区不空时，消费者才能从中取出产品，否则必须等到，缓冲区作为临界资源，各个进程必须互相等待。

在这里插入图片描述
注意：实现互斥的p操作一定要在实现同步的p操作之后，否则会产生死锁

（5）多生产者多消费者问题

桌子上有一个盘子，父亲和母亲往里边放水果，每次只能有一个人放。父亲放苹果，母亲放橘子，儿子专等盘子中的橘子，女儿专等盘子中的苹果。只有盘子为空时，父亲或母亲才能往里放水果，仅盘子有水果时，儿子或女儿才可以取走水果
在这里插入图片描述

（5）一生产者（生产多个产品）多消费者问题
假设系统中有三个抽烟进程和一个供应者进程，每个抽烟者不停的卷烟并抽掉它，但是要卷起一支烟需要三种材料，分别是烟草、纸、胶水。已知吸烟者1只有无限烟草，吸烟者2有无限纸，吸烟者3有无限胶水，那么供应者每次按顺序往桌子上放两种材料，能使得抽烟者按顺序吸的上烟。

设置信号量

semaphore offer1=0 （给消费者1的两种材料）
semaphore offer2=0 （给消费者2的两种材料）
semaphore offer3=0 （给消费者3的两种材料）
semaphore finish=0 （抽烟是否完成）

provider(){                       
	while(true){
		if(i==0){
			v(offer1);
		}else if(i==1){
			v(offer2);
		}else if(i==2){
			v(offer3);
		}
		i=(i+1)%3;
		p(finish);
	}
}
smoker1(){						smoker2(){						    smoker3(){
	while(true){					while(true){						while(true){
		p(offer1)						p(offer2)							p(offer3)
		卷烟、吸烟过程					卷烟、吸烟过程						卷烟、吸烟过程
		v(finish)						v(finish)							v(finish)
	}								}									}
}								}									}