操作系统笔记

一、操作系统的发展历程

操作系统的特征

并发(concurrency)
共享(sharing)
虚拟(virtual)
异步性(asynchronism)

历史四种操作系统

1.单道批处理系统

内存中始终只有一道作业运行
处理过程：P6 (监督程序 Monitor)
特点：
自动连续性 (无需人工干预，缺乏交互性)
顺序性 (磁盘/带上各程序先后进入内存，先进入先执行)
单道性 (内存中只有一道程序运行)

2.多道批处理系统

内存中有多个作业，而某一时刻CPU处理的是其中一个作业（一个程序IO请求时先执行另一个程序）
SPOOLing技术 (Simultaneous Peripheral Operation On Line 假装脱机技术) 欺骗进程，像是每个进程都各自拥有一台打印机一样。
特点：
资源利用率高
系统吞吐量大 (CPU和其他资源处于忙碌状态、仅当作业完成时或运行不下去时才进行切换)
平均周转时间长 (因要排队依次处理，故作业周转时间较长)
无交互能力

3.分时系统

作业直接进入内存 ;采用轮转运行方式。
关键问题：
及时接收：配置多路卡，主机以很快的速度周期性地扫描各个终端，接收终端发来的数据。
及时处理：不允许一个作业长期占用CPU，规定每个程序只允许很短的时间片(TimeSlice)后暂停，立刻调度下一个程序运行。
特点：
多路性：允许一台主机连接多个终端，按分时原则为每个用户服务。
独立性：各用户独占一个终端互不干扰，感觉是独占主机。
及时性：用户请求可在很短时间内得到响应。
交互性：用户可通过终端与系统进行人机交互，获得系统服务。

多道批处理系统和分时系统的区别

方式：类似于非抢占式和抢占式
目的：解决人机矛盾及CPU和I/O设备之间速度不匹配矛盾（不提供人机交互能力）和实现人机交互。

4.实时系统

计算机接收到外部信号后及时响应并处理外部事件，且要求在严格规定事件内
特点：多路性、独立性、及时性、交互性、可靠性

基本术语

脱机：不受主机或用户直接控制 (批处理系统)
联机：受...... (交互式系统)
作业：用户为特定目的要求计算机所做工作的集合 (用定义作业步的命令、作业控制语言(JCL) 来描述)
作业步：作业中各项有序而又相对独立的工作 (用命令定义)

操作系统的作用

二、进程的描述与控制

进程控制块 (Process Control Block, PCB)

进程描述

进程特征

动态性：程序只是一组有序的指令的集合，是静态的。进程是动态的。
并发性：是指多个进程实体同存于内存中，且能在一段时间内同时运行。程序(没有建立PCB)是不能参与并发执行的。
独立性：凡未建立PCB的程序都不能作为一个独立的单位参与运行。
异步性：进程按各自独立、不可预知的速度向前推进(故传统意义上的程序若参与并发执行其结果会产生不可再现性)

进程的基本状态

基本状态：
就绪(Ready)：分到了除CPU外的所有资源，一旦获得CPU即可立即执行。
执行(Running)：已获CPU正在执行。
阻塞(Block)：正在执行的进程由于某事件暂时无法继续执行。
状态间的转换：

进程运行机制

进程的创建

引起创建进程的事件
用户登录：分时系统中，若用户在终端登录成功，系统将为给用户建立一个进程并插入就绪队列中。
作业调度：多道批处理系统中，调度某作业时将其装入内存为之创建进程并插入就绪队列。
提供服务：
应用请求：用户进程自己创建的进程。
进程的创建
申请空白PCB：未新进程申请获得唯一的数字标识符，并从PCB集合中索取一个空白PCB。
分配所需资源：物理资源(内存、文件、I/O设备)和逻辑资源(CPU事时间等)。
初始化PCB：
初始化标识信息
初始化处理机状态信息
初始化处理机控制信息
插入就绪队列：若进程就绪队列能接纳新进程便将其插入。

进程的终止

引起进程终止的事件：
正常结束：批处理系统中，通常会在程序最后安排一条Holt指令向OS表示进程已结束。
异常结束：发送亦称时间无法继续进行
越界错
保护错：试图去访问不允许的资源、不恰当的方式访问(写自读文件)
非法指令：试图执行一条不存在的指令(May错误地转移到数据区并把数据当指令执行)
特权指令错：用户进程试图执行只许OS执行的指令
运行超时：进程的执行时间超过了指定的最大值。
等待超时：..等待时间超过..
算术运算错：试图执行呗禁止的运算
I/O故障：I/O过程中发生了错误
进程的终止过程：
读取状态：据进程标识符从PCB集合中检索出该进程的PCB并从中读取状态
终止进程：
若正处于执行状态，立即终止并置调度标志为真，用于指示该进程被终止后应重新进行调度
若有子孙进程也应都予以终止
归还资源：所拥有的所有资源归还父进程或操作系统
移出队列：被终止进程(PCB)从所在队列或链表中移出。

进程的阻塞和唤醒

引起进程阻塞的事件
请求系统服务
启动某种操作
新数据尚未到达
无新工作可做
阻塞和唤醒的特点
一个进程等待某一事件但尚不具备发生条件时，该进程自己调用来阻塞自己。
当等待队列中进程所等待的事件发生时，等待该事件的所有进程都将被唤醒。
一个处于阻塞状态的进程不可能自己唤醒自己。

阻塞：

唤醒：

进程的激活与挂起

挂起：
用户请求或父进程请求将自己的某个子进程挂起时，系统调用suspend()将指定进程或阻塞状态的进程挂起。
激活：
当发生激活事件时，若进程驻留在外存而内存已有足够的空间，则调用active()激活。

进程同步与信号量

同步机制应遵循的原则

空闲则让
忙则等待
有限等待：需能在有限时间内进入自己的临界区，避免“死等”状态。
让权等待：进程不能进入自己的临界区时应立即释放处理机，以免进程陷入“忙等”状态。

1.整型信号量

是一个整数值，表示空闲资源总数(又称为“资源信号量”)
非负表示当前空闲资源数
负值(的绝对值)当前等待临界区的进程数
初始值应该大于0
两个原子操作P,V操作，未临界资源设置一个互斥信号量mutex

2.记录型信号量


xxxxxxxxxx
Procedure wait(s)
  var S: semaphore;
  begin
         S.value:=s.value-1;
    if S.value<0 then block(S,L);
  end;
Procedure signal(s)
 Var S:semaphore;
 Begin 
    S.value:=S.value+1;
    If S.value<=0 then wakeup(S.L);
 End;

3.信号量集

1)AND型信号量集机制

思想：
将一段代码同时需要的多个临界资源，采用原子方式，要么全部分配给它，要么一个都不分配。称为Swait(Simultaneous Wait)。同样使用结束后一起释放，称为Ssignal。


xxxxxxxxxx
Swait(S1, S2, …, Sn)    //P原语；
{  
    if (S1 ≥1 and S2 ≥ 1 … Sn ≥ 1)//次序不重要
    {   //满足资源要求时的处理；
        for (i = 1; i <= n; ++i) 
            Si=Si-1; //注：与wait的处理不同，这里是在确信可满足
            //资源要求时，才进行减1操作
    }
    else //某些资源不够时的处理；
    {
        调用进程进入第一个小于1信号量的等待队列Si.queue ,阻塞调用进程;
    }
}


xxxxxxxxxx
Ssignal(S1, S2, …, Sn)
{
    for (i = 1; i <= n; ++i)
    {
        ++Si; //释放占用的资源；
        for (each process P waiting in Si.queue) //检查每种资源的等待队列中的所有进程；
        {
            从等待队列Si.queue中取出进程P;
            if(判断P是否通过Swait中的测试) //注:与signal不同，需重新判断
            {
                进程P进入就绪队列; 
                break;
            }
            else //未通过检查（资源不够用）时的处理；
            {
                进程P进入某等待队列；//然后继续循环判断下一个进程
            }
        }
    }
}

2)一般“信号量集”机制

Swait(S1, t1, d1; ...; Sn, tn, dn); 几种特定的情况：
Swait(S, d, d)表示每次申请d个资源，当少于d个时，便不分配。
Swait(S, 1, 1)表示互斥信号量;
Swait(S, 1, 0)作为一个可控开关，并不申请资源，当S>0时才能进入特定区。

经典进程同步问题

1. 生产者--消费者问题

涉及两类进程：生产者进程和消费者进程
需要保证以下同步关系：
多个进程互斥地访问公共缓冲区。互斥信号量 mutex
不能向满的缓冲区中添加产品。可用的空资源信号量 empty
不能从空的缓冲区中提取产品。可用的满资源信号量 full
full + empty = N
也可采用AND信号量集：
Swait(empty, mutex) | Swait(full, mutex)
Ssignal(mutex, full) | Ssignal(mutex, empty)

类C伪代码


xxxxxxxxxx
semaphore full=0;  // 满缓冲区单元个数
semaphore empty=n; // 空缓冲区单元个数
semaphore mutex=1; // 互斥信号量：控制队临界资源的访问
char buffer[n];    // 说明其他类型变量
int in=0;
int out=0;
char nextc, nextp;
void producer() // 生产者进程
{
    while(1)
    {
        produce an item nextp; // 生产一个数据
        wait(empty);           // 空缓冲区数量-1
        wait(mutex);           // 进入临界区
        buffer[in] = nextp;    // 将一个数据送入缓冲池
        in = (in + 1) % n;     // 修改in指针
        signal(mutex);         // 退出临界区
        signal(full);          // 满缓冲区数量+1
    }
}
void consumer() // 消费者进程
{
    while(1)
    {
        wait(full);                // 满缓冲区数量-1
        wait(mutex);               // 进入临界区
        nextc = buffer[out];       // 从缓冲区读取一个数据
        out = (out + 1) % n;       // 修改out指针
        signal(mutex);             // 退出临界区
        signal(empty);             // 空缓冲区数量+1
        consume the item in nextc; // 消费一个数据
    }
}
void main()
{
    cobegin // 进程并发执行
        producer();
        consumer();
    coend
}

2. 读者-写者问题

涉及两个进程：读者(reader)进程和写者(writer)进程。
需要保证以下关系：
“读 - 写” 互斥
“写 - 写” 互斥
“读 - 读” 允许
信号量等：
Wmutex: 互斥信号量：表示“允许写”，初值是1
Readcount：公共变量：表示“正在读”的进程数，初始值是0
Rmutex：互斥信号量：表示队Readcount的互斥操作，初值是1
也可采用一般信号量集机制：增加一个限制条件：同时读的“读者”最多R个
mx：表示允许写，初值是1
L：表示当前允许读者数目，初值为R

整型信号量：


xxxxxxxxxx
void writer()
{
    wait(Wmutex);
    Write;
    signal(Wmutex);
}
void reader()
{
    wait(Rmutex);
    if(Readcount==0) 
        wait(Wmutex);
    Readcount++;
    signal(Rmutex);
    Read;
    wait(Rmutex);
    Readcount--;
    if(Readcount==0)
        signal(Wmutex);
    signal(Rmutex);
}

一般信号量集


xxxxxxxxxx
void writer()
{
    Swait(mx,1,1; L,RN,0);
    Write;
    Ssignal(mx,1);
}
void reader()
{
    Swait(L,1,1; mx,1,0);
    Read;
    Ssignal(L,1);
}

3. 哲学家就餐问题

方法一：增加变量count，最多允许4个哲学家争夺筷子
方法二：仅哲学家左右两个筷子都可用时，他才拿起筷子
方法三：规定奇数号哲学家先拿他左边的筷子，偶数号相反

最多允许同时4个哲学家争夺筷子：


xxxxxxxxxx
var chopstick: array[0...4] of semaphore:=(1,1,1,1,1);
var count: semaphore:=4
//第i个哲学家的活动：
    repeat:
        wait(count);
        wait(chopstick[i]);
        wait(chopstick[(i+1)%5]);
        eat;
        signal(chopstick[(i+1)%5]);
        signal(chopstick[i]);
        signal(count);
        think;
    until false;

左右筷子都能用时才拿起筷子进餐


xxxxxxxxxx
var chopstick: array[0...4] of semaphore:=(1,1,1,1,1);
Process i:
    repeat:
        think;
        Swait(chopstick[i], chopstick[(i+1)%5]);
        eat;
        Ssignal(chopstick[i], chopstick[(i+1)%5]);
    until false;

奇偶号哲学家先拿左右边筷子


xxxxxxxxxx
var chopstick: array[0...4] of semaphore:=(1,1,1,1,1);
Process i:
    repeat:
        if i%2==1 then: // 奇数哲学家
            wait(chopstick[i]);
            wait(chopstick[(i+1)%5]);
            eat;
            signal(chopstick[(i+1)%5]);
            signal(chopstick[i]);
        else: // 偶数哲学家
            wait(chopstick[(i+1)%5]);
            wait(chopstick[i]);
            eat;
            signal(chopstick[i]);
            signal(chopstick[(i+1)%5]);
        think;
    until false;

做题写代码注意事项：

信号量初始值可能需要为1，那就必须说明（初始化）。
题上要是说了用P,V操作就别写成wait, signal了。
如果一个资源只取和放，就不需要用两个信号量了，哪怕是不同的进程。直接一个信号量就代表资源数量，如小和尚老和尚取水问题的桶。

管程(非重点)

用管程解决生产者消费者问题

管程描述：


xxxxxxxxxx
type producer-consumer=monitor
var
    in,out,count:integer;
    buffer: array [0..n-1] of item;
    notfull, notempty: condition;
procedure entry put(item)
begin
    if count≥n then notfull.wait;
    One unit → buffer;
    count:=count+1;
    if notempty.queue then notempty.signal;
end
procedure entry get(item)
begin
    if count≤0 then notempty.wait;
    One unit ← buffer;
    count:=count-1;
    if notfull.quene then notfull.signal;
end
begin
    in:=out:=0; count:=0;
end
begin monitor ProducerConsumer
{
    condition full, empty;
    int count;
    void put()
    {
        if(count==N)   wait(full);
        
        产品放入缓冲区；
        count++;
        
        if(count>=1) signal(empty);
    }
    void get()
    {
        if(count==0)   wait(empty);
 
        从缓冲区中取出产品;
        count--;
   
        if(count<=N-1) signal(full);
    }
 
    count = 0;
}
end monitor;

进程与线程的比较

调度：同一进程的多个线程间调度时，不引起进程的切换；不同进程间的线程调度需要切换。
并发：一个进程的多个线程之间可并发执行
资源的拥有：线程不拥有系统资源，不拥有代码段、数据段...
系统开销：
线程：系统仅为其保存少量寄存器内容
进程：整个当前CPU环境

银行家算法

银行家手中资源
每个人手中已有的资源
每个人总共需要的资源
一个个申请

一、操作系统的发展历程

操作系统的特征

历史四种操作系统

1.单道批处理系统

2.多道批处理系统

3.分时系统

多道批处理系统 和 分时系统 的区别

4.实时系统

基本术语

操作系统的作用

二、进程的描述与控制

进程控制块 (Process Control Block, PCB)

进程描述

进程特征

进程的基本状态

进程运行机制

进程的创建

进程的终止

进程的阻塞和唤醒

进程的激活与挂起

进程同步与信号量

同步机制应遵循的原则

1.整型信号量

2.记录型信号量

3.信号量集

1)AND型信号量集机制

2)一般“信号量集”机制

经典进程同步问题

1. 生产者--消费者问题

2. 读者-写者问题

3. 哲学家就餐问题

做题写代码注意事项：

管程(非重点)

进程与线程的比较

银行家算法

多道批处理系统和分时系统的区别