黎笛

2022-10-02 17:53 Java 发布于北京

关注

【八股文】操作系统

1.进程和线程的区别

进程是资源分配的基本单位，实现了操作系统的并发
线程是程序运行的基本单位，线程是进程的子任务

2.进程有哪几种状态

就绪状态：进程已获得除处理机以外的所需资源，等待分配处理机资源
运行状态：占用处理机资源运行，处于此状态的进程数小于等于cpu数
阻塞状态：进程等待某种条件，在条件满足之前无法执行

3.进程通信的方式

进程之间的信息交换

管道（pipe）：管道可用于具有亲缘关系的父子进程间的通信，有名管道除了具有管道所具有的功能外，它还允许无亲缘关系进程间通信
信号（signal）：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生
消息队列：是消息的链接表，它克服了上两种通信方式中信号量有限的缺点，具有写权限的进程可以按照一定得规则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信息；
共享内存：可以说这是最有用的进程间通信方式。它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等；
信号量：主要作为进程之间及同一种进程的不同线程之间得同步和互斥手段；
套接字：这是一种更为一般得进程间通信机制，它可用于网络中不同机器之间的进程间通信，应用非常广泛。

4.进程同步的方式

并发进程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通消息被称为进程同步，也就是保证多个进程能有条不紊的运行。

进程同步的方式：

临界区：对临界资源进程访问的那段代码，为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查
同步与互斥
信号量：整型变量，可以进行PV操作
管程：把控制的代码独立出来

5.进程调度算法

先来先服务（FCFS）

先请求CPU的进程先分配到CPU

短作业优先（SJF）

用时间长度决定优先级，抢占式

优先级调度算法

可以抢占式，也可以是非抢占式的。

优先级越高越先分配到CPU。

相同优先级先到先服务，存在的主要问题是：低优先级进程无穷等待CPU，会导致无穷阻塞或饥饿；解决方案：老化

时间片轮转调度算法

队列中的进程被分配时间片，时间片到则退出对CPU资源的使用

多级队列调度算法

将就绪队列分成多个独立的队列，每个队列都有自己的调度算法，队列之间采用固定优先级抢占调度。

其中，一个进程根据自身属性被永久地分配到一个队列中。

多级反馈队列调度算法

与多级队列调度算法相比，其允许进程在队列之间移动：若进程使用过多CPU时间，那么它会被转移到更低的优先级队列；在较低优先级队列等待时间过长的进程会被转移到更高优先级队列，以防止饥饿发生。

6.进程控制块PCB的作用

记录了操作系统所需的，用于描述进程的当前情况以及管理进程运行的全部信息，是操作系统的记录型数据结构

作用：

1）进程的唯一标识

2）能实现间断性运行方式

3）提供进程管理所需要的信息

4）提供进程调度所需要的信息

5）实现与其他进程的同步与通信

7.信号量机制实现进程同步和互斥

信号量其实就是个计数器，简单一点的例子就是a进程访问临界资源，把信号量设置为0，然后b进程也想访问，发现信号量为0，无法访问

用户进程可以通过使用操作系统提供的一对原语对信号量进行操作，从而很方便的实现了进程互斥，进程同步。

信号量机制实现进程互斥

步骤：

1）分析并发进程的关键活动，划定临界区

2）设置互斥信号量mutex，初值为1

3）在临界区之前执行P

4）在临界区之后执行V

mutex=1，标识两个进程皆未进入需要互斥的临界区

mutex=0，标识有一个进程进入临界区运行，另外一个必须等待，挂入阻塞队列

mutex=-1，表示有一个进程正在临界区运行，另外一个进程因等待而阻塞在信号量队列中，需要被当前已在临界区运行的进程退出时唤醒

信号量机制实现进程同步

步骤：

1）分析什么地方需要实现同步关系

2）设置同步信号量S，初始为0

3）在“前操作”之后执行V(S)

4）在“后操作”之前执行P(S)

下面的代码中，S就是同步信号量，若先执行到了V(S)，则s++，正常执行P(S)，保证了代码4在代码2之后执行

若先执行P(S)，s–之后表示没有可用资源，P操作会执行block原语，主动请求阻塞

P(1) {
    代码1；
    代码2；
     V(S)；
    代码3；
}

P(2) {
     P(S)
    代码4；
    代码5；
    代码6；
}

8.生产者-消费者模型

生产者-消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品使用

需求：

生产者每生产一个产品，就消耗一个缓冲区，只有当缓冲区不满的时候才能放入
消费者每消费一个产品，就消耗一个产品，只有当缓冲区不空的时候才能消费

做法：

因为缓冲区是临界资源，所以在访问的时候需要一个互斥信号量，实现互斥访问
为了同步生产者和消费者的操作，需要记录缓冲区的剩余大小empty和产品的个数full。当缓冲区大小不为0时，生产者才能放入产品；当产品个数不为0时，消费者才能拿走产品。

注：同步在前，互斥在后，防止死锁

producer() {
    while(1) {
        生产一个产品；
        P(empty);    //消耗一个空闲缓冲区
        P(mutex)；
        把产品放入缓冲区；    //临界区
        V（mutex）;
        V(full);     //增加一个产品
    }
}

consumer() {
     while(1) {
         P(full);    //消耗一个产品
         P(mutex)；
         从缓冲区取出一个产品；
         V（mutex）;
         V(empty);    //增加一个空闲缓冲区
         使用产品；
    }
}