Processes and ThreadsChapter 22.1 Processes2.2 Threads2.3 Interprocess communication2.4 Classical IPC problems2.5 Scheduling1ProcessesThe Process ModelMultiprogramming of four programsConceptual model of 4 independent, sequential processesOnly one program active at any instant为了描述程序在并发执行时对系统资源的共享，需要一个描述程序执行时动态特征的概念，这就是进程。2多道程序设计与进程管理 计算机中程序运行模式的发展历程顺序执行模式：单道程序独占CPU和其他资源并发执行模式：两个/多个程序共享CPU和其他资源多道程序设计：并发模式下的OS设计与实现程序运行模式的特征顺序执行模式顺序性、封闭性、独占性、确定性（结果可再现性）并发执行模式并发性、间断性、共享性、不确定性、独立性和制约性问题1：并发与并行的区别是什么？问题2：如何计算并发环境下的计算机工作效率？3并行与并发的概念差别 并行（Parallel）同一时刻，两个事物均处于活动状态示例：CPU中的超流水线设计和超标量设计 并发（Concurrency）宏观上存在并行特征，微观上存在顺序性同一时刻，只有一个事物处于活动状态示例：分时操作系统中多个程序的同时运行4并发所带来的效率提升5并发所带来的效率提升 顺序执行模式下的系统工作效率系统总运行时间：80CPU使用效率：CPU占用时间 / 总时间 40/80 = 50%DEV1使用效率：15 / 80 18.75%DEV2使用效率：25 / 80 = 31.25%并发执行模式下的系统工作效率系统总运行时间：45CPU使用效率：40 / 45 = 89%DEV1使用效率：15 / 45 = 33%DEV2使用效率：25 / 45 55.6%6并发所带来的设计难题 共享性带来的问题：如何调度或分配资源？最大限度的保证系统运行效率：谁首先获得资源？最大限度的保证系统运行安全：死锁情况的预防 间断性和不确定性带来的问题：如何保证互斥？互斥问题示例：见下页图经典IPC问题：进程管理的重点 间断性和独立性带来的问题：如何调度和保护？每个程序运行时都感觉不到间断：上下文切换 复杂应用带来的问题：如何进行通信？多个程序间可动态交换信息：进程通信机制7互斥问题 Get、Copy、Put为三个并发的程序 F、G为保存多条数据的缓冲区，S、T为临时缓冲区 三个程序顺序执行，可将F的值经过S、T保存到G中 正常情况下，不存在任何问题 但是程序运行顺序发生变化时，结果可能出错8互斥问题con.初始状态FSTG分析程序运行顺序3，4，5221，2G、C、P4，5331，2，3正确G、P、C4，5331，2，2错误C、P、G4，5321，2，2错误C、G、P4，5321，2，2错误P、C、GP、G、C9进程概念进程的核心思想 进程是某个程序在某个数据集合上的运行过程，它进程是某个程序在某个数据集合上的运行过程，它有程序、输入、输出和状态。有程序、输入、输出和状态。 在分时操作系统中，单个在分时操作系统中，单个CPU被若干进程共享，它被若干进程共享，它使用某种调度算法决定何时停止一个进程的运行，使用某种调度算法决定何时停止一个进程的运行，转而为其他进程提供服务。转而为其他进程提供服务。进进程概念程概念10进程的特征动态性：进程具有动态的地址空间（数量和内容），地址空间上包括：代码（指令执行和CPU状态的改变）数据（变量的生成和赋值）系统控制信息（进程控制块的生成和删除）独立性：各进程的地址空间相互独立，除非采用进程间通信手段；并发性、异步性：虚拟结构化：代码段、数据段和核心段（在地址空间中）；程序文件中通常也划分了代码段和数据段，而核心段通常就是OS核心（由各个进程共享，包括各进程的PCB）进进程概念程概念11进程与程序的区别进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。进进程概念程概念12进程控制块(PCB, process control block)进进程概念程概念进程控制块是由OS维护的用来记录进程相关信息的一块内存。每个进程在OS中的登记表项（可能有总数目限制），OS据此对进程进行控制和管理（PCB中的内容会动态改变），不同OS则不同处于核心段，通常不能由应用程序自身的代码来直接访问，而要通过系统调用，或通过UNIX中的进程文件系统(/proc)直接访问进程映象(image)。文件名为进程标识（如：00316），权限为创建者可读写。13进程控制块的内容进进程概念程概念进程描述信息：进程标识符(process ID)，唯一，通常是一个整数；进程名，通常基于可执行文件名（不唯一）；用户标识符(user ID)；进程组关系(process group)进程控制信息：当前状态；优先级(priority)；代码执行入口地址；程序的外存地址；运行统计信息（执行时间、页面调度）；进程间同步和通信；阻塞原因资源占用信息：虚拟地址空间的现状、打开文件列表CPU现场保护结构：寄存器值（通用、程序计数器PC、状态PSW，地址包括栈指针）14PCB的组织方式进进程概念程概念链表：同一状态的进程其PCB成一链表，多个状态对应多个不同的链表各状态的进程形成不同的链表：就绪链表、阻塞链表索引表：同一状态的进程归入一个index表（由index指向PCB），多个状态对应多个不同的index表各状态的进行形成不同的索引表：就绪索引表、阻塞索引表15进程上下文进程上下文是对进程执行活动全过程的静态描述。进程上下文由进程的用户地址空间内容、硬件寄存器内容及与该进程相关的核心数据结构组成。用户级上下文：进程的用户地址空间（包括用户栈各层次），包括用户正文段、用户数据段和用户栈；寄存器级上下文：程序寄存器、处理机状态寄存器、栈指针、通用寄存器的值；系统级上下文：静态部分（PCB和资源表格）动态部分：核心栈（核心过程的栈结构，不同进程在调用相同核心过程时有不同核心栈） 16Process CreationPrincipal events that cause process creation1.System initialization2.Execution of a process creation system call by a running process3.User request to create a new process4.Initiation of a batch job17Process Creation System CallUnix: fork() -only one system call two process (the parent and the child) have: the same memory image, the same environment strings, and the same open files. use execve() to change its memory image.Windows: CreateProcess() handles both process creation and loading the program into the new process.18Process TerminationConditions which terminate processes1.Normal exit (voluntary) ( Unix: exit(), Windows: ExitProcess() )2.Error exit (voluntary)3.Fatal error (involuntary)4.Killed by another process (involuntary) ( Unix: kill(), Windows: TerminateProcess() )19Process HierarchiesParent creates a child process, child processes can create its own processForms a hierarchyUNIX calls this a process groupWindows has no concept of process hierarchyall processes are created equal20Process States (1)Possible process statesrunning:运行态，正在占用CPU运行程序blocked:阻塞态，等待外部事件发生，无法占用CPUready:就绪态，可运行，但其他进程正在占用CPU，所有被暂时挂起Transitions between states shown21Problem问题1：为什么不能从阻塞态变为运行态呢？问题2：为什么不能从就绪态变为阻塞态呢？提示：三种状态的变换体现了OS的资源管理作用进程的核心思想在于运行CPU资源的分配22进程的复杂状态其他复杂的进程状态创建、中止、挂起三种状态五种状态模型增加了“创建”、“退出”两种状态七种状态模型针对进程的存在位置（内存或者外存），进一步增加“阻塞挂起”和“就绪挂起”两种状态进程状态模型的重要性OS管理CPU资源的核心运行机制直接关系到进程数据结构与相关算法的设计23进程的复杂状态con.24进程的复杂状态con.活动活动挂起挂起事件事件发生发生事件事件发生发生等待等待事件事件挂起挂起调度调度超时超时释放释放活动活动挂起挂起25Process States (2)Lowest layer of process-structured OShandles interrupts, schedulingAbove that layer are sequential processes26进程管理单个进程的管理进程的创建、删除：静态与动态概念的差别。 多个进程的管理树状进程集合：父进程和子进程进程的调度：保持CPU效率的关键 进程之间的通信最简单：两个进程之间如何传递信息？中级：如何保持进程之间的互斥？高级：如何维系进程之间的依赖关系？27Implementation of Processes (1)Fields of a process table entry28Implementation of Processes (2)Skeleton of what lowest level of OS does when an interrupt occurs29进程小结概念CPU资源的管理载体OS通过进程实现对CPU的管理核心思想动态概念进程与程序的区别进程实现生存周期状态的变迁进程管理单个进程进程调度进程通信进程序列进程树线程数据传递共享与互斥依赖关系维护术语Cocurrency & Parallel & MultiProgrammingProgram & Process & ThreadProgram & Process: 静态和动态的思想MultiProgramming: 并发与互斥的思想30线程进程：资源分配单位（存储器、文件）和CPU调度（分派）单位。又称为任务(task)线程：作为CPU调度单位，而进程只作为其他资源分配单位。只拥有必不可少的资源，如：线程状态、寄存器上下文和栈同样具有就绪、阻塞和执行三种基本状态31线程引入线程的目的是简化线程间的通信，以小的开销来提高进程内的并发程度。线程的优点：减小并发执行的时间和空间开销（线程的创建、退出和调度），因此容许在系统中建立更多的线程来提高并发程度。线程的创建时间比进程短；线程的终止时间比进程短；同进程内的线程切换时间比进程短；由于同进程内线程间共享内存和文件资源，可直接进行不通过内核的通信32ThreadsThe Thread Model (1)(a) Three processes each with one thread(b) One process with three threads33The Thread Model (2)Items shared by all threads in a processItems private to each thread34The Thread Model (3)Each thread has its own stack Every thread can access every memory address within the process address space. There is no protection between threads because 1) it is impossible, and 2) it should not be necessary.35Thread Callcreate new threads: thread_create()exit thread: thread_exit()one thread wait for a specific thread to exit: thread_wait()allow a thread to voluntarily give up the CPU to let another thread run: thread_yield()36进程和线程的比较地址空间和其他资源（如打开文件）：进程间相互独立，同一进程的各线程间共享某进程内的线程在其他进程不可见通信：进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信需要进程同步和互斥手段的辅助，以保证数据的一致性调度：线程上下文切换比进程上下文切换要快得多；37线程切换和进程切换38Reason for threadIn many applications, multiple activities are going on at once. By decomposing it into multiple sequential threads, the programming model becomes simpler.Threads do not have any resources attached to them, they are easier to create and destroy than processes.When there is substantial computing and also substantial I/O, having threads allows these activities to overlap, thus speeding up the application.Threads are useful on systems with multiple CPUs, where real parallelism is possible.39Thread Usage (1)A word processor with three threads threads: one interacts with user, another handles reformatting in the background, a third thread automatically save the entire file to disk during a specific time (handle the disk backups without interfering with the other two).40Thread Usage (2)A multithreaded Web server41Thread Usage (3)Rough outline of code for previous slide(a) Dispatcher thread(b) Worker thread42Thread Usage (4)Three ways to construct a server43用户线程(user-level thread)不依赖于OS核心，应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。如：数据库系统informix，图形处理Aldus PageMaker。调度由应用软件内部进行，通常采用非抢先式和更简单的规则，也无需用户态/核心态切换，所以速度特别快。一个线程发起系统调用而阻塞，则整个进程在等待。时间片分配给进程，多线程则每个线程就慢。用户线程的维护由应用进程完成；内核不了解用户线程的存在；用户线程切换不需要内核特权；用户线程调度算法可针对应用优化；44Implementing Threads in User SpaceA user-level threads package45Implementing Threads in User Space: AdvantageA user-level threads package can be implemented on an operating system that does not support threads.Doing thread switching is faster than trapping to the kernel, no trap is needed, no context switch is needed, the memory cache need not be flushed, and so on. This makes thread scheduling very fast.Allow each process to have its own customized scheduling algorithm.Scale better, since kernel threads invariably require some table space and stack space in the kernel, which can be a problem if there are a very large number of threads.46Implementing Threads in User Space: Problemsthe problem of how blocking system calls are implemented: 1) one blocking call may stop all the threads, 2) nonblocking system call changing require changes to the OS, 3) to tell in advance if a call will block: do the call if it is safe, if the call will block, the call is not made. Instead, another thread is run.the problem of page faults: block even though other runnable threads.Within a single process, there are no clock interrupts, Unless a thread enters the run-time system of its own free will, the scheduler will never get a chance.Programmers generally want threads in applications where the threads block often. Block vs computing. 47内核线程(kernel-level thread)依赖于OS核心，由内核的内部需求进行创建和撤销，用来执行一个指定的函数。Windows NT和OS/2支持内核线程；内核维护进程和线程的上下文信息；线程切换由内核完成；一个线程发起系统调用而阻塞，不会影响其他线程的运行。时间片分配给线程，所以多线程的进程获得更多CPU时间。48Implementing Threads in the KernelA threads package managed by the kernel49Implementing Threads in the KernelAdvantageNo run-time system is neededKernel threads do not require any new, nonblocking system calls.The kernel can easily check which thread (in the same process) when page fault.DisadvantageThe cost of a system call is substantial, so if thread operations (creation, termination, etc.) are common, much more overhead will be incurred.50Hybrid Implementations Multiplexing user-level threads onto kernel- level threads51Scheduler ActivationsGoal mimic functionality of kernel threadsgain performance of user space threadsAvoids unnecessary user/kernel transitions eg. block by synchronizing thread in user spaceKernel assigns virtual processors to each processlets runtime system allocate threads to processorsProblem: Fundamental reliance on kernel (lower layer) calling procedures in user space (higher layer)52Pop-Up ThreadsCreation of a new thread when message arrives(a) before message arrives(b) after message arrives53Making Single-Threaded Code Multithreaded (1)Conflicts between threads over the use of a global variable54Making Single-Threaded Code Multithreaded (2)Threads can have private global variables55SUN Solaris 线程举例Solaris支持内核线程(Kernel threads)、轻权进程(Lightweight Processes)和用户线程(User Level Threads)。一个进程可有大量用户线程；大量用户线程复用少量的轻权进程，不同的轻权进程分别对应不同的内核线程。56SUN Solaris 线程(con.)用户级线程在使用系统调用时（如文件读写），需要“捆绑(bound)”在一个LWP上。永久捆绑：一个LWP固定被一个用户级线程占用，该LWP移到LWP池之外临时捆绑：从LWP池中临时分配一个未被占用的LWP在使用系统调用时，如果所有LWP已被其他用户级线程所占用（捆绑），则该线程阻塞直到有可用的LWP例如6个用户级线程，而LWP池中有4个LWP如果LWP执行系统调用时阻塞（如read()调用），则当前捆绑在LWP上的用户级线程也阻塞。57SUN Solaris 线程(con.)用户线程、轻权进程和核心线程的关系58Windows NT线程就绪状态(Ready)：进程已获得除处理机外的所需资源，等待执行。备用状态(Standby)：特定处理器的执行对象，系统中每个处理器上只能有一个处于备用状态的线程。运行状态(Running)：完成描述表切换，线程进入运行状态，直到内核抢先、时间片用完、线程终止或进行等待状态。等待状态(Waiting)：线程等待对象句柄，以同步它的执行。等待结束时，根据优先级进入运行、就绪状态。转换状态(Transition)：线程在准备执行而其内核堆栈处于外存时，线程进入转换状态；当其内核堆栈调回内存，线程进入就绪状态。终止状态(Terminated)：线程执行完就进入终止状态；如执行体有一指向线程对象的指针，可将线程对象重新初始化，并再次使用。初始化状态(Initialized)：线程创建过程中的线程状态；59Windows NT线程(con.)60Windows NT线程(con.)CreateThread()函数在调用进程的地址空间上创建一个线程，以执行指定的函数；返回值为所创建线程的句柄。ExitThread()函数用于结束本线程。SuspendThread()函数用于挂起指定的线程。ResumeThread()函数递减指定线程的挂起计数，挂起计数为0时，线程恢复执行。61进程通信（IPC）进程间的关系完全无关（异步）：不同进程间无任何关联使用共享数据（互斥）：有效保护各个进程的正确运行存在先后顺序（同步）：保证进程运行顺序的正确进程通信需要考虑的问题如何实现两个进程间的信息传递如何协调两个或者多个进程之间的互斥和同步情况问题难点分析金字塔法则：20的简单问题80的困难问题难点：临界区的保护62Interprocess CommunicationHow one process can pass information to anotherMaking sure two or more process do not get into each others way when engaging in critical activities.Proper sequencing when dependencies are present.Note: passing information is easy for threads since they share a common address space. However, keeping out of each others hair and proper sequencing apply equally well to threads63Interprocess CommunicationRace ConditionsTwo processes want to access shared memory at same time64Spooler目录问题（互斥）OutOut：4 4InIn：7 7进程进程进程进程A A： N_f_s = In; N_f_s = In; /In = 7/In = 7InsertFileIntoSpoolerInsertFileIntoSpooler(N_f_s);(N_f_s);In=N_f_s+; In=N_f_s+; /In = 8/In = 8进程进程进程进程B B： N_f_s = In; N_f_s = In; /In = 8/In = 8InsertFileIntoSpoolerInsertFileIntoSpooler(N_f_s);(N_f_s);In=N_f_s+; In=N_f_s+; /In = 9/In = 94 4：File1File15 5：File2File26 6：File3File37 7：NullNull8 8：NullNullSpoolerSpooler目录目录目录目录进程切换，一切正常进程切换，一切正常进程切换，一切正常进程切换，一切正常65OutOut：4 4InIn：7 7进程进程进程进程A A： N_f_s = In; N_f_s = In; /In = 7/In = 7进程进程进程进程B B： N_f_s = In; N_f_s = In; /In = 7/In = 7InsertFileIntoSpoolerInsertFileIntoSpooler(N_f_s);(N_f_s);In=N_f_s+; In=N_f_s+; /In = 8/In = 84 4：File1File15 5：File2File26 6：File3File37 7：NullNull8 8：NullNullSpoolerSpooler目录目录目录目录进程切换进程切换进程切换进程切换进程进程进程进程A A： InsertFileIntoSpoolerInsertFileIntoSpooler(N_f_s);(N_f_s);In=N_f_s+; In=N_f_s+; /In = 8/In = 8进程切换，进程进程切换，进程进程切换，进程进程切换，进程B B数据丢失数据丢失数据丢失数据丢失66Interprocess Communication进程调度机制的深入理解何时发生进程调度时钟中断进程切换时的操作压栈，进入就绪队列边界情况的进程通信困难互斥情况调度顺序影响运行结果同步情况运行过程影响应用效果多进程分时运行的临界情况正常情况下不存在任何问题临界情况下将产生不可预知的后果（墨菲法则）解决的关键保持进程之间正确的运行顺序OS与普通应用程序设计都需要考虑解决机制：提升系统运行的稳定性67一些IPC概念竞争条件两个或者多个进程读写共享数据，而运行结果取决于进程运行时的精确时序，则这种情况称之为竞争条件当竞争条件存在时，进程处理结果可能失效甚至发生错误临界区对共享内存（数据）进行访问的程序片断称为临界区互斥防止多个进程同时操作相同共享数据的手段(多个进程不能同时使用同一个资源)死锁多个进程互不相让，都得不到足够的资源饥饿一个进程一直得不到资源（其他进程可能轮流占用资源）68Interprocess Communication同步关系分析两个或者多个进程在运行顺序上存在固定的规则由于分时操作系统的不确定性，导致同步关系无法保持必须进行显式的程序控制，保证同步关系的正确同步与互斥的差别互斥：体现为排他性，可表现为“01”关系(保护临界区，防止多个进程同时进入)同步：体现为时序性，比互斥更加复杂和多变(保证进程运行的顺序合理)解决思路保证解决办法对互斥和同步的适用性69Critical Regions (1)Four conditions to provide mutual exclusion1.No two processes simultaneously in critical region2.No assumptions made about speeds or numbers of CPUs3.No process running outside its critical region may block another process4.No process must wait forever to enter its critical region互斥原则：任何两个进程不能同时处于临界区通用性原则：不应对CPU的速度和数目进行任何假设有效性原则：临界区外的进程不应阻塞其他进程合理性原则：不得使进程在临界区外无限制的等待；当进程无法进入临界区时，应放弃CPU资源70Critical Regions (2)Mutual exclusion using critical regions71IPC机制忙等待模型（只解决互斥问题）进程进入临界区时进行严格的检查睡眠和唤醒模型（互斥与同步）通过改变进程的状态来实现互斥和同步消息传递模型（复杂的IPC机制）以公共的通信机制来控制进程状态变化，实现同步和互斥72忙等待模型模型思想设定一个变量，标识临界区的状态互斥进程均检查这个变量，只有当其满足条件时方可进入临界区模型方法关中断锁变量严格轮转Peterson解决方案73关中断解决思想在临界区中防止发生进程调度保证临界区操作的完整性方法分析用户控制系统中断是非常危险的本方法对多个CPU系统将失去作用进程进程进程进程A AClose_INT;Close_INT;Critical_region();Critical_region();Open_INT;Open_INT;进程进程进程进程B BClose_INT;Close_INT;Critical_region();Critical_region();Open_INT;Open_INT;74锁变量解决思想设定监控变量（lock），通过其值变化控制进程操作方法分析依然存在竞争条件，不能根本解决互斥问题致命缺陷：不具有操作的原子性进程进程进程进程A AWhile(lock != 0);While(lock != 0);lock lock 1; 1;Critical_region();Critical_region();lock lock 0 0；进程进程进程进程B BWhile(lock != 0); While(lock != 0); lock = 1;lock = 1;Critical_region();Critical_region();lock = 0;lock = 0;lock lock 0 075锁变量的缺陷示例进程进程进程进程A AWhile(lock != 0);While(lock != 0);进程进程进程进程B BWhile(lock != 0); While(lock != 0); lock lock 0 0进程进程进程进程A Alock lock 1; 1;Critical_Region();Critical_Region();进程进程进程进程B Block = 1;lock = 1;Critical_Region();Critical_Region();发生进程调度，互发生进程调度，互斥的进程开始运行斥的进程开始运行发生进程调度，发生进程调度，A并不并不知道知道B也进入临界区也进入临界区发生进程调度，发生进程调度，B并不并不知道知道A也进入临界区也进入临界区76Mutual Exclusion with Busy WaitingProposed solution to critical region problem(a)Process 0. (b) Process 1.严格轮转法：忙等待浪费CPU时间；存在边界情况，违反解决原则第三条77严格轮转法的缺陷示例进程进程进程进程A A进入退出临界区进入退出临界区进入退出临界区进入退出临界区NocriticalNocritical_region()_region(); ;turn turn 0 0进程进程进程进程B B进入退出临界区进入退出临界区进入退出临界区进入退出临界区完成非临界区操作完成非临界区操作完成非临界区操作完成非临界区操作等待进入临界区等待进入临界区等待进入临界区等待进入临界区第一次运行时，可第一次运行时，可严格保证互斥关系严格保证互斥关系进程进程B需要第二次进入临需要第二次进入临界区时，必须等待进程界区时，必须等待进程A将将turn值改为值改为1。但是进。但是进程程A的非临界区操作很慢的非临界区操作很慢78Mutual Exclusion with Busy Waiting (2)Petersons solution for achieving mutual exclusion79Use Petersons solution进程进程进程进程A AWhile(TRUE)While(TRUE) enter_region(AID);enter_region(AID);Critical_region;Critical_region;leave_region(AID);leave_region(AID); 进程进程进程进程B BWhile(TRUE)While(TRUE) enter_region(BID);enter_region(BID);Critical_region;Critical_region;leave_region(BID);leave_region(BID); 80Mutual Exclusion with Busy Waiting (3)Entering and leaving a critical region using the TSL instruction测试并加锁：硬件TSL指令硬件实现提高速度，适用于多处理机; 依然存在忙等待的问题TSL RX LOCK: 硬件实现锁变量机制, 保证LOCK读写原子性81忙等待模型分析优点分析实现机制简单易懂，可有效保证互斥缺点分析只适用于两个进程间互斥，不具有通用性忙等待严重浪费CPU资源，降低硬件效率“优先级调度”“忙等待” 优先级反转进程H和L，H优先级比L优先级高L先进入临界区，H后进入临界区H开始忙等待，而L由于无法获得CPU也不能离开临界区82睡眠-唤醒模型模型思想OS提供系统调用原语（Atomic Action），改变进程状态无法进入临界区的进程转为阻塞态，条件满足则被唤醒可有效克服忙等待造成的资源浪费更重要的优点：可同时实现同步与互斥模型方法简单的睡眠唤醒方法信号量机制管程方法83简单的睡眠唤醒方法操作系统原语设计Sleep()：调用该原语的进程将变为阻塞态Wakeup(ID)：该原语将唤醒ID标识的进程原语使用思想进入临界区前检查竞争条件，如不满足则睡眠离开临界区后唤醒互斥进程84生产者消费者问题问题描述一个有限空间的共享缓冲区，负责存放货物生产者向缓冲区中放物品，缓冲区满则不能放消费者从缓冲区中拿物品，缓冲区空则不能拿85Sleep and WakeupProducer-consumer problem with fatal race condition86潜在的竞争条件ProducerProducer进程进程进程进程 wakeup(consumer);wakeup(consumer);define N 100define N 100intint lock lock 0 0intint count = 0 count = 0ComsumerComsumer进程进程进程进程 if(count = 0)if(count = 0)ComsumerComsumer进程进程进程进程sleep();sleep();ProducerProducer进程进程进程进程 ProducerProducer进程进程进程进程sleep()sleep()；发生进程调度，导致发生进程调度，导致C进进程并未进行程并未进行SleepP进程认为进程认为C在睡眠，试在睡眠，试图唤醒图唤醒C由于错过了由于错过了Wakeup信号，信号，C进入了睡眠状态进入了睡眠状态P进程一直运行下去，填进程一直运行下去，填满缓冲区后也睡眠了满缓冲区后也睡眠了87临界情况count的访问未加限制，形成竞争条件必须增加唤醒等待位，以解决互斥问题方法分析较忙等待更进一步，有效节省CPU资源存在竞争条件，需要额外处理当互斥进程数增加时，方法有效性下降改进办法由OS提供宏观调控管理机制彻底消除调度顺序引起的错乱OS实现更高层次的原语级操作88信号量机制基本概念信号量：表示累积的睡眠或者唤醒操作Down与Up原语（P/V、S/W原语）Dijkstra于1965年提出Probern和Verhogen原语核心思想引入新的数据结构定义：信号量利用信号量，提供更为复杂的原语级操作从根本上解决“潜在竞争条件”问题可以方便的推广到一般情况，适用于多进程的互斥与同步89信号量与Down/Up原语基本概念对于一种互斥或者同步关系，用一个整型变量来描述当信号量大于0时，说明“环境安全”，可继续运行当信号量小于0时，说明“互斥等待”，只能阻塞推广到一般情况，信号量可解决复杂的同步互斥问题DownDown原语原语原语原语Down(s)Down(s) s = s - 1;s = s - 1;if(s 0) wait;if(s 0) wait; UpUp原语原语原语原语Up(s) Up(s) s = s+1;s = s+1;if(s = 0) wakeup();if(s 被阻塞条件变量不能象信号量那样积累信号，为了防止信号丢失，规定： wait操作必须在signal操作之前。98管程中的多个进程进入当一个进入管程的进程执行wait操作时，它应当释放管程的互斥权；当一个进入管程的进程执行signal操作时（如唤醒），管程中便存在两个同时处于活动状态的进程。Brinch Hansen的处理方法：执行signal操作的进程必须立即退出管程，即，signal语句只可作为管程过程的最后一条语句。如果在一个条件变量上有多个进程正在等待，则对该条件变量的signal后，系统调度程序只能在其中选择一个使其恢复运行。99Monitors (1)Example of a monitor100Monitors (2)Outline of producer-consumer problem with monitorsonly one monitor procedure active at one timebuffer has N slots101Monitors (3)Solution to producer-consumer problem in Java (part 1)102Monitors (4)Solution to producer-consumer problem in Java (part 2)103信号量模型分析优点分析彻底解决忙等待弊端，提高OS的管理层次可实现复杂的同步与互斥情况，特别是多进程间通信可最大限度的保证并发效率缺点分析实现机制复杂，互斥和同步关系分析困难存在死锁陷阱，需要谨慎小心严密的设计104消息传递模型模型思想提供Send和Receive原语，用来传递消息进程通过发送和接收消息来实现互斥与同步重要的优点：不仅实现了同步，还能够传送大容量信息设计要点如何保证消息传递中不丢失？（ACK机制）如何命名进程，使得其地址唯一并确认身份如何规范消息格式，降低处理时间105Message PassingThe producer-consumer problem with N messages106BarriersUse of a barrierprocesses approaching a barrierall processes but one blocked at barrierlast process arrives, all are let through107Dining Philosophers (1)Philosophers eat/thinkEating needs 2 forksPick one fork at a time How to prevent deadlock 互斥分析筷子：同一时刻只能有一个哲学家拿起筷子同步分析就餐：只有获得两个筷子后才能进餐特殊情况死锁：如果每个哲学家都拿起一只筷子，都饿死并行程度：五只筷子允许两人同时进餐108Dining Philosophers (2)A nonsolution to the dining philosophers problem109Dining Philosophers (3)Solution to dining philosophers problem (part 1)110Dining Philosophers (4)Solution to dining philosophers problem (part 2)111读者-写者问题问题描述写者向数据区放数据，读者从数据区获取数据多个读者可同时读取数据多个写者不能同时写数据读者和写者的控制策略变化多端112互斥分析读者和写者不能同时进入共享数据区多个写者不能同时进入共享数据区多个读者可以同时进入共享数据区同步分析读者进入缓冲区，写者必须等待写者进入缓冲区，读者必须等待读者优先：一旦有读者进入，则后续读者均可进入合理顺序：读者在先来的写者之后写者优先：只要有写者等待，则后续读者必须等待113The Readers and Writers ProblemA solution to the readers and writers problem114The Sleeping Barber Problem (1)互斥分析理发椅上只能有一位顾客等待座位是有限缓冲区同步分析只要存在顾客，理发师就不能睡觉信号量设计互斥信号量：实现对“等待顾客数”的互斥同步信号量1：理发师“睡眠”和“工作”的同步同步信号量2：等待顾客与等待座位的同步115The Sleeping Barber Problem (2)Solution to sleeping barber problem.116调度程序对CPU资源进行合理的分配使用，以提高处理机利用率，并使各用户公平地得到处理机资源。可从不同的角度来判断处理机调度算法的性能，如用户的角度、处理机的角度和算法实现的角度。实际的处理机调度算法选择是一个综合的判断结果。117调度程序(con.)记录所有进程的运行状况（静态和动态）当进程出让CPU或调度程序剥夺执行状态进程占用的CPU时，选择适当的进程分派CPU完成上下文切换进程的上下文切换过程：用户态执行进程A代码进入OS核心（通过时钟中断或系统调用）保存进程A的上下文，恢复进程B的上下文（CPU寄存器和一些表格的当前指针）用户态执行进程B代码注：上下文切换之后，指令和数据快速缓存cache通常需要更新，执行速度降低118SchedulingIntroduction to Scheduling (1)Bursts of CPU usage alternate with periods of I/O waita CPU-bound processan I/O bound process119Introduction to Scheduling (2)Scheduling Algorithm Goals120面向用户的调度性能准则周转时间：作业从提交到完成（得到结果）所经历的时间。包括：在收容队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待批处理系统平均周转时间T平均带权周转时间（带权周转时间W是 T(周转)/T(CPU执行)响应时间：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间分时系统截止时间：开始截止时间和完成截止时间实时系统，与周转时间有些相似。公平性：不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。优先级：可以使关键任务达到更好的指标。121面向系统的调度性能准则吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系批处理系统平均周转时间不是吞吐量的倒数，因为并发执行的作业在时间上可以重叠。如：在2小时内完成4个作业，而每个周转时间是1小时，则吞吐量是2个作业/小时处理机利用率：大中型主机各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙（指次数多，每次时间短）的作业搭配大中型主机注：调度算法本身的调度性能准则：易于实现、执行开销比122先来先服务(FCFS, First Come First Service)按照作业提交或进程变为就绪状态的先后次序，分派CPU；当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。最简单的算法。特点:比较有利于长作业，而不利于短作业; 有利于CPU繁忙的作业，而不利于I/O繁忙的作业。123最短作业优先(SJF, Shortest Job First)对FCFS算法的改进，其目标是减少平均周转时间 。对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。优点：比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量；缺点：对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。124Scheduling in Batch Systems (1)An example of shortest job first scheduling125最短剩余时间优先SRT(Shortest Remaining Time)SJF的变型允许比当前进程剩余时间更短的进程来抢占126Scheduling in Batch Systems (2)Three level scheduling127Scheduling in Interactive Systems (1)Round Robin Schedulinglist of runnable processeslist of runnable processes after B uses up its quantum128时间片轮转调度核心思想：每个进程运行固定的时间片，然后调入下一个进程 实现机理：维护就绪进程队列，采用FIFO方式一次读取 特殊控制：时间片内发生阻塞或结束，则立即放弃时间片 优缺点分析优点：绝对公平缺点：公平即合理吗？时间片如何设计才能保证效率？129优先级调度核心思想：为每个进程赋予不同级别的优先级，越高越优先 实现机理：维护一个优先级队列，自顶向下依次读取 特殊控制：静态优先级与动态优先级概念 优缺点分析优点：响应时间快，易于调整。最通用的方法。缺点：死规则，如何保证周转时间和吞吐量？130多级队列算法(Multiple-level Queue)引入多个就绪队列，通过各队列的区别对待，达到一个综合的调度目标；根据作业或进程的性质或类型的不同，将就绪队列再分为若干个子队列。每个作业固定归入一个队列。各队列的不同处理：不同队列可有不同的优先级、时间片长度、调度策略等。如：系统进程、用户交互进程、批处理进程等。131Scheduling in Interactive Systems (2)A scheduling algorithm with four priority classes132最短进程优先 核心思想：保证响应时间最快、平均周转时间最短 实现机理：依据先验信息，将进程按照运行时间增序调度估计值(aging)： T0 , T0 /2+ T1/2, T0 /4+ T1/4+T2 /2, T0 /8+ T1/8+T2 /4+ T3/2, 特殊控制：如何确定最短作业？（老化算法） 优缺点分析优点：保证了CPU的利用效率缺点：无法通用，约束条件多。133其它调度算法保证调度：n个用户，某个用户得到1/n的CPU能力公平分享调度：以用户而不是进程为考虑原则134彩票调度算法 核心思想：保证响应速度最快、依据进程对CPU资源的需求量调度 实现机理：维护定量的彩票，不同进程获取数量不同，随机选择 特殊控制：彩票交换：进程间可以动态自主调节调度顺序 优缺点分析优点：响应速度最快、CPU利用率最高缺点：OS实现机制复杂、吞吐量和周转时间无法保证135Scheduling in Real-Time SystemsSchedulable real-time systemGivenm periodic eventsevent i occurs within period Pi and requires Ci secondsThen the load can only be handled if136Policy versus Mechanism 调度机制不同调度算法适用于不同环境和不同目的调度算法一旦固定，则其最优、最坏情况均无法避免如能根据具体情况动态调整，则效果更佳 调度策略为用户提供改变调整调度机制的渠道实现方法提供系统调用，能够改变调度机制137Policy versus MechanismSeparate what is allowed to be done with how it is donea process knows which of its children threads are important and need priorityScheduling algorithm parameterizedmechanism in the kernelParameters filled in by user processespolicy set by user process138Thread Scheduling (1)Possible scheduling of user-level threads50-msec process quantumthreads run 5 msec/CPU burst139Thread Scheduling (2)Possible scheduling of kernel-level threads50-msec process quantumthreads run 5 msec/CPU burst140