八股-操作系统

内核态和用户态和系统调用

根据进程访问资源的特点，把进程在系统上的运行分为用户态和内核态

用户态具有较低的数据访问权限，可直接读取用户程序的数据，而内核态拥有较高的权限，几乎可以访问计算机的任何资源，当应用程序需要执行某些特殊权限的操作的时候，会通过系统调用切换到内核态

把进程分为用户态和内核态是出于安全性和性能上的考虑

用户态和内核态之间的切换有系统调用、中断、异常三种方式

系统调用是主动用户态进程主动要求切换的一种方式，通过系统调用，应用程序可以和操作系统之间进行交互，访问操作系统底层资源（文件、设备、网络

中断是外部设备完成用户操作请求之后，向cpu发出中断信号，这时cpu会暂停执行吓一跳指令先去执行中断信号对应的程序，如果中断之前执行的是用户态程序，那么此时就自然而然的发生了用户态到内核态之间的切换

异常是cpu在执行用户态程序的时候，发生了不可知的异常，此时进程会切换到异常处理的内核相关程序中，也就切换到了内核态。

进程和线程（重要）

进程和线程的基本定义，然后再让你对比一下两者

  • 进程是计算机上正在运行的一个程序的实例
  • 线程也被称为轻量级进程,是进程被划分为更小的运行单位。
  • 一个程序至少有一个进程，一个进程至少有一个线程
  • 进程和进程之间不共享资源是独立的，线程和线程之间共享同一个进程的资源,且有可能互相影响

进程和线程的状态

我们一般把进程大致分为 5 种状态，这一点和线程很像,

  1. 创建状态(new)：进程正在被创建
  2. 就绪状态(ready)：进程已处于准备运行状态，即进程获得了除了处理器之外的一切所需资源，一旦得到处理器资源(处理器分配的时间片)即可运行
  3. 运行状态(running)
  4. 阻塞状态(waiting)：又称为等待状态，进程正在等待某一事件而暂停运行如等待某资源为可用或等待 IO 操作完成。即使处理器空闲，该进程也不能运行。
  5. 结束状态(terminated)

内存管理（重要）

内存管理的目的、逻辑和物理地址

  • 内存的分配与回收：对进程所需的内存进行分配和释放，malloc 函数：申请内存，free 函数：释放内存。
  • 地址转换：将程序中的虚拟地址转换成内存中的物理地址。
  • 内存扩充：当系统没有足够的内存时，利用虚拟内存技术或自动覆盖技术，从逻辑上扩充内存。
  • 内存映射：将一个文件直接映射到进程的进程空间中，这样可以通过内存指针用读写内存的办法直接存取文件内容，速度更快。
  • 内存优化：通过调整内存分配策略和回收算法来优化内存使用效率。
  • 内存安全：保证进程之间使用内存互不干扰，避免一些恶意程序通过修改内存来破坏系统的安全性。

内存管理机制

  • 连续内存管理：为一个用户程序分配一个连续的内存空间，内存利用率一般不高。容易产生内存碎片

  • 非连续内存管理：允许一个程序使用的内存分布在离散或者说不相邻的内存中，相对更加灵活一些。

虚拟内存和请求分页

虚拟内存(Virtual Memory)本质上来说它只是逻辑存在的，是一个假想出来的内存空间
它允许程序访问比实际物理内存更大的内存空间。
在使用虚拟内存的系统中，每个程序都认为它拥有连续的、私有的内存空间，这被称为虚拟地址空间

虚拟内存的主要主要作用：

  • 隔离进程：物理内存通过虚拟地址空间访问，虚拟地址空间与进程一一对应。每个进程都认为自己拥有了整个物理内存，进程之间彼此隔离，一个进程中的代码无法更改正在由另一进程或操作系统使用的物理内存。
  • 提升物理内存利用率：有了虚拟地址空间后，操作系统只需要将进程当前正在使用的部分数据或指令加载入物理内存。
  • 简化内存管理：进程都有一个一致且私有的虚拟地址空间，程序员不用和真正的物理内存打交道，而是借助虚拟地址空间访问物理内存，从而简化了内存管理。
  • 多个进程共享物理内存：进程在运行过程中，会加载许多操作系统的动态库。这些库对于每个进程而言都是公用的，它们在内存中实际只会加载一份，这部分称为共享内存。
  • 提高内存使用安全性：控制进程对物理内存的访问，隔离不同进程的访问权限，提高系统的安全性。
  • 提供更大的可使用内存空间：可以让程序拥有超过系统物理内存大小的可用内存空间。
    这是因为当物理内存不够用时，可以利用磁盘充当，将物理内存页（通常大小为 4 KB）保存到磁盘文件（会影响读写速度），数据或代码页会根据需要在物理内存与磁盘之间移动。

局部性原理是指在程序执行过程中，数据和指令的访问存在一定的空间和时间上的局部性特点。其中，时间局部性是指一个数据项或指令在一段时间内被反复使用的特点，空间局部性是指一个数据项或指令在一段时间内与其相邻的数据项或指令被反复使用的特点。

  • 请求分页 ： 页表机制、缺页中断、页面置换算法

虚拟地址和物理地址

虚拟地址是程序开发时程序员与程序员进行交互的地址
物理地址就是内存地址寄存器中真正的地址

MMU(memeory management unit)将虚拟地址转化为物理地址,这个过程称之为地址转换

而地址转换有两种方式:

分段机制和分页机制

分段机制以一段连续的物理内存管理（不同长度的段）和分配物理内存，通过段表来映射虚拟地址和物理地址

分页机制把物理内存分为连续等长的物理页，通过页表来映射地址,虚拟地址空间中的任意虚拟页可以被映射到任意的物理页上，所以可以实现物理内存资源的离散分配

死锁

多个进程/线程同时被阻塞，它们中的一个或者全部都在等待某个资源被释放。由于进程/线程被无限期地阻塞，因此程序不可能正常终止。

死锁的必要条件

互斥、占有并等待、非抢占、循环等待

死锁预防、避免、检测与解除

预防死锁的方法

是通过考虑破坏第二个条件和第四个条件。

  1. 静态分配策略:静态分配策略破坏死锁产生的第二个条件（占有并等待）。指一个进程必须在执行前就申请到它所需要的全部资源，并且知道它所要的资源都得到满足之后才开始执行。进程要么占有所有的资源然后开始执行，要么不占有资源。这种策略简单但效率低下
  2. 层次分配策略:破坏了产生死锁的第四个条件(循环等待)。所有的资源被分成了多个层次，一个进程得到某一次的一个资源后，它只能再申请较高一层的资源；当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源，这样不会发生循环等待。

常用的解除死锁的方法有以下四种：

  1. 立即结束所有进程的执行，重新启动操作系统
  2. 撤销涉及死锁的所有进程，解除死锁后继续运行
  3. 逐个撤销涉及死锁的进程，回收其资源直至死锁解除。
  4. 抢占资源：从涉及死锁的一个或几个进程中抢占资源，把夺得的资源再分配给涉及死锁的进程直至死锁解除。

CPU 调度

几种常见的 CPU 调度算法

  • 先到先服务调度(First-Come First-Served Scheduling，FCFS)
  • 最短作业优先调度(Shortest Job First，SJF)
  • 优先级调度（Priority Scheduling）
  • 轮转法调度(Round Robin，RR)

多级队列调度（Multilevel Queue） 就诞生了。简单来说就是把就绪队列（存放有待执行进程）分成多个独立队列，每个队列都有自己的调度算法。

Linux相关（重要）

Linux 常用命令

1.cd 切换目录，2.mkdir创建目录,3.mv移动或重命名 ,4.cp复制, 5.touch 创建文件 7.find查找8.cat/tail/head/less查看 9.ps-ef查看进程 10.ifconfig 查看ip地址 11.rm删除

  • file:file通过探测文件内容判断文件类型，使用权限是所有用户

  • grep:grep命令可以指定文件中搜索特定内容，并将含有这些内容的行标准输出

  • tar：对文件进行打包，调用gzip或bzip对文件进行压缩或解压

  • 查看进程：ps -ef|grep 进程id 【ps:将某个进程显示出来 -A 　显示所有程序。 -e 　此参数的效果和指定”A”参数相同。 -f 　显示UID,PPIP,C与STIME栏位。】

  • 杀死叫firefox的进程：ps aux| grep firefox | awk ‘{print $2}’ |xargs kill *

xargs 命令是用来把前面命令的输出结果(PID)作为“kill -s 9”命令的参数，并执行该命令

$pkill -９ firefox *说明：pkill＝pgrep+kill，”-9” 即发送的信号是9，

pkill与kill在这点的差别是：pkill无须 “ｓ”，终止信号等级直接跟在 “-“ 后面

pgrep的p表明了这个命令是专门用于进程查询的grep

查看端口号: netstat –tunlp|grep 端口号或lsof -i:端口号

如何查看Linux系统进程？

通过ps命令可以查看当前系统运行的进程的列表，包括PID，进程名，CPU占用百分比，内存占用等信息。

可以使用top命令来查看Linux系统正在运行的进程。

如何查看a.txt的第7到第9行？

  • cat a.txt | tail -n +7 | head -n 9

  • sed -n ‘7,9p’ a.txt

查看文件a.txt的前3行

cat a.txt | head -n 3 或 head a.txt -n 3 (后3行用tail)

查看文件a.txt，显示第50行到第200行

cat a.txt | head -n 200 | tail -n +50
tail -n +50：从50行开始显示，显示50行以后的
head -n 200：显示前面200行

查看a.txt文件的第5行

awk 'NR==5' a.txt
head -n 5 a.txt | tail -n 1
sed -n 5p

一个文件中字段以逗号隔开，如何查看某一列的所有的数据？

awk -F[,] '{print $10}'

如何查看程序运行时的某个端口？

lsof -i :<端口号>

Linux 文件系统

常见目录说明：

  • /bin： 存放二进制可执行文件(ls、cat、mkdir 等)，常用命令一般都在这里；
  • /etc： 存放系统管理和配置文件；
  • /home： 存放所有用户文件的根目录，是用户主目录的基点，比如用户 user 的主目录就是/home/user，可以用~user 表示；
  • /usr： 用于存放系统应用程序；
  • /opt： 额外安装的可选应用程序包所放置的位置。一般情况下，我们可以把 tomcat 等都安装到这里；
  • /proc： 虚拟文件系统目录，是系统内存的映射。可直接访问这个目录来获取系统信息；
  • /root： 超级用户（系统管理员）的主目录（特权阶级^o^）；
  • /sbin: 存放二进制可执行文件，只有 root 才能访问。这里存放的是系统管理员使用的系统级别的管理命令和程序。如 ifconfig 等；
  • /dev： 用于存放设备文件；
  • /mnt： 系统管理员安装临时文件系统的安装点，系统提供这个目录是让用户临时挂载其他的文件系统；
  • /boot： 存放用于系统引导时使用的各种文件；
  • /lib 和/lib64： 存放着和系统运行相关的库文件 ；
  • /tmp： 用于存放各种临时文件，是公用的临时文件存储点；
  • /var： 用于存放运行时需要改变数据的文件，也是某些大文件的溢出区，比方说各种服务的日志文件（系统启动日志等。）等；
  • /lost+found： 这个目录平时是空的，系统非正常关机而留下“无家可归”的文件（windows 下叫什么.chk）就在这里。

僵尸进程和孤儿进程

  • 僵尸进程：子进程已经终止，担父进程仍然在运行，而且父进程没有调用wait或waitpid等系统调用来释放子进程占用的资源。这种情况下的子进程称为僵尸进程

  • 孤儿进程：父进程没了，但是子进程仍然在运行

Linux可以通过top指令来查看僵尸进程，zombie的值标识僵尸进程的数量

如何从亿万个数据中找到前100个数

采用分治法加堆排序

什么时候用多线程，什么时候用单线程

单线程 ：

  1. 程序简单，线性执行
  2. 避免多线程复杂性
  3. 任务不需要并发或并行处理
  4. 系统资源有限
  5. 出于开发成本考虑，单线程更加简单、易维护

多线程：

  1. 任务可并发
  2. io密集型任务，因为这些任务往往是阻塞的
  3. cpu密集型任务
  4. 提升程序响应速度：例如主线程复制用户交互，令一个线程负责处理数据计算
  5. 服务器需要同时处理多个客户端请求

内存分配方式

  • 连续内存分配:块状管理
  • 非连续内存分配：分段、分页、段页式(先分段，再分页)

分段和分页的区别

分段：

  • 用一段段不同长度的连续的物理内存分配物理内存
  • 通过段表映射虚拟地址和物理地址

分页：

  • 把物理内存分为连续等长的物理页
  • 用页表映射虚拟地址和物理地址

区别：

  • 页的大小固定、段的大小不固定
  • 分段容易出现外部内存碎片、分页解决了外部内存碎片
  • 分页机制采用了页表来完成虚拟地址到物理地址的映射，页表通过一级页表和二级页表来实现多级映射；而分段机制则采用了段表来完成虚拟地址到物理地址的映射，每个段表项中记录了该段的起始地址和长度信息。
  • 分页机制对程序没有任何要求，分段机制需要程序员将程序分为多个段