操作系统笔记1-进程管理

发表于 | 分类于

进程模型

进程是程序执行的一个实例

  • 状态转换

进程描述

PCB进程控制块，记录OS管理控制进程的数据结构，记录进程的描述信息，每个进程对应一个PCB

PCB是进程的一部分[程序，数据，PCB]，PCB版所进程的整个生命周期

PCB中的信息：进程本身标识信息[pid,uid,内存外存地址]，CPU现场，进程调度信息，进程占用资源信息

一般系统把所有PCB组织在一起放到内存中固定的区域，构成PCB表，因此PCB表的大小决定了系统中最多可同时存在的进程个数

进程控制

  • 进程创建

创建pcb->赋予pid->初始化pcb->设置相应的链接

  • 进程撤销

收回进程所占用资源->赊销pcb

  • 进程阻塞(运行->阻塞)

保护cpu现场到pcb->pcb插入到阻
塞队列

  • 进程唤醒(阻塞->就绪)

进程同步与互斥

多个进程相互交替执行，达到并发执行的状态

  • 打印机案例

当一个进程需要打印文件时，将文件放入一个特殊目录spooler等待队列中，另一个进程(打印机守护进程)周期性检查是否有文件需要打印，若有则打印指定的文件并将改文件名从队列中删除。

脱机目录中有许多槽位，每个槽位存放一个文件名，假设有两个共享变量，in指向下一个空闲槽位，out指向下一个要打印的文件，两个共享变量保存在一个所有进程都能访问的文件中。在一个时刻A与B进程都决定要将一个文件加入打印队列假设此时槽位7为空闲，A读到in=7，7存放到了一个局部变量中，这时发生一个时钟中断切换到进程B，读取in同样得到了7，此时的错误为进程A与B都认为下一个可用的槽位是7，B将文件名存入到槽7后更新in为8，并离开，切换到进程A恢复中断后其终端前储存的局部变量任然认为下一个空闲的槽位是7，而事实上此时已经是8，于是A将文件存入到槽7覆盖掉了进程B要打印的文件，于是进程B需要打印的文件永远不会得到打印

  • 同步

进程之间需要一种严格的时序关系

  • 互斥

以某种手段确保当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作

  • 临界

临界资源：必须互斥访问的共享资源

临界区：进程中访问临界资源的那段程序

实现互斥

对于一个好的实现互斥的解决方案应当满足这些条件：

  1. 任何两个进程不能同时处于临界区
  2. 临界区外进程不应阻止其他进程进入临界区
  3. 不应是进程在临界区外无限等待进入
  4. 不应对cpu的个数和进程之间的相对运行速度做任何假设

锁变量

设置一个共享变量lock变量在临界区内有进程时为0，无进程时为1

该方案不可取，因为在程序使用这个共享锁变量时依然会出现冲突

严格轮转法

设置一个共享变量turn记录轮到哪个进程进入临界区，初始值为0

1
2
3
4
5
6
7
8
9
10
//进程0
while(turn!=0);
critical_region();
turn=1;
noncritical_region();
//进程1
while(turn!=1);
critical_region();
turn=0;
noncritical_region()

开始进程0检查turn为0，进入临界区，此时进程1发现turn为0，因此等待，并在循环测试turn有无变为1（忙等待），这种方式浪费cpu时间，通常要避免

不是一个好办法

忙等待会造成的问题

  1. 浪费cpu时间
  2. 可能引起优先级反转，高优先级进程永远在就绪状态无法进入临界区

Peterson

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define FALSE 0
#define TRUE 1
#define N 2

int turn;           //轮到谁
int interested[N];  //兴趣数组初始化均为false
void enter_region(int process)
{
    int other;                  //另一个进程
    other=1-process;            //
    interested[process]=TRUE;   //表面本进程希望进入临界区（感兴趣）
    turn=process;               //设置标志位
    while(turn==process&&interested[other]==TRUE);
}
void leave_region(int process)
{
    interested[process]=FALSE;  //离开临界区
}

一开始没有任何进程在临界区，现在进程0调用enter_region()通过设置数组元素和turn置0来标识它希望进入临界区，因进程1不像进入，因此enter_region()很快返回，若进程1要想进入临界区，则在此处挂起直到interested[0]变成false即，进程0调用了leave_region()离开了临界区

关中断

进程要进入临界区前先关中断，离开临界区前开中断，这样进程在临界区时中断是被屏蔽的不会切换到另外的进程

缺点1.对多处理器系统无效；2.将关中断的权力交给用户不合适，若进程不打开中断则整个系统都会停止

机器指令

  1. TSL指令（Test and Set Lock测试并加锁）
    执行TSL指令的CPU将锁住总线，禁止其他CPU在本指令结束前访问内存，这样就解决了使用关中断方法在多个处理器上行不通的情况
  2. swap指令

信号量

OS引入用于实现同步与互斥的机制

两个访问信号量的原子操作：P（等待，当s<=0时等待，直到s>0，然后s–）/V（唤醒，s++）

含义

信号量s标识可用资源数量，P意味着请求分配一个资源，s-1，s<=时表示无可用资源，请求者必须等待别的进程释放了资源之后运行，V即释放一个资源

忙等待实现方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//信号量定义
typedef struct{
    int value;//信号量初值
    int lock;//锁，初值为0
}Semophore_t;
//P
void P(Semophore_t *ps)
{
    for(;;){
        //对ps操作的互斥
        while(TSL(&ps->lock));
        if(ps->value>0){
            ps->value--;
            break;
        }
        ps->lock=0;
    }
    ps->lock=0;
}
//V
void V(Semophore_t *ps)
{
    //对ps操作的互斥
    while(TSL(&ps->lock));
    ps->value++;
    ps->lock=0;
}

阻塞实现方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
typedef struct{
    int value;
    SemaQueue *list;//等待信号量的进程队列
    int lock;
}Semaphore_t;

void P(Semaphore_t *ps)
{
    while(TSL(&ps->lock));
    if(ps->value>0){
        ps->value--;
        ps->lock=0;
    }else{
        进程加入ps->list
        阻塞该进程，ps->lock=0
    }
}
void V(Semaphore_t *ps)
{
    while(TSL(&ps->lock));
    if(ps->list==NULL){
        ps->value++;
    }else{
        ps->list中移出一个进程P
        进程P放入就绪队列
    }
    ps->lock=0;
}

信号量应用实例（生产者消费者）

两类进程共享一个公共的固定大小缓冲区，一类生产者进程将信息放入缓冲区，一类消费者进程从缓冲区中取信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#define N 100 //缓冲区槽数
#define TRUE 1
typedef int semaphore;
semaphore mutex=1;  //控制对临界区的访问，确保进程不会同时访问缓冲区，初始值1
semaphore empty=N;  //记录缓冲区中空的槽数
semaphore full=0;   //记录缓冲区非空槽数
void producer()
{
    while(TRUE){
        producer();     //生产一项
        P(&empty);      //申请一个空槽
        P(&mutex);      //请求进入临界区
        append();       //新数加入缓冲区
        V(&mutex);      //离开临界区
        V(&full);       //递增非空槽数
    }
}
void consumer()
{
    while(TRUE){
        P(&full);       //满槽数减一
        P(&mutex);      //进入临界区
        remove();       //从缓冲区中取出一项数据
        V(&mutex);      //离开临界区
        V(&empty);      //空槽数加一
        consume();      //处理数据
    }
}

经典进程同步问题

  • 哲学家进餐问题
  • 读者写者问题
  • 睡眠的理发师问题

    进程间通信

  • 共享存储区

相互通信的进程之间与公共的内存区，每个进程都可向公共内存区中读写

  • 消息传递

使用消息队列或者邮箱

  • 管道

用于连接一个读进程一个写进程

Send Reecive 实现

阻塞方式为消息队列满或者空时，等待，非阻塞时为直接返回，通常Send用非阻塞，Recieve可用两种方式

1
2
3
4
5
6
7
8
9
10
//非阻塞的Send
void Send(QID qid,MSG &pMsg)
{

}
//阻塞的Receive
void Receive(QID qid,MSG &pMsg)
{
    
}

线程

线程是进程执行的一条执行路径，一个进程可以有多个线程，其中至少一个主线程；一个进程内的多个线程在同一个地址空间内；每个线程由自己的线程控制块TCB，包含自己的堆栈和状态信息，比PCB要小得多