电路设计

操作系统（面试复习整理）

2019-07-14 10:19发布

站内文章 / 电路设计
9504 0 1374

文章目录

1、进程

PCB（进程控制块）

PCB 进程状态 进程编号 程序计数器（即将执行的下个指令地址） 寄存器 内存界限 打开文件列表 …(CPU调度信息)

进程继承

fork() 创建子进程
exec() 代替父进程
wait() 父进程等待子进程消亡 子进程继承父进程
1、用户号（UIDs）和用户组号（GIDs）
2、环境
3、堆栈，共享内存，打开文件描述符
4、执行时的关闭标志、信号控制设定
5、进程组号，当前工作目录
子进程独有
1、进程号
2、父进程号
3、自己的文件描述符和目录流拷贝
父进程独有（不可继承）
1、进程正文，数据，锁定内存
2、异步输入输出 子进程终止条件
1、父进程终止
2、子进程任务结束，不再被需要
3、子进程是用来超过分配的资源

进程间通信

管道
匿名：在有血缘关系的进程中使用
命名（FIFO）：一种文件类型，无血缘关系中使用
信号
通知接受进程有某件事要发生
信号量
常用于线程间同步
消息队列
消息链接表，放在内存中，共享消息队列，有权限可以对消息队列进行读写消息操作
共享内存
两个或多个进程共享一个给定的存储区
最快的通信方式
套接字
一般进程间的通信方式

进程间同步

信号量：信号量为负，绝对值为等待信号量的进程个数
互斥锁
条件变量
读写锁（多进程并行读）
记录锁（提高并行性）

临界区问题

临界区：不予许多个进程交叉执行
临界区资源：互斥访问的资源
临界区问题
1、互斥：资源互斥访问
2、有空让进：对队列来说，队列需要是前进的
3、有限等待：对单个进程来说，等待时间应该是有限的，不应该无限等待

进程和线程

线程：CPU使用的基本单位
进程：操作系统资源分配的基本单位
一个进程有多个线程（任务），线程是轻量级的进程
线程调用fork()，创建的新进程将会复制所有线程

并发和并行

并发：多个事件，同一时间间隔，同一实体上完成
并行：多个事件，同一时间，不同实体上同时进行

2、CPU调度

调度准则

1、CPU使用率
2、吞吐量：单元时间内完成进程数量
3、周转时间：T完成−T到达T_{完成}-T_{到达}
4、等待时间：就绪队列中等待时间总和
5、响应时间：T第一次响应−T到达T_{第一次响应}-T_{到达}
6、带权周转时间T周转/T执行T_{周转}/T_{执行}

调度算法

FCFS
先到先服务，不抢占，前一个进程完成释放CPU后给下一个分配进程 SJF
不抢占：最短作业优先，完成后释放CPU
抢占：每次作业到达，判断剩余作业时间，最短剩余时间优先 优先级调度算法
抢占：优先级高，优先执行
非抢占：新作业达到，优先级高，加入队列头 轮转法调度（RR）
分时系统
按时间片分配CPU，一个进程执行完成，若一个时间片没用完，也释放CPU，就绪队列为循环队列。

死锁

死锁条件

1、互斥：资源不可同时访问
2、占有并等待：进程占有一部分资源，同时在等待另一部分的资源
3、非抢占：占有资源的进程不完成，不释放资源
4：循环等待：资源请求成环 安全状态：无死锁，有安全执行队列
不安全状态：可能产生死锁 分配图：无环不死锁，有环可能死锁 银行家算法：避免死锁

内存分配

给需要内存的进程分配内存的方法
1、首次分配：直接使用第一个足够大的孔
2、最佳适应：找到内存中最小的足够大的孔
3、最差适应：找到最大的孔
（1）、（3）会产生外部碎片

碎片问题解决

1、内存分配以固定大小为单位分配：会产生外部碎片
2、紧缩：将空闲空间合并
3、分页分段

按需调页

懒惰交换：只有需要时，才将页调入内存

页置换算法

FIFO：最旧的页被置换
OPT/MIN：最优置换，未来最长时间不使用的页被置换
LRU：最近最少使用的页被置换
近似LRU：每项有一个引用位
1、附加引用位：每个周期为一位，使用变成1，最小的被置换（如：00000000，记录八个时间片中的使用情况）
2、二次机会算法：一个应用位，若是0，被置换，若是1，本次不被置换，但是引用位变为0
3、增强型二次机会算法：（x，y）,x表示是否被使用，y表示是否被修改，被置换的概率为(0,0)>(0,1)>(1,0)>(1,1)

帧分配

1、平均算法
2、比例分配 多个进程竞争帧
全局置换：不管帧属于哪个进程
局部置换：只在进程本身资源中选择

3、磁盘调度

FCFS：先来先服务
SSTF：通过最短寻道时间来确定下一个寻找的磁道
SCAN：从一端向另一端移动，开头->尾部，尾部->开头
C-SACN：开头->尾部，开头->尾部
LOOK：只到最远的那个，不到磁盘尾部

热门文章