6.1810: Operating System Engineering 2023 <Lab7 lock: Parallelism/locking>

news/2024/2/24 8:51:18/文章来源:https://blog.csdn.net/qq_51103378/article/details/135451402

一、本节任务

二、要点 

2.1 文件系统(file system) 

xv6 文件系统软件层次如下:

通过路径树我们可以找到相应的文件:

fd(文件描述符)是进程用来标识其打开的文件的手段,每个进程有自己的文件打开表,并且系统会维护一个全局文件打开表(系统中所有打开的文件都保存在这个全局文件打开表中)。

进程通过 fd 将文件作为一系列字节来访问,每一个 fd 都有一个光标(cursor)来指向文件的当前访问位置:

read() 和 write() 系统调用都会使光标前进: 

也有一些特殊的文件,比如 pipe() 创建出来的缓冲区,其本质是一个文件,不同的进程使用 fd 对缓冲区文件进行读和写,从而实现进程间的通信: 

inode(index node)索引节点用来记录一个文件的详细信息,包括:

  • 记录文件的大小以及数据在磁盘上的存储位置;
  • 记录文件的硬链接数量(和打开 fd 数量);

inode 可以是指磁盘上的 inode,也可能指内存上的 inode 副本(读写 inode 时会先将其读入内存中)。磁盘上的 inode 被打包到一个称为 inode 块的相邻磁盘区域中,每个 inode 大小都一样,所以通过一个索引 i 能很容易找到相应的索引节点,这个索引 i 也被称为 i-number 或 inode number。

address1~12 为直接索引,指向的为数据块,而 indrect 为间接索引,指向的为 indirect block,indirect block 里面的地址才指向数据块,这种方式可以增加文件的最大大小,并且减少 dinode 结构体的大小。 

数据存储的位置? 

磁盘访问是十分低效的,我们可以将 RAM 的一部分作为磁盘的 cache,每次访问磁盘会将连续的部分内容复制到 RAM 上,当再次访问的时候就不需要去访问磁盘,而是访问复制到 RAM 上的内容即可,其替换策略为 LRU(least recently used)。buffer cache 有两个作用:

  1. 同步对磁盘块的访问,以确保只有一个块的副本在内存中,并且一次只有一个内核线程使用该副本;
  2. 缓存常用的块,以便不需要从慢速磁盘上重新读取它们。

相关代码在 bio.c 中,其中主要的接口为 bread() 和 bwrite():

  • bread():获取一个能在内存中读写的磁盘块的副本,使用 buf(buf.h)结构体来管理这个副本;
  • bwrite():后者将修改后的缓冲区写入磁盘上的对应块;
  • brelse():内核线程在使用完后这块缓冲区后需要使用 brelse() 来释放它;

磁盘布局: 

  

xv6 文件系统在磁盘上的结构如下图。xv6将磁盘划分为几个部分,文件系统不使用 block0(它用来保存引导扇区)。block1 称为超级块(superblock),它包含有关文件系统的元数据(如块中的文件系统大小、数据块的数量、inode 的数量和 log 中的块数)。从 block2 开始的块保持 log,log 之后是 inodes,每个块有多个 inode。在这些之后,位图(bitmap)块跟踪数据库的使用情况。其余的块是数据块,每个块要么在 bitmap 中标记为空闲,要么保存文件或目录的内容。超级块由一个称为 mkfs 的单独程序填充,该程序构建一个初始文件系统。 

Loging layer 可以帮助我们实现崩溃恢复(crash recovery)。出现这个问题的原因是,许多文件系统操作涉及对磁盘的多次写入操作,在某个写入操作后的崩溃可能会使磁盘上的文件系统处于不一致的状态。根据磁盘写入的顺序,崩溃可能会使 inode 留下对标记为 free 的块的引用(os 可能会将该 free 块分配给其他文件,这样就导致有两个文件共享同一个块,可能会导致严重的安全问题),也可能会留下已分配但未被引用的块。

xv6 通过一种简单的日志记录形式解决了文件系统操作过程中的崩溃问题。xv6 系统调用不会直接写磁盘上的文件系统数据结构,相反,它在磁盘上的日志中写入了它希望进行的所有磁盘写操作的描述,一旦系统调用在日志中记录了它所有的写入操作,它就会将一个特殊的提交记录写入磁盘,这表明该日志中包含了一个完整的操作。此时,系统调用才开始执行写磁盘上的文件系统数据结构操作。在这些写入操作完成之后,系统调用再将磁盘上的此次日志删除。

如果系统崩溃并重新启动,则文件系统代码将从崩溃中恢复。如果日志被标记为包含完整操作,则恢复代码将写入复制到磁盘文件系统中所属的位置。如果日志未标记为包含完整的操作,则恢复代码将忽略该日志。最后恢复代码再将日志删除。 所以,logging layer 能保证写操作要么执行完,要么不执行,避免出现数据不一致的情况。

系统调用一开始只会写 buffer cache, 而不是磁盘。

当系统调用完成后 —— commit:

  1. 将所有的更新的块写到磁盘的 log 上(在 log 上保存了更新块的副本);
  2. 将磁盘上的 log 设置为 committed;
  3. 然后再将更新的块写到要写的位置;
  4. 删除 log 上的记录;

当崩溃发生,reboot 后:

如果 log 被设置为 committed,将更新的块从磁盘的 log 上写到要写的位置。

三、Lab lock: Parallelism/locking

在多核机器上,锁的争用使得其性能变差,在本实验中,我们会重新设计部分代码以增加并行性。提高并行性通常需要改变数据结构和锁定策略,以减少争用。

3.1 Memory allocator (moderate)

这部分需要为每个 CPU 维护一个 freelist(kernel/kalloc.c),每个 freelist 都有自己的锁。不同 CPU 上的分配和释放可以并行运行,因为每个 CPU 将对不同的 freelist 进行操作。当一个 CPU 上的 freelist 为空,而另外一个 CPU 的 freelist 还有空闲页面时,没有空闲页面的 CPU 必须 “窃取” 另一个 CPU 的 freelist 的一部分。窃取可能会引入锁争用,但争用频率要比单个 freelist 要小很多。

首先将 kmem 变成一个数组,大小为 CPU 的个数: 

struct {struct spinlock lock;struct run *freelist;
} kmem[NCPU];

在 kinit() 函数中初始化每个结构体的锁:

void
kinit()
{for(int i = 0; i < NCPU; i++){char name[9] = {0};snprintf(name, 8, "kmem-%d", i);initlock(&kmem[i].lock, "kmem");}freerange(end, (void*)PHYSTOP);
}

使用 kfree() 来释放的页面,要注意释放的页面放到当前 CPU 的 freelist 中:

void
kfree(void *pa)
{struct run *r;if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)panic("kfree");// Fill with junk to catch dangling refs.memset(pa, 1, PGSIZE);r = (struct run*)pa;push_off();int id = cpuid();acquire(&kmem[id].lock);r->next = kmem[id].freelist;kmem[id].freelist = r;release(&kmem[id].lock);pop_off();
}

使用 kalloc() 分配页面时,需要注意的情况就是当前 CPU 的 freelist 里面没有空页面可用,这时候需要去其他 CPU 的 freelist 偷一个页面过来:

static struct run *steal_free_block(int id)
{struct run *p = 0;for(int i = 0; i < NCPU; i++){if(i != id){acquire(&kmem[i].lock);p = kmem[i].freelist;if(p){kmem[i].freelist = p->next;p->next = 0;release(&kmem[i].lock);break;}release(&kmem[i].lock);}}return p;
}void *
kalloc(void)
{struct run *r;push_off();int id = cpuid();acquire(&kmem[id].lock);r = kmem[id].freelist;if(r){kmem[id].freelist = r->next;}release(&kmem[id].lock);if(!r){r = steal_free_block(id);}pop_off();if(r)memset((char*)r, 5, PGSIZE); // fill with junkreturn (void*)r;
}

3.2 Buffer cache (hard)

在 kenel/bio.c 中的 bcache 结构体中的 lock 的竞争十分激烈,每次访问 bcache 结构体都需要请求这个锁,所以需要我们使用一些策略来减少竞争。

首先是 bcache 结构体需要使用 hash 桶 buf_table 来装入不同 blockno 的块,每个桶对应一个 lock: 

#define NBUCKET 13struct {struct spinlock lock[NBUCKET];struct buf buf[NBUF];// Linked list of all buffers, through prev/next.// Sorted by how recently the buffer was used.// head.next is most recent, head.prev is least.//struct buf head;struct buf buf_table[NBUCKET];
} bcache;

初始化每个桶和每个桶对应的锁: 

void
binit(void)
{struct buf *b;for(int i = 0; i < NBUCKET; i++){char name[9] = {0};snprintf(name, 8, "bcache-%d", i);initlock(&bcache.lock[i], name);bcache.buf_table[i].prev = &bcache.buf_table[i];bcache.buf_table[i].next = &bcache.buf_table[i];}int i;for(i = 0,b = bcache.buf; i < NBUF && b < bcache.buf+NBUF; i++,b++){int index = i % NBUCKET;b->next = bcache.buf_table[index].next;b->prev = &bcache.buf_table[index];initsleeplock(&b->lock, "buffer");bcache.buf_table[index].next->prev = b;bcache.buf_table[index].next = b;}
}

bget 函数会先根据 blockno 找到对应的 hash 桶,若块已被缓存到对应的桶中,则直接返回,若不存在则循环遍历各个桶找到空闲的块(b->refcnt == 0),若该块在其他桶中,则需要把该块放到当前 blockno 对应的桶中:

static struct buf*
bget(uint dev, uint blockno)
{struct buf *b;int index = blockno % NBUCKET;acquire(&bcache.lock[index]);// Is the block already cached?for(b = bcache.buf_table[index].next; b != &bcache.buf_table[index]; b = b->next){if(b->dev == dev && b->blockno == blockno){b->refcnt++;release(&bcache.lock[index]);acquiresleep(&b->lock);return b;}}release(&bcache.lock[index]);for(int i = index; ; i = (i+1) % NBUCKET){acquire(&bcache.lock[i]);for(b = bcache.buf_table[i].next; b != &bcache.buf_table[i]; b = b->next){if(b->refcnt == 0) {// change bucketif(i != index){b->next->prev = b->prev;b->prev->next = b->next;release(&bcache.lock[i]);acquire(&bcache.lock[index]);b->next = bcache.buf_table[index].next;b->prev = &bcache.buf_table[index];bcache.buf_table[index].next->prev = b;bcache.buf_table[index].next = b;}b->dev = dev;b->blockno = blockno;b->valid = 0;b->refcnt = 1;release(&bcache.lock[index]);acquiresleep(&b->lock);return b;}}release(&bcache.lock[i]);}panic("bget: no buffers");
}

下面几个函数根据 block 中的 blockno 来得到对应的桶: 

void
brelse(struct buf *b)
{if(!holdingsleep(&b->lock))panic("brelse");releasesleep(&b->lock);int index = b->blockno % NBUCKET;acquire(&bcache.lock[index]);b->refcnt--;release(&bcache.lock[index]);
}void
bpin(struct buf *b) {int index = b->blockno % NBUCKET;acquire(&bcache.lock[index]);b->refcnt++;release(&bcache.lock[index]);
}void
bunpin(struct buf *b) {int index = b->blockno % NBUCKET;acquire(&bcache.lock[index]);b->refcnt--;release(&bcache.lock[index]);
}

最后 kalloctest 和 bcachetest 还有 usertest 全部通过。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_925837.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

SaaS模式、springboot框架医院云HIS系统源码

HIS系统作为医院信息化的核心业务系统&#xff0c;如今已成为各个医疗机构的必备品了。大到三级二级医院&#xff0c;小到社区卫生服务中心&#xff0c;门诊&#xff08;门诊管理系统也可以理解为门诊的his系统&#xff0c;只是功能简单&#xff0c;模块较少&#xff09;。随着…

010:vue结合el-table实现表格小计总计需求(summary-method)

文章目录 1. 实现效果2. 核心部分3. 完整组件代码4. 注意点 1. 实现效果 2. 核心部分 el-table 添加如下配置&#xff0c;添加 show-summary 属性&#xff0c;配置 summary-method 函数 <el-table.......show-summary:summary-method"getSummaries" >...... …

Gartner发布CPS安全2024年预测:安全形势动荡的四大向量

随着威胁形势、自动化和人工智能采用的步伐以及供应商形势不断快速发展&#xff0c;我们为安全和风险管理领导者提供了四项预测&#xff0c;以规划 2024 年及以后 CPS 安全的未来发展方向。 主要发现 随着人工智能的采用加速增加网络物理系统&#xff08; CPS&#xff09;的“智…

【Internet Protocol】ip介绍,如何组局域网实现远程桌面和文件共享

文章目录 1.何为“上网”1.1 定义1.2 为什么连了WiFi就能上网了&#xff1f; 2.ip2.1 什么是ip2.2 为什么区分广域网和局域网&#xff0c;ip的唯一性2.3 如何查看设备的ip2.4 什么叫"ping"2.5 区分是否两个ip是否在同一局域网2.5.1 最稳妥的方式&#xff1a;ip&m…

mysql group_concat函数使用

CREATE TABLE aa (id int(11) DEFAULT NULL,name varchar(50) DEFAULT NULL ) ENGINEInnoDB DEFAULT CHARSETutf8mb41、基本查询 SELECT * FROM aa;2、以id分组&#xff0c;把name字段的值打印在一行&#xff0c;逗号分隔(默认) select id,group_concat(name) from aa group …

精确掌控并发:漏桶算法在分布式环境下并发流量控制的设计与实现

这是《百图解码支付系统设计与实现》专栏系列文章中的第&#xff08;16&#xff09;篇&#xff0c;也是流量控制系列的第&#xff08;3&#xff09;篇。点击上方关注&#xff0c;深入了解支付系统的方方面面。 本篇重点讲清楚漏桶原理&#xff0c;在支付系统的应用场景&#x…

解决打开 json 文件中文乱码的问题

如下图&#xff0c;pycharm 打开是下面的样子 右下角的编码尝试了好久&#xff0c;依然打不开 用代码打开就成功了 import jsonwith open(./Mydata/garbage_classification.json,encodingutf8,moder) as f:data json.load(f) print(data)控制台结果&#xff1a;

2024年“华数杯”国际大学生数学建模竞赛B题思路

本题难点在于数据获取和定性定量分析&#xff0c;代码部分没有太大价值、就不更新了 •中国的电力供应和许多因素相互作用。请研究它们之间的关系&#xff0c;并预测2024年至2060年中国电力供应的发展趋势。 首先得获取数据&#xff0c;中国的宏观数据相对容易&#xff08;包括…

两数之和(Hash表)[简单]

优质博文&#xff1a;IT-BLOG-CN 一、题目 给定一个整数数组nums和一个整数目标值target&#xff0c;请你在该数组中找出"和"为目标值target的那两个整数&#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是&#xff0c;数组中同一个元…

C#MQTT编程07--MQTT服务器和客户端(wpf版)

1、前言 上篇完成了winform版的mqtt服务器和客户端&#xff0c;实现了订阅和发布&#xff0c;效果666&#xff0c;长这样 这节要做的wpf版&#xff0c;长这样&#xff0c;效果也是帅BBBB帅&#xff0c;wpf技术是cs程序软件的福音。 wpf的基础知识和案例项目可以看我的另一个专…

单向不带头链表的使用

单向不带头链表的使用 链表的创建&#xff1a; typedef struct LNode {SLDataType data;struct LNode* next; }LNode,*LinkList; 按位查找 LNode* GetElem(LinkList L, int i) {int j 1;LNode* p L->next;if (i < 0)return NULL;if (i 0)return L;while (p &&…

一天一个设计模式---组合模式

基本概念 组合模式是一种结构型设计模式&#xff0c;它允许客户端统一对待单个对象和对象的组合。组合模式通过将对象组织成树形结构&#xff0c;使得客户端可以一致地使用单个对象和组合对象。 主要角色&#xff1a; Component&#xff08;组件&#xff09;&#xff1a; 定…

Git Merge、Rebase 和 Squash 之间的区别

文章目录 Git MergeGit RebaseGit Squash结论 作为一名开发人员&#xff0c;您可能使用过 Git 和 GitHub&#xff0c;掌握了版本控制的要点。通常通过拉取请求将分支的更改集成到主分支中是一项常见任务。许多人的默认选择是“合并”功能。 然而&#xff0c;版本控制领域提供了…

【软件测试】学习笔记-设计一个“好的”测试用例

本篇文章重点探讨如何才能设计出一个“好的”测试用例。 什么才算是“好的”测试用例&#xff1f; 什么才是“好的”测试用例&#xff0c;这个“好”又应该体现在哪些方面。这是一个看似简单实则难以回答的问题&#xff0c;即使深入思考后&#xff0c;也很难有非常标准的答案…

C++力扣题目501--二叉搜索树中的众数

给你一个含重复值的二叉搜索树&#xff08;BST&#xff09;的根节点 root &#xff0c;找出并返回 BST 中的所有 众数&#xff08;即&#xff0c;出现频率最高的元素&#xff09;。 如果树中有不止一个众数&#xff0c;可以按 任意顺序 返回。 假定 BST 满足如下定义&#xf…

【Redis】非关系型数据库之Redis的增删改查

目录 一、Redis的数据类型分类 二、Redis的字符串类型string 三、Redis的列表list 四、Redis的哈希hash 五、Redis的无序集合set 六、Redis的有序集合zset 七、Redis的通用命令 一、Redis的数据类型分类 通常Redis的数据类型有五大基础类型 String&#xff08;字符串&am…

多机TCP通讯之hello world(C++)

文章目录 TCP是什么准备工作CMakeLists.txt服务端代码客户端代码参考 TCP是什么 TCP&#xff08;传输控制协议&#xff09;是一种在计算机网络中广泛使用的协议&#xff0c;它提供了可靠的、面向连接的数据传输服务。TCP 是 OSI 模型中的传输层协议&#xff0c;它确保了数据的…

idea 安装免费Ai工具 codeium

目录 概述 ide安装 使用 chat问答 自动写代码 除此外小功能 概述 这已经是我目前用的最好免费的Ai工具了&#xff0c;当然你要是有钱最好还是用点花钱的&#xff0c;比如copilot&#xff0c;他可以在idea全家桶包括vs&#xff0c;还有c/c的vs上运行&#xff0c;还贼强&am…

安全狗方案入选工信部《2023年工业和信息化领域数据安全典型案例名单》

近日&#xff0c;工业和信息化部网络安全管理局公布了2023年工业和信息化领域数据安全典型案例名单。 安全狗与厦门卫星定位应用股份有限公司、中移 (上海) 信息通信科技有限公司联合申报的智慧交通云数据安全与隐私保障典型案例也成功入选。 厦门服云信息科技有限公司&#…

132基于matlab的采集信号模极大值以及李氏指数计算

基于matlab的采集信号模极大值以及李氏指数计算&#xff0c; 1)计算信号的小波变换。 2)求出模极大曲线。 3)计算其中两个奇异点的Lipschitz指数&#xff0c;程序已调通&#xff0c;可直接运行。 132matlab模极大曲线Lipschitz (xiaohongshu.com)