xv6操作系统#

背景#

• 内存保存在单向链表freelist当中，并使用自旋锁进行保护
• 内存相关操作
  • kfree：释放内存，头插
  • kalloc：分配内存，取头
• 物理内存是在多进程之间共享的，所以不管是分配还是释放页面，都要先获得一个内存分配的锁，才能对freelist进行操作

解决方案#

• old：一个内存锁和存储空闲页帧的链表
• new：为8个CPU每个CPU都分配了独立的内存锁和独立的存储空闲页帧的链表。在系统初始化的时候平均分配给8个freelist
• 窃取：
  • 释放自身的锁
  • 按顺序请求别freelist的锁
    • 为空，释放锁，重复操作
    • 不为空：获取空闲页帧，释放锁

背景#

由于对磁盘的读取非常慢，而内存的速度要快得多，因此将最近经常访问的磁盘块缓存在内存里可以大大提升性能。内存中的BufferCache就担任了磁盘缓存的作用。

解决方案（哈希桶）#

• 获取一个buf进行读/写操作bget(int blockno)
  • 求得哈希值
  • 获取桶的锁，从前往后遍历这个桶里的buf
  • 如果命中：增加buf的引用计数、为该buf上锁，释放哈希桶的锁，返回buf
  • 如果不命中：从后往前寻找引用树为0的buf、为buf上锁，释放哈希桶的锁，修改buf中的内容。返回buf
  • 该哈希桶中没有空闲的buf，进入全局窃取阶段
    • 先释放哈希桶的锁（要不然会有死锁）
    • 再依次获得全局锁与该哈希桶的锁(顺序反了也会有死锁)
    • 再查看自己有没有命中（避免一个桶里blockno重复）。如有：获得buf的锁、释放哈希桶的锁、全局锁
    • 如果没有命中：遍历除了自己的哈希桶。
      • 找到了引用数为0的：初始化这个buf，并将其添加到自己的哈希桶中，头插。获得这个buf的锁、释放这个被窃取的哈希桶、释放自己哈希桶、释放全局锁。
• brelse
  • 释放buf的锁
  • 获得对应的哈希桶的锁
  • 将其插入进去、并修改引用计数。如果引用计数为0的话，插入尾部
  • 释放哈希桶的锁