操作系统引论 目标和作用 目标：方便性、有效性、可扩展性、开放性
作为用户与计算机硬件系统之间的接口
操作系统作为计算机系统资源的管理者
实现了对计算机资源的抽象
发展过程 人工操作方式、脱机输入输出方式
基本特征
并发 - 并发性 是指两个或多个事件在同一时间间隔内发生，而并行性 是指两个或多个事件在同一时刻发生。
共享 - 资源共享 是指系统中的资源可供内存中多个并发执行的进程共同使用。一段时间内只允许一个进程访问的资源称为临界资源 一个进程访问结束并释放系统资源后才允许另一进程对该资源访问的方式称为互斥访问
虚拟 - 通过空分复用 或时分复用 技术将一条物理信道变为若干条逻辑信道的技术
异步 - 进程的执行本身具有异步性（不可预知完成时间与顺序）所以要设计同步机制
主要功能 处理机管理功能
内存管理功能
(I/O)设备管理功能
文件管理功能
操作系统与用户之间的接口
用户接口（联机用户接口、脱机用户接口、程序接口）
程序接口
结构设计 无结构 程序紧凑，高效利用内存
模块化结构 模块化OS由程序设计的模块化设计思想演变而来
提高OS设计的正确性、可理解性和可维护性。
增强OS的可适应性。
加速OS开发过程。
最初模块接口规定难以满足实际需求
无序设计
分层式结构 将模块接口法中对模块的设计顺序由无序变为有序，自底向上分层设计
易保证系统的正确性
易扩充和易维护性
系统效率降低：单向依赖的层次使得必须建立层次之间的通信机制增加通信开销
习题
设计现代OS的主要目标是什么？
试说明推动分时系统形成和发展的主要动力是什么。
为什么要引入实时操作系统？
试从交互性、及时性以及可靠性方面将分时系统与实时系统进行比较。
OS有几大特征？最基本的特征是什么？
处理机管理有哪些主要功能？其主要任务是什么？
存储器有哪些主要功能？其主要任务是什么？
设备管理有哪些主要功能？其主要任务是什么？
文件管理有哪些主要功能？其主要任务是什么？
进程的描述与控制 前趋图和程序执行 前趋图（Precedence Graph）是一个有向无循环图，用于描述进程之间执行的前后关系。
程序的顺序执行
程序的并发执行
进程的描述 而由程序段、相关的数据段和PCB三部分便构成了进程实体。
典型定义
进程是程序的一次执行。
进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位
特征
状态
PCB数据结构
进程标识符 - 用于惟一地标识一个进程。分为内部标识符和外部标识符处理机状态 - 组成：①通用寄存器②指令计数器③程序状态字PSW④用户栈指针进程调度信息 - 包括：①进程状态②进程优先级③进程调度所需的其它信息④事件，阻塞原因进程控制信息 - ①程序和数据的地址 ②进程同步和通信机制 ③资源清单 ④链接指针
pid
进程状态
现场
优先级
阻塞原因
程序地址
同步机制
资源清单
链接指针
PCB的组织方式
线性方式 将系统中的所有PCB组织在一张线性表中，将该表的首地址存放在一个专用区域中。链接方式 把具有同一状态的PCB，用其中的链接字链接成一个队列，排成就绪队列，若干个阻塞队列以及空白队列。索引方式 系统根据所有进程的状态建立几张索引表。
进程控制 进程控制是用于创建一个新进程，终止一个已完成的进程，或去终止一个因出现某事件而使其无法运行下去的进程，还负责进程运行中的状态转换。
操作系统内核 OS内核—-常驻内存。
支撑功能 - 中断处理 时钟管理 原语操作
资源管理功能 - 进程管理 存储器管理 设备管理
进程的创建 进程的层次结构 即父进程、子进程（可以继承父进程所拥有的资源）
引起创建进程的事件
用户登录
作业调度
提供服务
应用请求
进程创建 调用进程创建原语Creat（ ）按下述步骤创建一个新进程：
申请空白PCB。
为新进程分配资源。
初始化进程控制块。包括：
将新进程插入就绪队列。
进程的终止 引起进程终止的事件
正常结束: 批处理中用Holt指令，分时中用Logs off指令。
异常结束：
外界干预：外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行。
进程的终止过程
根据被终止进程的标识符ID，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。
若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。
若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。
将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。
将被终止进程（它的PCB）从所在队列（或链表）中移出，等待其他程序来搜集信息。
进程的阻塞与唤醒、挂起与激活 引起进程阻塞的事件
请求系统服务：提出I/O服务时，并不立即满足该进程的要求时，转变为阻塞状态来等待
启动某种操作：当进程启动某种操作后，在该操作完成之后才能继续执行。
新数据尚未到达：对于相互合作的进程而言。
无新工作可做。如发送进程。
进程阻塞过程 正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block( )把自己阻塞。
把进程控制块中的现行状态由“执行”改为“阻塞”，并将PCB插入阻塞队列。
转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换。
进程唤醒过程 当被阻塞进程所期待的事件出现时，则由有关进程（比如，用完并释放了该I/O设备的进程）调用唤醒原语wakeup( )，将等待该事件的进程唤醒。
首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪
然后再将该PCB插入到就绪队列中。
进程的挂起 当出现了引起进程挂起的事件时，系统将利用挂起原语suspend( )将指定进程进程挂起。
首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；
对于活动阻塞状态的进程，则将之改为静止阻塞状态。
进程的激活 当发生激活进程的事件时，则可将在外存上处于静止就绪状态的进程换入内存。 系统利用激活原语active( )将指定进程激活:
激活原语先将进程从外存调入内存，检查该进程的现行状态;
若是静止就绪，便将之改为活动就绪；若为静止阻塞，便将之改为活动阻塞。
进程同步 为什么：
进程同步的基本概念
两种形式的制约关系：1）间接相互制约关系。由于资源共享 2）直接相互制约关系。主要由于进程间的合作。
临界资源 一次仅允许一个进程访问的资源为临界资源 。临界区 把在每个进程中访问临界资源的那段代码称为临界区。同步机制规则 ：1)空闲让进 2)忙则等待 3)有限等待 4)让权等待
硬件同步机制 利用计算机硬件指令解决临界区问题
关中断
利用Test-and-Set指令实现互斥
利用Swap指令实现进程互斥
优点：
适用于任意数目的进程，在单处理器或多处理器上
简单，容易验证其正确性
可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量
缺点：
等待要耗费CPU时间，不能实现“让权等待”
可能“饥饿”：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上
信号量机制 信号量（Semaphores）机制:是一种卓有成效的进程同步工具。
整形信号量
必须置一次且只能置一次初值，并且初值不能为负数。
只能执行P、V操作。
必须成对使用P、V操作：P操作遗漏则不能保证互斥访问，V操作遗漏则不能在使用临界资源之后将其释放；P，V次序不能错误、重复或遗漏。
记录型信号量 只能用于共享一个临界资源
1 2 3 4 5 6 7 8 9 10 11 12 13 typedef struct{ int value; struct process_control_block *list; }semaphore; wait(semaphore *S){ S->value--; if(S->value<0)block(S->list); } signal(semaphore *S){ S->value++; if(S->value<=0)wakeup(S->list); }
信号量的初值：0，1，n三种情况
AND型信号量 AND同步机制的基本思想 ：将进程在整个运行过程中需要的所有资源，一次性全都地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。原子操作 ：要么全部分配到进程，要么一个也不分配。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Swait（S1，S2，···，Sn ） { while（true）{ if（ S1≥1 and S2≥1 and…and Sn≥1 ）{ for (i = 1 ; i<= n; i++){ Si = Si – 1; } break; }else{ place the process in the waiting queue associated with the first Si found with Si＜1, and set the program count of this process to the beginning of Swait operation//将进程置于与在 Si<1 的条件下找到的**第一个** Si 关联的等待队列中，并将此过程的程序计数设置为 Swait 操作的开始 } } Ssignal（S1，S2，···，Sn）{ for( i = 1; i<= n; i++ ){ Si = Si+1; Remove all the process waiting in the queue associated with Si into the ready queue//将与 Si 关联的队列中**所有**等待的进程移动到就绪队列中 } }
信号量集 一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源(预留下限)还存在一个临界值时的信号量处理
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Swait（S1，t1，d1，…，Sn，tn，dn）（满足ti≥ di） if( S1 ≥t1 &…& Sn≥tn){ for( i =1; i<=n; i++){ Si ＝Si － di; } }else{ Place the executing process in the waiting queue of the first Si with Si＜ti and set its program counter to the beginning of the Swait operation//将进程置于与在 Si<ti 的条件下找到的**第一个** Si 关联的等待队列中，并将此过程的程序计数设置为 Swait 操作的开始 }//end if }//end Swait Ssignal（S1，d1，···，Sn，dn）{ for( i =1; i<= n; i++){ Si = Si + di； Remove all the process waiting in the queue associated with Si into the ready queue//将与 Si 关联的队列中**所有**等待的进程移动到就绪队列中 } }
三种特例：
Swait(S,d,d)：允许每次申请d个资源。当资源数少于d时，不予分配。
Swait (S,1,1)：S>1，记录型信号量。S=1时，互斥型信号量。
Swait(S,1,0)，可控开关，当S>=1时，允许进入，S<1时，不能进入。
经典进程的同步问题 生产者——消费者问题 记录型信号量解决 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 void producer( ){ do{ … Produce an item in nextp; … wait(empty); wait(mutex); buffer(in):=nextp; in:=(in+1) mod n; signal(mutex); signal(full); }while(TRUE); } void consumer{ do{ wait(full); wait(mutex); nextc:=buffer(out); out:=(out+1) mod n; signal(mutex); signal(empty); Consumer the item in nextc; …… }while(TRUE); }
AND信号量解决 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 int in=0, out=0; item buffer[ n ]; semaphore mutex=1, empty=n, full=0; void producer( ){ do{ … produce an item in nextp; … Swait(empty, mutex); buffer[in] = nextp; in = (in+1) % n; Ssignal(mutex, full); }while(TRUE); } //end producer void consumer{ do{ Swait(full, mutex); nextc = buffer[out]; out = (out+1) % n; Ssignal(mutex, empty); consumer the item in nextc; }while(TRUE); }
哲学家进餐问题 几种解决方法：
至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。
仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。
规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是1、 2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐
AND信号量解决 1 2 3 4 5 6 7 8 semaphore chopstick[5]={1,1,1,1,1}; do{ ……; think; Sswait(chopstick[(i+1) % 5],chopstick[i]); eat; Ssignal(chopstick[(i+1) % 5],chopstick[i]); }while(TRUE);
读者——写者问题 记录型信号量解决 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 semaphore rmutex=1, wmutex = 1; int readcount = 0; void reader( ){ do{ wait(rmutex); if readcount=0 then wait(wmutex); readcount:=readcount+1; signal(rmutex); … perform read operation … wait(rmutex); readcount:=readcount-1; if readcount=0 then signal(wmutex); signal(rmutex); }while(TRUE); }//end reader void writer( ){ do{ wait(wmutex) perform write operation; signal(wmutex) }while(TRUE); } void main(){ cobegin reader(); writer(); coend }
信号量集解决 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 int RN; Semaphore L=RN, mx=1; //RN标示同时允许多少读进程存在 void reader( ){ do{ swait(L,1,1); swait(mx,1,0); … perform read operation; … ssignal(L,1); }while(TRUE); }//end reader void writer( ){ do{ swait(mx,1,1; L,RN,0); perform write operation; ssignal(mx, 1); }while(TRUE); } //end writer void main( ){ cobegin reader(); writer(); coedn }
进程通信 类型
消息传递通信的实现方法
直接通信方式原语 ）：
间接通信方式原语 ，分别用于信箱的创建、撤消和消息的发送、接收等。优点：在读/写时间上的随机性
消息格式 消息头：含控制信息如：收/发进程名，消息长度、类型、编号
消息格式进程同步方式 1）发送和接收进程阻塞（汇合）用于紧密同步，无缓冲区时。
进程运行与监控 Linux进程控制块 task_struct结构 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 pid_t pid; uid_t uid,euid; gid_t gid,egid; volatile long state; int exit_state; unsigned int rt_priority; unsigned int policy; struct list_head tasks; struct task_struct *real_parent; struct task_struct *parent; struct list_head children,sibling; struct fs_struct *fs; struct files_struct *files; struct mm_struct *mm; struct signal_struct *signal; struct sighand_struct *sighand; cputime_t utime, stime; struct timespec start_time; struct timespec real_start_time;
task_struct:进程状态 ——volatile long state;
1 2 3 4 5 #define TASK_RUNNING 0 #define TASK_INTERRUPTIBLE 1 #define TASK_UNINTERRUPTIBLE 2 #define TASK_ZOMBIE 4 #define TASK_STOPPED 8
进程状态切换
task_struct:文件管理
进程的启动 UNIX&Linux中创建进程的方式：
在shell中执行命令或可执行文件由shell进程调用fork函数创建子进程
在代码中（已经存在的进程中）调用fork函数创建子进程，fork创建的进程为子进程，原进程为父进程
Linux系统中进程0 （PID=0）是由内核创建，其他所有进程都是由父进程调用fork函数所创建的。进程0在创建子进程（PID=1，init进程）后，进程0就转为交换进程或空闲进程
进程1（init进程）是系统中其他所有进程的共同祖先
fork #include<unistd.h>头文件定义
1 2 3 /* Clone the calling process, creating an exact copy. Return -1 for errors, 0 to the new process, and the process ID of the new process to the old process. */
fork函数被正确调用后，将会在子进程中和父进程中分别返回
在子进程中返回值为0（不合法的PID，提示当前运行在子进程中）
在父进程中返回值为子进程ID（让父进程掌握所创建子进程的ID号）
出错返回-1
子进程是父进程的副本
子进程复制/拷贝父进程的PCB、用户空间（数据段、堆和栈）
父子进程共享正文段（只读）
子进程复制父进程的进程控制块
父进程的文件描述符表被子进程复制，父子进程的同一文件描述符指向同一个文件表
父子进程对同一文件访问基于相同的文件当前位置
父子进程对共享文件的常见处理方式：
父进程等待子进程完成。当子进程终止后，文件当前位置已经得到了相应的更新
父子进程各自执行不同的程序段，各自关闭不需要的文件
vfork函数保证子进程先执行，在它调用exec或者exit之后，父进程才会继续被调度执行（父进程处于TASK_UNINTERRUPTIBLE状态）
进程内存空间布局
命令行参数和环境变量 - 主要用于支撑函数调用 存放参数、局部变量等
堆栈 - 用于动态分配内存
未初始化的数据 - 程序执行之前，将此段中 的数据初始化为0，如 全局变量long sum[1000];
初始化的数据 - 包含了程序中需明确赋 初值的变量，如全局变量 int maxcount=99;
正文 - CPU执行的代码部分，正文 段通常是共享、只读的
进程的运行控制 设置环境变量 设置环境变量的三种方法：
putenv - 将环境变量字符串放入环境变量表中
setenv - 将指定环境变量的值设置为参数指定值
unsetenv - 删除指定的环境变量字符串
exec系列函数 进程调用exec系列函数在进程中加载执行另外一个可执行文件并不创建新进程 ，所以在调用exec系列函数后其进程ID(uid)并未改变，已经打开的文件描述符不变
execl execle execlp execv execve execvp
l：表示list，每个命令行参数都说明为一个单独的参数
v：表示vector，命令行参数放在数组中
e：表示由函数调用者提供环境变量表
p：表示通过环境变量PATH来指定路径，查找可执行文件
进程的监测 终止进程函数 头文件stdlib.h定义：void exit( int status )_exit 函数将会立即 返回内核exit 函数执行一些预先注册的终止处理函数,执行文件I/O操作的善后工作，使得所有缓冲的输出数据被更新到相应的设备,返回内核
获知子进程状态改变
主动获取 - 调用wait或waitpid函数等待子进程状态信息改变，并获取其状态信息
异步通知 - 当一个进程发生特定的状态变化（进程终止、暂停以及恢复）时，内核向其父进程发送SIGCHLD信号，父进程可以选择忽略该信号，也可以对信号进行处理（默认处理方式为忽略该信号）
僵尸进程：关闭 该进程打开的所有文件。而对于已经终止但父进程尚未对其调用wait或waitpid函数的进程（TASK_ZOMBIE状态），称为僵尸进程。
孤儿进程：父进程在子进程终止之前终止 ，则子进程的父进程将变为init进程，保证每个进程都有父进程，由init进程调用wait函数进行善后
wait函数 头文件：sys/wait.hpid_t wait(int *statloc); 系统提供的宏 来快速解析子进程的状态
如果一个进程有几个子进程，那么只要有一个子进程状态改变，wait函数就返回
如何才能使用wait函数等待某个特定 子进程的状态改变？
调用wait，然后将其返回的进程ID和所期望的子进程ID进行比较
如果ID不一致，则保存该ID，并循环调用wait函数，直到等到所期望的子进程ID为止
waitpid函数 功能：等待某个特定 子进程状态改变pid_t waitpid(pid_t pid, int *statloc, int options);
pid：pid == -1：等待任意子进程状态改变（同wait）；pid > 0：等待进程ID为pid的子进程状态改变；pid == 0：等待其组ID等于调用进程组ID的任意子进程；pid < -1：等待其组ID等于pid绝对值的任意子进程
statloc：用于存储子进程的状态改变信息
options：可以为0，也可以是以下常量：WNOHANG：如果没有任何已经终止的子进程则马上返回, 函数不等待，此时返回值为0；WUNTRACED：用于跟踪调试
waitpid可以实现非阻塞的等待操作，有时希望取得子进程的状态改变信息，但不希望阻塞父进程等待子进程状态改变
线程的基本概念
在一个已有进程中创建 一个新线程比创建一个全新进程所需的时间少。
终止 一个线程比终止一个进程花费的时间少。线程间切换 比进程间切换花费的时间少。
线程提高了不同的执行程序间通信 的效率。同一个进程中的线程共享存储空间和文件，它们无需调用内核就可以互相通信。
线程的引入 引入进程是为了使多个程序能够并发执行，以提高资源利用率和系统吞吐量；
一个可拥有资源的独立单位
一个可调度和分派的基本单位
调度和分派的部分通常称为线程 或轻型进程，而资源所有权的部分通常称为进程 。
线程与进程的比较 从调度性、并发性、系统开销和拥有资源等方面对线程和进程进行比较。
调度 在传统的操作系统中，进程作为拥有资源和独立调度、分派的基本单位。而在引入线程的操作系统中，则把线程作为调度和分派的基本单位，而进程作为资源拥有的基本单位。
并发 在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，使得操作系统具有更好的并发性，从而能更加有效地提高系统资源的利用率和系统的吞吐量。
拥有资源 一般而言，线程自己不拥有系统资源 (也有一点必不可少的资源)，但它可以访问其隶属进程的资源，即一个进程的代码段、数据段及所拥有的系统资源，如已打开的文件、I/O 设备等，可以供 该进程中的所有线程所共享。
独立性 同一进程中的不同线程共享进程的内存空间和资源。不同线程 的独立性低于不同进程 。
系统开销 线程的切换只需要保存和设置少量的寄存器内容，不涉及存储器管理方面的操作。
支持多处理机系统 一个进程分为多个线程分配到多个处理机上并行执行，可加速进程的完成。
线程的属性
轻型实体
独立调度和分派的基本单位
可并发执行
共享进程资源
线程的状态 同进程一样，线程之间也存在共享资源和相互合作的制约关系，致使线程在运行时也具有间断性。执行 状态:表示线程正获得CPU而运行；就绪 状态:表示线程已具备了各种运行条件，一旦获得CPU便可执行；阻塞 状态:表示线程在运行中因某事件而受阻，处于暂停执行的状态；
线程的组成 每个线程有一个TCB结构，即线程控制块，用于保存自己私有的信息，主要由以下部分组成：
一个唯一的线程标识符；
一组寄存器 ：包括程序计数器、状态寄存器、通用寄存器的内容；
线程运行状态：用于描述线程正处于何种运行状态；
优先级：描述线程执行的优先程度；
线程专有存储器：用于保存线程自己的局部变量拷贝；
信号屏蔽：对某些信号加以屏蔽；
两个栈指针：核心栈、用户栈。
进程线程对比
应用功能
线程
进程
创建
pthread_create
fork,vfork
退出
pthread_exit
exit
等待
pthread_join
wait、waitpid
取消/终止
pthread_cancel
abort
读取ID
pthread_self()
getpid()
同步互斥/通信机制
互斥锁、条件变量、读写锁
无名管道、有名管道、信号、消息队列、信号量、共享内存
线程间的同步和通信 ▪为使系统中的多线程能有条不紊的运行，系统必须提供用于实现线程间同步和通信的机制。在多线程OS中，通常提供多种同步机制:
互斥锁(mutex) - 互斥锁是一种比较简单的、用于实现进程间对资源互斥访问的机制。 由于操作互斥锁的时间和空间开销都较低，因而较适合于高频度使用的关键共享数据和程序段。
条件变量 - 每一个条件变量通常都与一个互斥锁一起使用。 单纯的互斥锁用于短期锁定，主要是用来保证对临界区的互斥进入。而条件变量则用于线程的长期等待， 直至所等待的资源成为可用的。
信号量机制 - 当某线程需利用信号量来实现同一进程中各线程之间的同步时，可调用创建信号量的命令来创建一私用信号量，其数据结构存放在应用程序的地址空间中。
线程的实现方式 用户级线程 用户级线程仅存在于用户空间中。对于这种线程的创建、撤消、线程之间的同步与通信等功能，都无须内核来实现。
线程切换不调用内核
调度是应用程序特定的：可以选择最好的算法
可运行在任何操作系统上（只需要线程库），可以在一个不支持线程的OS 上实现
当线程执行一个系统调用时，该线程及其所属进程内的所有线程都会被阻塞 。
多线程应用不能利用 多处理机进行多重处理。
内核支持线程 内核支持线程，是在内核的支持下运行的，即无论是用户进程中的线程，还是系统进程中的线程，他们的创建、撤消和切换等，是依靠内核实现的。
在多处理器系统中，内核能够同时 调度同一进程中多个线程并行执行；
如果进程中的一个线程被阻塞了，内核可以 调度该进程中的其它线程占有处理器运行，也可以运行其它进程中的线程；
内核支持线程具有很小的数据结构和堆栈，线程的切换比较快 ，切换开销小 ；
内核本身也可以采用多线程技术，可以提高系统的执行速度和效率 。从用户态转到内核态再转到用户态 进行，这是因为用户进程的线程在用户态运行，而线程调度和管理是在内核实现的，系统开销较大。
组合方式 用户级线程是在用户空间实现的。所有用户级线程都具有相同的数据结构，它们都运行在一个中间系统上：
习题
什么是前趋图？为什么要引入前趋图？
画出前趋图：S1:a=x+y;S2:b=z+1;S3:c=a-b;S4:w=c+1;
为什么要引入进程，会产生什么影响？
从动态性、并发性和独立性的角度比较进程和程序
PCB的作用？为什么说PCB是进程唯一标志
进程的三个基本状态转化原因
为什么要引入挂起状态，有什么性质？
进程切换时要保存的处理器状态信息有哪些？
引起进程创建的主要事件
引起进程撤销的主要事件
创建进程时所要完成的主要工作
引起进程阻塞或被唤醒的主要事件
从调度性、并发性、拥有资源及系统开销方面对比进程与线程
解释用户级线程与内核支持线程
处理机调度与死锁 处理机调度的层次
高级调度 - 又称长程调度或作业调度，将外存作业调入内存，创建PCB等，插入就绪队列。用于批处理系统。调度最慢
低级调度 - 又称进程调度或短程调度，决定就绪队列中的那个进程应获得处理机，并将处理机分配给选中的进程。调度最频繁
中级调度 - 又称内存调度，把外存上那些已经具备运行条件的就绪进程重新载入内存。从静止就绪到活动就绪。
处理机调度算法的目标 共同目标：
资源利用率：使系统处理器和资源尽可能忙碌
公平性：为进程合理分配CPU时间，不会发生饥饿
平衡性：为不同类型进程平衡分配资源
策略强制执行：如安全策略可无条件准确执行
批处理系统的目标
平均周转时间短
系统吞吐量高：尽量多地选择短作业运行
处理机利用率高：尽量选择计算量大的作业
分时系统的目标
响应时间快
均衡性：指系统响应时间的长短应与用户所请求服务的复杂性相适应。
实时系统的目标
截至时间的保证：开始截止时间 完成截止时间 硬实时、软实时
可以预测性：对调度结果的可预见性
作业与作业调度
作业 Job：用户提交给系统的一项相对独立的工作。程序+数据+作业说明书
作业步：在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，每一个加工步骤称为一个作业步，各作业步之间存在着相互联系。
作业流：依次执行的作业步，作业步间非并行的。
作业控制块(JCB) 作业在系统中存在的标志，保存了系统对作业进行管理和调度的全部信息。
作业标识
用户名称
用户账号
作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)
作业状态
调度信息(CPU 繁忙型、I/O 繁忙型、批量型、终端型)
资源需求(预计运行时间、要求内存大小、要求 I/O 设备的类型和数量等)
资源使用情况等
作业运行的三个阶段和三种状态 收容阶段：后备状态
作业调度的主要任务
接纳多少个作业：太多会影响系统服务质量，如延长周转时间；太少会导致资源利用率和系统吞吐量太低
接纳哪些作业：将哪些作业从外存调入内存，取决于所采用的调度算法
先来先服务(FCFS)和短作业优先(SJF )调度算法 在作业调度中是从后备队列调入内存运行。
先来先服务： 既可用于作业调度，也可用于进程调度。有利于长作业 （进程），而不利于短作业（进程）。
短作业(进程)优先调度算法SJ(P)F： 是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。对长作业不利 ，不能保证紧迫性作业(进程)会被及时处理，根据用户所提供的估计执行时间而定不准确。
优先级调度算法和高响应比优先调度算法 优先级调度算法：
高响应比优先调度算法：
进程调度 主要任务
保存处理机的现场信息
按某种算法选取进程
把处理机分配给进程strong text
进程调度机制
进程调度方式 非抢占方式： 一旦进程投入运行，除了进程完成或者需要阻塞外，不能剥夺其处理机。
进程运行完毕或因发生某事件而无法继续运行
因I/O请求而阻塞
因通信或者同步而阻塞
抢占方式： 允许根据某种原则，暂停正在执行的进程，重新分配处理机。
批处理：防止长进程长期占用CPU，公平
分时：人机交互
实时：紧迫任务的执行
优先权
短进程优先
时间片原则
轮转调度算法(RR) 基于时间片轮转
优先级调度算法 同样分为非抢占式和抢占式
多队列调度算法 针对：不同用户的调度策略需求:实时/分时/批处理混合系统
多级反馈队列调度算法 设置多个就绪队列，并为各个队列赋予不同的优先级。队列中的进程运行一个时间片后未结束则降级排到下一个队列的末尾 。最低优先权队列中的进程则按RR方式运行。
基于公平原则的调度算法
保证调度算法 - 保证的是绝对运行时间，即启动后在某个时间段内必须获得多少运行时间。 例如N个进程平均分配时间。
公平分享调度算法 - 按照用户数量平均分配时间，而不是进程间平均分配。
实时调度 实时调度必须满足实时任务对截至时间的要求
实现实时调度的基本条件
就绪时间
开始截止时间和完成截止时间
处理时间
资源要求
优先级
单处理机条件下必须保证处理时间与截至时间之比小于1
实时调度算法的分类 非抢占式
非抢占式轮转调度
非抢占式优先调度
抢占式
基于时钟中断的抢占式
立即抢占式
EDF最早截至时间算法 就绪队列按各任务截止时间的早晚排序；具有最早截止时间的任务排在队列的最前面。
LLF最低松弛度优先算法 松弛度=完成截至时间–剩余运行时间–当前时间
优先级倒置 即高优先级进程(或线程)被低优先级进程(或线程)延迟或阻塞。
规定进入临界区后不允许抢占
优先级继承机制(动态优先级)，即占用同样资源的低优先级进程继承需要资源的进程的高优先级
死锁 资源问题
可重用性资源(打印机)和消耗性资源(消息)
不可抢占性资源(打印机)
计算机系统的死锁 原因：
竞争可重用资源、可消耗资源
进程间推进顺序非法。
定义、必要条件和处理方法 定义：如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件 ，那么该组进程是死锁的
四个条件：
互斥条件：指进程对所分配到的资源进行排它性使用 。
请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求 。
不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链 。
预防死锁 通过设置某些限制条件 ，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。
破环条件2 通过：
第一种协议规定开始运行之前，必须一次性申请所需的全部资源
第二种协议规定进程在运行过程中要逐步释放已用资源再请求新资源
*优点**：简单、易于实现且很安全。
*缺点**：资源被严重浪费，使进程延迟运行。
破环条件3 当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足 时，必须释放它已经保持了的所有资源。待以后需要时再重新申请缺点 ：因反复地申请和释放资源，致使进程执行被无限推迟，延长进程周转时间、增加系统开销、降低吞吐量
破环条件4 将所有资源按类型进行线性排队，并赋予不同的序号。 所有进程对资源的请求必须严格按照资源序号递增的次序提出优点 ：相比前两种提高了资源利用率和系统吞吐量 缺点 ：各类资源分配的序号必须相对稳定限制了新设备类型的增加；作业使用顺序与系统规定顺序不同造成资源浪费；增加了程序设计难度。
避免死锁 是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。不会事先设置限制
Dijkstra银行家算法 可利用资源向量Available
死锁的检测与解除 检测死锁：通过系统所设置的检测机构 ，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；检测 到系统中已 发生死锁时，须将进程从死锁状态中解脱出来 。常用的实施方法是撤消或挂起一些进程。配套使用
检测： 系统必须保存有关资源的请求和分配信息，根据信息通过资源分配图 或死锁定理 的方法检测死锁
解除： 两种常用方法：抢占资源 (使死锁进程抢占其它进程资源以完成进程解除死锁)、终止进程 (终止或撤销死锁进程)
付出代价最小算法
一种找到付出代价最小的终止顺序，但成本高的算法：
先从死锁进程组中取出一个，形成第一层终止，若有n个死锁进程，则有n个第一层。
再从n个第一层中取一个，形成第二层终止，每个第一层又有n-1个第二层终止。
如此循环，直到解除死锁，将各层的总代价计算，得到最小的终止顺序。
另一种比较有效的算法：
找到死锁进程组中，终止代价最小的，将其从死锁进程组中删去。
再从新的死锁进程组中，找到终止代价最小的，删去。
如此循环，直到解除死锁。
习题 1、假设一个多级反馈队列的实现共有4级，各个队列的时间片长度是1、2、4、6秒，已知当前仅在第一级队列上有一个执行时长为10秒的进程O，在两秒后将有一个执行时长为8秒的任务A到达，请算出任务A的周转时间。
1
1:
1:
1:
1:
1:
所以答案等于1+4+2+4+4+1=16s
2、简述死锁的必要条件，以及预防死锁方法与必要条件的关系。
互斥条件：指进程对所分配到的资源进行排它性使用 。
请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求 。
不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链
预防死锁通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。预防死锁使四个必要条件中的第2、3、4条件之一不能成立：
破环条件2通过：第一种协议规定开始运行之前，必须一次性申请所需的全部资源
破环条件3当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源。待以后需要时再重新申请；
破环条件4将所有资源按类型进行线性排队，并赋予不同的序号。 所有进程对资源的请求必须严格按照资源序号递增的次序提出。
3、在银行家算法中，若出现下述资源分配情况，试问：
（1）该状态是否安全？
/1650529219846.png)
/1650532050974.png)
/1650616504120.png)
/1650618210434.png)
/1650618215534.png)
/1650619179190.png)
/IMG_20220304_151207_edit_772433114767030.jpg)
/1646809311457.png)
/1647413678022.png)
/1647413220791.png)
/%E6%9C%AA%E5%91%BD%E5%90%8D%E6%96%87%E4%BB%B6.png)
/1647848472429.png)
/1647853007722.png)
/1647855224272.png)
/1647855855262.png)
