君君的阅览室

操作系统复习

发表于

呜啦啦啦拉拉~~操作系统3天从入门到。。。。

os

小题

操作系统接口类型

  1. 命令接口：联机命令接口(终端处理程序、命令解释程序、联机命令)&脱机命令接口
  2. 程序接口(系统调用)
  3. 图形接口

    计算机系统的CPU工作模式

  4. 实模式
  5. 保护模式
  6. 虚拟8086模式

？？？？

  1. 用户模式
  2. 监督模式

进程的结构、状态及状态转换

PCB等

资源分配方式

临时区原则

  1. 忙则等待
  2. 有空让进
  3. 有限等待
  4. 让权等待（可选）

死锁条件

  1. 互斥
  2. 非抢占
  3. 占有并等待
  4. 循环等待

存贮体系、存贮保护

文件系统、文件组织

进程同步

多进程/线程对同一资源访问，都是读不会有什么问题，但是有一个写，就可能导致不同步。于是，对共享对象操作这一区域叫做临界区，对临界区访问需要互斥。

买面包问题

emmmm，就是一个冰箱里放着面包，要是没有面包就要买啦，这里有两个操作：查看是否有面包与没有就买面包，前者是只读操作，后者为写操作，当两个人同时查看发现没有面包，两个人会同时买面包，这样就买多啦，于是要想办法阻止它，做到没有就买，绝不买多。

  1. 重复买：先判断有没有面包，再判断有没有便签，若都没有就留下便签再去买面包，这里两个读与一个写都是可以打断的，这样就可能出现如注释：
    1
    2
    3
    4
    5
    6
    7
    if(nobread){            //这里打断，对方才进入并判断最后买下面包，再继续
        if(noNote){         //这里打断，对方才进入并判断最后买下面包，再继续
            leave Note;
            buy bread;
            remove Note;   
        }
    }
  2. 都不买：先留下便签，再判断有没有面包，有没有便签，最后都成立再去买，如注释：
    1
    2
    3
    4
    5
    6
    7
    leave Note;
    if(nobread){            
        if(noNote){         //永远为假
            buy bread; 
        }
    }
    remove Note;
  3. 都不买：都先留下自己的便签再检查对方是否已经贴了便签，如注释：
    1
    2
    3
    4
    5
    6
    7
    leave Note_1;           //这里打断，都检测到对方的便签
    if(noNote_2){            
        if(nobread){        
            buy bread;
        }
    }
    remove Note_1;
  4. 可行：先留下自己的便签，接下来检测若对方留下便签就等待并检测，这里两边代码不一致，前者轮询，而后者检测到前者没有便签则检测是否有面包，如注释：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    leave Note_1;           //这里打断
    while(Note_2);          //后者取消自己的便签后，这里继续~
    if(nobread){        
        buy bread;
    }
    remove Note_1;   
    //////////////////////////////////////////////////
    leave Note_2;           //接上一条注释，这里会发现前者想要买，就不会买并取消自己的便签
    if(noNote_1){
        if(nobread){
            buy bread;
        }
    }
    remove Note_2;
    这里可以看出出现争抢时，是一方主动让出了资源，这样另一方就有机会得到资源继续执行。另外，若是将上面的读取判断与置位作为一个原子操作，就不会出现这些情况。
  5. 可行：假设有个原子操作的加锁：
    1
    2
    3
    4
    5
    breadLock.Acquire();
    if(nobread){
        buy bread;
    }
    breadLock.release();

    Test-And-Set

    忙等待：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Lock{
      private static lock = 0;
        Acquire(){
            //lock被测试后不管之前是否为一现在都为一了，这个测试与置位是原子的，
            //不会被打断，所以之前为0那么while不进入循环，方法直接返回，否则循环等待
            while(testandset(lock));
        }
        release(){
            //这个过程不需要但是会被打断，因为它永远只会被有锁的进程执行
            lock=0;
        }
    }
    无忙等待：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Lock{
      private static lock = 0;
      private static WaitQueue = {};
        Acquire(){
            //lock被测试后不管之前是否为一现在都为一了，这个测试与置位是原子的，
            //不会被打断，所以之前为0那么while不进入循环，方法直接返回，否则循环等待
            if(testandset(lock)){
                //add this TCB to waitQueue;
                schedule();
            }
        }
        release(){
            lock=0;
            //remove oneTCB q from WaitQueue;
            wakeup(q);
        }
    }
    多个进程间自选等待：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    while{
        wating[i] = true;       //自己置位表示期待进入临界区
        key = true;             //将key置位，只有lock为false才能直接进入
        while(wating[i]&&key)   //wait本来为真，只有前面的进程退出临界区才会将它置为false，或者获取锁
            key=testandset(lock); 
        wating[i]=false;        //现在可以清除自己的wait标志啦，这个可以后移但必须清除，否者会死锁
        //临界区
        //..............
        j = (i+1)%n;
        while((j!=i)&&!wating[j])//一直循环直到遍历完或者找到等待锁的进程
            j=(j+1)%n;
        //退出区
        if(j==i)
            lock=false;         //当没有别的进程请求临界区再释放锁
        else
            wating[j]=false;    //这里是直接交出控制权给等待锁的其他进程，未置位锁
        //剩余区
    }

    Swap

    和testandset一样，就只写最基本的形式啦：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Lock{
      private static lock = 0;
        Acquire(){
            key=true
            while(key)
                swap(lock,key)
        }
        release(){
            //这个过程不需要但是会被打断，因为它永远只会被有锁的进程执行
            lock=0;
        }
    }

    信号量

    信号量与管程是操作系统提供的，操作系统保证它不会被打断，是原子的：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class semaphore{
      private static int sem;
      private static WaitQueue q;
        semaphore();
        semaphore(sem){
            this.sem=sem;
        }
      P(){
            sem--;
            if(sem<0){
                //Add this thread t to q;
                block(p);
            }
        }
        V(){
            sem++;
            if(sem<=0){
                remove a thread f from q;
                wakeup(t);
            }
        }
    }

    管程

    支持让权
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Condition{
      private static int numWaiting=0;
      private static WaitQueue q;
        signal(){
            sem--;
            if(numWaiting>0){
                //remove a thread t from q;
                wakeup(t)//
                numWating--;
            }
        }
        wait(lock){
            numWaiting++;
            //Add this thread t to q;
            release(lock);
            schedule();
            requrie(lock);
        }
    }

    生产者-消费者问题

    信号量法

    1
    2
    full = semaphore(0)
    empty = semaphore(n)
    生产者：
    1
    2
    3
    4
    5
    empty.P()
    lock.aquire()
    //写缓冲
    lock.release()
    full.V()
    消费者：
    1
    2
    3
    4
    5
    full.P()
    lock.aquire()
    //读缓冲
    lock.release()
    empty.V()
    这里用信号量来解决条件同步，锁可以用信号量做到互斥访问，即初始为1.

    管程法

    初始：
    1
    2
    count = 0;
    Condition notFull,notEmpty;
    生产者：
    1
    2
    3
    4
    5
    6
    7
    lock.aquire();
    if(count==n)
        notFull.Wait(&lock);
    //Add c to the buffer;
    count++;
    notEmpty.Signal();
    lock.release();
    消费者：
    1
    2
    3
    4
    5
    6
    7
    lock.aquire();
    if(count==0)
        notEmpty.Wait(&lock);
    //Remove c from buffer;
    count--;
    notFull.Signal();
    lock.release();

    读者-作者问题

    读读允许，读写互斥，写写互斥

    信号量法

    这里是读者优先的实现
    读者：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    P(CountMutex);
    if(Rcount==0)
      P(WriteMutex);
    ++Rcount;
    V(CountMutex);
    read;
    P(CountMutex);
    --Rcount;
    if(Rcount==0)
        V(WriteMutex);
    V(CountMutex);
    作者：
    1
    2
    3
    P(WriteMutex);
        write;
    V(WriteMutex);

    管程法

    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
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    class database{
        AR = 0;         //正在读
        AW = 0;         //正在写
        WR = 0;         //等待读
        WW = 0;         //等待写
        Lock lock;      //对上面的东东写操作需要加锁
        Condition okToRead;
        Condition okToWrite;
        read(){
            //wait untill no writers;
            startRead();
            read database;
            //check out-wait up  waiting writers;
            doneRead();
        }
        doneRead(){
            lock.Aquire();
            AR--;                   //读完以后，Active读者减一
            if(AR==0&&WW>0){        //如果没有正在读的并且等待写的大于0
                okToWrite.signal(); //准许写
            }
            lock.Release()
        }
        startRead(){
            lock.Aquire();
            while((AW+WW)>0){       //有作者正在写或在等待
                WR++;               //让读者等待
                okToRead.wait(lock);
                WR--;               //
            }
            AR++;                   //到这里说明可以读了，Active读者加一
            lock.Release()
        }
        write(){
            //wait untill no readers/writers;
            startWrite();
            write database;
            //check out - wait up waiting readers/writers
            doneWrite();
        }
        startWrite(){
            lcok.Aquire();
            while((AW+WW)>0){       //当有作者正在写或者等待写，则放入等待队列
                WW++;
                okToWrite.wait(lock);
                WW--;
            }
            AW++;
            lock.Release();
        }
        doneWrite(){
            lock.Aquire();
            AW--;
            if(WW>0){
                okToWrite.signal();
            }else if(WR>0){
                okToRead.broadcast();
            }
            lock.Release();
        }
    }

    哲学家进餐问题

    信号量法

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

    fork[] = semaphore(1)[5];
    void philosopher(int i){
        while(1){
            think();
            if(i%2==0){
                fork[i].P();
                fork[(i+1)%N].P();
            }else{
                fork[(i+1)%N].P();
                fork[i].P();
            }
            eat();
            fork[i].V()
            fork[(i+1)%N].V();
        }
    }

期末

理发问题

问题

理发店里有一把理发椅和一张可以坐n位顾客的沙发。如果没有顾客，理发师便在理发椅上睡觉；当一个顾客到来时，他会叫醒理发师为其理发；如果理发师正在理发时又有顾客来到，那么，如果有空椅子可坐，顾客就坐下来等待，否则就离开理发店。使用信号量解决此问题：

伪代码

还是一道生产者-消费者问题，生产者是顾客，消费者是理发师，这里当缓冲区满了会直接离开而不是阻塞，所以需要添加判断分支

1
2
3
4
barber = semaphore(0);       
mutex = semaphore(1);       //对num变量操作的锁
wait = semaphore(0);        //等待信号量
num = 0;                    //等待人数

理发师

1
2
3
4
5
6
7
8
while(1){
    wait.P();
    mutex.P()
        num--;
    mutex.V();
    //理发
    barber.V();             //为下一位理发
}

顾客

1
2
3
4
5
6
7
8
9
10
11
12
13
while(1){
    mutex.P()
        if(num==n){
            //离开
    mutex.V()
        }else{
            num++;
            wait.V()
            //坐下~
    mutex.V()
            barber.P()         //等待理发师理发
        }
}

抽烟问题

问题

有一个烟草代理和三个抽烟者，想抽烟这若要抽烟，必须具有烟叶，烟纸和火柴。三个抽烟者分别缺这三样之一。烟草代理会源源不断地分别供应烟叶，烟纸与火柴，将他们放在桌子上，缺它的人拿起他们抽烟，使用信号量同步烟草代理和三个抽烟者。

伪代码

1
2
3
4
//初始化
smoker[] = semaphore(0)[3];
agent = semaphore(1);
int turn;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//抽烟者1
while(1){
    smoker[0].P();
    agent.V();
}
//抽烟者2
while(1){
    smoker[1].P();
    agent.V();
}
//抽烟者3
while(1){
    smoker[2].P();
    agent.V();
}
1
2
3
4
5
6
7
8
9
10
11
12
//供应商
while(1){
    //当前还有东西则等待
    agent.P()
    //随机选一个给
    turn=rand(1,2,3);
    switch(turn){
        case 1:smoker[0].V();break;
        case 2:smoker[1].V();break;
        case 3:smoker[2].V();break;
    }
}

CPU调度

问题

设有一组进程，他们需要占用CPU的时间及优先级如下所示：

进程      CPU时间       优先级
P1          10            3
P2          1             1
P3          2             3
P4          1             4
P5          5             2

设各进程在时刻0按P1，P2，P3，P4，P5的顺序到达。

  1. 画出分别采用调度算法FCFS，SJF，非抢占式优先级调度及RR（时间片尾1）的调度顺序甘特图
  2. 1中各种调度算法下每个进程的周转时间
  3. 1中各种调度算法下每个进程的等待时间
  4. 哪个算法可以得到最小平均等待时间？

答

算法 周转时间 等待时间
FCFS 10+11+13+14+19=67 0+10+11+13+14=48
SJF 1+2+4+9+19=35 0+1+2+4+9=16
非抢占OPT 1+6+16+18+19=60 0+1+6+16+18=41
RR 2+4+7+14+19=46 1+3+5+9+9=27
3. SJF

同步-死锁避免

问题

观察下面的系统快照，

Allocation Need Available
A B C D A B C D A B C D
P0 0 0 3 2 0 0 1 2 1 6 2 2
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 3 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
  1. 当前是否处于安全状态，为什么？
  2. 如果P2请求（1 2 2 2），能分配给它吗？

答

  1. 安全，因为至少有一个安全序列（P0，P3,P1，P2,P4）
  2. 不能，尽管请求不大于需求并且存在资源，但是分配后的图如下，此时不再处于安全状态。
Allocation Need Available
A B C D A B C D A B C D
P0 0 0 3 2 0 0 1 2 0 4 0 0
P1 1 0 0 0 1 7 5 0
P2 2 5 7 6 1 1 3 4
P3 0 3 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6

段内存

问题

观察下列段表：

段   基地址     段长度
0     219        600  
1     2300       14
2     90         100
3     1327       580
4     1952       96

下列逻辑地址对应的物理地址是多少？

答

+ 0,430     649
+ 1,10      2310
+ 2,500     0
+ 3,400     1727
+ 4,112     0

内存-页面置换

问题

看一个二维矩阵A：

int A[][] = new int[100][100];

其中，A[0][0]位于页式存储系统（页面长200）的200地址处，一个进程在第0页（地址范围0~199），操作该矩阵，即指令取自第0页，如果有3个物理页帧，处理进程位于第1个页帧，其它两个页帧开始是空的。再假设采取LRU算法，下列矩阵初始化操作会引起多少次缺页：

  1. 列优先
    1
    2
    3
    4
    5
    for(int j=0;j<100;j++){
        for(int i=0;i<100;i++){
            A[i][j]=0;
        }
    }
  2. 行优先
    1
    2
    3
    4
    5
    for(int i=0;i<100;i++){
        for(int j=0;j<100;j++){
            A[i][j]=0;
        }
    }

    答

    设为C语言，A数组共占4*100*100个字节，即200页
  3. 列优先，则第一个页使用4字节就换到第三个页，以此方式访问，当可分配的页帧数为2时，每次关于j的for循环，有200次缺页，共有20000?10000次缺页。
  4. 行优先，共200次缺页。

内存-页面置换

问题

观察下列页面引用串：1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6.若分别采用如下的页面置换算法，会有多少次缺页？假设页帧数分别为1,2,3,4,5,6,7个。假设初始时物理页帧全是空的。

  1. LRU
  2. FIFO
  3. 最优算法

答

页帧数 LRU FIFO Optimal
1 20 20 20
2 18 18 15
3 15 16 11
4 10 14 8
5 8 10 7

内存-页面置换

问题

假定占有m块（初始为空）的进程有一个页访问时串，该页访问串的长度为p，其中涉及到n个不同的页号，对任何页面置换算法

  1. 缺页中断次数的下界是多少
  2. 缺页中断次数的上界是多少

答

  1. n
  2. p

文件-分配方法

问题

考虑一个含有100块的文件，假如文件控制块（和索引块，当用索引分配时）已经在内存中，当使用连续，链接，单级索引分配策略时，各需要多少次磁盘I/O操作？假设在连续分配时，在开始部分没有扩张的空间，但在结尾部分有扩展空间，并且假设待添加块的信息已在内存中：

  1. 在开始增加一块
  2. 在中间增加一块
  3. 在结尾增加一块
  4. 在开始删除一块
  5. 在中间删除一块
  6. 在结尾删除一块

答

连续 链接 索引
1 201 1 1
2 101 52 1
3 1 102?3 1
4 198 1 0
5 98 52 0
6 0 100 0

大容量存储-时间

问题

某软盘有40个磁道，磁头从一个磁道移至另一个磁道需要6ms，文件在磁盘上非连续存储，逻辑上相邻的数据块的平均距离为13磁道，每块的旋转延迟时间及传输时间分别为100ms、25ms，问读取一个100块的文件需要的时间？如果系统对磁盘进行了整理，让同一文件的磁盘块尽可能靠拢，从而是逻辑上相邻数据块的平均距离降为2磁道，这是读取一个100块的文件需要多少时间？

答

整理前，逻辑上相邻数据块的平均距离为13磁道，读一块数据需要的时间为：
13*6+100+25=203ms
因此，读取一个100块的文件需要的时间：
203*100=20300ms
磁盘整理后，读取一块的时间为：
2*6+100+25=137ms
因此，读取一个100块的文件需要时间：
137*100=13700ms

大容量存储-调度

问题

假设一个磁盘驱动器有5000个柱面，从0到4999，当前处理的请求在磁道143上，上一个完成的请求在磁道125上，按FIFO顺序排列的未处理的请求队列如下，86,1470,913,1774,948,1509,1022,1750,130。为了满足所有的磁盘队列中的请求，从当前位置开始，对下列各种磁盘调度算法计算磁盘臂必须移动的磁道数目。

答

1. FCFS: 143,86,1470,913,1774,948,1509,1022,1750,130                 7081
2. SSTF：143,130,86,913,948,1022,1470,1509,1750,1774                 1745
3. SCAN: 143,913,948,1022,1470,1509,1750,1774,4999,130,86            9769 
4. LOOK: 143,913,948,1022,1470,1509,1750,1774,130,86                 3319
5. C-SCAN: 143,913,948,1022,1470,1509,1750,1774,49990,0,86,130       9985 
6. C-LOOK: 143,913,948,1022,1470,1509,1750,1774,86,130               3363

来源

[1]苏大仙
[2]学堂在线-《操作系统》
[3]老师PPT