前言

对于学习ucore的时候,一些操作系统遗留下来的知识,以及面试常见的问题进行一下总结

正文

buddy system伙伴系统

Buddy system要解决的问题是频繁地请求和释放不同大小的一组连续页框,必然导致在已分配的块内分散了许多小块的空闲页面,由此带来的问题是,即使有足够的空闲页面可以满足请求,但要分配一个大块的连续页框可能无法满足请求。其要完成的作用,即高效的分配和回收资源,降低外部碎片。

基本单位是block,由2^n个物理page组成,然后n相同的空闲block组成双向链表,如果相邻的block也是空闲的就可以组成2^(n+1)大小的block,挂载在另一个order为n+1的双向链表中。

  • 取page的时候就是从1到2^n逐渐找,找到就逐渐分半划分到相应的双向链表中。
  • 释放的时候查看是否两个大小为b的空闲伙伴合并为2b,然后继续迭代直到不满足伙伴空闲

好处是

  • 较好的解决外部碎片问题
  • 为大内存设计
  • 当需要分配若干个内存页面时,用于DMA的内存页面必须连续,伙伴算法很好的满足了这个要求

坏处是

  • 合并要求比较难
  • 可能block中会浪费很多page
  • 进行block移动时候可能会有来回都懂,无效操作比较多

对于小的内存分配好像是slab具体我没看了

fork的具体过程

其实就是类似我们lab5的内容,fork的时候需要利用中断从用户态到内核态进行系统调用(这里应该有个保护现场的操作),然后为进程申请空闲块并分配进程号,然后拷贝父进程的pcb,页表信息,堆栈信息,GDT表等信息,最后将新进程设置为就绪态,等待调度,对于fork父进程返回的是子进程的id,自称中返回的是0,错误则为负数。

COW的机制实现

Copy on write机制,我们上面fork的时候父子进程指向虽然拷贝了相同的内存,但是因为cow机制只有当其中一进程进行写操作时,系统才会为其另外分配内存页面。

fork之后kernel把父进程中所有的内存页的权限都设为read-only,然后子进程的地址空间指向父进程。当父子进程都只读内存时,相安无事。当其中某个进程写内存时,CPU硬件检测到内存页是read-only的,于是触发页异常中断(page-fault),陷入kernel的一个中断例程。中断例程中,kernel就会把触发的异常的页复制一份,于是父子进程各自持有独立的一份。

死锁重入探测机制

Linux 提供了检测死锁的机制,主要分为 D 状态死锁和 R 状态死锁。

  • D 状态死锁
    进程等待 I/O 资源无法得到满足,长时间(系统默认配置 120 秒)处于 TASK_UNINTERRUPTIBLE 睡眠状态,这种状态下进程不响应异步信号(包括 kill -9)。如:进程与外设硬件的交互(如 read),通常使用这种状态来保证进程与设备的交互过程不被打断,否则设备可能处于不可控的状态。对于这种死锁的检测 Linux 提供的是 hung task 机制。触发该问题成因比较复杂多样,可能因为 synchronized_irq、mutex lock、内存不足等。D 状态死锁只是局部多进程间互锁,一般来说只是 hang 机、冻屏,机器某些功能没法使用,但不会导致没喂狗而系统死机。

  • R 状态死锁
    进程长时间(系统默认配置 60 秒)处于 TASK_RUNNING 状态垄断 CPU 而不发生切换,一般情况下是进程关抢占或关中断后长时候执行任务、死循环,此时往往会导致多 CPU 间互锁,整个系统无法正常调度,导致喂狗线程无法执行,无法喂狗而最终看门狗复位的重启。该问题多为原子操作,spinlock 等 CPU 间并发操作处理不当造成。本文所介绍的 Lockdep 死锁检测工具检测的死锁类型就是 R 状态死锁。

D状态死锁的检测主要依靠hung task机制

1.创建Normal级别的khungtaskd内核线程,在死循环中每隔sysctl_hung_task_timeout_secs时间后check一下,用schedule_timeout定时(节约定时器浪费的CPU)。

2.调用do_each_thread,while_each_thread宏遍历所有的进程信息,如果有D状态进程,则检查最近切换次数和task计算是否一致,即最近是否有调度切换,如果一致,则没有切换,打印相关信息,并根据sysctl_hung_task_panic开关决定是否重启。

R状态死锁检测依靠lockdep机制

1.通过cpu_callback函数调用watchdog_enable,在每个CPU core上创建SCHED_FIFO级别的实时线程watchdog,其中使用了hrtimer定时器,控制检查周期。

2.hrtimer定时器调用watchdog_timer_fn进行清狗的时间检查,而线程则每次重置清狗时间,如果watchdog_timer_fn发现狗的重置时间已经和当前时间差出危险值,则根据开关进行panic处理。

RCU机制

RCU(Read-Copy Update)“随意读,但更新数据的时候,需要先复制一份副本,在副本上完成修改,再一次性地替换旧数据”。这是 Linux 内核实现的一种针对“读多写少”的共享数据的同步机制。

  • 读标

    如果一个Reader企图占据一把RCU锁,它是不需要付出任何代价的,只需要设置一个标志,让外界知道有Reader在占据这把RCU锁,多个Reader可以共同持有一把RCU锁。

  • 写时拷贝

    如果有一个Write企图更新RCU锁所保护的数据,那么它会首先查看该RCU锁的读标志,如果有该标志,说明有最少一个Reader持有了该RCU锁,它需要对原始数据make a copy,写这个副本并将更新过的副本保存在某处,等待时机用该副本更新原始数据。

  • 更新时机

    这 个时机就是用副本更新原始数据的时间点,这个时间点如何确定是RCU锁实现的算法核心,它直接可以确定所有的数据结构。确切来讲,Writer必须 waitting for all readers leaving,方可Update原始数据,问题是,它是怎么知道所有的Reader都离开了呢?一个是利用禁止抢占,一个是利用计数器,具体看下这篇文章

Select poll epoll机制

可以看下这篇文章

其实都是I/O多路复用技术的系统实现调用,I/O多路复用就是通过一种机制,一个进程可以监视多个描述符,一旦某个描述符就绪(一般是读就绪或者写就绪),能够通知程序进行相应的读写操作。但select,pselect,poll,epoll本质上都是同步I/O,因为他们都需要在读写事件就绪后自己负责进行读写,也就是说这个读写过程是阻塞的,而异步I/O则无需自己负责进行读写,异步I/O的实现会负责把数据从内核拷贝到用户空间。

select本质上是通过设置或者检查存放fd标志位的数据结构来进行下一步处理,每当一个fd被唤醒后,都要循环遍历来寻找就绪设备,都是将fd数组从用户态复制到内核态,所以当连接的socket变很多时效率都会变慢,(poll没有连接限制,因为使用的是链表)

Epoll使用一个文件描述符管理多个描述符,将用户关系的文件描述符的事件存放到内核的一个事件表中,这样在用户空间和内核空间的copy只需一次,采用注册回调函数的方法来调用,效率提升,不是轮询的方式,不会随着FD数目的增加效率下降。只有活跃可用的FD才会调用callback函数;即Epoll最大的优点就在于它只管你“活跃”的连接,而跟连接总数无关,因此在实际的网络环境中,Epoll的效率就会远远高于select和poll。

总结

其余的常见面经题我就懒得放了,我自己整理了一份,等我搞完所有的东西后,再找机会发出来吧。