32进程 进程控制处理机调度 33进程的同步与通信

3.2进程、进程控制和处理机调度3.3进程的同步与通信一、单道程序工作环境下程序的顺序执行与特征1．程序的顺序执行：一个程序通常可分成若干个程序段，它们必须按照某种先后次序执行，仅当前一操作执行完后，才能执行后继操作。2、特征：（1）顺序性（2）封闭性（3）可再现性二、多道程序工作环境下程序的并发执行与特征1、程序的并发执行：多个程序交替执行2、特征：（1）间断性（2）非封闭性：机内状况有多个程序改变（3）不可再现性：运行结果与速度有关三、进程概念：可并发执行的有独立功能的程序在某个数据集合上的运行过程1、进程与程序的区别：程序是静态的永久的，进程是动态的暂时的进程与程序的联系：一个进程可执行多个程序一个程序可构成多个进程2、进程的特征：①动态性：进程的实质是程序的一次执行过程，有生命周期②并发性：多个进程能在一段时间内同时运行，资源共享③独立性：进程是系统分配资源的独立单位，各进程独立运行（它们的地址空间相互独立）。注意：凡未建立进程的程序，都不能作为一个独立的单位参加运行。进程是分配资源的单位，线程是分配CPU的单位④异步性：由于进程并发运行相互制约，所以各自按独立的、不可预知的速度向前推进。⑤结构性：PCB（进程控制块）组成程序段数据段PCB3、进程的分类：系统进程、用户进程4、进程的状态与转换进程的3种基本状态：活动状态①就绪（准备）状态当进程已分配到除CPU以外的所有必要的资源后，只要能再获得处理机，便能立即执行。在一个系统中，可以有多个进程同时处于就绪状态，通常把它们排成一个队列，称为就绪队列。②执行状态指进程已获得处理机，其程序正在执行。在单处理机系统中，最多只能有一个进程处于正在执行状态。③阻塞（等待、睡眠）状态进程因发生某事件（等待某事件的发生，如请求I/O、申请缓冲空间等）不具备运行条件，而暂停执行时的状态，亦即进程的执行受到阻塞。通常将处于阻塞状态的进程排成一个队列，称为阻塞队列。一般还增加两个基本状态：④新建状态：刚刚被创建，但未提交进入就绪队列尾部时的状态⑤退出状态：已被系统或进程终止，等待善后处理后退出挂起状态（静止）:暂不接受调度，并释放部分系统资源，从内存转移到外存①就挂②等挂转换类型及原因：进程的状态及其转换注意：活动状态有两个不可转换两个激活三个挂起两个（新建后）提交4、进程控制块PCB（1）作用：创建时设置是进程存在与否的唯一标记OS依据PCB才能感知、管理、控制进程（2）PCB内容：进程标识符、进程调度信息、处理机状态信息、进程控制信息下图示出了PCB的内容。主要有：进程标识符现行状态现场保留区程序与数据地址互斥与同步机构进程通信机构进程优先数资源清单链接字（队列指针）家族联系就绪执行等待等挂就挂退出新建①进程标识符用于唯一地标识一个进程②家族关系用于说明本进程与其它家族成员之间的关系③现行状态：说明进程的当前状态，以作为调度程序分配处理机的依据。当进程处于阻塞状态时，要在ＰＣＢ中说明阻塞的原因；④现场保留区：用于保存进程由执行状态变为阻塞状态时的CPU现场信息。⑤程序和数据地址：该进程的程序和数据存放在内存或外存中的地址。用以把进程控制块与其程序和数据联系起来。⑥进程的优先级表示进程使用ＣＰＵ时优先级别的一个整数。优先级高的进程可优先获得处理机；⑦互斥与同步机构实现进程间的互斥与同步时所必须的机构。例如，信号量或锁等；⑧资源清单它列出了进程所需资源及当前已分配到的资源；⑨链接字也称为进程队列指针进程的组织方式：通过链接（或索引）等方式形成就绪队列（索引表）、等待队列（索引表），便于对进程进行有效管理。四、进程控制：定义——建立、撤消、状态转化1、几个概念（1）原语（primitive）定义：完成某一特定功能的程序段，其执行是不可分割的。换言之，在一个操作中的所有动作，要么全做，要么全不做。特点：不允许中断，不允许并发（2）OS内核：OS常驻内存的程序和数据（3）内核基本功能：由原语完成——中断处理进程控制：建立、撤消、状态转化资源管理:时钟、I/0设备、文件系统2、进程创建和撤消原语（1）创建原语一个进程可借助于创建原语来创建一个新进程（父进程，子进程，进程树）。子进程继承父进程的所有资源。创建一个新进程的主要工作是：申请一空闲PCB→无空闲PCB，则创建失败；否则产生PID（进程标识）→申请必要的资源→初始化PCB→插入就绪队列尾部(2)撤消进程原语找出被撤消进程的PCB→该进程若正在执行，则终止该进程的执行→该进程若有子进程，则撤消其所有子进程→将该进程所拥有的全部资源，归还给父进程或系统→将被撤消进程的PCB从所在队列（或链表）中清除，放回到空闲PCB队列。（3）进程的阻塞原语①进程的阻塞是进程自身的一种主动行为：正在执行的进程，当出现请求操作系统服务、启动某种操作、新数据尚未到达、无新工作可做等事件时，由于无法继续运行，于是自己便通过调用block原语，把自己阻塞起来。②主要工作保存CPU现场→置该进程的状态→被阻塞进程入等待队列→转进程调度（4）唤醒进程的原语①被其他进程唤醒：进程所期待的事件出现，如I/O操作完成，其所期待的数据已经到达，则由有关进程（比如，用完并释放了该I/O设备的进程）调用唤醒原语weakup()，将等待该事件的进程唤醒。②主要工作从等待队列中摘下被唤醒进程→置进程的状态→将被唤醒进程送入就绪队列→转进程调度或返回。（5）挂起进程：挂起原语将进程挂起，该进程从内存转移到外存（6）激活进程：激活原语将进程激活，该进程从外存转移到内存五、线程概念的引入及其描述1、线程的概念:线程是进程中的一个实体1）进程与线程的区别与联系：联系：同一进程中所有线程共享但不拥有隶属进程的资源，且驻留在进程的同一主存地址空间中，它们之间的通信比进程间通信更为方便区别：①进程切换须付出较大的时空开销，线程却能轻装切换。②进程是拥有资源的独立单位线程是被系统独立调度（分派CPU）的基本单位。2）引入线程的目的：进程的引入是为了实现多个程序的并发执行线程的引入是为了减少并发执行时付出的时空开销使系统具有更好的并发性线程的描述多线程的进程模型进程控制块用户地址空间线程控制块线程控制块用户堆栈内核堆栈用户堆栈内核堆栈线程1线程2……3）线程新增的特征：共享性4）线程的基本状态：同进程（就绪、等待、执行、新建、退出）2、线程的类型（1）内核级线程KLT（Kernel-LevelThreads）1）存在于系统进程中，也可存在于用户进程中2）创建、撤消和切换都由内核实现（提供应用程序编程接口或系统调用），在内核空间中建立和维护PCB和TCB（2）用户级线程ULT（User-LevelThreads）1）仅存在于用户进程中2）创建、撤消、切换、和调度与内核无关，由线程库（包）在用户空间内实现3）KLT与ULT的区别①用户级线程切换速度快：用户级线程ULT通常发生在一个应用进程的诸线程之间，切换时无须进行用户态/核心态的来回切换②用户级线程调用一个系统调用时，系统把它看作是整个进程的行为，如进程被阻塞，所有用户级线程都不能继续运行内核级线程KLT调用一个系统调用时，系统把它看作是线程本身的行为，仅阻塞该线程（3）混合式线程：在某些操作系统中提供内核级线程和用户级线程形成混合式线程在这些系统中还在用户级线程和内核级线程之间定义了一种轻型进程LWP（Light-WeightProcess）。LWP的作用：①每一个用户级线程通过LWP与内核通信（且多个进程可多路复用一个LWP，但每次只能连接一个。）②实现内核和用户级线程的隔离，使用户级线程与内核无关。六、处理机调度1、概念（1）处理机调度有三级高级调度（宏观调度）又称作业调度（仅用于批处理）低级调度（微观调度）又称为进程调度或线程调度中级调度又称进程对换，按一定的算法在内存和外存之间进行进程对换（2）进程（线程）调度定义：选出一个就绪状态的进程（线程），实现进程（线程）从就绪状态到执行状态的转换注意：由进程（线程）调度程序完成分配处理机的任务2、低级调度方式非抢占方式即非剥夺方式：以这种调度方式运行时，不允许强行剥夺已经分配给某进程的处理机。例如，调度程序一旦把处理机分配给某进程后应让它一直运行下去，直至进程完成或发生某事件而阻塞时，才把处理机分配给另一进程。抢占式方式即剥夺调度方式：这是指进程正在运行时，系统可根据某种原则，剥夺已分配给它的处理机，并再分配给其他进程的一种调度方式。抢占的原则有：①优先权原则优先权高的进程可以剥夺优先权低的进程而运行；②短进程优先原则短进程到达后可以剥夺长进程的运行；③时间片原则一个时间片运行完后重新调度3、常用调度算法（1）先来先服务（FCFS或FIFO）算法：就绪队列按进程进入的先后次序排列，调度时，选队首进程投入运行，采用非抢占方式有利于长进程不利于短进程；有利于CPU繁忙型进程不利于I/O繁忙型进程（2）短进程优先算法（SPF）：从就绪队列中选出“预计执行时间”最短的进程优先运行，采用抢占方式改善了平均周转时间，有利于提高系统吞吐量，对长进程不利（3）响应比高者优先（HRN）ＨighestResponse-ratio设响应比为R，则一种常用的响应比的计算方法如下：R=（W+T）/T=1+W/TW：在后备队列中等待的时间；T：该作业估计要执行的时间。兼顾了等待时间与运行时间（4）时间片轮转法在分时系统中都采用时间片轮转法。在简单的轮转法中，系统将所有就绪进程按FIFO规则排成一个队列，把CPU分配给队首进程，并规定它执行一个时间片。当时间片完时，系统剥夺该进程的运行并将它送就绪队列末尾，重新把处理机分配给就绪队列中新的队首进程，同样也让它执行一个时间片。（5）优先权（级、数）算法把处理机分配给就绪队列中具有最高优先权的进程。采用非抢占方式和抢占方式该算法的关键是如何确定进程的优先权，常用以下两种方法：静态优先数。静态优先权是在创建进程时确定的，在整个运行期间不再改变。动态优先数。动态优先权是基于某种原则，使进程的优先权随时间而改变。改变原则：就绪队列中的进程,其优先数以速度a增加;正在执行的进程,其优先数以速度b下降．（6）多级反馈队列多级反馈队列方式系统中，设置了多个就绪队列，并赋予各队列以不同的优先权和时间片。(队列优先级越高，其队中进程运行时所得到的时间片就越小。进程创建时，排入优先级最高的队列末尾,若在规定的时间片内未完成,则该进程的优先级降低一级。)系统在调度时，总是先调度第一级队列上的进程执行：仅当第一级队列空时，才调度第二级队列上的进程执行；类推之，仅当第１～(n-1)级队列都空时，才调度第n级队列中的进程执行。如果处理机正在服务于第i级队列中的进程又有新进程进入较高级队列，则此时将引起重新调度，把处理机分配给新进程。七、进程间的制约关系——互斥、同步1、进程同步：进程间必须相互合作的协调关系称为进程同步2、进程互斥：对某些资源，进程间必须相互限制的关系称为进程互斥亦即指在多道程序环境下，每次只允许一个进程对临界资源进行访问。互斥也是一种同步，是竞争的同步。3、临界资源：一次仅允许一个进程使用的资源。例：打印机、磁带机、变量、队列、显示器4、临界区：访问临界资源的那段代码。访问临界资源的过程：临界区剩余区（1）进入区——进入临界区之前检查可否进入临界区，如进入设置“临界区正在被访问”标记（2）临界区（3）退出区——将“临界区正在被访问”标记清除（4）剩余区——其它代码5、加锁可实现互斥（1）X-----临界资源状态X=0资源已被占用，其它进程不可用1资源可用（2）上锁原语lock(X)：申请资源l:ifX=0gotol/*忙等*/elseX=0;注意：先测试能否进入临界区，如进入临界区再加锁（3）开锁原语unlock(X)：释放资源X=１（4）互斥的实现lock(X)（临界区）unlock(X)6、信号量机制实现互斥、同步（1）P-V操作对信号量S（整型数）的定义申请临界资源的P（S）原语：不可分割的两个动作①S=S-1②如果S≥0，则表示有资源，该进程继续执行如果S0，则表示无