《计算机操作系统-进程调度》课件

1、计算机操作系统进程调度，摘要，基础：进程调度策略：进程调度实现：互斥和同步-避免：死锁和饥饿-解决：几个经典问题(如生产者-消费者)-理解：进程通信，单程序和多程序执行，单程序执行过程，多程序执行过程，课堂思考和实践，设置时间0，在内存中它们的计算和输入/输出操作时间如表所示。尝试绘制单通道操作和多通道操作的时间关系图。是什么过程？为什么引入“过程”的概念？为了提高系统资源的利用率，出现了多通道编程技术，但是多通道程序的并发执行和资源共享带来了新的问题，破坏了程序的封闭性和可重复性。程序和机器执行程序的活动不再一一对应，并发程序之间可能存在相互限制。并发程序的独立性、并发性、动态性和相互制约性

2、反映了并发程序的本质，而程序的概念已经不能反映并发程序执行的本质。因此，人们引入过程的概念来描述并发程序的执行过程。进程：具有独立功能的程序在处理器上的数据集上执行进程，并分配基本的资源单元。这里，程序指的是一组操作序列，而数据集是接受由程序指定的操作的一组存储单元的内容。过程=程序的执行？过程和程序的区别和关系？过程和程序是两个相关的不同概念。它们的区别和联系可以概括如下：(1)过程是一个动态的概念，而程序是一个静态的概念。程序是指令的有序集合，没有任何执行的意义。而这个过程强调的是执行过程，它是动态创建的，计划执行，然后死亡。(2)过程是平行的，但程序不是。从过程的定义中，我们可以看到过程

3、有两个方面的并行性，即独立性和异步性。也就是说，不考虑资源共享，每个进程的执行是独立的，执行速度是异步的。显然，因为程序不反映执行过程，所以它没有并行特性。(3)进程是争夺计算机系统资源的基本单位，因此它的并行性受到系统本身的限制。这里，限制是对进程独立性和异步性的限制。(4)不同的进程可以包含相同的程序，只要对应于该程序的数据集是不同的。如何监控程序的执行？使用各种数据结构来记录多个进程(印刷电路板)，使用状态变化来跟踪多个进程，使用进程调度来选择和控制多个进程，以及使用并发控制来同步和协调多个进程。过程的静态描述，过程=程序数据过程控制块印刷电路板程序描述一个过程要完成的功能数据，它是一个

4、操作它的数据结构集，是程序执行时的一个基本工作空间和操作对象。过程控制块包含过程的描述信息、控制信息和资源信息，是过程动态特性的集中反映。过程状态和转换，过程控制，过程控制，即系统使用一些具有特定功能的程序段来创建和取消过程，并完成过程之间的转换，从而实现多个过程的高效并发执行和协调以及资源共享的目标。1.流程创建，2。流程撤销，3。进程阻塞，4。过程觉醒，5。进程切换：在某个时刻，一个正在运行的进程被中断，将CPU交给指定的进程。通常，当进程上下文被切换时，被切换的进程上下文的文本不被保留，但是进程在执行时使用的寄存器被保留。程序执行过程，单个过程，多个过程，独立过程相互独立，多个过程，协同

5、过程相互依赖，并行环境中没有完全独立的过程。程序执行过程、竞争进程共享互斥、共享资源、多进程、通信进程相互通信、程序执行中的问题， 没有资源竞争，只有中央处理器调度 多个进程相互依赖，争夺资源，有中央处理器调度。并发控制的实现策略：关键资源和关键区域机制：标志，信号量方法：锁定，P，V原语实现：互斥和同步，进程互斥(1)，关键资源：一次只能由一个进程使用的共享资源。一次只允许一个流程进入关键区域，进入后不允许其他流程进入。对于关键资源，多个进程必须相互独占地访问它。关键区域：在每个过程中访问关键资源的代码。关键区域是由属于共享公共数据或公共数据变量的不同并发进程的程序段引起的。间接限制：共享公

6、共资源对并发进程执行速度的间接限制。也就是说，由于共享某个公共资源，不允许并发进程在关键区域交叉执行的现象。互斥：一组并发进程中的一个或多个程序段必须在一个不允许交叉执行的单元中执行，因为它们共享一个公共资源。也就是说，不允许两个以上共享资源的并发进程同时进入关键区域称为互斥。进程互斥：一个进程正在访问一个关键资源，而另一个想要访问该资源的进程必须等待。当占用关键资源的进程退出关键区域时，允许另一个进程区域访问关键资源。为了防止两个过程同时进入关键区域，应该采用某些方法来协调它们。不管用什么方法，都应该遵循以下原则：当空闲让位于忙碌时，等待让位于等待，等待有限的等待；过程是互斥的(3)；互斥锁

7、定实现锁定关键区域以实现互斥：当进程进入关键区域时，它将锁定关键区域，直到它退出关键区域。当申请进入关键区域时，并发进程首先测试关键区域是否被锁定。如果关键区域被锁定，则在关键区域被解锁之前，流程不会获得关键区域。过程是互斥的(4)，关键区域的类名是S.为了确保每个关键区域只能执行一个程序段，设置了一个锁定位键。键s表示锁定位属于类名为s的临界区。锁定临界区程序描述如下：锁定(键s) 临界区解锁(键s)。当键s=1时，类名为s的临界区可用，当键s=0时，类名为s的临界区不可用。进程是互斥的(5)，一个简单的实现方法是：lock (x)=begin local v repeat v x直到lv=

8、1 x0结束，因为当几个进程同时调用lock (key s)时，在x0语句被执行之前，可能已经有两个以上的进程由于key s而出现问题。为了解决这个问题，一些机器在硬件中设置“测试和设置指令”以确保第一步和第二步不能分开。注意：当系统被实现时，锁定位键总是被设置在与公共资源相对应的数据结构中。进程互斥(6)，尝试考虑以下进程pa和Pb重复使用关键区域：pa a:锁定(键)s 解锁(键)转到a Pb b:锁定(键)解锁(键)转到b让进程pa通过锁定(键)显然，在进程PA执行解锁(键)进程之前，键s=0，进程PB没有机会进入关键区域。然而，在进程PA执行解锁(钥匙)进程之后，进程PA将由于转弯语句

9、而立即执行锁定(钥匙)进程。此时，因为解锁(钥匙)过程已经将钥匙的值设置为1，即解锁状态，所以过程PA可以再次进入临界区域s。只有当进程PA执行解锁(键s)并且在执行Goto A语句之前发生进程调度，这使得进程PA将处理器转移到进程PB，进程PB才能被执行。不幸的是，这种可能性非常小。因此，进程PB将处于永久饥饿状态。当使用锁定方法来实现进程间的互斥时，在某些情况下也会导致不公平。这个过程是互斥的(7)，这就像当一个学生想使用一个每个人都可以借用的教室而没有指定使用时间时，他必须先申请教室的使用权，然后去教室看看教室是否上锁。如果教室被锁上了，他下次必须再观察一次，看看教室的门是否已经打开。这

10、种重复将一直持续到他进门。从这个例子中，我们可以得到由锁定方法引起的问题的解决方案。最直观的方法之一是设置教室管理员。因此，如果一个学生申请使用教室，但没有这样做，教室管理员写下他的名字，并通知学生在教室门打开时进入。这样，不仅减少了学生多次到教室检查门是否打开的时间，也减少了学生自发检查造成的不公平。在操作系统中，这个管理员是一个信号量。信号量管理相应关键区域的公共资源，代表可用的资源实体。信号是铁路交通管理中的一种常用设备，交通管理者利用信号颜色的变化来实现交通管理。在操作系统中，信号量sem是一个整数。当sem大于或等于零时，它表示可用于并发进程的资源实体的数量，但是当sem小于零时，它

11、表示等待使用关键区域的进程的数量。显然，互斥信号量的sem初始值应该大于零，为了构建信号量，有必要解释信号量所代表的含义，分配初始值并建立相应的数据结构来指向那些等待使用临界区的进程。则该过程是互斥的(9)，并且p和v原语信号量的值只能通过p和v原语操作来改变(p和v分别是荷兰语Passeren和Verhoog的第一个字母，在英语中相当于pass和increment)。对于p，v原语，类名为s的临界区可以描述为当s做p(扫描电镜)临界区v(扫描电镜)外径。这里，sem是与关键区域中使用的公共资源相关的信号量。p原语操作将信号量sem减少1，而v原语操作将信号量sem增加1。必须强调的是，当某个

12、进程在临界区执行时，如果其他进程执行P原语操作，该进程不会返回到锁的起始点，因为它不能像调用锁时那样进入临界区，然后重新执行测试，而是在等待队列中等待其他进程执行V原语操作释放资源后进入临界区。这时，P原语的执行就真正完成了。此外，在几个进程未能通过P原语并进入等待状态后，如果某个进程执行V原语操作，其中一个等待进程可以进入关键区域，但其他进程必须等待。这些过程是互斥的(10)。原始操作的主要作用是：(1)扫描电镜负1；(2)如果sem在减1后仍然大于或等于零，则该过程继续执行；(3)如果在减去1后sem小于零，则进程被阻塞，然后在对应于信号的队列中，然后进程被转移到调度。这些过程是互斥的(1

13、1)。钒基元的主要作用是：(1)扫描电镜加1；(2)如果相加结果大于零，过程继续执行；(3)如果加法结果小于或等于零，从信号的等待队列中唤醒一个等待进程，然后返回原进程继续执行或转移到进程调度。使用P，V原语实现进程互斥使用P，V原语和信号量，可以解决并发进程的互斥问题让信号量sem成为互斥信号量，它的初始值是1，这意味着没有并发进程使用关键区域。显然，从以上各节的讨论来看，只要临界区位于P(扫描电子显微镜)和V(扫描电子显微镜)之间，就可以实现工艺之间的互斥。当一个进程想要进入关键区域时，它必须首先执行P原语操作，将信号量减少1。在一个进程完成对关键部分的操作后，它必须执行V原语操作来释放它

14、所占用的关键部分。由于信号量的初始值为1，任何进程在执行P原语操作后都会将sem值更改为0，这表明该进程可以进入关键区域。用信号量实现互斥时间值的改变、P1、S 10-1-2-101、P2、P3、信号量、等待操作信号量为非负，P1进入临界区，等待操作信号量为负，P2阻塞，等待操作从等待队列中唤醒进程。信号操作后，信号量不为正。信号操作后，信号量为正，表示在关键区域没有进程。用信号量实现并行进程PA和PB的互斥描述如下：1)设sem为互斥信号量，其取值范围为(1，0，-1)。Sem=1表示过程PA和PB都没有进入类名为s的关键区域，sem=0表示过程PA或PB已经进入类名为s的关键区域，sem=

15、-1表示一个过程已经进入关键区域，而另一个过程正在等待进入关键区域。2)描述：实践与思考一、在飞机网络售票系统中，在N个终端的终端售票过程中，尝试在同一个月的同一天销售同一张机票的过程。例如：让剩余的票单元被计数，并且算法PROCESPI (I=1，2， N) BEGIN BEGIN COUNT : INTEGER正确地并且同时执行N个票销售过程；s 3360s电泳；var Xi :整数；s :=1；根据乘客的要求进行计数；cobe gin P(s)；P1；Xi:=计数；P2；如果Xi=1，那么开始Pn；Xi :=Xi-1；coend Xi:=计数；结束。五(s)；输出一张票；结束其他输出“票售完”；结束。思考与实践二：甲、乙两个火车站之间有单轨交通。许多列车同时到达甲站，然后经过甲站到达乙站。离开乙站后，列车可以以不同的方式行驶。为了保证行车安全，请设计一个带有信号量机制的自动调度算法。程序互斥；开始(*主程序*)计数=n；(* n是列车数量*)；cobe gin Var s 3360s 3360s(:=1)；p(1)；程序P(I :整数)；p(2)；开始P(n)；重复