现代操作系统 Chapter 2 Part2.ppt

Chapter 2 Processes and threadsContents2.1 Processes2.2 Interprocess communication(IPC)2.3 Classical IPC problems2.4 Threads2.5 Scheduling22.4 Threads2.4.1 Threads usage2.4.2 The classical thread model2.4.3 Implementing threads in user space2.4.4 Implementing threads in the kernel32.4.1 Threads usageWhy would anyone want to have a kind of process within a process?It turns out there are several reasons for having these miniprocesses,called threads(线程线程).In many applications,multiple activities are going on at once.By decomposing such an application into multiple sequential threads that run in quasi-parallel(准并行准并行),the programming model becomes simpler.Threads are lighter weight than processes,they are easier to create and destroy than processes.Performance.When there is substantial computing and also substantial I/O,having threads allows these activities to overlap,thus speeding up the application.4An example of multithreadA word processor with 3 threads52.4.2 The classical thread modelThe process model is based on two independent concepts:resource grouping and execution.Sometimes it is useful to separate them;this is where threads come in.A process has an address space containing program text and data,as well as other resources.A thread has a program counter,registers,a stack.Process are used to group resources together;threads are the entities scheduled for execution on the CPU.6线程的引入线程的引入v进程的两个基本属性：进程的两个基本属性：进程是一个可拥有资源的独立单位；进程是一个可拥有资源的独立单位；进程同时又是一个可以独立调度和分配的基本进程同时又是一个可以独立调度和分配的基本单位。单位。v由于进程是一个资源拥有者，因而在进程的由于进程是一个资源拥有者，因而在进程的创建、撤消和切换中，系统必须为之付出较创建、撤消和切换中，系统必须为之付出较大的时空开销。也正因为如此，在系统中所大的时空开销。也正因为如此，在系统中所设置的进程数目不宜过多，进程切换的频率设置的进程数目不宜过多，进程切换的频率也不宜太高，但这也就限制了并发程度的进也不宜太高，但这也就限制了并发程度的进一步提高。一步提高。7线程的引入线程的引入v如何能使多个程序更好地并发执行，同时又尽量如何能使多个程序更好地并发执行，同时又尽量减少系统的开销，已成为近年来设计操作系统时减少系统的开销，已成为近年来设计操作系统时所追求的重要目标。所追求的重要目标。v能否能否将进程的两个基本属性分开将进程的两个基本属性分开，由操作系统分，由操作系统分别进行处理。即把处理机调度和其他资源的分配别进行处理。即把处理机调度和其他资源的分配针对不同的活动实体进行，以使之轻装运行；而针对不同的活动实体进行，以使之轻装运行；而对拥有资源的基本单位，又不频繁地对之进行切对拥有资源的基本单位，又不频繁地对之进行切换。换。v在这种思想的指导下，产生了在这种思想的指导下，产生了线程线程的概念。的概念。v线程是进程中的一个实体，是被系统独立调度和线程是进程中的一个实体，是被系统独立调度和分配的基本单位。分配的基本单位。8进程进程线程线程1线程线程2线程线程3进程进程1 分配处理机分配处理机资源分配资源分配线程示意图线程示意图9线程与进程的比较线程与进程的比较v下面将从四个方面比较线程和进程：下面将从四个方面比较线程和进程：调度调度并发性并发性拥有资源拥有资源系统开销系统开销10（1）调度）调度v在引入线程的操作系统中：在引入线程的操作系统中：线程是调度和分配的基本单位线程是调度和分配的基本单位进程是资源拥有的基本单位进程是资源拥有的基本单位v把传统进程的两个属性分开，线程便能轻装把传统进程的两个属性分开，线程便能轻装运行，从而可显著地提高系统的并发程度。运行，从而可显著地提高系统的并发程度。v在同一进程中，线程的切换不会引起进程的在同一进程中，线程的切换不会引起进程的切换；在由一个进程中的线程切换到另一个切换；在由一个进程中的线程切换到另一个进程中的线程时，才会引起进程的切换。进程中的线程时，才会引起进程的切换。11（2）并发性）并发性v在引入线程的操作系统中，不仅进程之间可在引入线程的操作系统中，不仅进程之间可以并发执行，而且在以并发执行，而且在一个进程中的多个线程一个进程中的多个线程之间亦可并发执行之间亦可并发执行，因而使操作系统具有更，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。和提高系统吞吐量。12（3）拥有资源）拥有资源v不论是传统的操作系统，还是设有线程的操不论是传统的操作系统，还是设有线程的操作系统，作系统，进程都是拥有资源的一个独立单位进程都是拥有资源的一个独立单位，它可以拥有自己的资源。它可以拥有自己的资源。v一般地说，一般地说，线程自己不拥有系统资源线程自己不拥有系统资源（只有（只有一些必不可少的资源），但它可以访问其隶一些必不可少的资源），但它可以访问其隶属进程的资源。属进程的资源。13（4）系统开销）系统开销v由于在创建或撤消进程时，系统都要为之分由于在创建或撤消进程时，系统都要为之分配或回收资源，因此，操作系统所付出的开配或回收资源，因此，操作系统所付出的开销将显著地大于在创建或撤消线程时的开销。销将显著地大于在创建或撤消线程时的开销。v进程切换的开销也远大于线程切换的开销。进程切换的开销也远大于线程切换的开销。14(a)Three processes each with one thread.Each thread operates in a different address space.The Classical Thread Model(b)One process with three threads.All three threads share the same address space.15The Classical Thread Modelsome items shared by all threads in a processsome items private to each thread16Thread statevLike a traditional process,a thread can be in any one of several states:running,blocked,ready,or terminated.vThe transitions between thread states are the same as the transitions between process states.17Thread creation and terminationvWhen multithreading is present,processes normally start with a single thread present.This thread has the ability to create new threads by calling a library procedure,for example,thread_create.vWhen a thread has finished its work,it can exit by calling a library procedure,say,thread_exit.18vAnother common thread call is thread_yield,which allows a thread to voluntarily give up the CPU to let another thread run.vWhy do we need this call?192.4.3 Implementing threads in user spacevThere are two main ways to implement a threads package:In user space:to put the threads package entirely in user space.The kernel knows nothing about them.In the kernel20A user-level threads package.A threads package managed by the kernel.21Advantages of user-level threads packagevA user-level threads package can be implemented on an OS that does not support threads.vThey allow each process to have its own customized scheduling algorithm.22The problems of user-level threads packagevIf a thread is blocked,the kernel,not even knowing about the existence of threads,naturally blocks the entire process until the disk I/O is complete,even though other threads might be runnable.vIf a thread starts running,no other thread in that process will ever run unless the first thread voluntarily gives up the CPU.232.4.4 Implementing threads in the kernelvThe kernel has a thread table that keeps track of all the threads in the system.When a thread wants to create a new thread or destroy an existing thread,it makes a kernel call.vAll calls that might block a thread are implemented as system calls,at considerably greater cost than a call to a run-time system procedure.vWhen a thread blocks,the kernel can run either another thread from the same process or a thread from a different process.242.5 Scheduling When a computer is multiprogrammed,it frequently has multiple processes or threads competing for the CPU at the same time.If only one CPU is available,a choice has to be made which process to run next.The part of the OS that makes the choice is called the scheduler,and the algorithm it uses is called the scheduling algorithm.252.5.1 Introduction to scheduling1.Process behaviorNearly all processes alternate bursts of computing with I/O requests.Figure 2-38261.Process behaviorvIn Fig 2-38(a),these processes spend most of their time computing,which are called compute-bound(计算密集型计算密集型).vIn Fig 2-38(b),these processes spend most of their time waiting for I/O,which are called I/O-bound(I/O密集型密集型).vAs CPU get faster,processes tend to get more I/O-bound.272.When to scheduleWhen a new process is created,a decision needs to be made whether to run the parent process or the child process.A scheduling decision must be made when a process exits.When a process blocks on I/O,on a semaphore,or for some other reason,another process has to be selected to run.When an I/O interrupt occurs,a scheduling decision may be made.28vA nonpreemptive scheduling algorithm(非抢占式调度算法非抢占式调度算法)picks a process to run and then just lets it run until it blocks or until it voluntarily releases the CPU.vA preemptive scheduling algorithm picks a process and lets it run for a maximum of some fixed time.293.Categories of scheduling algorithmsvIn different environments different scheduling algorithms are needed.vThree environments:BatchNonpreemptive algorithms,or preemptive algorithms with long time periods for each process,are often acceptable.InteractiveIn an environment with interactive users,preemption is essential to keep one process from hogging the CPU and denying service to the others.Real timeIn systems with real-time constraints,preemption is sometimes not needed.304.Scheduling algorithm goalsvAll systemsfairness giving each process a fair share of the CPUPolicy enforcement seeing that stated policy is carried outBalance keeping all parts of the system busyvBatch systemsThroughput(吞吐量吞吐量)maximize jobs per hourTurnaround time(周转时间周转时间)minimize time between submission and terminationCPU utilization keep the CPU busy all the time31Scheduling algorithm goalsvInteractive systemsResponse time respond to requests quicklyProportionality(均衡性均衡性)meet users expectationsvReal-time systemsMeeting deadlines avoid losing dataPredictability avoid quality degradation in multimedia systems32Some basic conceptsvThroughput is the number of jobs per hour that the system completes.vTurnaround time is the statistically average time from the moment that a batch job is submitted until the moment it is completed.vResponse time is the time between issuing a command and getting the result.332.5.2 Scheduling in batch systemsvFirst-come first-served(先来先服务先来先服务,FCFS)vShortest job first(最短作业优先最短作业优先)vShortest remaining time next(最短剩余最短剩余时间优先时间优先)341.FCFSvWhen the first job enters the system from the outside,it is started immediately and allowed to run as long as it wants to.It is not interrupted because it has run too long.vAs other jobs come in,they are put onto the end of the queue.vWhen the running process blocks,the first process on the queue is run next.vWhen a blocked process becomes ready,it is put on the end of the queue.35 An example of FCFS作业作业到达到达时间时间服务服务时间时间开始开始时间时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间A010111B110011011001C21101102100100D32001023022991.495平均平均125 25.9时间单位时间单位:分钟分钟36FCFS的特点的特点v易理解，便于在程序中应用。易理解，便于在程序中应用。v有利于长作业，不利于短作业。有利于长作业，不利于短作业。v有利于处理机繁忙的作业，不利于有利于处理机繁忙的作业，不利于I/O繁忙繁忙的作业。的作业。372.Shortest job first(SJF)vHere are four jobs A,B,C,D with run times of 8,4,4,4 minutes,respectively.vBy running in the order shown in(a),the turnaround times for A,B,C,D are 8,12,16,20 minutes,respectively.And the average is 14 minutes.vBy running these jobs using SJF,as shown in(b),the turnaround times are now 4,8,12,20 minutes for an average of 11 minutes.38SJFvConsider the case of four jobs,with run times of a,b,c,d,respectively.The first job finishes at time a,the second finishes at time a+b,and so on.vThe mean turnaround time is(4a+3b+2c+d)/4.vIt is clear that a contributes more to the average than the other times,so it should be the shortest job.39An example of SJF作作业业到达到达时间时间服务服务时间时间开始开始时间时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间A04B13C25D32E44平均平均40An example of SJF作作业业到达到达时间时间服务服务时间时间开始开始时间时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间A040441B136982.67C251318163.2D324631.5E4491392.25平均平均82.1413.Shortest Remaining Time NextWith this algorithm,the scheduler always chooses the process whose remaining run time is the shortest.42An example of SRTN作作业业到达到达时间时间服务服务时间时间开始开始时间时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间A02B04C31D31E31平均平均432.5.3 Scheduling in interactive systemsvRound-Robin Scheduling(轮转调度轮转调度)vPriority Scheduling(优先级调度优先级调度)vMultiple queue(多级队列多级队列)vShortest Process Next(最短进程优先最短进程优先)441.Round-Robin Scheduling vEach process is assigned a time interval,called its quantum(时间片时间片),during which it is allowed to run.vIf the process is still running at the end of the quantum,the CPU is preempted and given to another process.vIf the process has blocked or finished before the quantum has elapsed,the CPU switching is done when the process blocks.45How to set the length of the quantum?vP155vSetting the quantum too short causes too many process switches and lowers the CPU efficiency.vSetting the quantum too long may cause poor response to short interactive requests.46轮转调度算法举例轮转调度算法举例v设时间片设时间片q=4作业作业到达到达时间时间服务服务时间时间开始开始时间时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间A03B26C44D65E82平均平均47轮转调度算法举例轮转调度算法举例(续续)v设时间片设时间片q=4作业作业到达到达时间时间服务服务时间时间开始开始时间时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间A030331B26317152.5C4471171.75D651120142.8E821719115.5平均平均102.7148轮转调度算法举例轮转调度算法举例(续续)时刻时刻就绪队列中的进程就绪队列中的进程0无无(A到达后立即投入运行到达后立即投入运行)2B (此时此时A正在运行）正在运行）4C (B从时刻从时刻3 开始运行开始运行)6CD (此时此时B仍在运行仍在运行)7DB（此时（此时B的时间片已用完，把它重新放到的时间片已用完，把它重新放到就绪队列的尾部，并将队首进程就绪队列的尾部，并将队首进程C投入运行投入运行)8DBE(此时此时C仍在运行，新到达的进程仍在运行，新到达的进程E挂挂在队尾在队尾)vq=4时，各个，各个时刻就刻就绪队列中的列中的进程如下：程如下：492.Priority Scheduling vThe basic idea of this algorithm:each process is assigned a priority,and the runnable process with the highest priority is allowed to run.50优先权调度法的分类优先权调度法的分类v抢占式优先级调度法抢占式优先级调度法：任何时刻都严格按照：任何时刻都严格按照“高优先级进程在处理机上运行高优先级进程在处理机上运行”的原则进的原则进行进程的调度。行进程的调度。v非抢占式优先级调度法非抢占式优先级调度法：当系统中出现了比：当系统中出现了比正在运行的进程优先权更高的进程时，不会正在运行的进程优先权更高的进程时，不会剥夺正在运行的进程占有的处理机，该进程剥夺正在运行的进程占有的处理机，该进程会一直运行下去，直到完成或被阻塞，才让会一直运行下去，直到完成或被阻塞，才让另一优先权更高的进程运行。另一优先权更高的进程运行。51Priority SchedulingvHow to prevent high-priority process from running indefinitely?Each process may be assigned a maximum time quantum that is allowed to run.When this quantum is used up,the next highest priority process is given a chance to run.vPriorities can be assigned to processes statically or dynamically.52Priority SchedulingvIt is convenient to group processes into priority classes and use priority scheduling among the classes but round-robin scheduling within each class.533.Multiple queuesvBasic idea:Set up priority classes.Processes in the highest class were run for 1 quantum.Processes in the next-highest class were run for 2 quanta.Processes in the next class were run for 4 quanta,and so on.Whenever a process used up all the quanta allocated to it,it was moved down one class.54Example vConsider a process that needed to compute continuously for 100 quanta.vIt would initially be giver 1 quantum,then swapped out.Next time it would get 2 quanta before being swapped out.On succeeding runs it would get 4,8,16,32,and 64 quanta,although it would have used only 37of the final 64 quanta to complete its work.vOnly 7 swaps would be needed instead of 100 with a pure round-robin algorithm.55多级反馈队列调度算法多级反馈队列调度算法的性能的性能v该算法具有较好的性能，能较好地满足各种类型用该算法具有较好的性能，能较好地满足各种类型用户的需要：户的需要：终端型作业用户终端型作业用户。他们提交的大多属于交互型作业，通。他们提交的大多属于交互型作业，通常较小。系统只要能使这些作业在第一队列所规定的时常较小。系统只要能使这些作业在第一队列所规定的时间片内完成，便可使他们感到满意。间片内完成，便可使他们感到满意。短批处理作业用户短批处理作业用户。如果能在第一队列中执行一个时间。如果能在第一队列中执行一个时间片即可完成，便可获得与终端型作业一样的响应时间；片即可完成，便可获得与终端型作业一样的响应时间；对于稍长的作业，通常也可在第二和第三队列中执行完对于稍长的作业，通常也可在第二和第三队列中执行完成，其周转时间仍然较短。成，其周转时间仍然较短。长批处理作业用户长批处理作业用户。对于长作业，它将依次在第。对于长作业，它将依次在第1,2,n个队列中运行，而且运行的时间片逐渐增大，用户个队列中运行，而且运行的时间片逐渐增大，用户不必担心其作业长期得不到处理。不必担心其作业长期得不到处理。564.Shortest process nextvBecause SJF(Shortest Job First)always produces the minimum average response time for batch systems,it would be nice if it could be used for interactive processes as well.vIf we regard the execution of each command as a separate“job”,then we could minimize overall response time by running the shortest one first.572.5.4 Thread schedulingPossible scheduling of user-level threads with a 50-msec process quantum and threads run 5 msec per CPU burstPossible scheduling of kernel-level threads with the same characteristics as(a)58Thread schedulingvA major difference between user-level threads and kernel-level threads is the performance.vUser-level threads:A thread switch takes a handful of machine instructionsvKernel-level threads:A thread switch requires a full context switchHaving a thread block on I/O doesnt suspend the entire process as it does with user-level threads.59HomeworkP17017311,12,13,14,31,36,37,3860