Operating System Process Management - 1 Monday, August 11, 2008

Objectives Grasp the basic concepts of process, its states and transitions between the states. Understand the meaning of process mutex and process synchronization. Know the communication mechanism of processes. Understand the concepts of threads. 8/11/2008 6:14 PM bettynj@gmail.com

Roadmap Process Concepts Process Scheduling Interprocess Communication Mutex and Synchronization Classical IPC Problems Threads 早期的计算机系统只允许一次执行一个程序。这种程序对系统有完全的控制，能访问所有系统资源。现代计算机系统允许将多个程序调入内存并发执行。这一进步要求对各种程序提供更严格的控制和更好的划分。这些需求产生了进程的概念。 顺序执行的特征： 顺序性：按照程序结构所指定的次序（可能有分支或循环） 封闭性：独占全部资源，计算机的状态只由该程序的控制逻辑所决定 可再现性：初始条件相同则结果相同。如：可通过空指令控制时间关系。 并发执行的特点： 间断性：程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间，形成了相互制约的关系。这种相互制约导致并发程序具有“执行——暂停——执行”，这种间断性的活动规律。 失去封闭性：程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。 不可再现性：由于失去了封闭性，导致失去可再现性。 进程可以看做是正在执行的程序。进程需要一定的资源（如CPU时间、内存、文件和I/O设备）来完成其任务。这些资源在创建进程或进程执行时分配。 进程在大多数系统中是工作单元。这样的系统由一组进程组成：操作系统进程执行系统代码，用户进程执行用户代码。所有这些进程可以并发执行。 目前大多数现代操作系统支持多线程进程。 8/11/2008 6:14 PM bettynj@gmail.com

What is a Process An operating system executes a variety of programs: Batch system – jobs Time-shared systems – user programs or tasks Process is a program in execution, which helps to describe parallel easily. A process includes program counter, stack and data section CPU的活动的称呼： 批处理系统中执行作业； 分时系统使用用户程序或任务。 所有活动在许多方面都有相似之处，所以统称为进程。 进程这个技术术语是1966年由美国麻省理工学院的MULTICS系统设计人员J.H.Saltzer首先提出的。 进程有几种典型的定义： 进程是程序在处理机上的执行互动 进程是一个在处理机上可调度的实体 进程是一个计算过程，它可以与别的计算并发执行 进程是由伪处理机执行的一个程序 进程是程序的一次执行 进程是多道程序系统中控制程序管理下的基本程序单元 进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动，它是系统进行资源分配和调度的一个独立单位（1978年庐山会议） 进程是执行中的程序，它包括： 程序计数器，指示下一个要执行的指令和相关资源的集合。 进程堆栈段：包含临时数据，如方法参数、返回地址和局部变量 数据段：包含全局变量 8/11/2008 6:14 PM bettynj@gmail.com

The Process Model (a) Multiprogramming of four programs (b) Conceptual model of 4 independent, sequential processes (c) Only one program active at any instant 8/11/2008 6:14 PM bettynj@gmail.com

Process vs. Program process cpu Read the cookbook cookbook program material input Prepare the material Open the door Cooking switch 8/11/2008 6:14 PM bettynj@gmail.com

Process vs. Program A program is a passive entity, such as the contents of a file stored on disk A process is an active entity, with a program counter specifying the next instruction to execute and a set of associated resources Two or more processes may be associated with the same program, they are nevertheless considered two separate execution sequences 程序是完成所要求的功能时所应采取的顺序步骤，是执行指令的有序集合。 进程具有两个基本特性： 动态性：进程的实质是程序的一次运行活动，是一个动态概念。进程是一个有生命的过程，它有从动态地产生、动态地执行到动态地消亡的生命周期。 并发性：系统中可以同时存在多个进程，各个进程按照不可预知的速度各自独立地向前推进。 区别： 程序是一个静止的概念，作为一种资源可以永久存放在磁盘上。进程是程序执行的动态活动过程，随程序执行而诞生，随程序执行结束而消亡。 静止状态的程序和数据是相互独立的信息集合。进程中的程序和数据是一个不可分割的实体。 一个程序可以对应多个进程 8/11/2008 6:14 PM bettynj@gmail.com

Advantages Resource sharing Computation speedup logical (files) and physical(hardware). Computation speedup taking advantage of multiprogramming Modularity for protection. 8/11/2008 6:14 PM bettynj@gmail.com

Process Control Block (PCB) Information associated with each process: Process state Program counter CPU registers CPU scheduling information Memory-management information Accounting information I/O status information 进程实体由程序、数据和进程控制块3部分组成。 计算机系统内部，各个进程的状态和占用资源情况以及进程之间的关系是不断变化的，为了便于对进程进行管理和控制，系统必须记录下进程的这些信息。进程控制块就是记录进程有关信息的一个数据结构。 每个进程在操作系统内用进程控制块（PCB-process control block）来表示。一个PCB包含与特定进程相关的许多信息： 进程状态：可包括新的、就绪、运行、等待、停止等 程序计数器：计数器表示这个进程要执行的下一个指令的地址 CPU寄存器：包括累加器、索引寄存器、堆栈指针、通用寄存器和其他条件码信息寄存器，这些状态信息在出现中断时也需要被保存，以便进程以后能正确地继续执行。保存现场。 CPU调度信息：这些信息包括进程优先级、调度队列的指针和任何其他调度参数 内存管理信息：包括基址寄存器和界限寄存器的值、页表或段表 计账信息：包括CPU时间、实际使用时间、时间界限、记账数量、作业或进程数量等 I/O状态信息：包括分配给该进程的I/O设备列表、打开文件的列表等 8/11/2008 6:14 PM bettynj@gmail.com

Process Creation Principal events that cause process creation System initialization Execution of a process creation system User request to create a new process Initiation of a batch job 8/11/2008 6:14 PM bettynj@gmail.com

Example UNIX examples fork system call creates new process exec system call used after a fork to replace the process’ memory space with a new program. 新进程的地址空间也有两种可能： 1.子进程是父进程的复制品 2.子进程装入另一个程序进来 8/11/2008 6:14 PM bettynj@gmail.com

Process Hierarchies Parent creates a child process, child processes can create its own process Forms a hierarchy UNIX calls this a "process group" Windows has no concept of process hierarchy all processes are created equal 8/11/2008 6:14 PM bettynj@gmail.com

Process Relationships Resource sharing Parent and children share all resources. Children share subset of parent’s resources. Parent and child share no resources. Execution Parent and children execute concurrently. Parent waits until children terminate. Address space Child duplicate of parent. Child has a program loaded into it. 进程在执行过程中，能通过系统调用创建多个新进程。创建进程称为父进程，而新进程称为该进程的子进程。每一个新进程可以再创建其他进程，从而形成了进程树。 通常，进程需要一定的资源（如CPU时间、内存、文件、I/O设备），以完成其任务。 子进程可以从操作系统直接获得资源，也可以从其父进程获得资源，为了防止创建过多的子进程造成系统超载，可以限制子进程只能使用父进程的资源。 在进程创建时，它还能从父进程那里得到所需的初始化数据（或输入）。 当进程创建新进程时，有两种执行可能： 1.父进程与子进程并发执行 2.父进程等待，直到某个或全部子进程执行完毕 新进程的地址空间也有两种可能： 1.子进程是父进程的复制品 2.子进程装入另一个程序进来 8/11/2008 6:14 PM bettynj@gmail.com

Process Relationships (cont.) Independent process cannot affect or be affected by the execution of another process. Cooperating process can affect or be affected by the execution of another process 独立进程：不能影响或被系统内其他进程影响的进程，不与其它任何进程共享数据。 协作进程：能影响或被系统内执行的其他进程所影响的进程，与其他进程共享数据。 提供协作的好处： 信息共享：提供环境以允许对多个用户同样感兴趣的资源并发访问 加快计算：将一个特定任务分成子任务，每个子任务可以与其他子任务并行执行。 模块化：可将系统功能划分成独立进程或线程。 方便：单个用户也可能同时执行许多任务。 8/11/2008 6:14 PM bettynj@gmail.com

Process Termination Conditions which terminate processes Normal exit (voluntary) Error exit (voluntary) Fatal error (involuntary) Killed by another process (involuntary) 8/11/2008 6:14 PM bettynj@gmail.com

Process Termination (cont.) Process executes last statement and asks the operating system to decide it (exit). Output data from child to parent (via wait). Process’ resources are deallocated by operating system. Parent may terminate execution of children processes (abort). Child has exceeded allocated resources. Task assigned to child is no longer required. Parent is exiting, cascading termination. 当进程完成执行最后的语句并使用系统调用exit请求操作系统删除它时，进程终止。 这时，进程可以返回数据（输出）到其父进程（通过系统调用wait）。 所有进程资源，包括物理和虚拟内存、打印文件和I/O缓冲，会被操作系统所释放。 进程通过适当的系统调用（如abort）能终止另一个进程。父进程终止其子进程的原因有很多： 子进程使用了超过它所分配到的一些资源，要求父进程有一个检查其子进程的状态的机制。 分配给子进程的任务已不再需要。 父进程退出，级联终止（cascading termination） 8/11/2008 6:14 PM bettynj@gmail.com

Roadmap Process Concepts Process Scheduling Interprocess Communication Mutex and Synchronization Classical IPC Problems Threads 8/11/2008 6:14 PM bettynj@gmail.com

Process State As a process executes, it changes state running: Instructions are being executed. waiting: The process is waiting for some event to occur. ready: The process is waiting to be assigned to a process. new: The process is being created. terminated: The process has finished execution. Basic state 进程在执行时会改变状态： 新的：进程正在被创建 运行：指令正在被执行 等待：进程等待一定事件的出现（如I/O完成或收到某个信号） 就绪：进程等待被分配给某个处理器，一旦得到处理机即可运行 终止：进程已完成执行 多道系统中同时存在多个进程，由于系统资源有限，不可能同时满足各个进程对资源的要求，这就形成了进程对资源的竞争。 当某种资源被一个进程占用时，其它进程若要求使用该资源就必须等待，等待就是进程的一种状态。 此外，当一个进程占用处理机执行其程序时，该进程所处的是一种执行状态。 当该进程在使用设备进行输出输入时，其它等待处理机的进程之一就要由等待状态转换成使用处理机的执行状态。 由此可见，系统中地进程总是处于不同的状态下，并且它们的状态在动态地转换着。 8/11/2008 6:14 PM bettynj@gmail.com

Diagram of Process State 状态转换的说明 新-就绪：新进程被允许后进入就绪队列 就绪-运行：当处理机空闲时，系统按照一定调度算法从就绪状态中选择一个使其占用处理机运行。 运行-就绪：分配给进程的时间片用完时，或出现一个更紧急的进程时 运行-等待：运行的进程需要等待某一事件发生后，才能继续往下运行 等待-就绪：处于等待的进程，如果其等待的事件已经发生，表示阻塞的原因已解除，则该进程从等待转为就绪 注意点： 等待进程在等待原因解除后，虽然再次具备了运行条件，但不能直接运行，而要先转换成就绪，等待调度 从运行态到就绪态的转换是被动的 从运行态到等待的转换是主动的 从等待到就绪的状态转换是由外部事件引起的 8/11/2008 6:14 PM bettynj@gmail.com

Scheduling Structure Sequential processes Process-structured OS handles interrupts, scheduling 8/11/2008 6:14 PM bettynj@gmail.com

Scheduling Components The act of Scheduling a process means changing the active PCB pointed to by the CPU. Also called a context switch. A context switch is essentially the same as a process switch it means that the memory, as seen by one process is changed to the memory seen by another process. 8/11/2008 6:14 PM bettynj@gmail.com

Context Switch The CPU switching from process P0 to process P1. 进程关联是由进程PCB来表示的。 当发生上下文切换时，内核会将旧进程的关联状态保存在其PCB中，然后装入经调度要执行的新进程的已保存的关联状态。 上下文切换时间是系统额外开销，切换时系统不能做什么有用的工作。 上下文切换速度因机器而不同，它依赖于内存速度、必须被复制的寄存器的数量、是否有特殊指令。 上下文切换时间与硬件支持密切相关。 8/11/2008 6:14 PM bettynj@gmail.com

Context Switch (cont.) When CPU switches to another process, the system must save the state of the old process and load the saved state for the new process. Context-switch time is overhead; the system does no useful work while switching. Time dependent on hardware support. 上下文切换的任务是：将CPU切换到另一个进程需要保存原来进程的状态并装入新进程的保存状态。 进程关联是由进程PCB来表示的。 当发生上下文切换时，内核会将旧进程的关联状态保存在其PCB中，然后装入经调度要执行的新进程的已保存的关联状态。 上下文切换时间是系统额外开销，切换时系统不能做什么有用的工作。 上下文切换速度因机器而不同，它依赖于内存速度、必须被复制的寄存器的数量、是否有特殊指令。 上下文切换时间与硬件支持密切相关。 8/11/2008 6:14 PM bettynj@gmail.com

Process Scheduling Queues Process is driven by events that are triggered by needs and availability, and they are organized as different queues: Job queues –all processes in the system. Ready queues –all processes residing in main memory, ready and waiting to execute. Device queues –processes waiting for an I/O device. Process migration between the various queues. 进程进入系统时，会被加到作业队列中。该队列包括系统中所有进程。 驻留在内存中就绪的等待运行的进程保存在就绪队列上。 等待特定I/O设备的进程列表称为设备队列。每个设备都有自己的设备队列。 进程在其生命周期中会在各种调度队列之间迁移。 PCB的物理组织结构常用的有3种：线性表结构、索引表结构和链接表结构 线性表结构：所有进程的PCB全部放在主存中大小固定的一个连续区域中，形成一个线性表。每次使用一个PCB都需要扫描整个PCB表，适用于进程数较少的系统 索引表结构：对线性表做改进，给线性表中状态相同的进程PCB建立一个索引表。 链接表结构：进程总数在不断变化，线性表和索引表不利于这种变化。因此，有些操作系统适用链表数据结构把处于各种不同状态的进程链接在一起。这些由不同状态进程的PCB链接成的链表又称为状态队列。 8/11/2008 6:14 PM bettynj@gmail.com

Ready Queue and I/O Device Queues 8/11/2008 6:14 PM bettynj@gmail.com

Representation of Process Scheduling 进程调度的常用表示方法是队列图。 每个长方形框表示一个队列。有两种队列：就绪队列和一组设备队列。 圆形表示为队列服务的资源，箭头表示系统内进程的流向。 新进程首先处于就绪队列，等待被CPU选中执行（或分派）。执行过程中有几种事件可能发生： 进程可能发出一个I/O请求，并被放到I/O队列中。 进程可能创建一个新的子进程，并等待其结束。 进程可能由于中断而被强制移出CPU，并被放回到就绪队列。 8/11/2008 6:14 PM bettynj@gmail.com

Schedulers Long-term scheduler (or job scheduler) selects which processes should be brought into the ready queue. run seldom ( when job comes into memory ) controls degree of multiprogramming tries to balance arrival and departure rate through an appropriate job mix. Short-term scheduler (or CPU scheduler) selects which process should be executed next and allocates CPU. 进程在其生命周期中会在各种调度队列之间迁移。为实现调度，OS必须某种方式从这些队列中选择进程，该选择由调度程序完成。 批处理系统通常提交很多进程，它们保存在大容量存储设备（通常为磁盘）上的缓冲池中，以便后来执行。 长期调度程序或作业调度程序：从池中选择进程，并将它们装入内存以执行。 短期调度程序或CPU调度程序：从就绪可执行的进程中选择进程，并为其中之一分配CPU。 8/11/2008 6:14 PM bettynj@gmail.com

Schedulers (cont.) Short-term scheduler – three functions Code to remove a process from the processor at the end of its run. a) Process may go to ready queue or to a wait state. Code to put a process on the ready queue . a) Process must be ready to run. b) Process placed on queue based on priority. Code to take a process off the ready queue and run that process (also called dispatcher). a) Always takes the first process on the queue (no intelligence required) b) Places the process on the processor. 8/11/2008 6:14 PM bettynj@gmail.com

Schedulers (cont.) Medium-term scheduler Interrupt Handling Mixture of CPU and memory resource management. Swap out/in jobs to improve mix and to get memory. Controls change of priority. Interrupt Handling In addition to doing device work, it also readies processes, moving them, for instance, from waiting to ready 8/11/2008 6:14 PM bettynj@gmail.com

Schedulers (Cont.) Short Term Scheduler Short Term Scheduler Medium Term Scheduler Short Term Scheduler 两种调度的区别主要在频率上：短期调度频率高，长期调度频率低，且长期调度控制多道程序设计的程度，即内存中的进程数量。 Long Term Scheduler Interrupt Handler 8/11/2008 6:14 PM bettynj@gmail.com

Schedulers (Cont.) Processes can be described as either: I/O-bound process – spends more time doing I/O than computations, many short CPU bursts. CPU-bound process – spends more time doing computations; few very long CPU bursts. 进程可分为：I/O为主或CPU为主 I/O为主：在执行I/O方面比执行计算要花费更多的时间 CPU为主：很少产生I/O请求，更多时间用在计算上 8/11/2008 6:14 PM bettynj@gmail.com

Keystone Concept of process Process states Process control block Process scheduling 8/11/2008 6:14 PM bettynj@gmail.com

Homework Process in Linux OS Suppose that you were to design an advanced computer architecture that did process switching in hardware, instead of having normal interrupts handlers. What information would the CPU need? Describe how the hardware process switching might work. 8/11/2008 6:14 PM bettynj@gmail.com

Operating System Basic of Process Monday, August 11, 2008