concurrency-sort
psort 程序设计
项目文件结构
1 | concurrency-sort/ |
可用例程
- get_nprocs()
- get_nprocs_conf()
- mmap()
- fsync()
- read()
- fread()
程序要求
- 并行排序接收两个命令行参数
inputoutput
1 | prompt> ./psort input output |
输入文件格式
- record: key 4byte | value 96byte
程序操作
- 将所有记录读入内存,对记录进行排序,随后将其写入输出文件
- 在完成之前,通过调用
fsync()对输出文件进行强制写入 - 可以假设为一次性排序
concurrency-mapreduce
MapReduce 程序设计
原始论文
实验目标
- 学习 MapReduce 范式的通用特性
- 使用线程和相关函数实现一个正确且高效的 MapReduce 框架
- 获得更多编写并发代码的经验
MapReduce框架总体思路
用户只需要定义 Map() 与 Reduce() 函数,交由框架处理该函数指针即可
Map(): 接受一个输入对,并产生一组中间键值对。Reduce():MapReduce库将具有相同中间键K的中间值分组在一起,传入该函数- 接受一个中间键K和该键的一组值。将这些值进行合并为更小的集合
- 通常,每次对
Reduce()的调用产生零个或一个输出值 - 中间值通过迭代器提供给用户的reduce函数
MapReduce 可将许多不同类型的相关计算映射到该框架上。
并且多个 mapper 可以同时运行,多个 reducer 也可以同时运行。
用户不必亲自操作编写并行化程序,只需要编写 Map() 与 Reduce() 函数,并交由该框架提供的相关基础设施即可。
gcc note
concurrency-mapreduce 实验指导
该实验指导文档在实验编写完成后进行了修缮与逆向更新
更贴合实际的项目进度
MapReduce 实验指导
实验分析
本项目是 OSTEP(Operating Systems: Three Easy Pieces) 的并发 MapReduce 实验。目标是实现一个单机多线程简化版 MapReduce 框架,核心是实现 mapreduce.h 中声明的函数并设计线程安全的中心数据结构。
1. 理解数据流
整个框架的数据流是:
1 | argv[1..n] 文件列表 |
在写代码之前,建议把这条数据流画在纸上,标注每一步的输入和输出。这是理解后续所有实现细节的基础。
MapReduce-osdi04 Paper Read
MapReduce: 大规模集群上的简化数据处理
- 原始论文
摘要
用户侧
map函数:处理键值对,生成一组中间键值对reduce函数:合并与同一中间键关联的所有中间值
特性
- 自动并行化,适于在大型机器集群上执行。
- 运行时系统负责处理输入数据的分区、跨机器集合调度程序执行、处理机器故障以及管理所需机器间通信。提供了一种方法,封装了分布式系统的复杂性。
- 具有高扩展性,可以适配多种分布式程序任务
方案背景
MapReduce框架的出现,是为了解决,大量数据如何在大型分布式系统上实现并行化计算、分布数据和故障处理等,复杂的并发细节(该问题导致原来设计的简单计算任务代码,为了满足分布式系统的并发需求,而增加了大量的并发复杂性)
MapReduce在计算任务与分布式系统之间设计了一种新的抽象,将简单计算与复杂并发细节相分离。
MapReduce库的抽象设计受到Lisp及许多函数式语言中的 map 与 reduce 原语的启发。对输入的每个输入逻辑应用 map 操作,计算一组中间键值对,对共享相同键的值应用 reduce 操作,以适当的合并派生数据。将函数式的 map 与 reduce 的实现交由用户制定,库只需要提供并行化方法,使用户轻松实现程序并行化。该库将重新执行作为容错的主要机制。
map 与 reduce
- map 映射
- reduce 归约