1.假设CPU中有两个进程在运行,程序1和程序2。


小故事:厨师做蛋糕
厨师在按照食谱做一个新的蛋糕,他需要原料和食谱,并按照食谱一步一步走。
在厨师做蛋糕时,厨师的儿子跑了进来,说小手被蜜蜂蜇到了。这时厨师要放下手上的活去处理儿子受伤的小手(他就需要把之前的工作(做到哪一步)记录下来然后再去处理儿子的事情)
--食谱就可以当成程序,原料当成输入程序,厨师就是CPU,做蛋糕这个任务就是程序1,他儿子受伤的手就是程序2。

2.进程的切换

 在CPU中如果程序1的时间片用完就会轮到程序2执行,这时CPU运行程序1时需要用到的所有寄存器里的数据都要保存起来

3.进程切换图解过程

当CPU运行到程序1的304地址时,程序1的时间片结束,系统需要保存程序1的上下文 并运行程序2。一个程序1、2彼此切换的过程

4.内存中的进程

5.进程的状态

非运行态的进程存放在CPU维护的一个队列中,静静滴等待CPU调用,只用运行态的进程才占用CPU资源

6.进程的调度

 到底哪个进程应该占用CPU--调度的评判标准:公平(合理分配CPU资源)、响应时间(用户输入到产生反应的时间)、吞吐量(单位时间内完成的任务量)等,标准之间会存在冲突

  • 非抢占式(简单、系统开销小、适用于批处理系统)
     调度程序一旦把CPU分配给某一进程后便让它一直运行下去;直至进程完成或程序不能运行才将CPU分给其它进程。
  • 抢占式(适用于交互式系统)
     当一个进程在运行时,系统可以基于某种策略来切换进程。如优先权原则、短进程优先原则、时间片原则。

 6.1 批处理系统的调度

  • 先来先服务(队列,非抢占式)
  • 最短作业作业优先(系统的平均等待时间最短,需预先知道任务的运行时间)

 6.2 交互式调度

  • 轮转(每个进程分配一个固定的时间片)
  • 优先级(给每个进程分配一个优先级,优先级高的先执行--会出现进程程饿死,低优先级的没有执行的情况)--解决的方法:计算进程等待的时间,动态地调用。比如进程的优先级会随着等待时间的增长而提升

  • 多级队列反馈
     如果同一个优先级的进程在规定的时间片内没有执行完成,就把该进程移动下一个优先级队列中。比如图中绿色所示;反之,如果一个进程的等待时间过长就把它移动到上一个高优先级队列中。

7.进程间同步(经典的生产者消费者问题)

 生产者进程向队列中加入文件(一个)
 消费者进程从队列中取出文件(多个)
  time to show code

/*定义数据结构*/
public class Item {}  /*商品*/
Item[] buffer = new Item[5];  /*相当于定义一个队列(可循环)存来放商品*/
int in = out = counter =0;  /*in--生产位置;out--消费位置;counter--队列商品数量*/
/*生产者*/
while(true) {
    while(count == 5) {
        ;//啥也不做,队列满了
    }
    buffer[in] = Item;  /*把生成的商品放进队列中*/
    in = (in + 1)%5;  /*放完商品后,指针后移一位*/
    counter ++;    /*商品数量加1*/
}
/*消费者*/
while(true) {
    while(counter ==0) {
        ;//啥也不干,队列中还没东西消费
    }
    item = buffer[out];  /*取出out指向的商品*/
    out = (out + 1) % 5;
    counter --;
}

问题:在多进程的情况下,共享变量counter会出错。因为在机器层面中counter++-- 不是原子操作(操作不能在一个指令中完成)

问题解决

 加一个临界区,可在临界区内访问/修改临界区资源,但是进程进入临界区时,不允许其他进程在临界区内执行(修改操作)--这只要给临界区加一个锁就可以完成

加锁

  • 关闭中断
     CPU收到时钟中断以后,会检查当前进程的时间片是否已经用完,用完则切换。在进程进入临界区修改资源之前,通知系统 不做进程切换就可以了(这样别的进程就无法访问临界区了)。关闭了中断,CPU就不会被打断了,但是在离开临界区时一定要记得打开中断
     PS:把中断操作开发给应用程序是非常危险的

  • 用硬件指令来实现锁(设置一个原子的指令)

    boolean TestAndSet(boolean *lock) {
    #函数中的三条指令可以原子执行
    boolean rv = *lock;
    *lock = TRUE;   /*如果有进程进入则设为true*/
    return rv;
    } 
    #每个进程在进入临界区之前都要进行while循环判断lock是否变化
    #如果lock为true则该进程不断地循环判断(因为true表示已经有别的进程进去了临界区并在进去之前修改了lock的值 )
    boolean lock = false;
    do{
    while(TestAndSet(&lock)) {
        ;//什么也不做
    }
    
    临界区;
    
    lock = false;
    } while(true);
  • 信号量
     信号量s是个整数变量,除了初始化外,有两个操作-wait()和signal()也可称为pv操作或者down/up

    #表示进程进入临界区之前,执行--操作
    wait(S) {
    while(S <=0 ) {
        ;//啥也不做
    }
    S--;
    } 
    #表示进程出临界区后,执行++操作
    signal(S) {
    s++;
    }
    semaphore mutex = 1;
    wait(mutex);
    进入临界区
    signal(mutex);

    问题:当进程进入临界区之前会判断资源是否被占用,如果占用就会一直while循环--忙等

    typedef struct {
    int value;
    struct process *list;
    }semaphore;
    wait(semaphore S) {
    S->value--;
    if(S->value<0) {
        把当前进程加入S->list中
        block(); //进程阻塞,进入等待状态
    }
    }
    signal(semaphore *S) {
    S->value++;
    if(S->value <=0) {
        从s->list中取出一个进程p
        wakup(p);  //唤醒
    }
    }