进程概念

在多道程序环境下，允许多个程序并发执行，因此失去封闭性并具有间断性和不可再现性的特征，为此引入进程，更好地描述和控制程序的并发执行，实现操作系统的并发性和共享性。

进程控制块(PCB)：描述进程的基本情况和运行状态，进而控制和管理进程。

PCB是进程存在的唯一标志。创建进程实质是创建PCB，撤销进程实质是撤销PCB。

进程映像：由程序段、相关数据段、PCB组成。

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

特征

• 动态性：进程是程序的一次执行，具有生命周期。动态性是进程最基本的特征。
• 并发性、独立性、异步性、结构性

进程的状态与转换

进程创建过程

终端用户登录、作业调度、系统提供服务、用户程序的应用等请求都会引起进程的创建。

1. 为新进程分配唯一的进程标识号，申请空白的PCB；
2. 为进程分配资源，分配进程的程序、数据和用户栈必要的内存空间；
3. 初始化PCB，初始化标志信息、处理机状态信息、处理机控制信息、设置进程优先级；
4. 将新进程插入到就绪队列等待调度；

进程终止过程

正常结束、异常结束(存储区越界、保护错、非法指令、特权指令错、I/O故障)、外界干预等都会引起进程的终止。

1. 根据被终止进程标识符检索PCB，读取该进程的状态；
2. 若被终止的进程处于执行状态则立即终止，将处理机资源分配给其他进程；
3. 若有子进程，将其所有的子进程终止；
4. 释放该进程的所有资源；
5. 将PCB从所在队列中删除

进程的创建、撤销以及要求系统设备完成的I/O操作都是利用系统调用而进入内核。

进程的切换

1. 保存处理机上下文，包括程序计数器和其他寄存器；
2. 更新PCB信息；
3. 进程的PCB移入相应的队列，如就绪、阻塞；
4. 选择另一个进程，并更新其PCB；
5. 更新内存管理的数据结构；
6. 恢复处理机上下文；

进程的通信

• 共享存储

  通过对共享空间进行读写操作实现进程间的信息交换

• 消息传递

  进程间的数据交换以格式化的消息为单位

• 管道通信

  消息传递的特殊方式，所谓管道是指连接一个读进程和一个写进程以实现进程之间通信的一个共享文件。

  写进程以字符流的形式将大量的数据写入管道。

线程

线程是基本的CPU执行单元，线程是进程中的一个实体，是被系统独立调度和分派的基本单位。线程不拥有系统资源，只拥有在运行中必不可少的资源，可与同属同一进程的其他线程共享进程所拥有的全部资源。同一进程中的多个线程可以并发执行。

在传统操作系统中，拥有资源和独立调度的基本单位都是进程，引入多线程的操作系统中，线程是独立调度的基本单位，进程是拥有资源的基本单位。

处理机调度

处理及调度是对处理机进行分配，即从进程就绪队列中按照一定的算法选择进程并为其分配处理机，以实现进程并发执行。

调度层次

• 作业调度：只调入/调出一次；
• 中级调度：内存调度，提高内存利用率和系统吞吐量，进程的挂起/就绪；
• 进程调度：按照某种算法调度进程执行；

进程调度和切换程序是操作系统的内核程序。

进程调度方式

• 非剥夺方式/非抢占方式：一旦将CPU分配给某个进程，只有当该进程执行完或转换到等待状态时才会进行进程的切换。实现简单、开销小，适用于大多数批处理系统，但不适用于实时和分时系统。
• 剥夺调度方式/抢占方式：若有某个更紧迫的进程需要调度，则立即暂定正在运行的进程，将处理机分配给更为紧迫的进程。剥夺原则：优先权、短进程优先、时间片原则。

调度的基本原则

1. CPU利用率

2. 系统吞吐量：单位时间内CPU完成的作业数量；

3. 周转时间：作业提交到作业完成的时间；

   周转时间 = 作业完成时间 - 作业提交时间

   带权周转时间 = $\frac{作业周转时间}{作业实际运行时间}$

4. 等待时间

5. 响应时间

调度算法

• 先来先服务(FCFS)调度算法：每次从就绪队列中选择最先进入该队列的进程进行执行，直到进程完成或因某种原因阻塞才释放处理机；算法简单、效率低，对长作业有利，利于CPU繁忙型作业、不利于I/O繁忙型作业。

• 短作业优先(SJF)调度算法：每次从就绪队列中选择一个估计运行时间最短的进程进行执行。对长作业不利、未考虑作业紧迫度，平均等待时间、平均周转时间最少。

• 优先级调度算法：每次从就绪队列中选择优先级最高的进程进行执行。

• 高响应比优先调度算法：同时考虑每个进程的等待时间和估计的运行时间，在进行进程调度前先计算就绪队列中每个进程的响应比，选择响应比最高的进程进行执行。

  响应比$R_p=\frac{等待时间+要求服务的时间}{要求服务的时间}$

• 时间片轮转调度算法：总是选择就绪队列中第一个进程进行执行(先来先服务)，但仅能运行一个时间片，时间片用完即使进程并未完成运行，也必须释放处理机给下一个就绪进程。被剥夺的进程则重新排队，等待调度。

• 多级反馈队列调度算法：

  1. 设置多个队列，赋予每个队列不同的优先级，第1级队列优先级最高，依次降低;
  2. 赋予每个队列不同的进程执行时间片，第1级队列时间片最短，依次递增；
  3. 新进程首先进入第1级队列末尾排队，按照先来先服务调度算法等待调度，若该进程能在第1级的时间片内完成，则撤离系统，否则转入下一级队列末尾排队，依次类推。
  4. 仅当第1级队列为空时才调度第2级队列的进程执行，依次类推。若处理正在执行第$i$级队列中的进程，当新进程进入优先级较高的$i-1$级别队列时，则新进程抢占处理机，当前第$i$级进程转入第$i$级末尾重新排队。

进程同步

协调进程之间互相制约的关系。

1. 临界资源：一次仅允许一个进程使用的资源称为临界资源。对临界资源的访问必须互斥进行。
2. 同步：需要在某些位置上协调进程之间的工作次序而等待、传递信息所产生的制约关系。

3. 互斥：当一个进程使用临界资源时，其他要求进入临界区的进程必须等待。

   准则：

• 空闲让进：临界区空闲时，允许一个请求进入临界区的进程立即进入临界区
• 忙则等待：当已有进程进入临界区，其他试图进入临界区的进程必须等待
  • 有限等待：对访问请求的进程，应保证在有限时间内进入临界区
• 让权等待：当进程不能进入临界区时，应立即释放处理器，防止进程忙等待

互斥的基本方法

1.软件实现方法

单标志法

设置公用整型变量turn,用于指示被允许进入临界区的进程编号，进程必须交替进入临界区，否则违背空闲让进

//P0进程
while(turn!=0); //等待
critical section;//临界区
turn = 1;
remainder section;
//P1进程
while(turn!=1); //等待
critical section;//临界区
turn = 0;
remainder section;

双标志法

设置$flag[k]$,进入临界区前先检查进程$P_k$是否进入临界区,进程之间不需要交替进入，缺点为进程$p_i和p_j$可能同时进入临界区，违背忙等待

//Pi进程
while(flag[j] == true); //等待
flag[i] = true;
critical section;//临界区
flag[i] = false;
remainder section;
//Pj进程
while(flag[i] == true); //等待
flag[j] = true;
critical section;//临界区
flag[j] = false;
remainder section;

设置$flag[k]$,进入临界区前先设置本身进程标志为true,再检查进程$P_k$是否进入临界区,缺点是由于进程互相“谦让”容易形成饥饿现象，即进程都无法进入临界区

//Pi进程
flag[i] = true;
while(flag[j] == true); //等待
critical section;//临界区
flag[i] = false;
remainder section;
//Pj进程
flag[j] = true;
while(flag[i] == true); //等待
critical section;//临界区
flag[j] = false;
remainder section;

Peterson 算法

进入临界区前先设置本身进程标志为true,再设置turn标志，最后检查进程$P_k$是否进入临界区

//Pi进程
flag[i] = true;
turn = j;
while(flag[j] == true && turn == j); //等待
critical section;//临界区
flag[i] = false;
remainder section;
//Pj进程
flag[j] = true;
turn = i;
while(flag[i] == true && turn == i); //等待
critical section;//临界区
flag[j] = false;
remainder section;

2.硬件实现方法

中断屏蔽

CPU只在发生中断时引起进程切换，屏蔽中断能够保证当前运行的进程将临界区的代码顺利执行完毕

硬件指令

TestAndSet指令(原子操作)，为每个临界资源设置共享布尔变量lock,true表示资源正被占用

bool TestAndSet(bool *lock){
    bool old;
    old = *lock;
    *lock = true;
    return old;
}
//进程
while(TestAndSet(&lock)) //等待
critical section;//临界区
lock = false;
remainder section;

Swap指令

Swap(bool *x,bool *y){
    bool temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
//进程
key = true;//为每个进程设置局部布尔变量
while(key != false) //等待
    Swap(*lock,&key)
critical section;//临界区
lock = false;
remainder section;

信号量

1.整型信号量：定义为表示资源数目的整型量$S$

//申请资源
wait(S){
    while(S <= 0);
    S = S-1;
}
//释放资源
signal(S){
    S = S+1;
}

2.记录型信号量：定义为表示资源数目的整型量$value$和进程链表$L$(用于链接等待该资源的进程)

typedef struct{
    int value;
    struct process *L;
}semaphore;

//申请资源
void wait(semaphore S){
    S.value--;
    if(S.value < 0){
        add this process to S.L;
        block(S.L);//进程阻塞，放弃处理机
    }
}
//释放资源
void signal(semaphore S){
    S.value++;
    if(S.value <= 0){//仍有进程等待
        remove a process P from S.L;
        wakeup(P);//唤醒进程
    }
}

利用信号量实现进程同步

//进程Py中的y语句需要使用进程Px中x语句的运行结果
semaphore S = 0；
Px(){
    ...
    x；
    singal(S);//通知进程Py,语句x已完成
    ...
}
Py(){
    ...
    wait(S);//检查语句x是否已完成
    y；
    ...
}

利用信号量实现进程互斥

semaphore S = 1;//初始化信号量 资源数量
Px(){
    ...
    wait(S);//访问资源，加锁
    x；//临界区
    singal(S);//访问结束，解锁
    ...
}
Py(){
    ...
    wait(S);//访问资源，加锁
    y；//临界区
    singal(S);//访问结束，解锁
    ...
}

利用信号量实现前驱关系

$a:S1 \rightarrow S2,b:S1\rightarrow S3;c:S2 \rightarrow S4,d:S2\rightarrow S5;$

$e:S3 \rightarrow S6,f:S4\rightarrow S6,g:S5 \rightarrow S6$

semaphore a=b=c=d=e=f=g=0;//
S1(){
    ...
    singal(a);singal(b);//S1完成
}
S2(){
    ...
    wait(a);
    ...
    singal(c);singal(d);//S2完成
}
S3(){
    ...
    wait(b);
    ...
    singal(e);//S3完成
}
S4(){
    ...
    wait(c);
    ...
    singal(f);//S4完成
}
S5(){
    ...
    wait(d);
    ...
    singal(g);//S5完成
}
S6(){
    wait(e);
    wait(f);
    wait(g);
    ...
}

经典同步问题

1. 生产消费者问题

   semaphore mutex = 1;//临界区互斥信号量
   semaphore empty = n;//空闲缓冲区数
   semaphore full = 0;//满缓冲区数
   //生产者进程
   producer(){
       while(true){
           produce an item in nextp;
           wait(empty);//获取空缓冲区单元
           wait(mutex);//进入临界区
           add nextp ti buffer;//将数据放入缓冲区
           singal(mutex);
           singal(full);
       }
   }
   //消费者进程
   consumer(){
       while(true){
           wait(full);
           wait(mutex);
           remove an item from buffer;
           singal(mutex);
           singal(empty);
           consume the item;
       }
   }
   //empty和full的wait操作必须在mutex前
   

1. 读者-写者问题

   • 允许多个读者同时对共享文件进行读操作
   • 只允许一个写者向共享文件写数据
   • 写者完成写操作之前不允许其他读者进行读操作
   • 写者执行写操作之前，应让已有读者和写者全部退出

   //读进程优先
   int count = 0;//当前读者数量
   semaphore mutex = 1;//用于更新count时的互斥
   semaphore rw = 1;//互斥访问共享文件
   //写者进程
   writer(){
       while(true){
           wait(rw);
           writing;
           signal(rw);
       }
   }
   //读者进程
   reader(){
       while(true){
           wait(mutex);
           if(count == 0)//第一个读者读取时
               wait(rw);//阻止写进程写操作
           count++;
           signal(mutex);
           reading;
           wait(mutex);//读取完毕
           count--;
           if(count == 0)//当最后一个读进程读取完毕
               signal(rw)
           signal(mutex);
       }
   }
   

   //写进程优先
   int count = 0;//当前读者数量
   semaphore mutex = 1;//用于更新count时的互斥
   semaphore rw = 1;//互斥访问共享文件
   semaphore w = 1;//用于实现写优先
   //写者进程
   writer(){
       while(true){
           wait(w)
           wait(rw);
           writing;
           signal(rw);
           signal(w);
       }
   }
   //读者进程
   reader(){
       while(true){
           wait(w);//无写进程时进入
           wait(mutex);
           if(count == 0)//第一个读者读取时
               wait(rw);//阻止写进程写操作
           count++;
           signal(mutex);
           signal(w);
           reading;
           wait(mutex);//读取完毕
           count--;
           if(count == 0)//当最后一个读进程读取完毕
               signal(rw)
           signal(mutex);
       }
   }
   

1. 哲学家进餐问题

   semaphore chopstick[5]={1,1,1,1,1};//五根筷子
   semaphore mutex =  1;//设置取筷子的信号量
   //i号哲学家进程
   Pi(){
       do{
           wait(mutex);
           wait(chopstick[i]);//取左边筷子
           wait(chopstick[(i+1]%5);//取右边筷子
           signal(mutex);
           eat;
           signal(chopstick[i]);
           signal(chopstick[(i+1]%5);
           think;
       }
   }
   

1. 吸烟者问题w

   int random;
   semaphore offerTobaccoAndPaper;//烟草和纸
   semaphore offerTobaccoAndGlue;//烟草和胶水
   semaphore offerPaperAndGlue;//纸和胶水
   semaphore finish = 0;//记录抽烟完成
   //供应者进程
   provider(){
       while(true){
           random = rand.random(3);//1-3的整数随机数
           if(random == 1){
               signal(offerTobaccoAndPaper);//提供烟草和纸
           }
           else if(random == 1){
               signal(offerTobaccoAndGlue);//提供烟草和胶水
           }
           else{
               signal(offerPaperAndGlue);//提供纸和胶水
           }
           wait(finish);
       }
   }
   //拥有烟草者进程
   process(){
       while(true){
           wait(offerPaperAndGlue);
           ...
           signal(finish);
       }
   }
   //拥有纸者进程
   process(){
       while(true){
           wait(offerTobaccoAndGlue);
           ...
           signal(finish);
       }
   }
   //拥有胶水者进程
   process(){
       while(true){
           wait(offerTobaccoAndPaper);
           ...
           signal(finish);
       }
   }
   

死锁

定义：多个进程因竞争不可剥夺资源而造成的互相等待，若无外力作用，进程都将无法向前推进。

产生死锁的必要条件(同时满足)

• 互斥条件：某资源仅由一个进程占有
• 不剥夺条件：进程所获得资源在未使用完毕前，不可直接剥夺
• 请求和保持条件：进程已获得资源A，同时提出对资源B的请求，单资源B被其他进程占有，此失请求进程被阻塞，但对其资源A保持不放
• 循环等待条件：$pi$等待的资源被$p{i+1}$占有,$\dots$,$p_n$等待的资源被$p_0$占有

死锁处理策略

1. 预防死锁：设置限制条件，破环产生死锁的必要条件
2. 避免死锁：资源动态分配中，用某种方法防止系统进入不安全状态
3. 死锁检测及解除：允许死锁发生，通过系统检测及时地解除死锁

银行家算法

可利用资源矢量Available：每类资源可用的数目

最大需求矩阵Max：每个进程对每类资源的最大需求

分配矩阵Allocation：每个进程已分配到每类资源数目

需求矩阵Need：每个进程尚需的每类资源数目 $Need = Max - Allocation$

假设系统中有5个进程$p_0,p_1,p_2,p_3,p_4$和三类资源${A,B,C}$,各类资源数目分别为$10、5、7$,在$t_0$时刻资源分配情况如下表，求资源分配安全序列。

1. 求出Need矩阵

   $$\begin{bmatrix} 7 & 5 & 3\\ 3 & 2 & 2\\ 9 & 0 & 2\\ 2 & 2 & 2\\ 4 & 3 & 3 \end{bmatrix}(MAX) - \begin{bmatrix} 0 & 1 & 0\\ 2 & 0 & 0\\ 3 & 0 & 2\\ 2 & 1 & 1\\ 0 & 0 & 2 \end{bmatrix}(Allocation) = \begin{bmatrix} 7 & 4 & 3\\ 1 & 2 & 2\\ 6 & 0 & 0\\ 0 & 1 & 1\\ 4 & 3 & 1 \end{bmatrix}(Need)$$

2. Available向量与Need矩阵各行进行比较，找出比Available向量小的行，如$$

   $$p_1(1,2,2)<(3,2,2)\\p_3(0,1,1)<(3,2,2)$$

   选择$p_1$(或$p_3$)加入安全序列

3. 释放$p_1$所占有的资源，即把$p_1$的Allocation与Available向量相加,等到新的Available向量

   $$(2,0,0)+(3,3,2)=(5,3,2)=Available(new)$$

4. 再用更新后的Available向量和Need向量矩阵重复步骤2

安全序列：$[p_1,p_3,p_4,p_2,p_0]$

版权声明：原创,转载请注明来源,否则律师函警告

---