OS-review2

进程的概念

程序的执行顺序

顺序性

处理机的操作严格按照程序所规定的顺序执行，即每一操作必须在下一操作开始之前结束。

封闭性

程序一旦开始运行，其执行结果不受外界因素影响。因为程序运行时独占系统的各种资源，故这些资源的状态（除初始状态外）只有本程序才能改变。

可再现性

只要程序执行时的初始条件和执行环境相同，当程序重复执行时，都将获得相同的结果。

程序的并发执行

程序的并发执行指若干个程序或者程序段同时在系统中运行，这些程序或程序段在执行时间上是可重叠的，即一个程序运行还没结束，另一个程序已经开始了。

程序并发执行的特征

间断性

程序并发执行时，由于需要共享资源或为完成同一项任务而相互合作，致使并发程序之间形成了相互制约的关系。这些相互制约的关系将导致并发程序具有“执行-暂停-执行”这种间断性的活动规律。

失去封闭性

程序并发执行时，共享系统中的各种资源，这些资源的状态将由多个程序来改变，这将致使程序的运行失去封闭性。因此，某程序执行时，必然会受到其他程序的影响。

不可再现性

不可再现性。程序并发执行时，由于失去了封闭性，也将失去运行结果的可再现性。也就是说，对于同一个程序而言，即使其运行的初始条件相同，但当其被重复执行时其运行结果可能不同。

进程的基本特征

动态性

并发性

使得程序能够并发的执行，能够提高资源的利用率

独立性

进程是一个基本的独立单位

异步性

进程是一个能够独立运行的基本单位

结构特征

为每个进程配置一个进程控制块(PCB)，里面包含着当前进程的信息，为了便于下下次重新执行的时候使用。

进程的状态及其变化

就绪状态(ready)

该进程已经获得除了处理机之外的所有资源，只需获得处理机就可以立马运行

执行状态(run)

当进程获得处理机资源并且在运行的时候，此状态就成为执行状态

阻塞状态(blocked)

正在执行的状态，因为发生某种事件(等待I/O)而无法进行，此状态就成为阻塞状态

进程运行状态图

进程控制块(PCB)

进程控制块包含内容

进程标识符

每个进程都必须有惟一打的标识符，以区别于系统内部的其他进程

进程当前状态

说明进程的当前状态，作为进程调度分配CPU的依据

进程队列指针

用于记录PCB队列中的下一个指针

程序的数据和地址

指出进程的程序和数据所在的内(外)存地址

进程优先级

描述使用CPU的紧迫程度，是进程调度的一个一句

CPU现场保护

将此时CPU的状态信息储存起来(pc,状态寄存器，通用寄存器等)保护现场，以便重新获得CPU的时候恢复原来的PCU现场信息而继续执行。

通信信息

记录进程在执行过程中与与其他进程发生的信息交换

家族关系

指明该进程的父进程，子进程等家族关系

占有资源清单

列出进程所需资源以及当前获得的资源

进程控制

核心态和用户态(user mode or kernel mode)

核心态(kernel mode)

核心态又称管态和系统态，是操作系统管理程序执行时机器所处的状态，具有较高的特权，能执行以切指令，访问所有寄存器和存储区

用户态

用户态又称目态，时用户程序执行时机器所处的状态，它具有较低的权限，执行执行规定的指令，访问指定的寄存器和存储区

进程创建

创建原语的主要功能是为被创建进程形成一个PCB，主要操作是:先向系统申请一个空闲的PCB，并为子进程分配必要的资源，然后将子进程的PCB初始化，并将此PCB插入就绪队列，最后返回一个进程标识号(即子进程的进程标识号，pid)。

进程撤销

一个进程执行完毕后，应该予以撤销，释放资源。撤销进程有两种撤销策略，一种是只撤销指定进程，另一种策略是撤销指定进程及其子孙进程。
撤销原语的主要功能就是收回被撤销进程所占用的所有资源，并撤销它的进程控制块。
主要操作过程:先从PCB集合中找到被撤销进程的PCB，若被撤销的进程正处于执行状态，则立即停止该进程的执行，并设置重新调度的标志，以便进程撤销后将处理机分配给其他进程。对后一种撤销策略，若被撤销进程有子孙进程，还应将该进程的子孙进程予以撤销。对于被撤销进程的所占有资源，或者归还给父进程，或者归还给系统，最后撤销其进程控制块

进程阻塞与唤醒

阻塞原语的作用是将进程由执行状态转为阻塞状态，而唤醒原语的作用则是将进程由阻塞状态变为就绪状态
当一个进程期待某一时间尚未出现时，该进程调用阻塞原语将自己阻塞起来。阻塞原语的主要操作过程:在阻塞一个进程时，由于该进程正处于执行状态
1.应中断处理机，保存该进程的CPU现场，停止运行该进程
2.然后将该进程插入到响应时间的等待队列中
3.再从就绪队列中选择另一个进程投入。
对于阻塞状态的进程，当该进程期待的事件出现时，由发现者进程调用唤醒原语将阻塞的进程唤醒，使其进入就绪状态。唤醒源于的主要操作如下:
1.将被唤醒的进程从相应的等待队列中移出
2.将状态改为就绪并插入就绪队列

当执行状态->阻塞状态时，是进程机子调用阻塞原语取完成，而阻塞->就绪，则是另一个发现者进程调用唤醒原语实现的，一半发现者线程与被唤醒的进程是合作的并发进程。

线程的概念

（1）线程是进程内的一个执行单元。
（2）线程是进程内的一个可调度实体。
（3）线程是程序（或进程）中相对独立的一个控制流序列。
（4）线程是执行的上下文，其含义是执行的现场数据和其他调度所需的信息。
（5）线程是进程内一个相对独立的、可调度的执行单元。
线程自己基本上不用有资源，只拥有在运行时必不可少的一点资源(如程序计数器，一组寄存器和栈)，但它可以与同属一个进程的其他线程共享进程拥有的全部资源。

线程的实现

在只有进程概念的操作系统中可由用户程序利用函数库提供线程的控制机制
还一种做法是同时在操作系统内核和用户程序两个层次上提供线程控制机制。
内核级线程是指依赖于内核，由操作系统内核完成创建和撤销的线程。在支持内核级线程的操作系统中，内核维护进程和线程的上下文信息，并完成线程切换工作。
用户级线程是指不依赖于操作系统核心，由应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制的线程。由于用户级线程的维护由应用进程完成，不需要操作系统内核了解用户级线程的存在，因此可用于不支持内核级线程的多进程操作系统，甚至
是单用户操作系统。

互斥与同步的基本概念

临界资源

概念:我们把一次仅允许一个进程使用的资源成为临界资源

临界资源的访问过程

进入区

进入临界区使用临界资源，进入前要检查是否可进入，若可，则设置正在访问临界区的标志，阻止其他进程同时进入临界区

临界区

进程中访问临界资源的那段代码，又称临界段。

退出区

将正在访问临界区的标志清楚

剩余区

代码中的其余部分

互斥

在操作系统中，如果这两个进程不能同时访问同一个临界资源，则他们之间是互斥关系。

互斥准则

空闲让进

没有进程处于临界区时，可以允许一个请求进入临界区的进程立即进入临界区

忙则等待

当已有进程进入临界区时，其他试图进入临界区的进程必须等待

有限等待。

对要求访问临界资源的进程，应保证能在有限时间内进入临界区

让权等待

当进程不能进入临界区时，应释放处理机

同步

概念:同步时指多个互相合作的进程，在一些关键点上可能需要互相等待或互相交换信息，这种相互制约的关系成为进程同步

利用硬件解决互斥问题

中断屏蔽方法

若一个进程使用处理机执行它的临界代码时，要防止其他进程再进入其临界区访问的最简单方法是进制一切中断的发生。
优点:简单有效
不足:限制了处理机交替执行程序的能力，执行的效率会明显降低。若将关中断的权利交给用户进程，当一个进程关中断后而不再开中断，则系统可能会因此中止

硬件指令方法

TS(Test-ans-Set)

bool TS(bool *lock)
{
    bool old;
    old = *lock;
    *lock=true;
    return old;
}

功能是读出指定标志后把标志设置为真，true 表示正在占用，false 表示空闲，初始值为 false 在进程访问临界资源之前，利用TS指令检查和修改标志lock;若有进程在临界区则重复检查，直到进程退出。

while(TS(&lock))
{
    code segment;
    lock = false;
    remain code;
}

Swap

Swap(boolean *a，boolean *b) 
{ 
 boolean temp; 
 temp = *a; 
 a = *b; 
 *b = temp; 
}

利用Swap指令实现进程互斥的时候，为每个资源设置一个共享布尔变量lock，初始为false，每个进程设置一个局部变量key用于与lock交换信息，在进入临界区之前交换出lock的内容，当交换出来的为false时，就可进入。

key = true; 
while (key!= false) Swap(&lock，&key); 
进程的临界区代码 code segment ; 
lock = false ; 
remain code;

信号量(semaphore)

信号量时一个确定的二元组(S,Q),S是一个非负初值的整形变量，Q是一个初始状态为空的队列。S表示系统中某类资源的数目，当大于0时，表示系统当前可用资源的数目，小于0时，绝对值表示系统中因请求该类资源而被阻塞的进程数目，除了初值，信号量仅能由P操作(Wait)和V操作(Signal)改变。

P操作(Wait)

P(S),其中S是一个信号量，主要操作如下
1.S=S-1
2.若S>=0则进程继续运行；否则阻塞该进程，并将它插入该信号量的等待队列中。

V操作(Signal)

V(s),其中S是一个信号量，主要操作如下:
1.S=S+1;
2.若S>0则进程继续执行，否则从信号量等待队列中移出第一个进程，使其变成就绪状态并插入就绪队列，然后返回原进程继续执行。

利用信号量(semaphore)实现互斥

假设两个进程p1,p2,设置S的初值为1，代码如下，把P和V操作放在临界区的开头和结尾。

int main() 
{ 
 semaphore S=1; 
 cobegin 
 P1(); 
 P2(); 
 coend 
} 
P1() 
{ 
Μ /*“Μ”表示剩余区*/ 
 P(S); 
 进程 P1 的临界区; 
 V(S); 
Μ
} 
P2() 
{ 
Μ
 P(S); 
 进程 P2 的临界区; 
 V(S); 
Μ
}

利用PV操作完成前驱图

观察到只有p2-p6资源互斥，所以我们设置5个信号量，初始值为0。
观察p1,发现由两个子节点，所以执行完p1之后，s1的值应该为2，所以应该v(s1)两次
观察p2,发现需要等待p1执行完毕，所以需要P(s1),等待p1执行完毕，有两个子节点，应该v(s2)两次
······
剩余的以此做法依次类推即可

semaphore f1=0; /*表示进程 P1 是否执行完成*/ 
semaphore f2=0; /*表示进程 P2 是否执行完成*/ 
semaphore f3=0; /*表示进程 P3 是否执行完成*/ 
semaphore f4=0; /*表示进程 P4 是否执行完成*/ 
semaphore f5=0; /*表示进程 P5 是否执行完成*/ 
int main() 
{ 
 cobegin 
 P1(); 
 P2(); 
 P3(); 
 P4(); 
 P5(); 
 P6(); 
 coend 
} 
void P1() 
{ 
Μ /*“Μ”表示进程中的程序代码，下同*/ 
 v(f1); 
 v(f1); 
} 
void P2() 
{ 
 p(f1); 
Μ
 v(f2); 
 v(f2); 
} 
void P3() 
{ 
 p(f1); 
Μ
 v(f3); 
} 
void P4() 
{ 
 p(f2); 
Μ
 v(f4); 
} 
void P5() 
{ 
 p(f2); 
Μ
 v(f5); 
} 
void P6() 
{ 
 p(f3); 
 p(f4); 
 p(f5); 
Μ
}

生产者与消费者关系

semaphore full=0; /*满缓冲单元的数目*/ 
semaphore empty=n; /*空缓冲单元的数目*/ 
semaphore mutex=1; /*对有界缓冲区进行操作的互斥信号量*/ 
main() 
{ 
 cobegin 
 producer(); 
 consumer(); 
 coend 
…
} 
producer() 
{ 
 while(true) 
 { 
 生产一个产品; 
 p(empty); 
 p(mutex); 
 将一个产品送入有界缓冲区; 
 v(mutex); 
 v(full); 
 } 
} 
consumer() 
{ 
 while(true) 
 { 
 p(full); 
 p(mutex); 
 从缓冲区中取一个产品; 
 v(mutex); 
 v(empty); 
 消费一个产品; 
 } 
}

注意：无论在生产者进程还是在消费者进程中，P 操作的次序都不能颠倒，否则将可能造成死锁。

管程

管程在功能上和信号量及PV操作类似，属于一种进程同步互斥工具，但是具有与信号量及PV操作不同的属性。
管程由三部分组成:局部于管程的共享变量说明，对该数据结构进行操作的一组过程以及对局部于管程的数据设置初始值的语句。

管程的基本特性

1.局部于管程的数据只能被局部于管城内的过程所访问。
2.一个进程只有通过调用管程内的过程才能进入管程访问共享数据
3.每次仅允许一个进程在管程内执行某个内部过程。即进程互斥地通过调用内部过程进入管程。

进程通信

低级进程通信方式

进程互斥与同步就是一种进程间的通信方式，由于进程互斥与同步交换的信息量较少且效率较低，因此称这两种同学新方式为低级进程通信方式，P,V成为低级进程通信原语。

高级进程通信方式

目前，高级进程通信方式可分为:共享存储器系统，消息传递系统以及管道通信系统。

共享存储器系统

为了传输大量数据，在存储器划出一块共享存储器，各个进程可以用过对共享存储区进行读写实现通信。
细节:再通信前，进程向系统申请建立一个共享存储区，并指定该共享存储区的关键字，若该共享存储区已经建立，则将该共享存储区的描述符返回给申请者，然后申请者把获得的共享存储区附接到本进程的地址空间上。

消息传递系统

进程间的数据交换以信息为单位，程序员使用系统提供的一组通信命令(原语)来实现通信。

直接通信方式

发送进程直接把信息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列取得消息。

间接通信方式

发送进程把消息发到某个中间实体中，接收进程从中间实体中取得消息，

管道通信系统

管道是用于连读进程和写进程以实现它们之间通信的共享文件，向管道提供输入的发送进程(即写进程)以字符流形式将大量的数据送入管道，而接收管道输出的接收进程

消息缓冲通信