《现代操作系统Chapter2P.ppt》由会员分享，可在线阅读，更多相关《现代操作系统Chapter2P.ppt（60页珍藏版）》请在三一办公上搜索。
1、Chapter 2 Processes and threads,Contents,2.1 Processes2.2 Interprocess communication(IPC)2.3 Classical IPC problems2.4 Threads2.5 Scheduling,2.4 Threads,2.4.1 Threads usage2.4.2 The classical thread model2.4.3 Implementing threads in user space2.4.4 Implementing threads in the kernel,2.4.1 Threads u
2、sage,Why 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
3、 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 ap
4、plication.,An example of multithread,A word processor with 3 threads,2.4.2 The classical thread model,The 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
5、 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、时空开销。也正因为如此，在系统中所设置的进程数目不宜过多，进程切换的频率也不宜太高，但这也就限制了并发程度的进一步提高。,线程的引入,如何能使多个程序更好地并发执行，同时又尽量减少系统的开销，已成为近年来设计操作系统时所追求的重要目标。能否将进程的两个基本属性分开，由操作系统分别进行处理。即把处理机调度和其他资源的分配针对不同的活动实体进行，以使之轻装运行；而对拥有资源的基本单位，又不频繁地对之进行切换。在这种思想的指导下，产生了线程的概念。线程是进程中的一个实体，是被系统独立调度和分配的基本单位。,分配处理机,资源分配,线程示意图,线程与进程的比较,下面将从四个方面比较线程和进程：调度并发性
7、拥有资源系统开销,（1）调度,在引入线程的操作系统中：线程是调度和分配的基本单位进程是资源拥有的基本单位把传统进程的两个属性分开，线程便能轻装运行，从而可显著地提高系统的并发程度。在同一进程中，线程的切换不会引起进程的切换；在由一个进程中的线程切换到另一个进程中的线程时，才会引起进程的切换。,（2）并发性,在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。,（3）拥有资源,不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。一般
8、地说，线程自己不拥有系统资源（只有一些必不可少的资源），但它可以访问其隶属进程的资源。,（4）系统开销,由于在创建或撤消进程时，系统都要为之分配或回收资源，因此，操作系统所付出的开销将显著地大于在创建或撤消线程时的开销。进程切换的开销也远大于线程切换的开销。,15,(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 threa
9、ds share the same address space.,16,The Classical Thread Model,some items shared by all threads in a process,some items private to each thread,Thread state,Like a traditional process,a thread can be in any one of several states:running,blocked,ready,or terminated.The transitions between thread state
10、s are the same as the transitions between process states.,Thread creation and termination,When 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.When a thread has
11、finished its work,it can exit by calling a library procedure,say,thread_exit.,Another common thread call is thread_yield,which allows a thread to voluntarily give up the CPU to let another thread run.Why do we need this call?,2.4.3 Implementing threads in user space,There are two main ways to implem
12、ent a threads package:In user space:to put the threads package entirely in user space.The kernel knows nothing about them.In the kernel,21,A user-level threads package.,A threads package managed by the kernel.,Advantages of user-level threads package,A user-level threads package can be implemented o
13、n an OS that does not support threads.They allow each process to have its own customized scheduling algorithm.,The problems of user-level threads package,If 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 comple
14、te,even though other threads might be runnable.If a thread starts running,no other thread in that process will ever run unless the first thread voluntarily gives up the CPU.,2.4.4 Implementing threads in the kernel,The kernel has a thread table that keeps track of all the threads in the system.When
15、a thread wants to create a new thread or destroy an existing thread,it makes a kernel call.All calls that might block a thread are implemented as system calls,at considerably greater cost than a call to a run-time system procedure.When a thread blocks,the kernel can run either another thread from th
16、e same process or a thread from a different process.,2.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 t
17、he choice is called the scheduler,and the algorithm it uses is called the scheduling algorithm.,2.5.1 Introduction to scheduling,1.Process behaviorNearly all processes alternate bursts of computing with I/O requests.,Figure 2-38,1.Process behavior,In Fig 2-38(a),these processes spend most of their t
18、ime computing,which are called compute-bound(计算密集型).In Fig 2-38(b),these processes spend most of their time waiting for I/O,which are called I/O-bound(I/O密集型).As CPU get faster,processes tend to get more I/O-bound.,2.When to schedule,When a new process is created,a decision needs to be made whether
19、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.,A nonpreemptive schedu
20、ling algorithm(非抢占式调度算法)picks a process to run and then just lets it run until it blocks or until it voluntarily releases the CPU.A preemptive scheduling algorithm picks a process and lets it run for a maximum of some fixed time.,3.Categories of scheduling algorithms,In different environments differ
21、ent scheduling algorithms are needed.Three 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
22、 service to the others.Real timeIn systems with real-time constraints,preemption is sometimes not needed.,4.Scheduling algorithm goals,All systemsfairness giving each process a fair share of the CPUPolicy enforcement seeing that stated policy is carried outBalance keeping all parts of the system bus
23、yBatch systemsThroughput(吞吐量)maximize jobs per hourTurnaround time(周转时间)minimize time between submission and terminationCPU utilization keep the CPU busy all the time,Scheduling algorithm goals,Interactive systemsResponse time respond to requests quicklyProportionality(均衡性)meet users expectationsRea
24、l-time systemsMeeting deadlines avoid losing dataPredictability avoid quality degradation in multimedia systems,Some basic concepts,Throughput is the number of jobs per hour that the system completes.Turnaround time is the statistically average time from the moment that a batch job is submitted unti
25、l the moment it is completed.Response time is the time between issuing a command and getting the result.,2.5.2 Scheduling in batch systems,First-come first-served(先来先服务,FCFS)Shortest job first(最短作业优先)Shortest remaining time next(最短剩余时间优先),1.FCFS,When the first job enters the system from the outside,
26、it is started immediately and allowed to run as long as it wants to.It is not interrupted because it has run too long.As other jobs come in,they are put onto the end of the queue.When the running process blocks,the first process on the queue is run next.When a blocked process becomes ready,it is put
27、 on the end of the queue.,36,An example of FCFS,时间单位:分钟,FCFS的特点,易理解，便于在程序中应用。有利于长作业，不利于短作业。有利于处理机繁忙的作业，不利于I/O繁忙的作业。,2.Shortest job first(SJF),Here are four jobs A,B,C,D with run times of 8,4,4,4 minutes,respectively.,By running in the order shown in(a),the turnaround times for A,B,C,D are 8,12,16,20
28、 minutes,respectively.And the average is 14 minutes.By 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.,SJF,Consider the case of four jobs,with run times of a,b,c,d,respectively.The first job finishes at time a,the second finish
29、es at time a+b,and so on.The mean turnaround time is(4a+3b+2c+d)/4.It is clear that a contributes more to the average than the other times,so it should be the shortest job.,An example of SJF,An example of SJF,3.Shortest Remaining Time Next,With this algorithm,the scheduler always chooses the process
30、 whose remaining run time is the shortest.,An example of SRTN,2.5.3 Scheduling in interactive systems,Round-Robin Scheduling(轮转调度)Priority Scheduling(优先级调度)Multiple queue(多级队列)Shortest Process Next(最短进程优先),1.Round-Robin Scheduling,Each process is assigned a time interval,called its quantum(时间片),duri
31、ng which it is allowed to run.If the process is still running at the end of the quantum,the CPU is preempted and given to another process.If the process has blocked or finished before the quantum has elapsed,the CPU switching is done when the process blocks.,How to set the length of the quantum?,P15
32、5Setting the quantum too short causes too many process switches and lowers the CPU efficiency.Setting the quantum too long may cause poor response to short interactive requests.,轮转调度算法举例,设时间片q=4,轮转调度算法举例(续),设时间片q=4,轮转调度算法举例(续),q=4时，各个时刻就绪队列中的进程如下：,2.Priority Scheduling,The basic idea of this algorit
33、hm:each process is assigned a priority,and the runnable process with the highest priority is allowed to run.,优先权调度法的分类,抢占式优先级调度法：任何时刻都严格按照“高优先级进程在处理机上运行”的原则进行进程的调度。非抢占式优先级调度法：当系统中出现了比正在运行的进程优先权更高的进程时，不会剥夺正在运行的进程占有的处理机，该进程会一直运行下去，直到完成或被阻塞，才让另一优先权更高的进程运行。,Priority Scheduling,How to prevent high-priori
34、ty 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.Priorities can be assigned to processes statically or dynamically.,Priority Scheduling,It is conveni
35、ent to group processes into priority classes and use priority scheduling among the classes but round-robin scheduling within each class.,3.Multiple queues,Basic 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 quant
36、a.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.,Example,Consider a process that needed to compute continuously for 100 quanta.It would initially be giver 1 quantum,then swapped out.Next time it would
37、 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.Only 7 swaps would be needed instead of 100 with a pure round-robin algorithm.,多级反馈队列调度算法的性能,该算法具有较好的性能，能较好地满足各种类型用户的需要：终端型作业用
38、户。他们提交的大多属于交互型作业，通常较小。系统只要能使这些作业在第一队列所规定的时间片内完成，便可使他们感到满意。短批处理作业用户。如果能在第一队列中执行一个时间片即可完成，便可获得与终端型作业一样的响应时间；对于稍长的作业，通常也可在第二和第三队列中执行完成，其周转时间仍然较短。长批处理作业用户。对于长作业，它将依次在第1,2,n个队列中运行，而且运行的时间片逐渐增大，用户不必担心其作业长期得不到处理。,4.Shortest process next,Because SJF(Shortest Job First)always produces the minimum average res
39、ponse time for batch systems,it would be nice if it could be used for interactive processes as well.If we regard the execution of each command as a separate“job”,then we could minimize overall response time by running the shortest one first.,2.5.4 Thread scheduling,Possible scheduling of user-level
40、threads with a 50-msec process quantum and threads run 5 msec per CPU burst,Possible scheduling of kernel-level threads with the same characteristics as(a),Thread scheduling,A major difference between user-level threads and kernel-level threads is the performance.User-level threads:A thread switch takes a handful of machine instructionsKernel-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.,Homework,P17017311,12,13,14,31,36,37,38,
