链接方式
执行指针 就绪队列指针
PCB1 PCB2 PCB3 PCB4 PCB5 PCB6 PCB7 PCB8 PCB9 4 3 0 8
阻塞队列指针 空闲队列指针
7 9 0 0
索引方式
执行指针
PCB1 PCB2
PCB3
就绪表指针
PCB4 PCB5 PCB6
阻塞表指针
PCB7
进程调度队列
• 作业队列——系统中所有进程集合 • 就绪队列——驻留主存的所有就绪态进 程集合 • 设备队列——等待I/O设备的进程集合 • 进程在各种队列中迁移
程序段 数据段
操作对象及工作区
1. 进程控制块 (PCB, process control block) 的作用
• PCB是OS中最重要的记录型结构，记录用于描 述进程执行情况及控制进程运行的全部信 息。 。 • PCB是进程存在的唯一标志，是每个进程在OS 中的登记表项，OS据此对并发进程进行控制和 管理。 • PCB常驻于由OS维护的内存核心区，不能由应 用程序自身的代码来直接访问，而要通过系统 调用间接访问。 • OS专门开辟PCB区将所有的PCB组织成若干个链 表或队列。
进程图 A
B D C
E
F
G
H
引起创建进程的事件 （1） 用户登录。 （2） 作业调度。 由系统内核创建 （3） 提供服务。 （4） 应用请求。 由自己创建
进程的创建
• 原语CREAT（）按下述步骤创建一个新 进程: （1） 申请空白PCB。 （2） 为新进程分配资源：为代码、数据、 用户栈分配空间。 （3） 初始化进程控制块：初始化标识信 息、处理机状态（PC、SP)、处理机控制 信息（进程状态、优先级）。 （4） 将新进程插入就绪队列 。
• 父进程创建子进程，子进程还可创建子进程，从 而形成进程树。 • 父子进程关系： – 资源继承共享 • 父子进程共享所有的资源 • 子进程共享父进程资源的子集 • 父进程和子进程之间不共享资源 – 执行关系： • 父进程和子进程并发执行 • 父进程等待子进程执行结束 – 地址空间 • 子进程是父进程的复制（克隆） • 子进程将自己代码装入其中。
1 2 3
• 顺序执行的特征： – 顺序性：按照程序结构所指定的次序 执行（可能有分支或循环） – 封闭性：独占全部资源，计算机的状 态只由于该程序的控制逻辑所决定， 结果不受外界因素的影响 – 可再现性：初始条件相同则结果相同。
2）程序的并发执行
• 引入并发执行的目的是为了提高资源利用率。 • 并发执行的特征（在不加入任何系统控制情况 下）： – 间断性：表现为“走走停停”，一个程序可 能走到中途停下来，失去原有的时序关系； – 失去封闭性：共享资源，受其他程序的控制 逻辑的影响。如：一个程序写到存储器中的 数据可能被另一个程序修改，失去原有的不 变特征。 – 失去可再现性：失去封闭性 －>失去可再现 性；外界环境在程序的两次执行期间发生变 化，失去原有的可重复特征。
• 2. 进程的特征 • （1）动态性：创建产生，调度执行，受制 于资源，撤销消亡。 –进程具有动态的地址空间（数量和内容）， 地址空间上包括：代码、数据、进程控制 块（PCB） • （2）并发性：多个进程同时存在于内存， 宏观上同时运行。 • （3）独立性：资源分配的单位。 –各进程的地址空间相互独立，除非采用进 程间通信手段
就绪队列和各种I/O队列
进程状态的转换
2.2
进程控制
• 进程管理中最基本功能是进程控制 • 进程控制任务： – 进程的创建、终止、进程状态的转变等 • 进程控制一般由OS内核的原语（primitive）来 实现。 – 原语：由若干条指令构成的“原子操作 (atomic operation)”过程，作为一个整 体而不可分割－－要么全都完成，要么全 都不做。 – 许多系统调用是原语。但并不是所有的系 统调用都是原语
• 并发执行的条件：达到封闭性和可再现 性（正确性的要求）。
2.1.2 进程的定义与特征
• 1. 进程的定义 – 一个具有一定独立功能的程序在一个 数据集合上的一次动态执行过程。 – 在未引入线程的系统中，进程是处理 机、存储器和外设等资源的分配和回 收的单位。 – 引入多进程，提高了对硬件资源的利 用率，但又带来额外的空间和时间开 销，增加了OS 的复杂性。
例：单处理机系统中，可并行的是 I 进程与进程 II 处理机与设备 III 处理机与通道 IV 设备与设备 答： II III IV
2.1.3 进程的状态
就绪状态：进程已获得除处理 机外的所需资源，等待分配处理 机资源；只要分配到CPU就可执 行。在某一时刻，可能有若干个 进程处于该状态
就绪
阻塞态：正在执行的进程由于发 生某事件，如申请系统服务或资 源、通信、I/O操作等，而暂时无 法继续执行时，放弃处理机而进 入的状态，又称等待状态。
操作系统需要挂起某些进程以便检查运行中的资源使用情况 或进行记账。
挂起引起的状态转换
静止状态 挂起状态 活动状态 非挂起状态
• 引入的新状态 –1) 就绪挂起（静止就绪）：进程在外存， 但只要进入内存，即可运行； –2) 阻塞挂起状态（静止阻塞）：进程在 外存并等待某事件的出现。
有挂起状态的进程状态图
• UNIX： – fork 系统调用：创建一个子（新）进程。 精确复制父进程 – exec系统调用： 在 fork 之后执行，用 新的代码替换原父进程的代码。
void main (int argc, char *argv[ ]) { int pid; pid = fork( ); if ( pid < 0) { fprint ( stderr, “fork failed”); exit (-1); } else if ( pid == 0) { execlp (“ /bin/ls”, “ls”, NULL); } else { wait ( NULL); printf (“ child complete”); exit (0); } }
某事件已发生
进程调度 时间片完
执行 阻塞 等待某事件发生 执行状态：占用处理机资源运行
；处于此状态的进程的数目小于 等于CPU的数目。
挂起状态
• 引入原因：
（1）终端用户请求
终端用户发现自己运行的程序有问题，希望暂停自己程序的 执行
（2）父进程请求
父进程希望挂起自己的某个子进程，以便考察和修改该子进 程
Байду номын сангаас
• （4）异步性：进程按各自独立的、不可 预知的速度向前推进。 • （5）结构化：进程实体由代码段，数据 段和进程控制块(PCB) 组成。 –进程控制块包含在核心区。内存核心 段通常存放OS核心部分，由各个进程 共享，包括各进程的PCB。 –程序文件中通常划分为代码段和数据 段
• 3. 进程与程序的区别 – 1) 进程是动态的，程序是静态的；程 序是有序代码的集合；进程是程序的 执行。 – 2) 进程是暂时的，程序是永久的。 – 3) 进程与程序的组成不同：进程的组 成包括程序、数据和进程控制块。 – 4) 进程与程序的对应关系：通过多次 执行，一个程序可对应多个进程；通 过调用关系，一个进程可包括多个程 序。
执行
挂起 调度 I/O请求
释放
活动 阻塞
活 动 就 绪
激活 挂起
挂起 激活
静止 就绪
释 放
静止 阻塞
创建状态和终止状态
静止 就绪
许 可
激活 进程调度
时间片完
挂起 挂起
运行态 进程完成 释放
创建
许可
活动 就绪
活动 阻塞
终止 挂起 激活
静止 阻塞
2.1.4
进程控制块
PCB
进程控制块
动态特征的集中反映 描述要完成的功能
2.2.1
进程的创建（Creation of process）
• 1.进程图（Process Graph） –树状结构，父子进程关系。 –子进程可以继承父进程所拥有的资源，如 打开文件、缓冲区等。当子进程被撤销应 将继承的资源归还给父进程。撤销父进程 也必须同时撤销所有的子进程。 –PCB中设臵了家族关系表项。
（3）负荷调节需要
高优先级的进程要执行，而内存不空，系统将低优先级进程 对换至外存。 提高处理机效率：就绪进程表为空时，要提交新进程，而此 时内存不空，需挂起阻塞态的进程 为运行进程提供足够内存（对换及调整负荷）：资源紧张时， 暂停某些进程，如：实时任务执行，而内存紧张
（4）操作系统的需要
利用PCB完成进程间切换
进程P0
执行 状态存入PCB0 从PCB1载入状态 闲置 Idle 中断或系统调用 状态存入PCB1 从PCB0载入状态 执行 闲置 Idle
操作系统
中断或系统调用
进程P1
· · · · · ·
闲置 Idle
执行
3. PCB的组织方式 • 将处于同一状态的PCB组织在一起，有两 种组织方式： – 链表：同一状态的进程其PCB构成一个链 表，多个状态对应多个不同的链表，如： 就绪链表、阻塞链表 – 索引表：同一状态的进程归入一个index 表（由index指向PCB），多个状态对应 多个不同的index表
第二章 进程管理
• 为了描述程序在并发执行时对系统资源 的共享，我们需要一个描述程序执行时 动态特征的概念，这就是进程或线程。 在本章中，我们将讨论进程的概念和进 程间的关系。
2.1 进程的基本概念
2.1.1 程序的执行特征 • 程序的执行有两种方式：顺序执行和并 发执行。 • 1）顺序执行是单道批处理系统的执行方 式。
• （3）进程调度信息： –进程的当前状态； –优先级(priority)； –运行统计信息（执行时间、页面调 度）； –事件：阻塞原因等。
•
（4）进程控制信息： – 程序段和数据段的地址； – 进程间同步和通信； – 资源占用信息：除CPU外的进程所 需的全部资源及已分配资源清单 – 链接指针：本进程所在队列的下一 个进程的PCB首地址。