6.S081的Lab学习——Lab7: Multithreading

2024-06-20 05:52

本文主要是介绍6.S081的Lab学习——Lab7: Multithreading,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 前言
  • 一、Uthread: switching between threads (moderate)
    • 提示:
    • 解析
  • 二、Using threads (moderate)
    • 解析:
  • 三、Barrier (moderate)
    • 解析:
  • 总结


前言

一个本硕双非的小菜鸡,备战24年秋招。打算尝试6.S081,将它的Lab逐一实现,并记录期间心酸历程。
代码下载

官方网站:6.S081官方网站

安装方式:
通过 APT 安装 (Debian/Ubuntu)
确保你的 debian 版本运行的是 “bullseye” 或 “sid”(在 ubuntu 上,这可以通过运行 cat /etc/debian_version 来检查),然后运行:

sudo apt-get install git build-essential gdb-multiarch qemu-system-misc gcc-riscv64-linux-gnu binutils-riscv64-linux-gnu 

(“buster”上的 QEMU 版本太旧了,所以你必须单独获取。

qemu-system-misc 修复
此时此刻,似乎软件包 qemu-system-misc 收到了一个更新,该更新破坏了它与我们内核的兼容性。如果运行 make qemu 并且脚本在 qemu-system-riscv64 -machine virt -bios none -kernel/kernel -m 128M -smp 3 -nographic -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0 之后出现挂起

则需要卸载该软件包并安装旧版本:

  $ sudo apt-get remove qemu-system-misc$ sudo apt-get install qemu-system-misc=1:4.2-3ubuntu6

在 Arch 上安装

sudo pacman -S riscv64-linux-gnu-binutils riscv64-linux-gnu-gcc riscv64-linux-gnu-gdb qemu-arch-extra

测试您的安装
若要测试安装,应能够检查以下内容:

$ riscv64-unknown-elf-gcc --version
riscv64-unknown-elf-gcc (GCC) 10.1.0
...$ qemu-system-riscv64 --version
QEMU emulator version 5.1.0

您还应该能够编译并运行 xv6: 要退出 qemu,请键入:Ctrl-a x。

# in the xv6 directory
$ make qemu
# ... lots of output ...
init: starting sh
$

本实验将使您熟悉多线程。您将在用户级线程包中实现线程之间的切换,使用多个线程来加速程序,并实现一个屏障。

切换分支执行操作

git stash
git fetch
git checkout thread
make clean

一、Uthread: switching between threads (moderate)

在本练习中,您将为用户级线程系统设计上下文切换机制,然后实现它。为了让您开始,您的xv6有两个文件:user/uthread.c和user/uthread_switch.S,以及一个规则:运行在Makefile中以构建uthread程序。uthread.c包含大多数用户级线程包,以及三个简单测试线程的代码。线程包缺少一些用于创建线程和在线程之间切换的代码。

您的工作是提出一个创建线程和保存/恢复寄存器以在线程之间切换的计划,并实现该计划。完成后,make grade应该表明您的解决方案通过了uthread测试。

完成后,在xv6上运行uthread时应该会看到以下输出(三个线程可能以不同的顺序启动):

$ make qemu
...
$ uthread
thread_a started
thread_b started
thread_c started
thread_c 0
thread_a 0
thread_b 0
thread_c 1
thread_a 1
thread_b 1
...
thread_c 99
thread_a 99
thread_b 99
thread_c: exit after 100
thread_a: exit after 100
thread_b: exit after 100
thread_schedule: no runnable threads
$

该输出来自三个测试线程,每个线程都有一个循环,该循环打印一行,然后将CPU让出给其他线程。

然而在此时还没有上下文切换的代码,您将看不到任何输出。

您需要将代码添加到user/uthread.c中的thread_create()和thread_schedule(),以及user/uthread_switch.S中的thread_switch。一个目标是确保当thread_schedule()第一次运行给定线程时,该线程在自己的栈上执行传递给thread_create()的函数。另一个目标是确保thread_switch保存被切换线程的寄存器,恢复切换到线程的寄存器,并返回到后一个线程指令中最后停止的点。您必须决定保存/恢复寄存器的位置;修改struct thread以保存寄存器是一个很好的计划。您需要在thread_schedule中添加对thread_switch的调用;您可以将需要的任何参数传递给thread_switch,但目的是将线程从t切换到next_thread。

提示:

  1. thread_switch只需要保存/还原被调用方保存的寄存器(callee-save register,参见LEC5使用的文档《Calling Convention》)。为什么?
  2. 您可以在user/uthread.asm中看到uthread的汇编代码,这对于调试可能很方便。
  3. 这可能对于测试你的代码很有用,使用riscv64-linux-gnu-gdb的单步调试通过你的thread_switch,你可以按这种方法开始:
(gdb) file user/_uthread
Reading symbols from user/_uthread...
(gdb) b uthread.c:60

这将在uthread.c的第60行设置断点。断点可能会(也可能不会)在运行uthread之前触发。为什么会出现这种情况?

一旦您的xv6 shell运行,键入“uthread”,gdb将在第60行停止。现在您可以键入如下命令来检查uthread的状态:

(gdb) p/x *next_thread

使用“x”,您可以检查内存位置的内容:

(gdb) x/x next_thread->stack

您可以跳到thread_switch 的开头,如下:

(gdb) b thread_switch

(gdb) c

您可以使用以下方法单步执行汇编指令:

(gdb) si

gdb的在线文档在这里。

解析

首先我们要明白线程切换的流程:

  1. 保存当前线程的上下文:在进行线程切换之前,操作系统需要保存当前线程的状态,这包括寄存器的内容、程序计数器的值等,以便之后可以恢复到这个状态。
  2. 更新线程状态:将当前线程的状态更新为等待状态或者就绪状态,这取决于线程是否需要被调度。
  3. 选择新的线程:操作系统的调度器会选择一个新的线程来执行。这个选择过程可能基于多种调度算法,如轮转调度、优先级调度等。
  4. 加载新线程的上下文:一旦新的线程被选中,操作系统需要加载这个线程的上下文,包括恢复之前保存的寄存器状态和程序计数器的值。
  5. 更新线程状态:将新线程的状态更新为运行状态。
  6. 更新CPU寄存器:CPU的寄存器需要更新为新线程的寄存器值,这样CPU就可以从新线程的程序计数器指定的位置开始执行指令。
  7. 开始执行新线程:CPU开始执行新线程的指令。

线程除了独享的寄存器和栈之外,都是共享的部分,所以不需要全部切换,所以在用户级线程切换时,只需要保存寄存器和栈即可。
所以首先我们需要搞一个结构体来存储上下文。因为这是用户级线程,不需要设计用户栈和内核栈,用户页表和内核页表等等切换。

可以模仿proc.h中的内核上下文切换保存寄存器contest结构体

注意!注意!这次是在用户文件夹工作路径了

//user/uthread.c
struct context {uint64 ra;uint64 sp;// callee-saveduint64 s0;uint64 s1;uint64 s2;uint64 s3;uint64 s4;uint64 s5;uint64 s6;uint64 s7;uint64 s8;uint64 s9;uint64 s10;uint64 s11;
};

然后把它加到线程结构体中。

//user/uthread.c
struct thread {char       stack[STACK_SIZE]; /* the thread's stack */int        state;             /* FREE, RUNNING, RUNNABLE */struct context context;
};

然后模仿kernel/swtch.S,在user/uthread_switch.S中写入如下代码

//user/uthread_switch.S.text/** save the old thread's registers,* restore the new thread's registers.*/.globl thread_switch
thread_switch:/* YOUR CODE HERE */sd ra, 0(a0)sd sp, 8(a0)sd s0, 16(a0)sd s1, 24(a0)sd s2, 32(a0)sd s3, 40(a0)sd s4, 48(a0)sd s5, 56(a0)sd s6, 64(a0)sd s7, 72(a0)sd s8, 80(a0)sd s9, 88(a0)sd s10, 96(a0)sd s11, 104(a0)ld ra, 0(a1)ld sp, 8(a1)ld s0, 16(a1)ld s1, 24(a1)ld s2, 32(a1)ld s3, 40(a1)ld s4, 48(a1)ld s5, 56(a1)ld s6, 64(a1)ld s7, 72(a1)ld s8, 80(a1)ld s9, 88(a1)ld s10, 96(a1)ld s11, 104(a1)ret    /* return to ra */

修改thread_schedule,添加线程切换语句

//uthread.cvoid 
thread_schedule(void)
{struct thread *t, *next_thread;/* Find another runnable thread. */next_thread = 0;t = current_thread + 1;for(int i = 0; i < MAX_THREAD; i++){if(t >= all_thread + MAX_THREAD)t = all_thread;if(t->state == RUNNABLE) {next_thread = t;break;}t = t + 1;}if (next_thread == 0) {printf("thread_schedule: no runnable threads\n");exit(-1);}if (current_thread != next_thread) {         /* switch threads?  */next_thread->state = RUNNING;t = current_thread;current_thread = next_thread;/* YOUR CODE HERE* Invoke thread_switch to switch from t to next_thread:* thread_switch(??, ??);*/thread_switch((uint64)&t->context, (uint64)&current_thread->context);} elsenext_thread = 0;
}

thread_create函数中需要设置ra和sp寄存器,分别指向函数的入口地址和栈的初始地址,可以仿照 /kernel/proc.c 的127-128行来写

//uthread.c
void 
thread_create(void (*func)())
{struct thread *t;for (t = all_thread; t < all_thread + MAX_THREAD; t++) {if (t->state == FREE) break;}t->state = RUNNABLE;// YOUR CODE HEREt->context.ra = (uint64)func;t->context.sp = (uint64)t->stack + STACK_SIZE;
}

结果成功输出
在这里插入图片描述

二、Using threads (moderate)

在本作业中,您将探索使用哈希表的线程和锁的并行编程。您应该在具有多个内核的真实Linux或MacOS计算机(不是xv6,不是qemu)上执行此任务。最新的笔记本电脑都有多核处理器。

这个作业使用UNIX的pthread线程库。您可以使用man pthreads在手册页面上找到关于它的信息,您可以在web上查看,例如这里、这里和这里。

文件notxv6/ph.c包含一个简单的哈希表,如果单个线程使用,该哈希表是正确的,但是多个线程使用时,该哈希表是不正确的。在您的xv6主目录(可能是~/xv6-labs-2020)中,键入以下内容:

$ make ph
$ ./ph 1

请注意,要构建ph,Makefile使用操作系统的gcc,而不是6.S081的工具。ph的参数指定在哈希表上执行put和get操作的线程数。运行一段时间后,ph 1将产生与以下类似的输出:

100000 puts, 3.991 seconds, 25056 puts/second
0: 0 keys missing
100000 gets, 3.981 seconds, 25118 gets/second

在这里插入图片描述

您看到的数字可能与此示例输出的数字相差两倍或更多,这取决于您计算机的速度、是否有多个核心以及是否正在忙于做其他事情。

ph运行两个基准程序。首先,它通过调用put()将许多键添加到哈希表中,并以每秒为单位打印puts的接收速率。之后它使用get()从哈希表中获取键。它打印由于puts而应该在哈希表中但丢失的键的数量(在本例中为0),并以每秒为单位打印gets的接收数量。

通过给ph一个大于1的参数,可以告诉它同时从多个线程使用其哈希表。试试ph 2:

$ ./ph 2
100000 puts, 1.885 seconds, 53044 puts/second
1: 16579 keys missing
0: 16579 keys missing
200000 gets, 4.322 seconds, 46274 gets/second

在这里插入图片描述

这个ph 2输出的第一行表明,当两个线程同时向哈希表添加条目时,它们达到每秒53044次插入的总速率。这大约是运行ph 1的单线程速度的两倍。这是一个优秀的“并行加速”,大约达到了人们希望的2倍(即两倍数量的核心每单位时间产出两倍的工作)。

然而,声明16579 keys missing的两行表示散列表中本应存在的大量键不存在。也就是说,puts应该将这些键添加为什么两个线程都丢失了键,而不是一个线程?确定可能导致键丢失的具有2个线程的事件序列。在answers-thread.txt中提交您的序列和简短解释。

[!TIP] 为了避免这种事件序列,请在notxv6/ph.c中的put和get中插入lock和unlock语句,以便在两个线程中丢失的键数始终为0。相关的pthread调用包括:

pthread_mutex_t lock; // declare a lock
pthread_mutex_init(&lock, NULL); // initialize the lock
pthread_mutex_lock(&lock); // acquire lock
pthread_mutex_unlock(&lock); // release lock

当make grade说您的代码通过ph_safe测试时,您就完成了,该测试需要两个线程的键缺失数为0。在此时,ph_fast测试失败是正常的。到哈希表中,但出现了一些问题。请看一下notxv6/ph.c,特别是put()和insert()。

不要忘记调用pthread_mutex_init()。首先用1个线程测试代码,然后用2个线程测试代码。您主要需要测试:程序运行是否正确呢(即,您是否消除了丢失的键?)?与单线程版本相比,双线程版本是否实现了并行加速(即单位时间内的工作量更多)?

在某些情况下,并发put()在哈希表中读取或写入的内存中没有重叠,因此不需要锁来相互保护。您能否更改ph.c以利用这种情况为某些put()获得并行加速?提示:每个散列桶加一个锁怎么样?

修改代码,使某些put操作在保持正确性的同时并行运行。当make grade说你的代码通过了ph_safe和ph_fast测试时,你就完成了。ph_fast测试要求两个线程每秒产生的put数至少是一个线程的1.25倍。

解析:

首先回答为什么多线程中会丢失了键:简单来说这涉及到了多进程的隔离问题,当多个进程同时向 bucket放数据时,如果进程不是隔离的,也就是说都可以访问到同一个索引,那么就可能出现最终只有一个进程的值被放进去了,造成了键值覆盖。因此需要使用进程锁来避免这一情况。

put函数与get函数中关键就一句话

//通过键的哈希值计算出它应该被存储在哪个桶(bucket)中。NBUCKET是一个宏,表示桶的数量。
int i = key % NBUCKET;

这个NBUCKET为5。也就是有五个散列桶
所以需要队插入操作上锁,来使得每次插入只有一个进程使用。
看源代码notxv6/ph.c中一共有五个散列桶,那就来五个

// notxv6/ph.c
pthread_mutex_t lock[NBUCKET];

然后在put函数与get函数中添加上锁与解锁语句

// notxv6/ph.c
static 
void put(int key, int value)
{int i = key % NBUCKET;pthread_mutex_lock(&lock[i]);// is the key already present?struct entry *e = 0;for (e = table[i]; e != 0; e = e->next) {if (e->key == key)break;}if(e){// update the existing key.e->value = value;} else {// the new is new.insert(key, value, &table[i], table[i]);}pthread_mutex_unlock(&lock[i]);
}static struct entry*
get(int key)
{int i = key % NBUCKET;pthread_mutex_lock(&lock[i]);struct entry *e = 0;for (e = table[i]; e != 0; e = e->next) {if (e->key == key) break;}pthread_mutex_unlock(&lock[i]);return e;
}

最后记得在main函数中初始化

......
// notxv6/ph.c
int
main(int argc, char *argv[])
{pthread_t *tha;void *value;double t1, t0;for (int i = 0; i < NBUCKET; i++) {pthread_mutex_init(&lock[i], NULL);}
......

很简单
在这里插入图片描述

三、Barrier (moderate)

在本作业中,您将实现一个屏障(Barrier):应用程序中的一个点,所有参与的线程在此点上必须等待,直到所有其他参与线程也达到该点。您将使用pthread条件变量,这是一种序列协调技术,类似于xv6的sleep和wakeup。
您应该在真正的计算机(不是xv6,不是qemu)上完成此任务。

文件notxv6/barrier.c包含一个残缺的屏障实现。

$ make barrier
$ ./barrier 2
barrier: notxv6/barrier.c:42: thread: Assertion `i == t' failed.

2指定在屏障上同步的线程数(barrier.c中的nthread)。每个线程执行一个循环。在每次循环迭代中,线程都会调用barrier(),然后以随机微秒数休眠。如果一个线程在另一个线程到达屏障之前离开屏障将触发断言(assert)。期望的行为是每个线程在barrier()中阻塞,直到nthreads的所有线程都调用了barrier()。

您的目标是实现期望的屏障行为。除了在ph作业中看到的lock原语外,还需要以下新的pthread原语;详情请看这里和这里。

确保您的方案通过make grade的barrier测试。

pthread_cond_wait在调用时释放mutex,并在返回前重新获取mutex。

我们已经为您提供了barrier_init()。您的工作是实现barrier(),这样panic就不会发生。我们为您定义了struct barrier;它的字段供您使用。

有两个问题使您的任务变得复杂:

  1. 你必须处理一系列的barrier调用,我们称每一连串的调用为一轮(round)。bstate.round记录当前轮数。每次当所有线程都到达屏障时,都应增加bstate.round。
  2. 您必须处理这样的情况:一个线程在其他线程退出barrier之前进入了下一轮循环。特别是,您在前后两轮中重复使用bstate.nthread变量。确保在前一轮仍在使用bstate.nthread时,离开barrier并循环运行的线程不会增加bstate.nthread。

使用一个、两个和两个以上的线程测试代码。

解析:

这个实验的意思就是添加一个同步节点。当所有进程都到达了这个节点就唤醒所有进程继续执行,没全到就到达的进程会被休眠。

最主要的是这个给出的结构体

// notxv6/barrier.c
struct barrier {pthread_mutex_t barrier_mutex; //互斥锁,用于保护共享资源的访问,确保在修改共享数据时只有一个线程可以访问pthread_cond_t barrier_cond; //一个条件变量,用于线程间的同步。当一个线程到达障碍物时,如果其他线程还没有到达,它会在这个条件变量上等待int nthread;      // Number of threads that have reached this round of the barrier//这个整数变量记录了已经到达当前轮次障碍物的线程数量。当这个数量等于参与同步的线程总数时,所有线程都到达了障碍物int round;     // Barrier round//这个整数变量用于跟踪障碍物的轮次。每次所有线程都到达障碍物时,round 会增加,表示进入下一轮
} bstate;

则:

// notxv6/barrier.c
static void 
barrier()
{// YOUR CODE HERE//// Block until all threads have called barrier() and// then increment bstate.round.//pthread_mutex_lock(&bstate.barrier_mutex); //上锁bstate.nthread++;if (bstate.nthread == nthread) {bstate.round++; //增加 round 的值bstate.nthread = 0; //重置 nthreadpthread_cond_broadcast(&bstate.barrier_cond);  //唤醒所有等待的线程} else {pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex); //在cond上进入睡眠,释放锁mutex}pthread_mutex_unlock(&bstate.barrier_mutex); //解锁
}

比较简单的
在这里插入图片描述

总结

这个实验主要是关于进程的使用,感觉意犹未尽,比起前面的确实是难度不高。

这篇关于6.S081的Lab学习——Lab7: Multithreading的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1077281

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

线性代数|机器学习-P36在图中找聚类

文章目录 1. 常见图结构2. 谱聚类 感觉后面几节课的内容跨越太大,需要补充太多的知识点,教授讲得内容跨越较大,一般一节课的内容是书本上的一章节内容,所以看视频比较吃力,需要先预习课本内容后才能够很好的理解教授讲解的知识点。 1. 常见图结构 假设我们有如下图结构: Adjacency Matrix:行和列表示的是节点的位置,A[i,j]表示的第 i 个节点和第 j 个

Node.js学习记录(二)

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件