操作系统原理期末复习

第一章

操作系统的基本特性：

并发与（资源）共享、虚拟、异步

操作系统四大功能：

处理机管理、存储器管理、设备管理、文件管理，除此之外，还需要提供友好的用户接口

设计现代OS的目标是：

提高资源利用率和方便用户

单道批处理系统是在解决人机矛盾和CPU与I/O设备速率不匹配矛盾的过程中形成的

第二章 进程与线程

进程之间的通信（进程之间的数据交互）：
1.共享存储（数据共享、存储区共享）,
2.消息传递（直接通信、间接通信）,
3.管道通信

管道通信是单向进行的！！！管道文件pipe文件，本质是一个内存中的缓冲区（先进先出FIFO）
FIFO 是 管道通信 与 共享存储 不一样的地方！！！

单向传播通信----半双工通信
双向同时进行通信-----全双工通信
一个管道可以有多个写进程，一个读进程（有争议，但是还是以此为准）

动态性是进程最重要的特性，以此来区分文件形式的静态程序
操作系统引入进程的概念，是为了从变化的角度动态分析和研究程序的执行

系统总是通过PCB对进程进行控制，PCB是进程存在的唯一标志

各进程的存储地址空间相互独立，因此进程之间的信息传递无法直接进行

程序的封闭性是指程序的执行结果之取决于进程本身，不受外界影响，进程的执行速度不会改变其执行结果
失去封闭性，不同速度下的进程执行结果不同（并发进程存在共享变量！！！）

线程的调度组织与控制、状态转化、创建、终止等等，与进程类似

引入线程后，进程仍然是资源分配的单位，内核级线程是处理机调度和分派的单位，线程本身不具有资源，但它可以共享所属进程的全部资源

一个内核程序，映射到用户级后有多个线程，这些线程之间的切换不需要内核级切换进程，不需要内核的支持

多对一的线程模型中，由于只有一个内核，用户级的多线程对于操作系统来说是透明的，当改进程的一个线程被阻塞后，该进程就会被阻塞
作为对比，一对一的线程模型中，每个用户级的线程都会映射到一个内核级的线程，当某个线程被阻塞时，不会影响其他线程

信箱实现进程之间的互相通信（消息传递中的间接通信），需要涉及两个原语：发送原语和接受原语

对进程的理解

进程是一个独立的运行单位，也是操作系统进行资源分配和调度的基本单位，包括了pcb,程序和数据以及执行栈区
线程是一种特殊的进程

一个进程是程序在一个数据集上的一次运行过程，运行于不同的数据集，将会形成不同的进程

系统动态DLL库中的系统线程，被不同的进程调用，他们是（ 相同 ）的线程
这题理解不了，就这样记吧。。。

pcb所包含的数据结构的内容有：
进程标志信息、进程控制信息、进程资源信息、cpu现场信息
具体而言有：进程ID、cpu状态、堆栈指针

进程中的线程共享进程内的全部资源，但是进程中某些线程的栈指针对其他线程的透明的，不能与其他线程共享

主要要区分阻塞态和就绪态

只有从运行态到阻塞态的转换是由进程自身决定的
从运行态到就绪态的转换是由于进程的时间片用完
从就绪态到运行态是被动的
从阻塞态到就绪态是由协作进程决定的

进程唤醒的概念

当阻塞态的进程等待的某资源（不包括处理机）可用时，进程就会被唤醒

在多线程模型中，用户级线程和内核级线程的链接方式分为多对一、一对一、多对多

操作系统为每个用户级线程建立一个线程控制块属于一对一模型

用户级线程的切换可以在用户空间完成，内核级线程的切换需要操作系统帮助进行调度，因此用户级线程的切换效率更高

用户级线程可以在不支持内核级线程的操作系统上实现

父进程与子进程可以并发执行
父进程可以与子进程共享一部分资源，但是不能共享虚拟地址空间，在创建子进程时，会为子进程分配资源，如虚拟地址空间等
临界资源一次只能为一个进程所用，所以父进程和子进程不能同时使用同一临界资源

内核级线程

在内核级线程中，同一进程中的线程切换，需要从用户态转到内核态进行，系统开销较大（相比于用户级线程）
当内核级线程阻塞时，cpu将调度同一进程中的其他内核级线程执行
内核级线程的程序实体可以在内核态运行
对于多处理机系统，核心可以同时调度同一进程的多个线程并行执行

用户级线程

进程中的某个用户级线程被阻塞，则整个进程也会被阻塞，即进程中的其他用户级线程也会被阻塞
线程的调度不需要内核的直接参与，控制简单
线程切换代价小
允许每个进程定制自己的调度算法，线程管理比较灵活

注意：跨进程的用户级线程调度需要内核参与！！！

一个进程从运行态变为就绪态，必定会引起进程的切换

题目： 在具有通道设备的单处理器系统中实现并发技术后， 各进程在某一时间断内并发运行，CPU与I/O设备并行工作

解析：正是因为CPU与I/O设备的并行工作，才使各进程能并发执行！！！不懂，背就完了

第三章 处理机调度

若每个作业只能建立一个进程，为了照顾短作业用户，应采用（短作业优先调度算法）；为了照顾紧急作业用户，应采用（基于优先级的剥夺式优先队列调度算法），为了实现人机交互，应采用（时间片轮转调度算法）；而能使短作业，长作业，交互作业用户都满意，应采用（多级反馈队列调度算法）

操作系统的基本特性

并发与资源共享，同时还有虚拟性和异步性

现代OS的目标是

提高资源利用率和方便用户

操作系统具有的四大功能

处理机管理、存储器管理、设备管理、文件管理

为解决人机交互问题，引入时间片的概念，采用

时间片轮转调度算法

实时系统可以分为

实时信息处理系统和实时控制系统、多媒体系统和嵌入式系统

I/O软件通常被组织成

用户层软件、设备独立性软件、设备驱动程序、和I/O中断处理程序四个层次

银行家算法

银行家算法中的数据结构：

（1）可利用资源向量Available：包含m个元素的数组，每个元素代表一类可用的资源数目，初始值是系统可配备的资源数，动态变化回收

（2）最大需求矩阵Max：是一个n*m的矩阵，定义了系统中n个进程中的每个进程对m类资源的最大需求

（3）分配矩阵Allocation：也是一个n*m的矩阵，定义了系统中每一类资源当前已分配给每一个进程的资源数

（4）需求矩阵Need：也是一个n*m的矩阵，表示每一个进程尚且需要的各类资源数

有公式：

Need[i,j]=Max[i,j]-Allocation[i,j]

银行家算法：是一种避免死锁的方法

Requesti[j]=k 表示进程i需要资源 j 的数量为 k

伪代码

if( Requesti[j]=k ≤ Need[i,j])
{
  if( Requesti[j]=k ≤ Available[j] )
  {
    //系统将资源分配给进程
    //并修改如下数据
    Available[j] -= Requesti[j];
    Allocation +=Requesti[j];
    Need[i,j] -= Requesti[j];
  }
  else（目前所需资源不足，等待...）
}
else(认为出错了，所需资源大于其宣布的最大资源量)
//系统执行安全性算法，检验是否安全
if(safe)
{
  //正式进行分配
}
else
{
  //本次试探分配作废，系统回复原来状态，让该进程处于等待状态
}

重点在安全性算法，所以需要好好看看

服务完进程后，Available更新为+=Allocation

生产者-消费者问题

设有两个生产者进程A、B和一个销售者进程C，他们共享一个无限大的仓库，生产者A只生产A产品，生产者B只生产B产品。生产者每次循环生产一个产品，然后入库供销售者销售；销售者每次循环从仓库取出一个产品销售。如果不允许同时入库，也不允许边入库边出库，而且要求两个生产者在生产A产品和生产B产品时的件数满足以下关系：

-n≤生产A的件数-生产B的件数≤m

其中n,m是正整数，但对仓库中A产品和B产品的件数无上述要求，请用信号量机制写出A、B、C三个进程的工作流程。

分析：生产者A、B和消费者之间不能同时将产品入库和出库，故仓库是一个临界资源。

生产的A、B产品必须满足：-n≤生产A的件数-生产B的件数≤m。

仓库的管理只要求出入库互斥，由于仓库无限大，只需操作互斥就可以完成，出库要考虑有无产品，SA对应于仓库中的A产品量，SB对应于仓库中的B产品量；

销售要满足：-n≤生产A的件数-生产B的件数≤m，用difference表示A的件数-B的件数，即

difference=A的件数-B的件数，

difference==-n 的时候，不能取产品B，只能取A；

difference==m 的时候，不能取产品A，只能取B；

-n< difference< m，即可以取产品A也可以取产品B；

答：为了互斥地入库和出库，需为仓库设置一初值为1的互斥量信号mutex；为了使生产的产品件数满足-n≤生产A的件数-生产B的件数≤m，需要设置两个同步的信号量，其中SAB表示当前允许A生产的产品数量，其初始值为m ，SBA表示当前允许B生产的产品数量，其初值为n；

另外还需要设置一个整数difference表示所销售的A、B产品数量之差，而为了同步生产者和销售者并使销售的A、B产品的件数满足 -n≤生产A的件数-生产B的件数≤m，还需要设置三个资源信号量，其中S对应于仓库中的总的产品量，SA对应于仓库中的A产品量，SB对应于仓库中的B产品量，他们的初值都为0.

https://blog.csdn.net/liushall/article/details/81569609

假设缓冲区大小为10，生产者、消费者线程若干。生产者和消费者相互等效,只要缓冲池未满,生产者便可将消息送入缓冲池;只要缓冲池未空,消费者便可从缓冲池中取走一个消息。

用伪代码将简单的逻辑表达清楚！

// items代表缓冲区已经使用的资源数，spaces代表缓冲区可用资源数
// mutex代表互斥锁
// buf[10] 代表缓冲区，其内容类型为item
// in、out代表第一个资源和最后一个资源
var items = 0, space = 10, mutex = 1;
var in = 0, out = 0;
item buf[10] = { NULL };

producer {
    while( true ) {
        wait( space );  // 等待缓冲区有空闲位置， 在使用PV操作时，条件变量需要在互斥锁之前
        wait( mutex );  // 保证在product时不会有其他线程访问缓冲区

        // product
        buf.push( item, in );  // 将新资源放到buf[in]位置 
        in = ( in + 1 ) % 10;
        
        signal( mutex );  // 唤醒的顺序可以不同
        signal( items );  // 通知consumer缓冲区有资源可以取走
    }
}

consumer {
    while( true ) {
        wait( items );  // 等待缓冲区有资源可以使用
        wait( mutex );  // 保证在consume时不会有其他线程访问缓冲区

        // consume
        buf.pop( out );  // 将buf[out]位置的的资源取走
        out = ( out + 1 ) % 10;

        signal( mutex );  // 唤醒的顺序可以不同
        signal( space );  // 通知缓冲区有空闲位置
    }
}

不能将线程里两个wait的顺序调换否则会出现死锁。

例如(调换后)，将consumer的两个wait调换，在producer发出signal信号后，如果producer线程此时再次获得运行机会，执行完了wait(space)，

此时，另一个consumer线程获得运行机会，执行了 wait(mutex) ，如果此时缓冲区为空，那么consumer将会阻塞在wait(items)，而producer也会因为无法获得锁的所有权所以阻塞在wait(mutex)，这样两个线程都在阻塞，也就造成了死锁。

哲学家就餐问题

同步问题，大量并发控制问题的案例

要求在多个进程之间分配多个资源，并且不会出现死锁和饥饿

解决死锁问题的三种方案：

（1）允许最多4个哲学家同时坐在桌子上----这样避免了5个筷子同时在5个人手上的情况

（2）只有一个哲学家的两个筷子都可以用时，他才能拿起它们（他必须在临界区内拿起两个筷子）

（3）使用非对称的解决方案，即单号的哲学家先拿起左边的筷子，接着右边的筷子；双号的哲学家先拿起右边的筷子，再拿起左边的筷子

方案一：

第一种解决死锁问题的办法就是同时只允许四位哲学家同时拿起同一边的筷子，这样就能保证一定会有一位哲学家能够拿起两根筷子完成进食并释放资源，供其他哲学家使用，从而实现永动，避免了死锁。举个最简单的栗子，假定0~3号哲学家已经拿起了他左边的筷子，然后当4号哲学家企图去拿他左边的筷子的时候，将该哲学家的线程锁住，使其拿不到其左边的筷子，然后其左边的筷子就可以被3号哲学家拿到，然后3号哲学家进餐，释放筷子，然后更多的哲学家拿到筷子并进餐。

​ 如何才能实现当4号哲学家企图拿起其左边的筷子的时候将该哲学家的线程阻塞？这个时候就要用到该问题的提出者迪杰斯特拉（迪杰斯特拉最短路径算法，银行家算法）提出的信号量机制。因为同时只允许有四位哲学家同时拿起左筷子，因此我们可以设置一个信号量r，使其初始值为4，然后每当一位哲学家企图去拿起他左边的筷子的时候，先对信号量做一次P操作，从而当第五位哲学家企图去拿做筷子的时候，对r做一次P操作，r = -1，由r < 0得第五位哲学家的线程被阻塞，从而不能拿起左筷子，因此也就避免了死锁问题。然后当哲学家放下他左边的筷子的时候，就对r做一次V操作。

semaphore chopstick[5]={1,1,1,1,1};
semaphore r=4;
void philosopher(int i)
{
  while(true)
  {
    think();
    wait(r);                       //请求进餐
    wait(chopstick[i]);            //请求左边的筷子
    wait(chopstick[(i+1)mod5]);    //请求右边的筷子
    eat();
    singal(chopstick[(i+1)mod5]);  //释放右边的筷子
    singal(chopstick[i]);          //释放左边的筷子
    singal(r);                     //释放信号量r
    think();
  }
}

方案二：

使用AND信号量机制，意思就是如果想给某个哲学家筷子，就将他需要的所有资源都给他，然后让他进餐，否则就一个都不给他。

​根据上面的分析，可以将代码修改为：

semaphore chopstick[5]={1,1,1,1,1};
void philosopher(int t)
{
  while(true)
  {
    think();
    Swait(chopstick[i];chopstick[(i+1)mod5]);//将左右筷子资源都分配给一个哲学家
  eat();
  singal(chopstick[(i+1)mod5];chopstick[i]);
  think();
  }
}

方案三：

规定奇数号哲学家先拿起他左边的筷子，然后再去拿他右边的筷子，而偶数号的哲学家则相反，这样的话总能保证一个哲学家能获得两根筷子完成进餐，从而释放其所占用的资源，代码如下：

semaphore chopstick[5]={1,1,1,1,1};
void philosopher(int i)
{
  while(true)
  {
    if(i mod 2==0)    //偶数哲学家，先右后左
    {
      wait(chopstick[(i+1)mod 5]);
      wait(chopstick[i]);
      eat();
      singal(chopstick[i]);
      singal(chopstick[(i+1)mod 5]);
    }
    else             //奇数哲学家，先左后右
    {
      wait(chopstick[i]);
      wait(chopstick[(i+1)mod 5]);
      eat();
      singal(chopstick[(i+1)mod 5]);
      singal(chopstick[i]);
    }
  }
}

补充内容：什么是信号量机制？

https://blog.csdn.net/theLostLamb/article/details/80741319

信号量s是具有非负整数值的全局变量，只能由两种特殊的操作来处理，这两种操作称为P和V：

P(s)：如果s是非零的，那么P将s减1，并且立即返回。如果s为零，那么就挂起这个线程，直到s变为非零，而一个V操作会重启这个线程。在重启之后，P操作将s减1，并将控制返回给调用者。

V(s)：V操作将s加1。如果有任何线程阻塞在P操作等待s变成非零，那么V操作会重启这些线程中的一个，然后该线程将s减1，完成它的P操作。