愿你坚持不懈,努力进步,进阶成自己理想的人

—— 2017.09, 写给3年后的自己

操作系统总结——处理器管理

一、系统工作流程

处理器执行程序的方式称为系统工作方式,也称为工作流程

1、程序的特点

  • 顺序性:程序的一组指令的执行,应该按照程序员所编写的顺序执行,否则就可能引起错误
  • 可再现性:程序在同样的初始数据下,多次运行的结果应该保持一致

2、顺序执行

顺序执行的工作方式,是指处理器在执行一道程序开始后,只有在这道程序执行完成后,才能执行下一道程序。其外在表现就是单任务,顺序执行具有两个特征:

  • 封闭性:运行中的程序,不会受到其他程序的影响
  • 可再现性:处理器无需做任何额外的控制,就能保证程序的可再现性

3、并发执行

并发执行,是指处理器在开始执行一道程序后,在这道程序执行完毕之前,可以开始执行下一道程序。其外在表现就是多任务,并发执行的核心在于多道程序的交替执行,单一时间内从微观上而言,只有一道程序能够占用CPU,但是因为交替执行的时间很短,所以在宏观上来看,就好像程序在同时执行。它具有三个特征:

  • 随机性:哪一道程序先运行、运行多久都是随机的、不确定的
  • 不可再现性:并发执行可能会破坏程序的可再现性,如下例子:
PA() {
    int x;
    x = count;  // (1)
    x = x+1;    // (2)
    count = x;  // (3)
}

PB() {
    int y;      
    y = count;  // (4)
    y = y-1;    // (5)
    count = y;  // (6)
}

由于并发执行的核心在于交替执行,所以执行语句的顺序就是不确定的,假设执行流程为 count = 100; PA(); PB();,正确执行后的结果,就应该是count = 100。然后看如下分析:
1)假如交替执行的顺序是(1)(2)(3)(4)(5)(6),那么结果是100,正确
2)假如交替执行的顺序是(1)(4)(5)(6)(2)(3),那么一开始PA()得到执行,x的值为100,此后调度程序调度PB(),在调度之前,需要先保存PA()的现场,此后执行PB()得到count = 99,此后调度程序调度PA(),恢复保存的现场,x的值仍然为100,故执行后,count的值最终变成101,错误

  • 相互制约:某些情况下,会出现当一道程序运行的时候,另一道程序就不能运行,否则就会导致错误的现象,即一道程序的运行制约另一道程序

4、并行执行

并行执行主要是存在于多处理机系统,是真正意义上的同时执行。如某计算机有2个CPU,那么在同一时刻,程序A可以占用CPU1运行,程序B可以占用CPU2运行,它们就实现了并行执行

二、进程

1、进程是一道程序在一个数据集上的一次运行过程,进程和任务的概念是等价的。简单而言,进程就是运行中的程序
2、进程的特征:进程有5个特征:

  • 动态性:每个进程都有一个生命周期,有从创建、运行到消亡的过程。和程序的区别在于:程序是静态的,进程是动态的
  • 并发性:多个进程可以并发执行
  • 独立性:一个进程的程序和数据只能由该进程自身访问(进程的地址空间是私有的)
  • 结构性:进程在操作系统中的实现,是定义一个数据结构——进程控制块(PCB)来表示一个进程
  • 异步性:每一个进程的运行过程不可预知,完成时间也不可预知,随时都可以创建一个或多个新进程

3、进程的状态:进程有就绪运行阻塞三个状态(三个生命周期)。当一个进程刚刚被创建的时候,它的状态是就绪,进程状态的转换如:

4、进程控制块(PCB):进程控制块是设计来用于管理进程的数据结构,它是一个较为复杂的结构,可以分为3个组成部分:

  • 基本描述信息部分:进程名(pname)、进程标识符(pid)、用户标识(uid)、进程状态(pstate)等
  • 管理信息部分:进程和数据的地址、I/O操作相关参数、进程通信信息、下一个PCB的指针等
  • 控制信息部分:现场信息、调度参数、同步互斥的信号量

5、PCB队列:PCB队列是用来存储不同状态进程的队列,PCB队列可以有多个。通常使用链表实现

  • 就绪队列:存储就绪状态的进程,CPU在运行完一个进程后,可以从就绪队列中根据调度算法取出一个进程,使之占用CPU执行
  • 等待队列:存储阻塞状态的进程

6、原语:原子性是指一组操作是不可分割的,它之中的指令要么全都执行,要么全不执行,如果有一个指令没有执行成功,就要回到开始时的状态,所有的指令都要重新执行

三、进程同步

由于并发性破坏了程序可再现性,所以就需要操作系统执行一定的手段来保证程序的可再现性。而进程的同步,便是操作系统解决该问题的手段
1、破坏程序可再现性的两个例子:

  • P1进程和P2进程均执行打印操作,占用同一打印机资源,如:
P1: Print(A, Line1);
    Print(A, Line2);
    Print(A, Line3);

P2: Print(B, Line1);
    Print(B, Line2);
    Print(B, Line3);

在并发执行的过程中,由于交替执行,就有可能造成打印出来的效果如下:

A:Line1
B:Line1
B:Line2
A:Line2
B:Line3
A:Line3

这显然不是正确的结果。而造成这一问题的原因在于使用了同一资源,而这种资源一次只能让一个进程使用(称为临界资源,常用的临界资源有打印机、存储单元、堆栈、链表、文件等)
2、某些任务中,要实现将计算机上A磁盘的文件备份到B磁盘上。某种实现如下:

ProcessRead:
    readFromSourceDisk();
    saveTo(buffer1);

ProcessMove:
    move(buffer1, buffer2);

ProcessWrite:
    readFrom(buffer2);
    writeToTargetDisk();

正确的执行情况下,应该是Read进程将源磁盘文件读入缓冲区buffer1,Move进程将缓冲区buffer1的数据移入缓冲区buffer2,Write进程将缓冲区buffer2的数据写入目标磁盘。在这种情况下,如果要并发执行应该是如下的顺序,才不会造成错误:

File1 Read1 --> Move1 --> Write1
      File2               Read2 --> Move2 --> Write2
            File3                             Read3 --> Move3 --> Write3

3、制约关系:

  • 间接制约:由于使用了同一临界资源,需要暂时限制其他进程的执行
  • 直接制约:任务是由多进程协作完成,进程的执行顺序有严格要求,不按照执行顺序则会发生错误
    4、同步关系:一组并发进程中,每个进程至少与同组的另一个进程存在单向依赖相互依赖关系,称这组进程具有同步关系,称为同步进程
  • 单向依赖:一个进程的执行必须等另一个进程的某个指令执行完才能进行:
进程A:        进程B:
   .             .
   .             .
   .             .
   L1 <-------- L2
   .             .
   .             .

必须等L2执行完后才能执行L1
  • 相互依赖:由任务的反复执行所产生,如进程A第一次运行不受限制,进程B第一次执行就依赖于进程A