CS537 P6管理信息 代写

程序代写

该文档是关于CS537 P6项目的说明，包括截止日期、迟交惩罚、测试、协作、资源使用等规定。项目要求在Linux实验室机器上完成一个并发的键值（KV）存储服务器，实现线程安全的KV存储、Ring Buffer和通过共享内存区域的进程间通信，并理解和优化同步机制以提高性能。文档还提供了项目的详细信息、起始代码和实现细节，以及最佳实践的建议。

  • 截止日期：2024年4月16日晚上11:59。
  • 项目可以迟交最多3天，但每迟交一天将被扣10个百分点。
  • 延期天数：
    • 如果您需要在项目上额外的时间，每个人将有2天的个人项目延期天数和3天的小组项目延期天数（本学期总共5天延期天数）。在截止日期后，我们将为按时评分制作提交目录的副本。
    • 要使用延期天数或迟交作业，您将提交文件以及一个额外的文件，该文件仅包含一个数字，表示您的作业迟交的天数（例如1、2、3）。每连续一天，我们将复制任何包含这些slipdays.txt文件的目录。在提交最终作业时，此文件必须存在，否则我们将不知道对您的代码进行评分。
    • 我们将从一个项目到另一个项目跟踪您的延期天数和迟交提交，并在您用完延期天数后开始扣除百分比。
    • 在用完延期天数后，如果迟交1天，您最多可以获得90％的分数；迟交2天，最多可以获得80％的分数；迟交3天，最多可以获得70％的分数，但对于任何单个作业，如果没有例外情况，我们在第三天后将不接受提交。这意味着如果您在单个作业上使用了两个个人延期天数，您只能再迟交一天，总共迟交3天，扣除10％的分数。
    • 任何例外情况都需要向教师请求。
    • 示例slipdays.txt
    1
  • 测试将在~cs537 - 1/tests/P6中提供。该目录中有一个README.md文件，其中包含运行测试的说明。测试部分完成，您的项目可能会根据其他测试进行评分。
  • 问题：我们将使用Piazza回答所有问题。
  • 协作：作业可以自己完成或与一个伙伴一起完成。从其他任何人复制代码都被视为作弊。阅读此内容以获取更多关于什么是可以的和什么是不可以的信息。请不要这样做，以帮助我们大家度过一个愉快的学期。
  • 这个项目将在Linux实验室机器上完成，这样您可以更多地了解在典型的基于UNIX的平台（Linux）上用C编程。您的解决方案将在这些机器上进行测试。
  • 如果适用，一个名为resources.txt的描述在线资源使用情况的文档应包含在您的提交中。欢迎您使用在线资源来帮助您完成作业。我们不建议您使用大型语言模型，如ChatGPT。对于本课程，我们已经看到这些工具给出的示例或解释接近但不完全正确，如果学生不知道正确答案，会让他们更加困惑。请注意，当您向教学人员寻求帮助时，我们不会协助您使用这些LLM，并且我们希望您能够向教学人员介绍您的代码和逻辑。在线资源（例如stack overflow）和生成工具正在改变包括计算机科学和教育在内的许多行业。但是，如果您使用在线资源，您需要提交一份文档，描述您对这些资源的使用情况。在该文档中表明您的解决方案中有多少是完全由您自己完成的，有多少是利用这些工具完成的。请具体说明，指出使用的资源以及您与这些资源的交互方式。不给予外部资源信用是一种剽窃形式。在您的代码中对使用资源的地方进行注释是一种很好的做法。您不会因为使用LLM或阅读帖子而受到惩罚，但您不应该在在线论坛上发布关于本课程项目的帖子。您的大部分代码也应该是您自己努力编写的，并且您应该能够解释您提交的所有代码。
  • 提交方式：
    • 复制文件common.h、client.c、ring_buffer.h、ring_buffer.c、kv_store.c和Makefile（如果使用了kv_store.h也包括在内）。您的代码应该正确编译并运行。
    • 小组项目提交：每个小组只需要提交一次。要提交，一个人应该将代码放在他们的提交目录中（另一个人应该为空）。

键值服务器

在这个项目中，您将在客户端 – 服务器模型中实现一个并发的键值（KV）存储作为服务器。有一个服务器进程和一个客户端进程；它们都是多线程进程。它们使用共享内存区域进行进程间通信。您需要在共享内存中实现一个并发的环形缓冲区和一个共享的请求状态板来处理请求。

目标

  • 实现一个线程安全的并发KV存储。
  • 实现一个线程安全的环形缓冲区。
  • 理解通过共享内存区域的进程间通信。
  • 理解并优化同步机制以提高性能。

项目细节

并发KV存储 上图说明了这个项目的客户端 – 服务器模型。 服务器和客户端都是多线程进程。它们通过文件支持的共享内存映射进行通信，该映射分为两个区域：环形缓冲区和请求状态板。 – 客户端： 客户端通过环形缓冲区向服务器提交PUT/GET请求。 – 服务器： 服务器包含一个KV存储，用于处理这些请求。它从环形缓冲区读取客户端请求，处理它们；完成请求后，在请求状态板的预先指定窗口中更新其完成状态以及响应。因此，客户端可以读取特定窗口来检查特定请求的完成状态和响应。 在这个例子中，客户端有三个线程，服务器有两个。请求状态板中每个客户端线程有两个窗口。KV存储的初始哈希表大小设置为5。 服务器使用以下命令执行：

./server -n 2 -s 5

这里，-n是线程数量，-s是KV存储的初始哈希表大小。 客户端使用以下命令执行：

./client -n 3 -w 2

这里，-n是线程数量，-w是请求状态板中每个客户端的窗口数量。 您需要实现键值服务器以及环形缓冲区。 我们为您提供了环形缓冲区的定义（ring_buffer.h）。 我们还提供了客户端代码（client.c）。但是，您需要使共享区域线程安全。

环形缓冲区

环形缓冲区，也称为循环缓冲区，是一种数据结构，它使用单个固定大小的缓冲区，就好像它是端到端连接的一样。 这个环形缓冲区类似于生产者 – 消费者模型中的共享缓冲区。它通过允许客户端并发提交请求（生产者），服务器消费这些请求进行处理（消费者），促进了客户端和服务器之间的通信。 环形缓冲区看起来如下：

struct ring { // 在ring_buffer.h中定义
    //..
    struct buffer_descriptor buffer[RING_SIZE]; // 这就是环形缓冲区
Programming Help
};
int init_ring();
void ring_submit(struct ring *r, struct buffer_descriptor *bd); 
void ring_get(struct ring *r, struct buffer_descriptor *bd);

这里，init_ring()初始化环形缓冲区。 客户端通过ring_submit()向缓冲区提交新请求。 服务器使用ring_get()从缓冲区获取请求。 客户端请求看起来如下：

struct buffer_descriptor { // 在ring_buffer.h中定义
    enum REQUEST_TYPE req_type; // PUT/GET
    key_type k;     // 键
    value_type v;   // 值
    int res_off;    // 结果偏移量（以字节为单位）
    int ready;      // 完成状态标志
};

请求类型为PUT或GET。如果是PUT请求，则提供键和值。如果是GET请求，则仅提供键。 提交请求时，ready标志设置为0。 结果偏移量存储客户端将查找此请求状态的位置偏移量。请求状态板包含更多详细信息。 由于多个服务器线程和多个客户端线程可以同时访问环形缓冲区，您需要使其线程安全。

请求状态板

请求状态板在共享内存区域中紧随环形缓冲区。 它由窗口组成，每个窗口包含请求的完成状态和响应。 该板在客户端线程之间平均分配。这意味着，每个客户端线程在板中拥有固定数量的连续窗口（w，在客户端的命令行参数中指定）。从代码角度看，每个窗口也是struct buffer_descriptor类型（与每个客户端请求相同）。 客户端使用结果偏移量（res_off）将每个请求与板中的一个窗口相关联。结果偏移量存储从共享内存的起始位置开始，相关窗口的（字节）偏移量。服务器处理请求后，它将请求的响应存储在该偏移量中，然后将ready标志设置为1。客户端可以检查窗口以确定特定请求是否完成并检索响应。 自然地，客户端线程一次不能提交超过w个请求，因为它需要在请求中通过res_off指定特定的窗口。 drawing 例如，假设在上面的图中，共享内存区域从地址0x60开始。环形缓冲区结束，请求状态板从地址0x110开始。然后，客户端线程1的第一个请求将包含res_off = 208（0x130 - 0x60 = 208）。

KV存储

服务器的KV存储应实现为哈希表，使用以下哈希函数（在common.h中定义）：

h(key) = key % table - size

初始哈希表大小（s）作为服务器的命令行参数提供。 但是，您可以自由选择哈希表的类型（例如，开放寻址、链地址等）。 由于多个线程将使用KV存储来服务客户端的请求，您需要使其线程安全。 有两种方法来实现KV存储的线程安全版本： – 粗粒度锁定 – 它使用单个锁来保护整个KV存储，这意味着您强制对KV存储进行顺序访问，即使不同的线程可能在KV存储的不同部分工作。 – 细粒度锁定 – 它使用更细粒度的锁来保护KV存储，允许更多的并发访问。这意味着您应该为KV存储的不同部分使用不同的锁。这将允许多个线程同时安全地在KV存储上工作。*您必须为您的项目实现此功能。我们希望您的实现比粗粒度锁定更快。因此，您应该明智地选择适当的锁粒度级别。更多和更细的锁意味着更多的线程可以同时访问KV存储；然而，这也意味着更多的内存和锁管理开销。

起始代码和实现细节

提供了以下四个文件：

  • common.h包含类型定义和哈希函数。您不得更改此文件。
  • ring_buffer.h定义了环形缓冲区的结构和操作，您应该在ring_buffer.c中实现。您可以自由地向struct ring添加/删除字段，但不要更改接口函数。但是，如果必要，您可以仅添加新字段到struct buffer_descriptor，不要删除当前元素。
  • client.c实现了多线程客户端应用程序。它初始化文件支持的共享内存。共享文件名是shmem_file，对于这个项目是固定的。它初始化环形缓冲区，向环形缓冲区提交请求进行处理，并检查请求的完成情况。请注意，此文件使用您对环形缓冲区的实现。不要更改此文件，因为我们将替换它。此进程可以将服务器程序作为子进程进行fork。使用./client - h执行此文件以了解更多关于其命令行参数的信息。
  • Makefile构建客户端和服务器。

您必须实现以下两个文件：

  • ring_buffer.c： 在这里，您应该实现ring_buffer.h中的三个函数原型。
    • init_ring()：此函数初始化环形缓冲区。
    • ring_submit(*r, *bd)：此函数向环形缓冲区提交一个新项目。它应该是线程安全的，如果没有足够的空间，它将阻塞。
    • ring_get(*r, *bd)：此函数从环形缓冲区检索一个项目。它应该是线程安全的，如果缓冲区为空，它将阻塞。
  • kv_store.c： 在这里，您应该实现KV存储和服务器应用程序。它应该具有以下功能：
    • put(key_type k, value_type v)：此函数用于将键值对插入存储。如果键已存在，则更新相关的值。
    • get(key_type k)：此函数用于从存储中检索与给定键相关联的值。如果键未找到，则返回0。
    • 服务器应该能够从环形缓冲区获取请求，并在完成请求后更新请求状态板。我们希望服务器随着线程数量的增加而更快。
    • 还应实现服务器的main()函数，具有以下命令行参数：
      • -n：服务器线程数量
      • -s：初始哈希表大小

最佳实践

  • 考虑使用原子操作来更新环形缓冲区中的头和尾索引，以确保线程安全而无需锁定。您也可以在KV存储中使用它们。原子操作通常比互斥锁或信号量更快，因为它们不涉及上下文切换或内核干预的开销，这在锁定机制中很常见。它们是硬件级操作，可以在不锁定整个数据结构的情况下执行。您可能会从DPDK环形缓冲区中获得灵感。在这个项目中使用原子操作是可选的。