search

rrain7 / 2021Records

缅怀一下荒废的上半年
0 stars 0 forks source link

八股文-操作系统 #4

Open rrain7 opened 2 years ago

rrain7 commented 2 years ago

操作系统八股文 (想写一篇脱离低级趣味的八股文, 555555555)

rrain7 commented 2 years ago

死锁的四个必要条件是什么

rrain7 commented 2 years ago

死锁的四个必要条件是什么

rrain7 commented 2 years ago

进程, 线程, 协程 的区别?

人们都希望同时运行多个程序, 比如在工作的同时也希望听听音乐, 摸摸鱼. 对于现代操作系统来说, CPU是有限的, 而希望运行的应用数量大于CPU的数量. 操作系统通过虚拟化CPU来提供这种假象. 通过让一个进程只运行一个时间片, 然后切换到其他进程, 操作系统提供了存在多个虚拟CPU的假象. 操作系统为正在运行的程序提供的抽象, 就是所谓的进程. 那么构成进程的是什么呢?

经典的观点是一个程序只有一个执行点(一个程序计数器, 用来存放要执行的指令), 但多线程程序会有多个执行点(多个程序计数器, 每个都用于取指令和执行). 每个线程类似与独立的进程, 只有一点区别: 它们共享地址空间, 从而能够访问相同的数据. 单个线程的状态与进程的状态非常类似, 线程有一个程序计数器, 记录从哪里获得指令, 每个线程都有自己的一组用于计算的寄存器. 若有两个线程运行在一个处理器上, 从运行一个线程T1 切换到另一个线程T2 必定发生上下文切换. 与进程上下文切换类似, 进程的上下文切换, 我们将状态保存在进程控制块, 现在需要一个或多个线程控制块保存每个线程的状态. 但是有一点区别就是: 线程的地址空间保持不变. 进程和线程之间的另一个主要区别在于 栈. 简单的传统进程地址空间中只有一个栈, 在多线程的进程中, 每个线程独立运行, 都拥有自己的栈.

rrain7 commented 2 years ago

死锁的四个必要条件是什么

关于锁, 我们如何实现锁呢? 在实现之前, 先看看如何评价一种锁的实现效果. 一些标准:

  1. 提供互斥: 锁是否可以阻止多个线程进入临界区
  2. 公平性: 当锁可用时, 是否每个竞争的线程有公平的机会抢到锁
  3. 性能问题: 使用锁之后增加的时间开销 包括几种场景:
    • 只有一个线程抢锁, 释放锁的开支
    • 一个CPU上多个线程竞争, 性能如何?
    • 多个CPU 多个线程竞争时的性能
rrain7 commented 2 years ago

关于锁🔒

如何给数据结构加锁?

  1. 如何加锁才能让特定的数据结构功能正确?
  2. 如何对该数据结构加锁, 能够保证高性能, 让许多线程同时访问该结构, 即并发访问?
rrain7 commented 2 years ago

锁并不是并发程序设计所需要的唯一原语 具体来说, 很多情况下, 线程需要检查某一个条件满足后, 才会运行 如何等待一个条件

多线程程序中, 一个线程等待某些条件是很常见的, 简单的方案是自旋直到条件满足, 这个是极其低效的, 甚至某些情况下是错误的, 那么, 线程如何等待一个条件?

rrain7 commented 2 years ago

对内存的虚拟化

操作系统提供对物理内存进行抽象 -- 地址空间

地址空间

一个进程的 地址空间 包含运行的程序的所有内存状态。 比如：

当我们描述「地址空间」时，所描述的是操作系统提供给运行程序的抽象， 程序不在物理地址 0～16 k 的内存中，而是加载在任意的物理地址。

如何虚拟化内存？

操作系统如何在单一的物理内存上为多个运行的进程（所有进程共享内存）构建一个私有的、可能 很大的地址空间的抽象？

虚拟内存系统的一个目标是：透明

透明指的是：操作系统提供的假象不应该被应用程序看破。

另一个目标是：效率 第三个目标是：保护

操作系统应确保进程受到保护（protect），不会受其他进程影响，操作系统本身也不会受进程影响。

虚拟化内存的基本机制：硬件和操作系统的支持

基于硬件的地址转换：利用地址转换，硬件将指令中的虚拟地址转换为数据实际存储的物理地址。

每次内存引用，硬件都会进行地址转换，将运行应用的内存引用重定位到为实际的物理地址。

仅仅依靠于硬件不足以实现 虚拟内存，它只提供了底层机制来提高效率，操作系统必须在关键时刻介入，设置好硬件完成地址转换。

同样，所有这些工作都是为了创造一种美丽的假象：每个程序都拥有私有的内存，那里存放着它自己的代码和数据。虚拟现实的背后是丑陋的物理事实：许多程序其实是在同一时间共享着内存，就像CPU（或多个CPU）在不同的程序间切换运行。通过虚拟化，操作系统（在硬件的帮助下）将丑陋的机器现实转化成一种有用的、强大的、易于使用的抽象。

基于硬件动态重定向

基址（base） + 界限（bound）机制 具体来说：每个 CPU 需要两个硬件寄存器，基址寄存器+界限寄存器

这组基址和界限寄存器，让我们能够将地址空间放在物理内存的任何位置，同时又能确保进程只能访问自己的地址空间。

进程中使用的内存引用是 虚拟地址 硬件会将 虚拟地址 + 基址寄存器的内容，得到物理地址，再发送给内存系统。

界限寄存器提供了访问保护，确保进程产生的所有地址都在进程的地址“界限”中。

操作系统需要干啥？动态重定向，操作系统的职责

在一些关键的时刻， 操作系统需要介入，以实现基址和界限方式的虚拟内存

  1. 内存管理： 需要为新进程分配内存，从终止的进程回收内存，一般通过空闲列表（free list）来管理内存
  2. 基址/界限管理： 必须在上下文切换时正确设置基址/界限寄存器
  3. 异常处理：当异常发生时执行的代码，可能的动作是终止犯错的进程

一般来说，操作系统正确设置硬件后，就任凭进程直接在 CPU 上执行，只有进程行为不端或者中断的时候才介入。

上述 基址+界限 的方式，可能在堆和栈之前存在很大的空闲区域，这样的虚拟内存很浪费。另外，如果剩余物理内存无法提供连续区域来放置完整的地址空间，进程便无法运行。

这样的虚拟内存显然不够灵活，怎么支持大地址空间？

分段：泛化的基址/界限

引入不止一个 基址+界限寄存器 对， 而是给地址空间每个逻辑段一对。

分段的机制使得操作系统能够将不同的段放到不同的物理内存区域，从而避免了虚拟地址空间中的未使用部分占用物理内存。

虚拟内存的相关策略：如何管理空间？空间不足，哪些页面应该释放？

==todo==