本文共 8895 字,大约阅读时间需要 29 分钟。
目录
一、进程的概念和特征
1. 进程的概念
在多道程序环境下,允许多个程序并发执行,此时他们将失去封闭性,并具有间断性和不可再现性的特征。为此引入了进程的概念,以便更好地描述和控制程序的并发执行,实现操作系统的并发性和共享性。
为了使参与并发执行的程序能独立运行,必须为之配置一个专门的数据结构,称为进程控制块(Process Control Block, PCB)。系统利用PCB来描述进程的基本情况和运行状态,进而控制和管理进程。相应的,由程序段、相关数据段和PCB三部分构成了进程映像(也称进程实体),所谓创建进程,实质上就是创建进程映像中的PCB;而撤销进程,实质上就是撤销进程的PCB。值得注意的是,进程映像是静态的,而进程是动态的。
注意:PCB是进程存在的唯一标志。
传统操作系统中的进程可以定义为:进程是进程实体(即进程映像)的运行过程,是系统进行资源分配和调度的一个独立单位。
2. 进程的状态
进程通常有以下五种状态:
(1)创建状态:进程正在被创建,尚未到达就绪状态。
(2)就绪状态:进程已处于准备运行状态,即进程已获得除了处理器之外的一切所需资源,一旦得到处理器资源(处理器分配的时间片)即可运行。
(3)运行状态:进程正在处理器上运行(单核 CPU 下任意时刻最多只有一个进程处于运行状态)。
(4)阻塞状态:又称为等待状态,指进程正在等待某一事件而暂停运行,如等待某资源为可用或等待 IO 操作完成。此时即使处理器空闲,该进程也不能运行。
(5)结束状态:进程正在从系统中消失。可能是进程正常结束或其他原因中断退出运行。
3. 进程控制
3.1 进程创建
允许一个进程创建另一个进程,此时创建者称为父进程,被创建的进程称为子进程。子进程可以继承父进程的所有资源,当子进程被撤销时,应将其从父进程那里获得的资源归还给父进程。此外,在撤销父进程时,也必须同时撤销其所有子进程。
注意,在Linux系统中,创建子进程的方法是使用系统调用fork()函数。具体可以参考 。
3.2 进程终止
引起进程终止的事件主要有:正常结束、异常结束和外界干预三种。
- 正常结束:表示进程的任务已经完成且准备退出运行;
- 异常结束:表示进程在运行时,发生了某种异常事件,使程序无法继续运行,如存储区越界、I / O故障等;
- 外界干预:指进程应外界的请求而终止运行,如操作员干预、父进程请求或父进程终止等。
3.3 进程的阻塞和唤醒
正在执行的进程由于期待的某些事件未发生,如请求系统资源失败、等待某种操作的完成等,则由系统自动执行阻塞原语,使自己由运行状态变为阻塞状态。可见,进程的阻塞是进程自身的一种主动行为,也因此,只有处于运行态的进程才能将其转化为阻塞状态。
当被阻塞的进程所期待的事件出现时,则由相关进程调用唤醒原语将等待该事件的进程唤醒。
需要注意的是,阻塞原语和唤醒原语是一对作用刚好相反的原语,必须成对使用。阻塞原语是由被阻塞进程自我调用实现的,而唤醒原语则是由一个与被唤醒进程相合作或被其他相关的进程调用实现的。
3.4 进程在操作系统中的状态(用户态、内核态)
进程在操作系统上运行的状态可以分为两种:用户态和内核态。
用户态是指进程在执行用户自己的代码,这个时候CPU访问资源是受限的,程序不能直接访问操作系统内核中的数据。
内核态是指进程在内核代码中执行,这时候CPU可以访问任何计算机资源。
进程从用户态切换到内核态的方式:
(1)系统调用:这是用户态进程主动要求从用户态切换到内核态的方式,用户态进程通过系统调用申请使用内核态中的程序完成任务。系统调用的核心机制是使用操作系统为用户特别开放的一个中断来实现。
(2)异常:当CPU在执行运行在用户态下的进程时,若发生了异常(如缺页异常),就会触发由当前运行进程切换到处理此异常的内核相关程序中,也即切换到内核态中了。
(3)外围设备的中断:当外围设备完成用户请求的操作后,会向CPU发出相应的中断信号,这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序,如果先前是在用户态下进行的,那么自然就要发生用户态到内核态的切换,
注意:
对于大多数进程来说,其创建、撤销等都是利用系统调用而进入内核,再由内核中相应的处理程序完成的。
二、进程调度算法
进程调度的主要任务是按照某种方法和策略从就绪队列中选取一个进程,将处理器分配给它。下面介绍几种常用的调度算法:
1. 先来先服务(FCFS)调度算法
FCFS是一种最简单的调度算法(属于不可剥夺算法),它每次从就绪队列中选择最先进入该队列的进程,将处理器分配给它。
特点:
- 算法简单,但效率低;
- 对长进程有利,但对短进程不利(因为若一个长进程先到达,就会使后面许多短进程等待很长时间);
- 有利于CPU繁忙型进程,但不利于I/O繁忙型进程;
- 不适用于分时系统或实时系统。
2. 短进程优先(SPF)调度算法
它每次从就绪队列中选择一个估计运行时间最短的进程,将处理器分配给它。
特点:
- SPF是平均等待时间最少的进程调度算法。
缺点:
- 对长进程不利,可能造成长进程出现“饥饿”现象;
- 未考虑进程的紧迫程度;
3. 时间片轮转调度算法
此算法的系统将所有就绪进程按到达时间的先后次序排成一个队列,调度时总是选择排好序后就绪队列中的第一个进程,即按照先来先服务的原则进行选择,但是不同的是,每个进程只能运行一个时间片(如100ms)。在使用完一个时间片后,即使进程并未完成,它也必须释放处理器资源。
特点:
- 属于剥夺算法;
- 适用于分时系统。
4. 优先级调度算法
此算法需要为每个进程分配优先级,每次从就绪队列中选择具有最高优先级的进程。具有相同优先级的进程以 FCFS 方式选择。可以根据内存要求,可以根据时间要求或任何其他资源要求来确定优先级。
5. 多级反馈队列调度算法
此算法可以看成是时间片轮转调度算法和优先级调度算法的综合,通过动态调整进程优先级和时间片大小来实现。具体实现思想如下:
(1)应设置多个就绪队列,并为各个队列赋予不同的优先级,从第1级到第n级的优先级逐次降低;
(2)赋予各个队列中进程执行时间片的大小也各不相同,在优先级越高的队列中,进程运行的时间片越小;
(3)当一个进程进入内存后,先将它放入第一级队列的末尾,按FCFS原则排队,当轮到该进程执行时,若它能在该时间片内完成,便可准备撤离;若不能,则将该进程转入第二级队列的末尾等待...依次执行;
(4)仅当第1级队列为空时,调度程序才调度第2级队列中的进程;仅当第1 ~(i - 1)级队列均为空时,才会调度第 i 级队列中的进程。若处理器正在执行第 i 级队列中的某进程时,又有新进程进入优先级较高的队列,那么新进程将抢占处理器,调度程序会把正在进行的进程放回到第 i 级队列的末尾。
举一个例子:
有一个进程需要100个时间片才能执行完,如果采用时间片轮转调度算法,那么需要交换100次才能执行完。此时,多级队列的每个时间片大小为1、2、4、8、16... 进程在第一个队列没执行完,就会被移到下一个队列,这样,该进程只需要交换7次即可。
三、进程通信
1. 进程通信的概念
每个进程各自有不同的用户地址空间,任何一个进程的全局变量在另一个进程中都看不到,所以两个进程之间要交换信息必须通过内核,在内核中开辟一块缓冲区,进程 1把数据从用户空间拷贝到该缓冲区,进程 2再从该缓冲区把数据读走,如图3-1所示。这种机制就叫做进程间通信。
图3-1 进程间通信模型
2. 进程通信方式
进程通信通常有以下六种方式:
(1)管道 / 匿名管道(Pipe)
管道的实质是一个内核缓冲区,进程以先入先出的方式从缓冲区存取数据,管道一端的进程顺序的将数据写入缓冲区,另一端的进程则顺序的读出数据。
特点:
- 数据只支持单向传输,需要双方通信时,需要建立起两个管道;
- 只能用于具有亲缘关系的进程之间(如父子进程或兄弟进程);
(2)有名管道(FIFO)
匿名管道,由于没有名字,只能用于亲缘关系的进程间通信。为了克服这个缺点,提出了有名管道(FIFO)。有名管道不同于匿名管道之处在于它提供了一个路径名与之关联,以有名管道的文件形式存在于文件系统中,这样,即使与有名管道的创建进程不存在亲缘关系的进程,只要可以访问该路径,就能够彼此通过有名管道相互通信,因此,通过有名管道不相关的进程也能交换数据。
值得注意的是,有名管道严格遵循先入先出,对匿名管道及有名管道的读总是从开始处返回数据,对它们的写则把数据添加到末尾。它们不支持诸如lseek()等文件定位操作。有名管道的名字存在于文件系统中,内容存放在内存中。
(3)消息队列消息队列是存放在内核中的消息链表,与管道相比,消息队列可以独立于读写进程存在,并且读进程可以根据消息类型有选择地接收信息,而不像管道那样只能默认接收。
(4)信号量
信号量是一个计数器,用于多进程对共享数据的访问,信号量的意图在于进程间同步。这种通信方式主要用于解决与同步相关的问题并避免竞争条件。
(5)共享内存
为了在多个进程间交换信息,内核专门留出了一块区域,该区域允许多个进程直接读写。不同进程可以及时看到对方进程对共享内存中数据的更新。这种方式需要依靠某种同步操作,如互斥锁和信号量等。
因为数据不需要在进程间复制,所以这是最快的一种进程通信方式。
(6)套接字
此方法主要用于不在同一台计算机但通过网络连接计算机上的进程进行通信。
此部分更详细的资料可以参考:。
四、进程同步
这里注意区分一下进程同步和进程通信:
- 进程通信:进程间传输信息;
- 进程同步:控制多个进程按一定顺序执行。
进程通信是一种手段,而进程同步是一种目的。也可以说,为了能够达到进程同步的目的,需要让进程进行通信,传输一些进程同步需要的信息。
1. 进程同步的相关概念
临界资源:这里的资源指的是多个进程可以共享的资源,共享有互斥共享和同步共享两种方式,而互斥共享的资源就称为临界资源,互斥共享就是同一时刻只能有一个进程访问该资源。
临界区:对临界资源进行访问的那段代码。
同步:多个进程因为合作产生的直接制约关系,使得进程有一定的先后执行关系。
互斥:多个进程在同一时刻只有一个进程能进入临界区。
2. 进程同步的方式
信号量(Semaphore):
信号量是一个整型变量,它允许同一时刻多个进程访问同一资源,但是需要控制同一时刻访问此资源的最大进程数量。操作系统可以对信号量执行 down和 up操作,也就是 P和 V操作:
- down : 如果信号量大于 0 ,执行 -1 操作;如果信号量等于 0,进程睡眠,等待信号量大于 0;
- up :对信号量执行 +1 操作,唤醒睡眠的进程让其完成 down 操作。
如果信号量的取值只能为 0 或者 1,那么就成为了 互斥量(Mutex) ,0 表示临界区已经加锁,1 表示临界区解锁。
五、死锁
1. 死锁的概念
死锁是指两个或两个以上的进程在执行过程中,因争夺资源而造成的一种互相等待的现象,若没有外力作用,它们都将无法继续执行。这种现象称之为死锁。
2. 产生死锁的四个必要条件
(1)互斥条件:竞争的资源在同一时刻只能由一个进程使用。
(2)请求与保持条件:进程因请求资源而阻塞时,对已获得的资源不放。
(3)不剥夺条件:进程所获得的资源在用完之前,不能被其他进程强行夺走。
(4)循环等待条件:若干进程之间形成了头尾相接的循环等待链,链中每一个进程已获得的资源同时被下一个进程所请求。
3. 死锁的处理策略
(1)预防死锁:即破坏死锁产生的条件,在死锁发生前进行预防工作。
- 互斥条件:大多情况下无法破坏,因为这是操作系统部分资源本身的特性。
- 请求保持条件:可以在运行前一次性申请所有资源。
- 不剥夺条件:当进程请求新的资源得不到满足时,它必须立即释放保持的所有资源。
- 循环等待条件:可采用顺序资源分配法,给系统中的资源进行编号,规定所有进程必须按照编号递增的顺序请求资源。
(2)避免死锁:不破坏死锁产生的条件,而是在资源分配过程中,用某种算法判断防止系统进入不安全状态,比如银行家算法。(此方法会导致系统开销增加)
(3)死锁检测和解除:前面两种都是死锁产生之前的策略。死锁检测是利用检测系统检测当前系统是否处于死锁状态(一种有效的方式是检测有向图中是否存在环),并确定当前死锁相关的进程和资源,执行死锁解除策略。死锁解除主要的方式就是剥夺,即将进程所占的资源强行收回,分配给其他资源。
4. 死锁实例
//死锁class DeadLockDemo{ static class MyThread1 implements Runnable{ private Object o1 = new Object(); private Object o2 = new Object(); public MyThread1(Object o1, Object o2){ this.o1 = o1; this.o2 = o2; } @Override public void run(){ synchronized (o1){ System.out.println(Thread.currentThread().getName() + "已持有锁o1"); try{ Thread.sleep(200); //睡眠一段时间是为了确保线程thread2可以先获取锁o2 }catch (InterruptedException e){ e.printStackTrace(); } synchronized (o2){ //争夺锁o2 System.out.println(Thread.currentThread().getName() + "已持有锁o2"); } } } } static class MyThread2 implements Runnable{ private Object o1 = new Object(); private Object o2 = new Object(); public MyThread2(Object o1, Object o2){ this.o1 = o1; this.o2 = o2; } @Override public void run(){ synchronized (o2){ System.out.println(Thread.currentThread().getName() + "已持有锁o2"); try{ Thread.sleep(200);//睡眠一段时间是为了确保线程thread1可以先获取锁o1 }catch (InterruptedException e){ e.printStackTrace(); } synchronized (o1){ //争夺锁o1 System.out.println(Thread.currentThread().getName() + "已持有锁o1"); } } } } public static void main(String[] args) { Object o1 = new Object(); Object o2 = new Object(); Thread thread1 = new Thread(new MyThread1(o1, o2)); Thread thread2 = new Thread(new MyThread2(o1, o2)); thread1.start(); thread2.start(); }}
上述实例执行结果如下:
可知已经陷入死锁状态
可以使用等待/通知机制来解决上述死锁问题,代码如下:
//上述死锁例子的解决class SolveDeadLockDemo{ static class MyThread1 implements Runnable{ private Object o1 = new Object(); private Object o2 = new Object(); public MyThread1(Object o1, Object o2){ this.o1 = o1; this.o2 = o2; } @Override public void run() { synchronized (o1){ try{ Thread.sleep(200); System.out.println(Thread.currentThread().getName() + "已持有锁o1"); }catch (InterruptedException e){ e.printStackTrace(); } synchronized (o2){ System.out.println(Thread.currentThread().getName() + "已持有锁o2"); o2.notify(); //唤醒等待的线程 } } } } static class MyThread2 implements Runnable{ private Object o1 = new Object(); private Object o2 = new Object(); public MyThread2(Object o1, Object o2){ this.o1 = o1; this.o2 = o2; } @Override public void run(){ synchronized (o2){ try{ Thread.sleep(200); System.out.println(Thread.currentThread().getName() + "已持有锁o2"); o2.wait(); //当前线程等待并释放锁o2 }catch (InterruptedException e){ e.printStackTrace(); } synchronized (o1){ System.out.println(Thread.currentThread().getName() + "已持有锁o1"); } } } } public static void main(String[] args) { Object o1 = new Object(); Object o2 = new Object(); Thread thread1 = new Thread(new MyThread1(o1, o2)); Thread thread2 = new Thread(new MyThread2(o1, o2)); thread1.start(); thread2.start(); }}
上述实例执行结果如下:
可知死锁已解决
六、参考
《王道考研系列——操作系统考研复习指导》
转载地址:https://blog.csdn.net/m0_37415978/article/details/115422592 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!