MOS_Chapter2_Process And Thread

2.1 进程

多道程序设计中一个CPU在不同进程间切换形成伪并行的假象.

由此真正的并行的概念模型逐渐出现

2.1.1进程模型

进程模型中，所有可运行的软件（包括操作系统）被组织成若个顺序进程sequential process 也叫进程process

进程与程序的区别、关系？

进程是某种类型的一个活动，有程序、输入、输出以及状态。单个处理器可以被不同进程共享，进程调度算法决定不同进程工作的行止与顺序。一个程序运行两遍是两个进程。

2.1.2 进程创建

4个主要事件导致进程的创建

系统初始化
运行时的程序使用创建进程的系统调用
用户请求创建新进程
一个批处理作业的初始化（大型机系统认为有资源处理作业时就创建一个进程来处理）

所有情况中，都是一个已存在的进程执行系统调用创建进程。

父子进程之间的关系

父子进程有不同的地址空间，子进程的地址空间是父进程的副本（参数、代码都是一样的）其中不可写的内存区是共享的。

另一种描述：子进程共享父进程所有内存，只有对它们的内存写操作时才会复制一份（可写的内存不可共享）

2.1.3进程的终止

进程的终止条件

正常退出（自愿）：系统调用
出错退出（自愿）：出现错误后终止
严重错误（非自愿）直接被系统中断
被其他进程杀死（非自愿）主动kill

2.1.5进程的状态

运行态（占用CPU）
就绪态（可运行，等待CPU）
阻塞态（需要外部事件，否则不能运行

2.1.6进程的实现

进程本身是一个抽象概念。支持它实现的抽象模型的是进程表process table。一个进程表项（进程控制块）代表一个进程。

什么是进程表项？
包含了进程状态的信息：程序计数器，堆栈指针，内存分配，打开文件的状态，调度信息，状态转换保存的信息。

中断向量interrupt vector的位置与I/O相关联，它包含了中断服务程序的入口地址。

举例：磁盘中断。
如果进程3在运行。中断硬件程序将程序计数器，程序状态字，寄存器信息压入堆栈，计算机跳转到中断向量指示的地址。由硬件完成。然后由中断服务例程接管剩余工作。
所有中断都有保存寄存器开始，该例程一般由汇编语言完成，可供所有中断程序使用（尽管中断引起的原因不同）。例程结束后调用C程序处理中断剩余工作。完成工作之后使下一个进程就绪，执行进程调度，载入寄存器值以及内存映射

中断发生后的底层实现：

硬件压入堆栈程序计数器等
硬件从中断向量装入新的程序计数器
汇编语言过程保存寄存器的值
汇编语言过程设置新的堆栈
C中断服务例程运行
调度程序决定下一个进程
C过程返回至汇编代码
汇编语言过程开始运行新的进程

2.2线程

每个进程有一个地址空间和一个控制线程而同一个地址空间允许运行多个线程（迷你进程）

2.2.1线程的使用

为什么要有线程？

在应用中需要同时发生多个活动，将这些应用分解成可以并行运行的多个顺序线程会使程序设计的模型更简单。
多线程模型：并行实体共享同一个地址空间和所有可用数据。
线程比进程更轻量级，更快地创建。
对于大量计算与IO处理，运行彼此重叠进行。
以组织Web服务器分析多线程的作用：

多线程：并行性阻塞系统调用
进程被分为三个线程，分别是：
分派程序线程从网络读入工作请求并检查请求。选择一个被阻塞的工作线程，唤醒它。
工作线程：处理请求，检查请求是否在高速缓存中，否则阻塞从磁盘调入。
单线程进程：无并行性，阻塞
循环：获得请求，检查请求，在下一个请求前完成整个工作。等待磁盘时，服务器空转（阻塞）不处理其他请求
有限状态机：并行性，非阻塞，中断
在请求到来时检查，如果高速缓存中得到满足则正常运行，否则运行一个非阻塞的磁盘操作。服务器在表格记录当前请求的状态再去处理下一个事件。下一个事件可能是新的请求或者是磁盘对之前磁盘操作的返回（信号、中断的形式）。每次服务器改变请求工作的状态时，必须显示地保存或者重新装入相应的计算状态。

2.2.2线程模型

进程模型基于两种独立的概念：资源分组处理与执行
线程的独立性很小
线程之间没有保护：不可能也没必要。
线程模型中的内容：程序计数器寄存器堆栈状态
进程模型中的内容：地址空间全局变量打开的文件子进程信号与信号处理等等。

2.2.4用户空间实现线程

第一种方法:整个线程包放在用户空间中，内核不可见，因此线程当作常规进程处理。

优点:

可以在不支持线程的操作系统上实现
进程内允许自定义对线程的调度算法。

每个进程都有一个专用的线程表。由运行时的系统管理。
装入所有线程的状态信息之后，进行线程的切换不需要陷入内核，速度快上一个数量级。
线程与进程一个关键差别：
线程完成运行时会把该线程信息保存在线程表中并进行线程切换，两者都是本地过程不需要陷入内核，不需要上下文切换，不需要内存高速缓存刷新。

用户级线程包的另一个问题是，如果一个线程开始运行，那么在该进程中的其他线程就不能运行，除非第一个线程自动放弃CPU。

一个可能的解决方案是让运行时系统请求每秒一次的时钟信号（中断），但
是这样对程序也是生硬和无序的。

2.2.5在内核中实现线程

此时不再需要运行时系统了。另外，每个进程中也没有线程表。相反，在内核中有用来记录系统中所有线程的线程表。当某个线程希望创建一个新线程或撤销一个已有线程时，它进行一个系统调用，这个系统调用通过对线程表的更新完成线程创建或撤销工作。

内核态与用户态切换线程对比:

所有能够阻塞线程的调用都以系统调用的形式实现，

当一个线程阻塞时，内核根据其选择，可以运行同一个进程中的另一个线程（若有一个就绪线程）或者运行另一个进程中的线程。

在用户级线程中，运行时系统始终运行自已进程中的线程，直到内核剥夺
它的CPU(或者没有可运行的线程存在了）为止。

2.2.6混合实现

内核只识别内核级线程，并对其进行调度。其中一些内核级线程会被多个用
户级线程多路复用。

2.3进程间通信

进程间通信(InterProcess Communication, IPC)的三个问题
第一个问题：一个进程如何把信息传递给另一个
第二个问题：确保两个或更多的进程在关键活动中不会出现交叉
第三个问题与正确的顺序有关

2.3.1 竞争条件

协作的进程会共享一些都能读写的公用存储区。两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，称为竞争条件(racecondition)

2.3.2临界区

互斥(mutualexclusion), 即以某种手段确保当一个进程在使用一个共享变朵或文件时，其他进程不能做同样的操作来避免竞争条件。

我们把对共享内存进行访问的程序片段称作临界区域(criticalregion)或临界区(criticalsection)

如果我们能够适当地安排，使得两个进程不可能同时处千临界区中，就能够避免竞争条件。而这种方法一般满足下列四个条件

两个进程不能同时处于其临界区
对CPU的速度与数量没有假设
临界区外运行得到进程不得阻塞其他进程
不能使进程无限期等待进入临界区(忙等待)

2.3.3 忙等待的互斥

屏蔽中断:让每个进程刚刚进入临界区后屏蔽所有中断(包括CPU的时钟中断),因此CPU不会切换进程.

缺点:屏蔽中断的权限交给用户进程不可取,如果一直被用户进程中断；系统会终止.对内核来说,使用几条指令屏蔽中断非常方便。

结论：屏蔽中断对OS是一项有用技术，对用户进程不适合。

锁变量

假设有一个共享变量（锁变量），初始值为0，当一个进程想进入其临界区，先测试锁，0表示可已进入，进入前锁设置为1再进入；否则等到锁为0.

缺点：锁同样是临界资源，需要互斥否则会有竞争条件。

严格轮转

turn：设置轮转值，用于记录哪个进程进入临界区，并检查或更i性能共享内存。

开始时，进程0检查turn，发现其值为0，于是进入临界区。进程1也发现其值为0，所以再等待循环中不断测试turn知道其值为1.

忙等待busy waiting：连续测试一个便改良直到某个值出现为止。缺点：浪费CPU。使用情况：一般用于等待时间非常短的情况。

自学锁spin lock：用于忙等待的锁

//进程0
while(TRUE)
{
	while(turn!=0);
    critical_region();
    turn = 1;
    noncritical_region();
}

Peterson解法

#define FALSE 0
#define TRUE 1
#define N 2

int turn;//轮转的对象
int interested[N];//对临界区有兴趣/即将占领临界区

void enter_region(int process) //其中一个进程
{
	int other; //另一个进程
    
    other  = 1- process;
    interested[process] = TRUE; //对临界区感兴趣
    turn = process ; //给感兴趣的轮转
    while(turn==process&&interested[other]==TRUE); //如果一个在执行 另一个感兴趣,则空转
}
void leave_region(int process)
{
    interested[process] = FALSE;//不再空转
}

现在0进程调用enter_region,标识进入临界区。

如果1不想要进入临界区，则皆大欢喜，没有竞争

如果1运行enter_region，进程1将在while一直空转，直到另一个退出

2.3.4睡眠与唤醒

Peterson解法与TSL、XCHG解法都有忙等待的缺点：本质上，当一个进程想进入临界而去，先检查是否允许进入，若不允许在原地等待直到允许。

优先级反转问题priority inversion problem：优先级低的进程处于就绪，优先级高的进程处于忙等待导致低进程无法被调度而不能释放临界区资源。

生产消费者问题producer-consumer、有界缓冲区问题：两个进程共享一个公共固定的缓冲区。一个、多个生产者（将信息放入缓冲区），一个、多个消费者（从缓冲区中取出信息）

count为0消费者休眠，否则count-1；生产者同理

竞争条件：对count访问未加以限制。

缓冲区为空,消费者读取count为0,此时调度程序运行生产者,count+1.但刚刚消费者读取到的是0因此一直休眠,于是生产者唤醒消费者.但消费者逻辑上还没有休眠(刚刚读取到0),wakeup信号无效.当消费者继续运行(count=0)继续真睡眠.生产者吃在会填满整个缓冲区再睡眠.因此都睡眠下去.

唤醒等待位可以暂时解决这个问题:当wakeup信号发送给一个清醒的进程信号时,位置为1.

2.3.5信号量

信号量(semaphore) (互斥):累计唤醒次数.0代表没有唤醒操作,正数表示有一个以上唤醒操作.

信号量另一种用途:同步synchronization:信号量full empty保证某种事件的顺序发生/不发生

down和up操作是不可分割的原子操作.(一旦一个信号量开始操作,不会被阻塞)

信号量解决生产者消费者问题

#define N 100
typedef int semaphore;
semaphore mutex = 1,empty=N,full=0;//分别是控制对临界区的访问,缓冲区空槽数目,缓冲区满槽数
void producer(void)
{
	int item;
    while(TRUE)
    {
		item = produce_item();
        down(&empty);//
        down(&mutex); //进入临界区
        insert_item(item); //将新数据放入缓冲区
        up(&mutex);//离开缓冲区
        up(&full);
        
    }
}
void consumer(void)
{
    int item;
    while(TRUE)
    {
        down(&full);
        down(&mutex);
        item = remove_item();
        up(&mutex);
        up(&full);
    }
}

2.3.6互斥量

互斥量mutex:不包含信号量的计数能力,信号量的简化版本.仅使用于管理共享资源或一小段代码(例如线程)

互斥量的状态:0解锁/1枷锁,二进位表示

使一个线程睡眠的语句应该总是要检查这个条件，以保证线程在继续执行前满足条件，因为线程可能已经因为一个UNIX信号或其他原因而被唤醒(导致信号丢失)。

2.3.7管程

考虑到死锁问题:用信号量解决生产者消费者问题时,down/up操作顺序更改会发生什么呢?

down(&empty) down(&mutex); 两者顺序交换.

先进入临界区,mutex=0, 这时缓冲区满了,生产者阻塞,调用消费者,but mutex=0进入不了临界区.此时产生死锁.

管程monitor:进程可再任何时候调用管程中的过程,但不饿能再管程之外访问管程内的数据.即任意时刻管程中只能有一个活跃的进程.

**条件变量condition variables:**使进程再无法继续运行时被阻塞.

当一个管程过程发现它无法继续运行时,再某个条件变量上使用wait使进程阻塞, 并调用另一个等待管程的进程进入管程.

2.3.8消息传递

进程间通信,是系统调用的部分.

设计要点

涉及到不同机器上的通信进程. 特殊确认acknowledgement以及身份确认authentication

解决生产者消费者问题

生产者,消费者都使用信箱.生产者向消费者新鲜发送包含数据的消息,消费者向生产者心想发送空的消息.目标信箱容纳被发送但未被目标接收的消息.

2.3.9 屏障

屏障barrier:当一个进程达到某阶段遇到屏障时,戒备屏障阻拦,当所有进程都达到该屏障才能进入下一个阶段.

2.3.10 避免锁:读-复制-更新

允许写操作来更新数据,及时还有其他进程正在使用它,而不需要锁住临界区

读-复制-更新RCU: 将更新过程中的移除和再分配过程分离开.利用树的结构(Github)

2.4调度

完成进程选择工作的称为调度程序(使用调度算法)

进程的行为

I/O活动:当一个进程等待外部设备完成工作而被阻塞时

调度时机:需要调度的几种情况
1. 创建一个新进程后,决定允许父/子进程
2. 一个进程退出时
3. 一个进程阻塞在I/O和信号量上
4. 再一个I/O中断
调度算法分类
1. 批处理:处理周期性作业,减少了进程的切换
2. 交互式:抢占式(服务器常用)需要服务多个突发的用户/进程,不可能一直等待
3. 实时:进程无法快速完成工作时自己阻塞

实时系统与交互式系统的差别:实时系统只运行那些用来推进现有应用的程序，而交互式系统是通用的，它可以运行任意的非协作甚至是有恶惹的程序。

调度算法的评价指标

吞吐量throughout:系统每小时完成的作业数量

周转时间turnaround time 一个批处理作业提交开始到作业完成为止的平均时间

不同系统的核心评价指标不同

2.4.2批处理系统的调度

先来先服务first-come first-served

按照先后顺序的单一队列.

优点:易于理解

缺点:平均周转时间较长

最短作业优先shortest job first:顾名思义

优点:短作业优先调度

最短剩余时间 shortest remaining time next

2.4.3交互式系统中的调度

轮转调度round robin

每个进程被分配一个时间片quantum 允许该进程在该时间片内运行,结束时还在运行就剥夺,并切换

时间片的长度是关键因素

优先级调度

考虑外部因素,给进程设置优先级,优先级高的先运行

优先级可以静态与动态地设置

多级队列

因为进程切换过多导致切换速度太慢,又或者长时间片的进程影响到响应的时间,因此设置不同优先级的队列拥有不同的时间片.当一个进程用完分配到该级队列的时间片后,会移到下一级.

一个进程最初被分配一个时间片-最高优先级

4 8 16 直到它被完成

最短进程优先
保证调度
彩票调度
公平分享调度(关注不同用户的进程)

2.4.4实时系统中的调度

实时的概念:

硬实时:必须满足绝对的截止时间

软实时:可以容忍错过截止时间.

2.4.5策略与机制分离

调度算法以某种形式参数化

2.4.6线程调度

用户级线程与内核级线程差别在于性能.用户级线程切换只需少量指令,内核及线程需要完整的上下级切换

用户级线程可自定义线程调度程序

2.5经典IPC问题

2.5.1 哲学家进餐的同步问题-互斥访问有限资源

问题描述:

五个哲学五把叉子五盘食物,进食需要两把叉子,哲学家两种交替活动：吃饭、思考。吃饭时拿起相邻的两把叉子，每次拿一把，没有先后顺序，和吃就思考。

饥饿starvation：所有程序不停地运行，但没有进展。哲学家同时拿到左叉子，查看又叉子是否可用，导致一直重复这个过程。

解决：哲学家拿到左叉子后，达不到右叉子时随机等待一段时间

#define N   5
#define Left  (i+N-1)%N 
#define Rgiht (i+1)%N
#define thinking  0
#define hungry 1 //哲学家视图拿起叉子
#define eating 2
typedef int semaphore;
int state[N]  、、跟踪哲学家的状态
semaphore mutex = 1,s[N]; //互斥量 哲学家的信号量

void philosopher(int i)
{
    while(TRUE){

    	}
}
void take_forks(int i)
{
    down(&mutex);
    state[i] = hungry;//记录处于饥饿
    test(i);//尝试拿起两把叉子
    up(&mutex);
    down(&s[i]);//如果拿不到,就阻塞
}
void  put_forks(i)
{
    down(&mutex);
    state[i] = thingking; //就餐完毕
    test(Left); //检查左边的邻居现在可以吃吗?
    test(right);//检查左边的邻居现在可以吃吗?
    upp(&mutex);
}
void test(i)
{
	if(state[i] == hungry&&state[left]!=eating&&state[right]!=eating)
    {
	state[i] = eating;
        up(&s[i]);
    }
}

2.5.3读者-写者问题（数据库）

问题：

一个飞机订票系统，许多竞争的进程想同时读写一个数据数据库，但一个进程正在写，其他所有进程都不能访问该数据
解决:

typedef int semaohore 
    semaphore mutex =1 ;
semaphore db = 1;
int rc = 0;
void reader(void)
{
    while(TRUE)
    {
		down(&mutex);
        rc = rc+1;
        if(rc==1) down(&db);
        up(&mutex);
        read_data_base();
        
        down(&mutex);
        rc = rc - 1;
        if(rc==0) up(&db);
        up(&mutex);
        use_data_read();
    }
}
void writer(void)
{
    while(TRUE)
    {
        
    thing_up_data;
    down(&db);
    write_data_base();
    up(&db);
    }
}

Exercise

图2-2中给出了三个进程状态。理论上，三个状态之间可以有六种转换，每个状态两个。但图中只给出了四种转换。其余两种转换是否可能发生？
假设要设计一种先进的计算机体系结构，它使用硬件代替中断来完成进程切换。进程切换时CPU恁要哪些信息?i行描述用硬件完成进程切换的工作过程。
当代计算机中，为什么中断处理程序至少有一部分是由汇编语言编写的？
中断或系统调用把控制权转交给操作系统时，为什么通常会用到与被中断进程的栈分离的内核栈？
考虑一个6级多道程序系统（内存中可同时容纳6个程序）。假设每个进程的I/0等待占40%,那么CPU利用率是多少？
假设要从互联网上下载一个2GB大小的文件，文件内容可从一组镜像服务器获得，每个服务器可以传输文件的一部分。假设每个传输访求给定起始字节和结束字节。如何用多线程优化下载时间？
为什么图2-lla的模型不适用千在内存中使用高速缓存的文件服务器？每个进程可以有自己的高速缓存吗？
图2-2中给出了三个进程状态。理论上，三个状态之间可以有六种转换，每个状态两个。但图中只给出了四种转换。其余两种转换是否可能发生？

请添加图片描述

Blocked to Running: I/O is blocked but it can be running directly.

Ready to Blocked: Can not. Because only running processes can be blocked when they run on the CPU but Ready processes don’t use CPU. CPU use schedule procedure to do it .

假设要设计一种先进的计算机体系结构，它使用硬件代替中断来完成进程切换。进程切换时CPU恁要哪些信息?请描述用硬件完成进程切换的工作过程。

搞清楚进程切换需要做什么
切换进程本身的动作,进程调度
信息保存到堆栈/寄存器
取出进程的信息完成进程切换
哪些硬件分别来完成哪些动作
寄存器保存指向进程表的指针
I/O完成,CPU保存当前机器状态到当前进程表项
中断向量指向中断设备,并获取另一个进程的进程表项

当代计算机中，为什么中断处理程序至少有一部分是由汇编语言编写的？

汇编语言更低级,速度快可以直接访问CPU,一些高级语言不可以

中断或系统调用把控制权转交给操作系统时，为什么通常会用到与被中断进程的栈分离的内核栈？

内核栈保存了内核的状态信息, 如果将其信息保存到用户栈则用户可能获得其他进程信息

用户栈满了或者写入程序错误不会使OS崩溃

8.考虑一个6级多道程序系统（内存中可同时容纳6个程序）。假设每个进程的I/0等待占40%,那么CPU利用率是多少？

1-0.4^6 先计算CPU无法被利用:每个进程都在I/O 减去即可

9.假设要从互联网上下载一个2GB大小的文件，文件内容可从一组镜像服务器获得，每个服务器可以传输文件的一部分。假设每个传输访求给定起始字节和结束字节。如何用多线程优化下载时间？

连接可以被多个线程共享,客户端创建多个线程,每个线程分别获取路径文件的一部分从这个镜像服务器

10.为什么图2-lla的模型不适用于在内存中使用高速缓存的文件服务器？每个进程可以有自己的高速缓存吗？

请添加图片描述

a图是单线程进程,资源不共享.要想需要保持文件系统的一致性,需要进行加锁等,防止读写错误

11.当一个多线程进程创建子进程时，如果子进程复制父进程的所有线程，就会出现问题：假如父进程中有一个线程正在等待键盘输入，现在就有两个线程在等待键盘输入，父进程和子进程各有一个。这种问题在单线程进程中也会发生吗？

不会如果一个单线程进程在阻塞,不可能有余力创建子进程

12.图2-8给出了一个多线程Web服务器。如果读取文件只能使用阻塞的read系统调用，那么Web服务器应该使用用户级线程还是内核级线程？为什么？

对于阻塞的read系统调用,如果是用户及线程,整个进程都会被阻塞,多线程被阻止,但内核级线程允许线程阻塞而不会影响其他线程

14.既然计算机中只有一套寄存器，为什么图2-12中的寄存器集合是按每个线程列出而不是按每个进程列出？

当一个线程阻塞时,该个线程信息会保存到寄存器中,

当一个进程停止时,会保存所有线程到寄存器,不是最小单位.

16.线程可以被时钟中断抢占吗？如果可以，在什么情形下可以？如果不可以，为什么不可以？

用户级线程不可用被抢占,中断时整个进程都会终止

内核级线程可以被单独抢断,比如一个线程运行太久,就会被抢占.

18.在用户态实现线程的最大优点是什么？最大缺点是什么？

优点:高效率,切换快,不用陷入内核进行切换

缺点:一个线程阻塞,整个进程也阻塞

27.在使用线程的系统中，若使用用户级线程，是每个线程一个栈还是每个进程一个栈？如果使用内核级线程呢？诮解释。

对于用户级线程:每个进程一个栈

对于内核级线程:所有线程一个栈

正确答案:每个线程都有自己的栈存储变量与返回值等

31.一个可以屏蔽中断的操作系统如何实现信号量？

屏蔽中断后读取信号量的值,如果down后为0,他会将调用的进程放在阻塞进程中.如果up,查找阻塞进程的信号量,如果有不为0,从阻塞态移除并运行,中断打开

33如果一个系统只有两个进程，可以使用一个屏陎来同步这两个进程吗？为什么？

可以使用, 效果比较好,因为只需要等待一个进程

34如果线程在内核态实现，可以使用内核信号量对同一个进程中的两个线程进行同步吗？如果线程在用户态实现呢？假设其他进程中没有线程需要访问该信号量。请解释你的答案。

无论是内核信号量还是用户信号量都需要对于访问信号量的线程进行阻塞.

对于内核线程,一个线程访问信号量被阻塞,仍然可以切换到另一个线程运行

而用户态线程在进行线程同步时,一个线程肯定需要被阻塞,因此整个进程都被阻塞,无法同步

36一个快餐店有四类雇员：(1)领班，接收顾客点的菜单；(2)厨师，准备饭菜；(3)打包员，将饭菜装在袋子里；(4)收银员，将食品袋交给顾客并收钱。每个雇员可被看作一个可以进行通信的串行进程，那么进程间通信模型是什么？请将这个模型与UNIX中的进程联系起来。

通信的是菜单,饭菜,袋子,UNIX中四个进程是由管道连接起来的

42请说明在Round-robin调度算法中时间片长度和上下文切换时间是怎样相互影响的．

时间片过长轮询时间造成浪费

时间片过短可能无法完成上下文切换

45有5个批处理作业A~E,它们儿乎同时到达一个计算中心。估计它们的运行时间分别为10、6、2、4和8分钟。其优先级（由外部设定）分别为3、5、2、1和4,其中5为最高优先级。对千下列每种调度算法，计算其平均进程周转时间，可忽略进程切换的开销。
(a)轮转法

同时到达,无特殊顺序就从A开始

R1:ABCDE R2:ABCDE R3:ABDE R4:ABDE R5:ABE R6:ABE R7:AE R8:AE R9:A R10:A

轮转法要点: 作业结束时间是在作业结束的那一轮的结束时间,不是他本身结束的时间

A:5+5+4+4+3+3+2+2+1+1=30

B:554433=24

C:55=10

D:5544=18

E:55443322=28

平均周转时间:22

(b)优先级调度

优先级高的先做完,优先级顺序B6E8A10C2D4

6+6+8+6+8+10+6+8+10+2+6+8+10+2+4 / 5= 18.8

10+16+18+22+30 / 5=19.2

(d)最短作业优先

2 6 12 20 30 /5=14

对于(a),假设系统具有多道程序处理能力，每个作业均公平共享CPU时间1对千(b)~(d),假设任一时刻只有一个作业运行，直到结束。所有的作业都是CPU密集型作业。

46运行在CTSS上的某个进程需要30个时间片才能完成。该进程必须被调人多少次（包括第一次，即在该进程运行之前）？

什么是CTSS:多级队列

第一次 1 接下来 2 4 8 15(16)最后没到16就被执行完毕一共5次