操作系统原理学习笔记--进程管理

进程管理

要点：基础：进程描述及控制策略：进程调度实现：互斥与同步避免：死锁与饥饿解决：几个经典问题进程的引入程序的顺序执行源代码程序，目标程序和可执行程序程序执行：编辑，编译，链接，执行程序的结构：顺序，分支，循环结构程序执行的特征：顺序性，封闭性，可再现性程序并发执行多道程序设计技术：多个程序并发执行程序并发执行时的特征：间断性，非封闭性，不可再现性并发执行引发的问题：协调各程序的执行顺序：输入数据还未全部输入内存时，计算必须等待多个执行程序共享系统资源，程序之间可能会相互影响，甚至影响输出结果选择那些，多少个程序进入内存执行内存中的执行程序谁先执行，谁后执行内存如何有效分配？进程的概念定义：可并发执行的程序，在一个数据集合上的运行过程申请、拥有资源~调度（线程）程序：静态概念，是指令和数据的集合，可长期存储进程与程序对应关系一个程序可以对应一个进程或者多个进程一个进程可以对应一个程序，或者一段程序进程的特征动态性并发性独立性异步性引入进程带来的问题增加了空间开销：为进程建立数据结构额外的时间开销：管理和协调，跟踪，填写和更新有关数据结构，切换进程，保护现场更难控制：协调多个进程竞争和共享资源如何预防；解决多个集成因为竞争资源而出现的故障处理机的竞争尤为突出进程的结构组成（进程映像）：程序，数据集合，进程控制块PCB（Process Control Block）PCB是进程存在的唯一标志。创建进程时，创建PCB；进程结束时，系统将撤销其PCBPCB进程标识信息：进程的内部（系统分配给它的标示）和外部标示符（name of a person）处理机状态信息：通用寄存器值，指令计数器值，程序状态字PSW值，用户栈指针值进程调度信息：进程状态，进程优先权，进程调度的其他信息其他信息：程序及数据指针，进程同步和通讯机制，资源清单，连接指针PCB的组织方式单一队列：所有进程的PCB通过链表组织成为一个单一队列。适用于进程数目不多的系统。如windows操作系统表格结构（查找效率较高）PCB按进程状态不同组织成不同的表格：就绪进程表，执行进程表（多机系统中）及阻塞进程表系统分别记载各PCB表的起始地址PCB多级队列
进程的状态进程的执行轨迹：进程执行的指令序列，用以观察处理机的执行过程两状态模型：执行，未执行

并非所有进程只要“未执行”就处于就绪状态，有的需要阻塞，等待IO完成；“未执行”又可以分为就绪和阻塞进程的五状态执行Running：占用处理机（单处理机环境中，某一时刻仅一个进程占用处理机）就绪Ready：准备执行阻塞Blocked：等待某事件发生才能执行，如等待I/O完成等新New：进程已经创建，但未被OS接纳为可执行进程终止Terminated：因停止或取消，被OS从执行状态释放
某些系统允许父进程在任何情况下终止其子进程。如果一个父进程被终止，其子进程都必须终止
问题：多个进程竞争内存资源内存资源紧张无就绪进程，处理机空闲：I/O的速度比处理机的速度慢很多，可能出现全部进程阻塞等待I/O解决方法采用交换技术：换出一部分进程到外存，以腾出内存空间采用虚拟存储技术：每个进程只能装入一部分程序和数据（存储管理部分）对换技术，交换技术将内存中暂时不能运行的进程，或暂时不用的数据和程序，换出到外存，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存进程挂起的原因进程全部阻塞，处理机空闲系统负荷过重，内存空间紧张操作系统的需要。操作系统可能需要挂起后台进程或一些服务进程，或者某些导致系统故障的进程终端用户的请求父进程的请求被挂起进程的特征不能够立即执行可能是等待某事件发生，若是，则阻塞条件独立于挂起条件，即使阻塞事件发生，该进程也不能够执行使之挂起的进程为：自身，父进程，OS只有挂起他的进程才能使之由挂起状态转换为其他状态挂起与阻塞是否只能挂起阻塞进程如何激活一个挂起进程两个概念：进程是否等待事件，阻塞与否；进程是否被换出内存，挂起与否4种状态组合：就绪：进程在内存，准备执行阻塞：进程在内存，等待事件就绪/挂起：进程在外存，只要调入内存即可执行阻塞/挂起：进程在外存，等待事件处理机可调度执行的进程有两种：新创建的进程或换入一个以前挂起的进程通常为了避免增加系统负载，系统会换入一个以前挂起的进程执行
进程的控制两种执行模式：系统模式（又称为系统态）、控制模式或内核模式具有较高特权运行系统特定的指令，包括读写控制寄存器的指令，基本IO指令以及与存储管理有关的指令及一些特定的内存区内核模式下的处理机及其指令、寄存器和内存都受到完全控制和保护用户模式（或用户态）较低的特权用户一般运行在用户模式模式切换用户->系统：用户执行到一条系统调用，进入操作系统内核执行系统->用户：执行完系统调用的功能，返回到用户程序特殊情况：程序执行到结束语句时，切换到系统模式，不再返回到用户程序操作系统内核基于硬件的第一层软件扩充，提供操作系统最基本的功能，是操作系统工作的基础；现代操作系统中，为减少系统本身的开销，往往将一些与硬件紧密相关的（如中断处理程序，设备驱动程序等），基本的，公共的，运行频率较高的模块（如时钟管理，进程调度等），以及关键性数据结构独立开来，使之常驻内存，并对他们进行数据保护。通常把这一部分称为操作系统的内核。用户通过系统调用访问操作系统的功能，这些功能最终都通过操作系统内核实现。一般滴，操作系统内核功能可以概括地划分为资源管理功能和支撑功能资源管理：进程管理：进程创建和终止，调度，状态转换，同步和通信，管理PCB存储管理：为进程分配地址空间，对换，段/页管理IO设备管理：缓存管理，为进程分配IO通道和设备支撑功能：中断处理统计监测时钟管理原语（Primitive）：原子操作进程的创建与终止进程的阻塞与唤醒进程的挂起与激活进程切换进程切换&模式切换进程切换：作用与进程之间的一种操作模式切换：进程内部所引用的一种操作，当用户程序和转入系统调用，或者相反时，该操作将被引用进程切换一定会引发模式切换，反之则不然进程调度调度是指，在一个队列中，按照某种方法（算法），选择一个合适的个体的过程。调度的关键是需要某种方法或者算法，好的调度算法有利于选择到合适的个体调度目标公平性处理机利用率提高系统吞吐量尽量减少进程的响应事件调度原则：满足用户的要求：响应时间：（考虑尽可能使绝大多数用户的请求能在响应时间内完成，常用于评价分时系统的性能）周转时间：作业提交给系统开始到作业完成的这段时间间隔，评价批处理系统的性能截止时间：实时系统中，某任务必须开始执行的最迟时间，或必须完成的最迟时间，常用来评价实时系统的性能满足系统的需求：系统吞吐量处理机利用率各类资源的平衡使用公平性及优先级调度方式：非剥夺方式执行完毕or申请IO阻塞自己不利于“及时性”要求较高的分时和实时系统，主要用于批处理系统剥夺方式操作系统可以在新进程到来时，或某个具有较高优先权的被阻塞进策划那个插入就绪队列时，或在基于时间片调度的的系统中，时间片用完而中断当前进程的执行，调度新的进程执行这种方式会产生较多的中断，主要用于实时性要求较高的实时系统及性能要求较高的批处理系统调度类型批处理调度，分时调度，实时调度和多处理机调度长程调度（外存到内存）：long-term scheduling又称为高级调度或者作业调度，它为被调度作业或用户程序创建进程，分配必要的系统资源，并将新创建的进策划那个插入就绪队列，等待短程调度某些采用交换技术的系统将新创建的进程插入到就绪/挂起队列，等待中程调度在批处理系统中，作业进入系统后，先驻留在磁盘上，组织成批处理队列，称为后备队列。长程调度从该队列中选择一个或者多个作业，为之创建进程
考虑的问题：选择多少个进入内存--取决于多道程序的度，即允许同时在内存中运行的进程数选择那些作业：取决于长程调度算法中程调度（进程间的外存内存之间）又称为中级调度内存空间紧张时，或处理机找不到一个可执行的就绪进程时，需要选择一个进程（阻塞或就绪状态）换出到外存，释放出内存空间给别的进程使用；当内存空间较充裕时，从外存选择一个挂起状态的进程调度到内存（换入）；
目的：为了提供内存的利用率和系统的吞吐量只有支持进程挂起的操作系统才具有中程调度功能短程调度（内存里）：也成为进程调度，或低级调度，决定就绪队列中的那个进程将获得处理机短程调度运行频率最高现代操作系统几乎都具有短程调度功能IO调度（相近的磁道）进程调度算法FCFS(先来先服务)：同时适合于三种调度非剥夺调度方式，实现简单，看似公平注意：后进入队列的运行时间较短的进程或者IO型进程而言，可能需要较长时间的等待对段进程不公平短进程优先（对FCFS的改进）非剥夺。难以准确预测进程的执行时间可能导致长进程饥饿采用非剥夺调度方式，未考虑进程的紧迫程度，不适合于分时系统和事务处理系统时间片轮转调度法
用户数多时进程急剧增加时间片大小会影响处理性能进程切换会增加系统额外开销太长太短都不好综合考虑系统最大用户数，响应时间，系统效率等因素对于短的，计算型的进程较有利不适合IO型的进程改进方法之一：可以将IO阻塞时间完成的进程单独组织成一个就绪队列，该队列进程的时间片可以设置的小一点，且优先调度基于优先级的调度算法设定进程的优先级进程完成功能的重要性进程完成功能的紧迫性为均衡系统资源的使用，指定进程（作业）优先级进程对资源的占用程度，例如，可以为短进程（或作业）赋予较高的优先级静态与动态优先级动态优先级：剩余时间最短者优先（剥夺型）响应比高者优先进程的优先级与等待时间成正比难以准确的估计进程的语气执行时间计算响应比增加系统开销反馈调度法根据执行历史而非未来进行调度，将解决这个问题根据进程的执行历史调整调度方式的调度方法，它结合了优先级和时间片轮转调度的方法
有利于交互性短进程或批处理作业，他们一般只需要一个或者几个时间片即可完成可能是长进程的周转时间急剧增加如果不断有新进程进来，还可能时长进程海长期饥饿现象可以为各队列设置不同的时间片，优先级愈低时间片愈长实时系统（Real-Time System）能及时响应外部事件爱你的请求，在规定时间内完成对该事件的处理，并控制所有的实时任务协调一致的运行的计算机系统分为实时控制系统和实时信息处理系统实时控制系统：要求进行实时控制的系统主要用于生产过程的控制。（自动控温，武器控制，导弹制导，自动驾驶）实时信息处理系统对信息进行实时处理的系统很短的时间为用户做出正确的回答（飞机订票，情报检索）实时任务（real-time task）具有即时性要求的，常常被重复执行的特定进程，在实时系统中常被称为任务周期性划分周期性实时任务周期性的控制某个外部事件非周期性实时任务必须联系着一个截止时间（开始截止时间，完成截止时间）对截止时间的要求硬实时任务（错过了出现难以预测的结果，可能是灾难性的）软实时任务（错过了影响不会太大）目标：硬实时任务必须完成，软实时任务尽量完成公平性和最短时间响应时间等要求已不再重要算法：实时性要求不太高的基于时间片轮转调度算法基于 优先级的调度算法最早截止时间优先调度算法，即优先调度截止时间最近的实时任务速度单调调度算法（RMS）根据任务周期大小赋予优先级，最短优先任务具有最高优先级其中任务周期（period），之一个任务到达至下一个任务到达之间的时间范围任务速度（rate），即周期（以秒记）的倒数任务周期的结束，表示任务的硬截止时间，任务的执行时间不应超过任务周期以任务速度为参数，则优先级函数式一个单调递增的函数广泛用于工业实时系统的周期性任务调度线程引入线程是为了减少程序并发执行时系统所付出的额外开销，使系统具有更好的并发性两个基本属性进程是一个拥有资源的独立单位同时又是一个可以独立调度的基本单位由进程到线程目标：既能提高进程的并发度，又能降低系统的额外开销实现：将进程的资源申请和调度属性分开，即进程作为资源的申请和拥有者，但是不作为调度的基本单位，这样就产生了线程的概念线程自身基本上不拥有系统资源，只拥有少许运行中必不可少的私有资源，线程可与同属一个进程的其他线程共享进程的全部资源进程中的所有线程共享该进程的状态三种基本状态：就绪执行阻塞一般不具有挂起状态一个进程可以创建和撤销多个线程，同一进程的多个线程可以并发执行线程的操作包括:派生（SPawn）阻塞（Block）解除阻塞（Unblock）结束（Finish）线程阻塞不一定会引起进程的阻塞类型：用户级线程（由应用程序完成）和内核级线程进程中的某个线程需要等待另一线程的输入数据而阻塞时，整个进程并不会阻塞，即进程保持执行状态，其内的某个线程也是执行状态。当某线程因为IO阻塞时，内核需要启动系统IO，控制从用户级转到系统内核级，这时常会引起整个进程阻塞，随即将发生进程切换，进程调度程序重新调度另一个就绪进程执行。混合模式
进程的互斥与同步问题：如何协调多个进程对系统资源，如内存空间，外部设备等的竞争和共享？如何解决多个进程因为竞争资源而出现的执行结果异常，设置系统不稳定，失效等问题。并发控制：竞争资源死锁某些资源必须互斥的使用--临界资源访问临界资源的那段代码称为临界区任何时刻，只允许一个进程进入临界区，以此实现进程对临界资源的互斥访问
互斥使用临界区在进程需要使用临界资源时，通过获得临界区的使用权实现的。首先，在进入区判断是否可以进入临界区，如果可以进入，则必须设置临界区使用标志，阻止其他后来的进程进入临界区。后来的进程通过查看临界区使用标志，知道自己不能够进入临界区，就进入阻塞队列，将自己阻塞当临界区内的进程时候用完毕，推出临界区时，即在退出区修改临界区使用标志，并负责唤醒阻塞队列中的一个进程，让其进入临界区必须保证“临界区使用标志”是可以被系统中的所有进程共享的全局变量，而且诸进程对该标志的修改操作必须互斥的进行临界区使用原则每次只允许一个进程进入临界区（忙则等待）进程只能在临界区内逗留有限时间，不得使其他进程在临界区外无限等待（有限等待） 如果临界区空闲，则只要有进程申请就立即让其进入（空闲让进）进入临界区的进程，不能够在临界区内长时间阻塞等待某事件，必须在一定期限内退出临界区（让权等待）不能限制进程的执行进度及处理机的数量竞争资源可能引起死锁
竞争资源可能引起饥饿并发控制-共同协作多个进程常常需要共同修改某些共享变量，表格文件数据库等，协作完成一些功能必须确保他们对共享变量的修改时正确的，保证数据的完整型共享协作同样涉及到互斥死锁和饥饿问题，当更强调对数据的写操作必须互斥的进行必须保证数据的一致性（银行存款取款余额）一般通过事务处理来保证数据的一致性，进入临界区的进程必须一次性完成对这一些列数据的修改操作只有该进程退出临界区以后，才允许其他进程进入临界区进行数据修改，以保证数据的一致性。并发控制-通信协作当进程进行通信合作时，各个进程之间需要建立连接，通信进程需要同步和协调。进程通信的方式很多，包括消息传递，管道，共享存储区等。通过消息传递实现进程通信时，由于没有共享资源，故无需互斥，但仍可能出现死锁与饥饿通信死锁与饥饿互斥与同步的解决策略软件方法由进程自己，通过执行相应的程序指令，实现与别的进程的同步于互斥，无需专门的程序设计语言或操作系统的支持很难正确的控制进程间的同步与互斥，而且可能会大大增加系统的额外开销硬件方法通过屏蔽中断或采用专门的机器指令控制同步与互斥减少了系统额外开销，需要太强的硬件约束条件，以及可能导致进程饥饿与死锁现象，没有成为通用的解决方法信号量方法（重点）由操作系统，或专门的程序设计语言提供特别支持，包括信号量方法，管程方法和消息传递方法通用方法管程方法消息传递方法软件方—ekker算法Peterson算法初步设想：控制两个互斥进入临界区，可以让两个进程轮流进入临界区保证了互斥出现忙等现象a非要等b用完一次才能使用下一次第一次改进为临界区设置状态标志，表明临界区是否可用，空闲时，任何一个进程都能进入进程在临界区失败问题不能保证互斥
第二次改进预先表明希望进入临界区会死锁会忙等第三次改进使他们表明态度，懂得“谦让”Dekker互斥算法

Peterson方法硬件算法屏蔽中断
约束太强，代价太大专用机器指令Test and set 指令exchange指令

优点：简单，易于证明；同时适合与单处理机系统和共享内存的多处理机系统中多个进程的互斥；缺点：忙等现象依然存在，但属于可接受的忙等；可能出现饥饿现象可能导致死锁信号量方法实例：信号灯两个或者两个进程可以通过传递信号进行合作，可以迫使进程在某个位置暂时停止执行（阻塞等待），知道它受到一个可以向前推进的信号（被唤醒）相应的，实现信号灯作用的变量称为信号量，常定义为记录型变量s，其中一个域为整型，另一个域为队列，其元素为等待信号量的阻塞进程信号量定义
定义对信号量的两个原子操作：wait（s）和signal（s）；早期这两个原语被称为P(s)和V(s)

信号量的类型：互斥信号量和资源信号量互斥信号量用于申请或者释放资源的使用权，常初始化为1资源信号量用于申请或归还资源，可以初始化为大于1的正整数，表示系统中某类资源的可用个数wait操作用于申请资源（或使用权），进程执行wait原语时，可能会阻塞自己signal操作用于释放资源（或归还资源使用权），进程执行signal原语时，有责任唤醒一个阻塞进程信号量的物理意义s.count表示可用资源数
生产者/消费者问题



必须使生产者和消费者互斥进入缓冲区。即，某时刻只允许一个实体（生产者或消费者）访问缓冲区，生产者互斥消费者和其他任何生产者。生产者不能够向满缓冲区写数据，消费者也不能在空缓冲区中取数据，即生产者与消费者必须同步



读者