操作系统

一、操作系统原理

操作系统：

  • 是管理计算机硬件与软件资源的程序，是计算机系统的内核与基石

  • 是资源分配器和控制程序，管理所有资源，防止资源的错误或不当使用

  • 为用户提供一个与系统交互的操作界面（GUI、CLI）

1. 系统调用

系统调用是操作系统内核对外提供的服务，为运行在用户态的程序提供了访问关键资源的途径。

用户态和内核态

根据进程访问资源的特点，可以把进程为两个运行级别：

  • 用户态 (user mode) 的进程只能访问有限的资源

  • 内核态 (kernel mode) 的进程几乎可以访问计算机的所有资源

分类

  • 进程管理：创建、管理进程

  • 进程通信：在进程间传递信息

  • 内存管理：分配、回收内存

  • 文件管理：创建、管理文件系统中的文件

  • 通信：创建网络连接，收发数据包

  • 设备管理：请求访问访问鼠标、键盘等硬件设备

2. 进程管理

进程状态

进程调度算法

  • 先到先服务

    从就绪队列中选择一个最先进入该队列的进程执行。

  • 短作业优先

    从就绪队列中选出一个估计运行时间最短的进程执行。

  • 时间片轮转

    每个进程被轮流分配一个时间段（时间片）执行。

  • 优先级调度

    为每个流程分配优先级，首先执行具有最高优先级的进程，依此类推。

  • 多级反馈队列

    目前公认的一种较好的进程调度算法，既能使高优先级的作业得到响应又能使短作业迅速完成。

进程通信

推荐阅读：进程间通信IPC

  • 匿名管道 (Pipes) 用于具有亲缘关系的父子进程间或者兄弟进程间的通信。

  • 有名管道 (Names Pipes) 可以实现本机任意两个进程间的通信。

  • 消息队列 (Message Queuing) 存在于内核中的消息链表，可以实现多个进程间的通信。

  • 信号量 (Semaphores) 是一个计数器，用于协调多进程对共享数据的访问。

  • 共享内存 (Shared memory) 速度最快的进程间通信方式，多个进程访问同一块内存空间，不同进程可以看到其他进程对共享内存中数据的更新。

  • 套接字 (Sockets) 使不同主机之间的进程可以进行双向通信，详见计算机网络 - Socket.

进程同步

TODO

3. 死锁

死锁是指两个或两个以上的进程在执行过程中由于资源竞争而造成的阻塞现象，若无外力作用，它们都将无法推进下去。

发生死锁的必要条件

  • 互斥：每个资源只能分配给一个进程

  • 占有并等待：已经得到了某个资源的进程可以再请求新的资源

  • 不可抢占：已经分配给一个进程的资源不能被抢占，只能被占有它的进程显式释放

  • 循环等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源

死锁预防

通过破坏死锁发生的的必要条件，在程序运行之前预防发生死锁。

  • 破坏互斥条件 例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。

  • 破坏占有并等待条件 要求所有进程在开始执行前请求所需要的全部资源。

  • 破坏不可抢占条件 如果一个进程没有申请到所需的所有资源，它要释放所占有的资源。

  • 破坏循环等待条件 给资源统一编号，进程只能按编号顺序来请求资源。

死锁避免

在程序运行时避免发生死锁。

可以使用银行家算法，确保资源调度处于安全状态中。

死锁检测与恢复

当检测到死锁发生时，采取措施进行恢复。

死锁检测

  • 每种资源只有一个实例（环搜索）

  • 每种资源有多个实例（类似银行家算法）

死锁恢复

  • 依次中断死锁进程，直到死锁环消失

  • 允许抢占资源

4. 内存管理

内存管理主要负责：

  • 内存的分配与回收

  • 地址转换：将逻辑地址转换成相应的物理地址

  • 扩充内存空间：利用虚拟化技术从逻辑上扩充内存

内存管理机制

连续分配

将内存分为几个固定大小的块，每个块分配给一个进程。

非连续分配

  • 分页 将内存分为大小相等且固定的页，使用页表记录一个进程可以访问的页。

  • 分段 按照用户进程中的自然段划分逻辑空间。每个进程可以有多个段，如代码段、数据段等等。

  • 段页式 进程的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。

虚拟内存

作用

利用虚拟化技术从逻辑上扩充内存，为每个进程提供了一致的、私有的地址空间。

每个进程拥有自己的地址空间，这个地址空间被分成很多页，这些页被映射到物理内存。由于程序运行的局部性原理，不需要将所有页都保存在物理内存中。

页面置换算法

地址映射过程中，如果发现所要访问的页面不在内存中，则发生缺页中断。此时，如果内存中并没有空闲的页面，操作系统必须在内存中选择一个页面将其移出内存，以便为即将调入的页面让出空间。

常见的页面置换算法有：

  • OPT (Optimal Replacement) 选择在最长时间内不再被访问的页面淘汰，该算法无法实现，一般作为衡量其他置换算法性能的标准。

  • FIFO (First In First Out) 总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进行淘汰。

  • LRU (Least Currently Used) 该算法记录每个页面的最近访问时间，当淘汰一个页面时，选择现有页面中最久未使用的页面予以淘汰。

    （具体实现见缓存 - 数据过期策略 - LRU）

  • LFU (Least Frequently Used) 选择在之前时期使用最少的页面作为淘汰。

5. 文件管理

TODO

二、Linux

体系结构

Shell

Shell 是系统的用户界面，提供了用户与内核进行交互操作的接口。它接收用户输入的命令，并把它送入内核去执行。

Shell有多个版本，我们以BASH (Bourne Again Shell)为例介绍一些Shell的常用命令。

管道

管道操作符|可以将一个命令的标准输出作为另一个命令的标准输入。

查找文件

find [basedir] [option]
find ~ -name "README.md"    # 在用户目录下查找名称为README.md的文件
find . -name "README*"        # 在当前目录下模糊查找
find ~ -iname "README.md"    # 不区分文件名大小写

检索文件内容

grep [option] pattern filename
grep -n 'the' log.txt        # 在log.txt文件中查找'the'出现的行并显示行号
grep 'a\{2,5\}' log.txt        # 在log.txt文件中查找 出现2-5次的a, { 和 } 需要使用 \ 进行转义

统计文件内容

awk指令每次处理一行文本，按输入分隔符进行切片 每个切片依次命名为$1, $2, $3... （$0 表示一整行）

awk [option] 'cmd' filename
awk '{print $1, $4}' netstat.txt        # 打印netstat.txt文件中每行的第1、4列
awk '$1=="tcp" {print $0}' netstat.txt    # 当每行的第一列为"tcp"时，打印该行

批量编辑文件内容

sed [option] 'sed command' filename
sed -i 's/^Str/String/' test.txt        # 将test.txt文件中所有以'Str'开头的字符串替换成'String'
上一页计算机网络下一页数据结构与算法

最后更新于