导图社区 操作系统
- 73
- 1
- 0
- 举报
操作系统
操作系统框架：计算机的存储体系（用于暂存CPU的运算数据，以及与硬盘等外部存储器交换的数据。）、基本特征（进程控制、进程同步、进程通信、死锁处理、处理机调度等。）、基本功能、等等
编辑于2022-03-26 11:17:31- 相似推荐
- 大纲
OS
https://www.topgoer.cn/docs/data-structures-questions/data-structures-questions-1d94t1bk0bgcl
计算机的存储体系
CPU寄存器
寄存器是中央处理器的组成部份，可用来暂存指令、数据和位址。通常有通用寄存器，如指令寄存器IR、程序计数器(PC)、累加器(ACC)、堆栈指针寄存器(SP)等，另外还有状态寄存器(标记状态Z、N、V、C)。寄存器最靠近CPU，随取随用，速度最快。
Cache
高速缓冲存储器，位于CPU与内存之间，容量小但速度快。由于CPU快而内存慢，CPU不存在直接读或者写内存的情况,每次读或者写内存都要访问Cache。
Cache Line是cache与内存同步的最小单位，典型的虚拟内存页面大小为4K，Cache line为32或64字节。
Cache又分为L1、L2、L3（L1、L2一般集成在CPU上）
理论上L1有着跟寄存器相同的速度，但L1工作在写通过(write-through)模式下时，需要加锁用来同步cache和内存的内容，这段期间L1不能被访问，所以L1就没寄存器快。
L2、L3同样需要加锁，并且L2比L1慢，L3比L2慢
Cache下还有一个TLB，TLB是一个内存管理单元用于改进虚拟地址到物理地址转换速度的缓存。
内存
即RAM(主要针对DRAM)
用于暂存CPU的运算数据，以及与硬盘等外部存储器交换的数据。
CPU访问内存流程
找到数据(一般为操作数)地址(或地址的地址)。（地址一般放在通用寄存器内）
将地址送往内存管理单元（MMU），由MMU将虚拟的内存地址翻译成实际的物理地址。
将物理地址送往内存控制器，由控制器进行译码找到对应的存储体。
从对应的存储体读取数据送回给控制器，最后再送回CPU。
硬盘等辅助存储设备
常见的有磁性旋转机械盘和基于闪存的固态硬盘SSD
鼠标等外接设备
从上至下，越来越便宜，访问速度越来越慢，访问时间越来越长。
基本特征
并发和并行
共享
分为互斥共享和同时共享。互斥共享的资源称为临界资源。
需要用同步机制来实现对临界资源的访问。
虚拟
虚拟技术把一个物理实体转换为多个逻辑实体。
有两种虚拟技术：时分复用技术和空分复用技术。
异步
异步指进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进。
基本功能
进程管理
进程控制、进程同步、进程通信、死锁处理、处理机调度等。
内存管理
内存分配、地址映射、内存保护与共享、虚拟内存等。
文件管理
文件存储空间的管理、目录管理、文件读写管理和保护等。
设备管理
主要包括缓冲管理、设备分配、设备处理、虛拟设备等。
系统调用
定义：如果一个进程在用户态需要使用内核态的功能，就进行系统调用从而陷入内核，由操作系统代为完成。
系统调用举例
进程控制
fork();exit();wait()
进程通信
pipe();mamp();shmget()
文件操作
open();read();write()
设备操作
ioctl();read();write()
信息维护
getpid();alarm();sleep()
安全
chmod();umask();chown()
大内核微内核
大内核
将操作系统功能作为一个紧密结合的整体放到内核。
由于各模块共享信息，因此有很高的性能。
微内核
操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。
因为需要频繁地在用户态和核心态之间进行切换，所以会有一定的性能损失。
中断分类
外中断
CPU执行指令以外的事件：I/O 完成中断、设备输入/输出处理中断等
时钟中断、控制台中断
异常
CPU执行指令内部的事件
非法操作、地址越界、算数溢出
陷入
在用户程序中使用系统调用
进程管理1
进程
进程是资源分配的基本单位。
进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。
线程
线程是独立调度的基本单位。
进程线程区别
拥有资源
进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。
调度
在同一进程中，线程的切换不会引起进程切换，从一个进程内的线程切换到另一个进程中的线程时，会引起进程切换。
系统开销
通信方面
进程间通信 (IPC) 需要进程同步和互斥手段的辅助，以保证数据的一致性
线程间可以通过直接读/写同一进程中的数据段（如全局变量）来进行通信
进程状态转换
new、ready、running、waiting、terminated
ready态：等待被调度
waiting态：等待资源
进程只能自己阻塞自己，因为只有进程自身才知道何时需要等待某种事件的发生
只有就绪态和运行态可以相互转换、其它状态之间都是单向转换
进程调度算法
批处理系统
批处理系统没有太多的用户操作，在该系统中调度算法目标是保证吞吐量和周转时间。
先来先服务
短作业优先
最短剩余时间优先
交互式系统
交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。
时间片轮转算法
注意时间片轮转算法的效率和时间片的大小
优先级调度
了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级
多级反馈队列
时间片轮转调度算法和优先级调度算法的结合
实时系统
分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时
进程同步实现
临界区
对临界资源进行访问的那段代码称为临界区。
为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。
同步与互斥
同步：多个进程按一定顺序执行。
互斥：多个进程在同一时刻只有一个进程能进入临界区。
信号量
PV操作，P [减少，down]和 V[增加，up]
阻塞——down操作，对信号量-1，如果信号量等于 0，进程睡眠，等待信号量大于 0
唤醒——up操作，对信号量+1，唤醒睡眠的进程让其完成 down 操作。
down 和 up 操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断。
如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁
管程
一种程序结构，结构内的多个子程序（对象或模块）形成的多个工作线程互斥访问共享资源。
在一个时刻只能有一个进程使用管程。
管程引入了 条件变量 以及相关的操作：wait() 和 signal() 来实现同步操作。
经典同步问题
读-写问题
允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。
哲学家进餐问题
#define N 5 // 哲学家个数 void philosopher(int i) {// 哲学家编号：0 － 4 while(TRUE) { think(); // 哲学家在思考 take_fork(i); // 去拿左边的叉子 take_fork((i + 1) % N); // 去拿右边的叉子 eat(); // 吃面条中…. put_fork(i); // 放下左边的叉子 put_fork((i + 1) % N); // 放下右边的叉子 } }
如果恰巧所有哲学家同时拿起左手边的筷子，那么就无法拿起右手边的筷子，造成死锁。
semaphore mutex // 互斥信号量，初值1 void philosopher(int i) // 哲学家编号i：0－4 { while(TRUE){ think(); // 哲学家在思考 P(mutex); // 进入临界区 take_fork(i); // 去拿左边的叉子 take_fork((i + 1) % N); // 去拿右边的叉子 eat(); // 吃面条中…. put_fork(i); // 放下左边的叉子 put_fork((i + 1) % N); // 放下右边的叉子 V(mutex); // 退出临界区 } }
正确，但每次只允许一人进餐
为了防止死锁的发生，可以设置两个条件（临界资源）：
必须同时拿起左右两根筷子； 只有在两个邻居都没有进餐的情况下才允许进餐。
进程管理2
进程通信
进程通信【进程间传输信息】与进程同步【控制多个进程按一定顺序执行】很容易混淆
进程通信是一种手段，而进程同步是一种目的。也可以说，进程通信是为了达到进程同步目的的一种手段。
线程通信与进程通信
进程间通信方式
直接通信
Send(Receiver,message);//发送一个消息message给接收进程Receiver Receive(Sender,message);//接收Sender进程发送的消息message
间接通信
类似邮件系统
管道
int pipe(int fd[2]);
只支持半双工通信（单向传输）
只能在父子进程中使用
命名管道
FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据
消息队列
消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难；
信号量
它是一个计数器，用于为多个进程提供对共享数据对象的访问。
共享内存
这是最快的一种 IPC。[因为数据不需要在进程之间复制]
套接字
套接字与其它通信机制不同的是，它可用于不同机器间的进程通信。
线程间通信方式
synchronized同步
本质上就是 “共享内存” 式的通信。
wait/notify机制
while轮询的方式
这种方式会浪费 CPU 资源。
进程操作
PCB
进程控制块是进程存在的惟一标识，系统通过PCB的存在而感知进程的存在。
系统通过 PCB 对进程进行管理和调度。
PCB 包括创建进程、执行进程、退出进程以及改变进程的优先级等。
组成
代码段（程序）
数据段（数据）
堆栈段（控制块PCB）
程序转换为进程分几个步骤
1.内核将程序读入内存，为程序分配内存空间.
2.内核为该进程分配进程标识符 PID 和其他所需资源.
3.内核为进程保存 PID 及相应的状态信息，把进程放到运行队列中等待执行，程序转化为进程后可以被操作系统的调度程序调度执行.
进程0和进程1
Unix
进程 0 是系统引导时创建的一个特殊进程，在其调用 fork 创建出一个子进程（即 PID=1 的进程 1，又称 init）后，进程 0 就转为交换进程（有时也被称为空闲进程），而进程1（init进程）就是系统里其他所有进程的祖先。
Linux
进程0是Linux引导中创建的第一个进程，完成加载系统后，演变为进程调度、交换及存储管理进程。
进程1是init 进程，由0进程创建，完成系统的初始化. 是系统中所有其它用户进程的祖先进程。
创建一个进程
Linux系统下使用 fork() 函数创建一个子进程
pid_t fork(void);
返回0，则是子进程
返回>0，则是父进程
返回-1,则是错误
系统中已经有太多的进程存在
调用fork()函数的用户进程太多
pid_t vfork(void);
产生的子进程和父进程完全共享地址空间
包括代码段、数据段和堆栈段
除了 0 号进程（该进程是系统自举时由系统创建的），Linux 系统中的任何一个进程都是由其他进程创建的。
子进程v.s.父进程
子进程完全复制了父进程的地址空间的内容，包括堆栈段和数据段的内容。子进程并没有复制代码段，而是和父进程共用代码段。想想why？
退出进程
void exit(int status);
孤儿进程与僵尸进程
父进程需要调用 wait() 或者 waitpid() 系统调用取得子进程的终止状态
一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被 init 进程（进程号为1）所收养，并由 init 进程对它们完成状态收集工作。孤儿进程并不会有什么危害。
一个进程使用 fork 创建子进程，如果子进程退出，而父进程并没有调用 wait 或 waitpid 获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵尸进程。最有危害的是产生出大量僵尸进程的那个父进程。
解决办法——子进程退出时向父进程发送SIGCHILD信号，父进程处理SIGCHILD信号。在信号处理函数中调用wait进行处理僵尸进程。
守护进程
独立于控制终端并且周期性地执行某种任务或等待处理某些发生的事件。
守护进程经常以超级用户（root）权限运行，因为它们要使用特殊的端口（1-1024）或访问某些特殊的资源。
如sshd、httpd、crond、mysqld、syslogd等
上下文切换
是指CPU从一个进程或线程切换到另一个进程或线程。
通过中断或系统调用
CPU 切换到另一个进程需要保存当前进程的状态并恢复另一个进程的状态
死锁
原因
可重用资源引起的
消耗资源过多引起的
造成死锁的原因就是多个线程或进程对同一个资源的争抢或相互依赖
资源
资源包括，软件(程序)和硬件(扫描仪)
可剥夺资源（Preemptable）和不可剥夺资源 （Nonpreemptable）
一般来说对于由可剥夺资源引起的死锁可以由系统的重新分配资源来解决，所以一般来说大家说的死锁都是由于不可剥夺资源所引起的。
必要条件
互斥：每个资源要么已经分配给了一个进程，要么就是可用的。
占有和等待：已经得到了某个资源的进程可以再请求新的资源。
不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
循环等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。
处理策略
鸵鸟策略
大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。
检测死锁并恢复
仔细地对资源进行动态分配，以避免死锁。
通过破除死锁四个必要条件之一，来防止死锁产生。
不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。
死锁恢复
利用抢占恢复
利用回滚恢复
通过杀死进程恢复
死锁预防
破坏互斥条件
破坏占有和等待条件
破坏不可抢占条件
破坏循环等待
死锁避免
在使用前进行判断，只允许不会出现死锁的进程请求资源。
如何在程序开发中避免死锁
死锁，发生的主要原因在于了有多个进程去竞争资源，也就是同时去抢占。
可以自己写一个支持多线程的消息管理类，单开一个线程访问独占资源，其它线程用消息交互实现间接访问。 这种机制适应性强、效率高，更适合多核环境。
内存管理
虚拟内存
虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。它向进程屏蔽了底层了RAM和磁盘
每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。
这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。
虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序称为可能。
分页系统地址映射
内存管理单元（MMU）
管理着地址空间和物理内存的转换。
页表（Page table）
页（地址空间）和页框（物理内存空间）的映射表
子主题
页面置换算法
定义：在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。
目的：页面置换算法的主要目标是使页面置换频率最低
算法
Optimal
所选择的被换出的页面将是最长时间内不再被访问
Least Recently Used(LRU)
最近最久未使用的页面换出
因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高
Not Recently Used(NRU)
优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。
First In First Out(FIFO)
选择换出的页面是最先进入的页面。
该算法会将那些经常被访问的页面也被换出，从而使缺页率升高。
第二次机会算法
检查最老页面的 R 位
如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉
如果是 1，就将 R 位清 0，并把该页面放到链表的尾端
Clock
时钟算法使用环形链表将页面链接起来，再使用一个指针指向最老的页面。
分段
虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，每一页再与内存进行映射。
把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。
段页式
程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。
分页v.s.分段
1.对程序员的透明性：分页透明，但是分段需要程序员显示划分每个段。
2.地址空间的维度：分页是一维地址空间，分段是二维的。
3.大小是否可以改变：页的大小不可变，段的大小可以动态改变。
4.出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。
设备管理
磁盘结构
磁盘调度算法
先来先服务(First Come First Served,简称FCFS)
平均寻道时间可能较长
最短寻道时间优先(Shortest Seek Time First,简称SSTF)
可能会有饥饿现象
电梯算法(SCAN)
总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求
系统处理过程
1.编译系统
hello.c文件
#include <stdio.h> int main(){ printf("Golang is Best Language\n"); return 0; }
gcc -o hello hello.c
等价于
预处理cpp
gcc -E hello.c -o hello.i
编译cc1
gcc -S hello.i -o hello.s
汇编as
as hello.s -o hello.o
链接
gcc hello.o -o hello
2.静态链接
静态连接器以一组可重定向目标文件为输入，生成一个完全链接的可执行目标文件作为输出。
两个任务
符号解析
重定位
3.目标文件
可执行目标文件：可以直接在内存中执行
可重定向目标文件：可与其它可重定向目标文件在链接阶段合并，创建一个可执行目标文件
共享目标文件：这是一种特殊的可重定向目标文件，可以在运行时被动态加载进内存并链接
4.动态链接
静态链接的问题
当静态库更新时那么整个程序都要重新进行链接
对于 printf 这种标准函数库，如果每个程序都要有代码，这会极大浪费资源
解决→共享库
在 Linux 系统中通常用 .so 后缀来表示，Windows 系统上它们被称为 DLL。
特点
在给定的文件系统中一个库只有一个文件，所有引用该库的可执行目标文件都共享这个文件，它不会被复制到引用它的可执行文件中
在内存中，一个共享库的 .text 节（已编译程序的机器代码）的一个副本可以被不同的正在运行的进程共享。