Ayy2

时间停止吧，你是多么的美丽

发表于 更新于 Disqus：

C++移动语义&智能指针

摘自https://www.learncpp.com/cpp-tutorial/

在一个局部函数内部new一个对象，我们容易忘记对它delete，从而造成内存泄漏：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>

void someFunction()
{
    Resource* ptr = new Resource();

    int x;
    std::cout << "Enter an integer: ";
    std::cin >> x;

    if (x == 0)
        throw 0; // the function returns early, and ptr won’t be deleted!

    // do stuff with ptr here

    delete ptr;
}

对此，我们可以采用RAII编程范例：通过局部变量的自动析构性，定义一个Auto_ptr1类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>

template <typename T>
class Auto_ptr1
{
	T* m_ptr {};
public:
	// Pass in a pointer to "own" via the constructor
	Auto_ptr1(T* ptr=nullptr)
		:m_ptr(ptr)
	{
	}

	// The destructor will make sure it gets deallocated
	~Auto_ptr1()
	{
		delete m_ptr;
	}

	// Overload dereference and operator-> so we can use Auto_ptr1 like m_ptr.
	T& operator*() const { return *m_ptr; }
	T* operator->() const { return m_ptr; }
};

// A sample class to prove the above works
class Resource
{
public:
    Resource() { std::cout << "Resource acquired\n"; }
    ~Resource() { std::cout << "Resource destroyed\n"; }
};

int main()
{
	Auto_ptr1<Resource> res(new Resource()); // Note the allocation of memory here

        // ... but no explicit delete needed

	// Also note that we use <Resource>, not <Resource*>
        // This is because we've defined m_ptr to have type T* (not T)

	return 0;
} // res goes out of scope here, and destroys the allocated Resource for us

将指针包含在类里，通过类的析构函数，可以做到自动释放内存。

但是这么做会有问题，例如两个Auto_ptr1可能管理同一个指针：

1
2
3
4
5
6
7
int main()
{
	Auto_ptr1<Resource> res1(new Resource());
	Auto_ptr1<Resource> res2(res1); // Alternatively, don't initialize res2 and then assign res2 = res1;

	return 0;
}

这样会对同一个地址delete两次，造成ub。

同样地，如果将Auto_ptr1作为函数参数或者函数返回值，都会出现奇怪的问题。

因此一种解决方式，是采用移动语义：通过转移ownership来替代浅拷贝：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>

template <typename T>
class Auto_ptr2
{
	T* m_ptr {};
public:
	Auto_ptr2(T* ptr=nullptr)
		:m_ptr(ptr)
	{
	}

	~Auto_ptr2()
	{
		delete m_ptr;
	}

	// A copy constructor that implements move semantics
	Auto_ptr2(Auto_ptr2& a) // note: not const
	{
		// We don't need to delete m_ptr here.  This constructor is only called when we're creating a new object, and m_ptr can't be set prior to this.
		m_ptr = a.m_ptr; // transfer our dumb pointer from the source to our local object
		a.m_ptr = nullptr; // make sure the source no longer owns the pointer
	}

	// An assignment operator that implements move semantics
	Auto_ptr2& operator=(Auto_ptr2& a) // note: not const
	{
		if (&a == this)
			return *this;

		delete m_ptr; // make sure we deallocate any pointer the destination is already holding first
		m_ptr = a.m_ptr; // then transfer our dumb pointer from the source to the local object
		a.m_ptr = nullptr; // make sure the source no longer owns the pointer
		return *this;
	}

	T& operator*() const { return *m_ptr; }
	T* operator->() const { return m_ptr; }
	bool isNull() const { return m_ptr == nullptr; }
};

class Resource
{
public:
	Resource() { std::cout << "Resource acquired\n"; }
	~Resource() { std::cout << "Resource destroyed\n"; }
};

int main()
{
	Auto_ptr2<Resource> res1(new Resource());
	Auto_ptr2<Resource> res2; // Start as nullptr

	std::cout << "res1 is " << (res1.isNull() ? "null\n" : "not null\n");
	std::cout << "res2 is " << (res2.isNull() ? "null\n" : "not null\n");

	res2 = res1; // res2 assumes ownership, res1 is set to null

	std::cout << "Ownership transferred\n";

	std::cout << "res1 is " << (res1.isNull() ? "null\n" : "not null\n");
	std::cout << "res2 is " << (res2.isNull() ? "null\n" : "not null\n");

	return 0;
}
/*
Resource acquired
res1 is not null
res2 is null
Ownership transferred
res1 is null
res2 is not null
Resource destroyed
*/

这其实就是早期 std::auto_ptr 的写法。但是这个东西是很危险的，以至于在C++17标准中被删除。例如你将auto_ptr传入函数（并在函数结束时析构），但是调用者函数的对应的auto_ptr并不知道自己维护的指针已经释放了。二是auto_ptr没办法采用数组delete（挖坑，数组delete和普通delete的区别），三是auto_ptr没办法与STL容器很好地交互。

介绍移动语义之前，需要了解一下右值引用的性质。

要知道，函数的返回值是右值（然后用赋值=赋给左值），而右值引用可以延长返回值的生命周期：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>

class Fraction
{
private:
	int m_numerator { 0 };
	int m_denominator { 1 };

public:
	Fraction(int numerator = 0, int denominator = 1) :
		m_numerator{ numerator }, m_denominator{ denominator }
	{
	}

	friend std::ostream& operator<<(std::ostream& out, const Fraction& f1)
	{
		out << f1.m_numerator << '/' << f1.m_denominator;
		return out;
	}
};

int main()
{
	auto&& rref{ Fraction{ 3, 5 } }; // r-value reference to temporary Fraction

	// f1 of operator<< binds to the temporary, no copies are created.
	std::cout << rref << '\n';

	return 0;
} // rref (and the temporary Fraction) goes out of scope here

那，考虑将右值和右值引用作为函数参数，会是什么情况呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>

void fun(const int& lref) // l-value arguments will select this function
{
	std::cout << "l-value reference to const: " << lref << '\n';
}

void fun(int&& rref) // r-value arguments will select this function
{
	std::cout << "r-value reference: " << rref << '\n';
}

int main()
{
	int x{ 5 };
	fun(x); // l-value argument calls l-value version of function
	fun(5); // r-value argument calls r-value version of function

	return 0;
}
/*
l-value reference to const: 5
r-value reference: 5
*/

可以发现，当我们传入一个右值5，会采用形参为右值引用的重载函数。相比于const的左值引用（可以用右值初始化const左值引用），编译器认为右值引用是更好的选择。

那传入右值引用呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>

void fun(const int& lref) // l-value arguments will select this function
{
	std::cout << "l-value reference to const: " << lref << '\n';
}

void fun(int&& rref) // r-value arguments will select this function
{
	std::cout << "r-value reference: " << rref << '\n';
}

int main()
{
	int&& ref{ 5 };
    fun(ref);

	return 0;
}
/*
l-value reference to const: 5
*/

我操，居然右值引用是左值。这说明 int&& ref 是 int&& 类型的左值。

另外，根据learncpp，和不能返回左值引用一样，你也不能返回右值引用（虽然本身返回的是int&&类型的左值，但是它引用的是一个生命周期已经结束的右值，这很危险）

我们知道，const左值引用可以接受右值为参数。这里看看learncpp的copy类型auto_ptr：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>

template<typename T>
class Auto_ptr3
{
	T* m_ptr {};
public:
	Auto_ptr3(T* ptr = nullptr)
		: m_ptr { ptr }
	{
	}

	~Auto_ptr3()
	{
		delete m_ptr;
	}

	// Copy constructor
	// Do deep copy of a.m_ptr to m_ptr
	Auto_ptr3(const Auto_ptr3& a)
	{
		m_ptr = new T;
		*m_ptr = *a.m_ptr;
	}

	// Copy assignment
	// Do deep copy of a.m_ptr to m_ptr
	Auto_ptr3& operator=(const Auto_ptr3& a)
	{
		// Self-assignment detection
		if (&a == this)
			return *this;

		// Release any resource we're holding
		delete m_ptr;

		// Copy the resource
		m_ptr = new T;
		*m_ptr = *a.m_ptr;

		return *this;
	}

	T& operator*() const { return *m_ptr; }
	T* operator->() const { return m_ptr; }
	bool isNull() const { return m_ptr == nullptr; }
};

class Resource
{
public:
	Resource() { std::cout << "Resource acquired\n"; }
	~Resource() { std::cout << "Resource destroyed\n"; }
};

Auto_ptr3<Resource> generateResource()
{
	Auto_ptr3<Resource> res{new Resource};
	return res; // this return value will invoke the copy constructor
}

int main()
{
	Auto_ptr3<Resource> mainres;
	mainres = generateResource(); // this assignment will invoke the copy assignment

	return 0;
}
/*
mine:
Resource acquired
Resource acquired
Resource destroyed
Resource destroyed

learncpp:
Resource acquired
Resource acquired
Resource destroyed
Resource acquired
Resource destroyed
Resource destroyed
*/

按理来说应该有六行，但是我的编译器忽略了返回值。

挖坑，Auto_ptr3& operator=(const Auto_ptr3& a) 前面引用的含义 & ，它防止又调用一次copy constructor

这样我们就实现了一个基于copy的智能指针。但是，通过移动语义，可以做的更好。

C++11为类提供了移动构造函数和移动赋值重载，它们的参数都是右值引用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>

template<typename T>
class Auto_ptr4
{
	T* m_ptr {};
public:
	Auto_ptr4(T* ptr = nullptr)
		: m_ptr { ptr }
	{
	}

	~Auto_ptr4()
	{
		delete m_ptr;
	}

	// Copy constructor
	// Do deep copy of a.m_ptr to m_ptr
	Auto_ptr4(const Auto_ptr4& a)
	{
		m_ptr = new T;
		*m_ptr = *a.m_ptr;
	}

	// Move constructor
	// Transfer ownership of a.m_ptr to m_ptr
	Auto_ptr4(Auto_ptr4&& a) noexcept
		: m_ptr(a.m_ptr)
	{
		a.m_ptr = nullptr; // we'll talk more about this line below
	}

	// Copy assignment
	// Do deep copy of a.m_ptr to m_ptr
	Auto_ptr4& operator=(const Auto_ptr4& a)
	{
		// Self-assignment detection
		if (&a == this)
			return *this;

		// Release any resource we're holding
		delete m_ptr;

		// Copy the resource
		m_ptr = new T;
		*m_ptr = *a.m_ptr;

		return *this;
	}

	// Move assignment
	// Transfer ownership of a.m_ptr to m_ptr
	Auto_ptr4& operator=(Auto_ptr4&& a) noexcept
	{
		// Self-assignment detection
		if (&a == this)
			return *this;

		// Release any resource we're holding
		delete m_ptr;

		// Transfer ownership of a.m_ptr to m_ptr
		m_ptr = a.m_ptr;
		a.m_ptr = nullptr; // we'll talk more about this line below

		return *this;
	}

	T& operator*() const { return *m_ptr; }
	T* operator->() const { return m_ptr; }
	bool isNull() const { return m_ptr == nullptr; }
};

class Resource
{
public:
	Resource() { std::cout << "Resource acquired\n"; }
	~Resource() { std::cout << "Resource destroyed\n"; }
};

Auto_ptr4<Resource> generateResource()
{
	Auto_ptr4<Resource> res{new Resource};
	return res; // this return value will invoke the move constructor
}

int main()
{
	Auto_ptr4<Resource> mainres;
	mainres = generateResource(); // this assignment will invoke the move assignment

	return 0;
}
/*
Resource acquired
Resource destroyed
*/

认真看一下移动语义的实现~（挖坑：noexcept

由于Resource自始自终都只有一个（只不过所有权转移了很多次），因此只有一次构造和一次析构。

我们将移动语义与右值挂钩。这是因为右值一般来讲都是暂时使用的东西，在以后的程序执行不需要使用。因此比起前面使用左值来实现移动语义，右值更加安全。我们不希望类似于 a=b 这种东西会影响到 b 。

我们观察到，函数 generateResource 返回的是一个左值，但是似乎根据结果来看，返回过程采用了移动语义（即没有构造新值）。这是可以的，C++内部也是这么干的。因为返回的左值在离开函数后会立即销毁，我们没必要在这里使用深拷贝。

learncpp网站上给出建议：对于move-enabled的类，有时候禁止使用拷贝构造和拷贝赋值会更好：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>

template<typename T>
class Auto_ptr5
{
	T* m_ptr {};
public:
	Auto_ptr5(T* ptr = nullptr)
		: m_ptr { ptr }
	{
	}

	~Auto_ptr5()
	{
		delete m_ptr;
	}

	// Copy constructor -- no copying allowed!
	Auto_ptr5(const Auto_ptr5& a) = delete;

	// Move constructor
	// Transfer ownership of a.m_ptr to m_ptr
	Auto_ptr5(Auto_ptr5&& a) noexcept
		: m_ptr(a.m_ptr)
	{
		a.m_ptr = nullptr;
	}

	// Copy assignment -- no copying allowed!
	Auto_ptr5& operator=(const Auto_ptr5& a) = delete;

	// Move assignment
	// Transfer ownership of a.m_ptr to m_ptr
	Auto_ptr5& operator=(Auto_ptr5&& a) noexcept
	{
		// Self-assignment detection
		if (&a == this)
			return *this;

		// Release any resource we're holding
		delete m_ptr;

		// Transfer ownership of a.m_ptr to m_ptr
		m_ptr = a.m_ptr;
		a.m_ptr = nullptr;

		return *this;
	}

	T& operator*() const { return *m_ptr; }
	T* operator->() const { return m_ptr; }
	bool isNull() const { return m_ptr == nullptr; }
};

这个东西非常像 std::unique_ptr 。正如其名，unique 的性质让它不能被复制。

std::move 用于将左值转化为右值，这样可以使用移动语义：

1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
	std::string a, b;
	b = "nuaa is garbage";
	a = std::move(b);
	std::cout << "a=" <<a << '\n' << "b=" << b;
	return 0;
}
/*
a=nuaa is garbage
b=
*/

但是原有的字符串b变为了空值，这也是意料之内的。

但是根据learncpp上的建议：不要对任何被std::move后的对象的值有任何假设

因此我们以后要避免依赖b的具体的值的操作。

发表于 Disqus：

1. xv6-摆烂-理解

大三上学期突然很想自学CS，然后在寒假学了CSAPP的大部分后开始了MIT 6.S081这个课程。用时大概两个月(2.25-4.24)从零开始自学OS到完成了除network外的所有lab，包括2020年和2021年的版本。

学这东西纯属兴趣，想体验一下科班的感觉（

学习路径

我并没有看课程视频，原因是我英语非常差。我看的是这个翻译后的版本：https://mit-public-courses-cn-translatio.gitbook.io/mit6-s081

一般就是，先根据课程要求，浏览一遍xv6 book上对应的章节及源码，然后看上面那个文档，然后再回到xv6 book当中巩固一下。

然后lab的话，前期是根据课程安排进行的。但到后面课程会开始讲一些论文，我是在那之前把所有lab给完成的。所以在写这个文章的时候，我其实还没有结束这门课程的学习。如标题所见，这只是我这两个月来对lab的回顾。我会继续后续论文的学习

lab 1 Xv6 and Unix utilities (2020/2021)

这个其实主要目的是让你安装好环境+熟悉一下xv6的代码结构。主要任务是使用xv6自带的系统调用实现一些功能，比较难的可能是 primes 那个实验，需要你使用多进程通信来完成素数筛。

我当时的想法大致是给每个进程都维护了一个要筛的素数（通过向管道写入第一个数来完成），如果当前传进来的数没办法整除当前进程所维护的素数，就交付给它的子进程处理。

lab 2 system calls (2020/2021)

这个lab就开启了你魔改内核的征程（不是）。你需要实现两个系统调用trace和sysinfo，分别追踪系统调用以及空闲内存与进程的数量。算是最简单的lab之一了，跟着Hint做就行。

lab 3 page tables (2021)

这个lab主要考察你对RISCV和xv6内页表的理解。由于时间太过遥远，我不太记得清楚其中的细节了。但总之也是一个比较简单的lab。

lab 3 page tables (2020)

其实这个才是真正的lab3（，2021年的是阉割的版本

我是到最后才完成的这个lab，原因是它真的非常难！大概耗费了我三天时间

这个lab要求我们为每个进程都额外维护一个内核页表，来简化 copyin/copyinstr 函数所需要的内核/进程页表之间的转换。

你需要为这个进程的内核页表写很多函数，例如初始化，拷贝页表等。

你还需要兼顾效率，即你需要在同一个物理地址上同时为内核页表以及进程的内核页表建立映射，而非直接拷贝物理空间。这涉及到许多细节，可能需要允许一些非法情况发生。

lab 4 traps (2020/2021)

这个lab考察你对xv6内部如何处理trap的细节，相对来说也是比较难的。通过了解xv6如何让trap机制透明来完成该lab中的alarm功能，例如保存上下文，设置pc、ra寄存器等。

另外顺带一提，在这个lab中，你实现的backtrace函数非常实用，可以直接拷贝到其它lab中，非常方便调试。

lab 5 xv6 lazy page allocation (2020)

这个lab考察你对page fault的理解。通过对特定的page fault的处理，使内核能够“按需”分配物理内存。

同时你也需要修改其它函数，让它能够允许一些非法情况的发生。

lab 6 Copy-on-Write Fork for xv6 (2020/2021)

同样考察page fault的理解。COW fork和lazy page allocation都是可以通过处理page fault来实现的功能，但是前者可能要更难一些。因为在fork之后，新进程的页表和父进程的页表指向同一块区域，因此需要对page进行计数。这个涉及到一些多线程并发的东西，例如自旋锁来维护每个page的计数的不变性。

总之也算是比较难的一个lab。

lab 7 Multithreading (2020/2021)

这个lab有点意思，它不仅考察了你对xv6进程调度的理解，还让你了解了一下 UNIX pthread 库函数的使用，来实现多线程并发以及barrier。

多线程并发编程是个老生常谈的话题，我以后大概也会花时间深入了解一下。

但是lab本身是简单的。

lab 8 lock (2020/2021)

这个lab的主要任务是改善xv6原有的对lock的粗粒度的使用。需要你给出更加细粒度的lock方案。

对于每个lock，你需要明确它所保护的不变性。

之前无聊的时候写过解法：https://atri2333.github.io/2024/04/12/lock-lab/

lab 9 file system (2020/2021)

这个lab有两个任务：第一个任务是采用页表分层的思想，将inode的indirect数据block也进行分层，来大幅扩展一个文件所能支持的大小。第二个任务是实现 symlink 系统调用，创建一个新的文件类型symlink，并可以通过这个symlink来追踪其它文件或symlink。

讲真文件系统这章我学的有点仓促，感觉有些东西并没有特别懂，但是对于lab本身还是够用。

lab 10 mmap (2020/2021)

这个lab要求你实现一个阉割版的mmap系统调用，及其对应的阉割版的munmap系统调用，能让用户可以通过访问内存来同步访问文件。

算是对前面的lab的总结了，它涉及到了页表、page fault、文件系统等知识点。

杂谈

关于调试，一般来讲是推荐gdb。但是根据我亲身经历（或者acmer的破习惯），printf调试法更加有用。这可能是由于我gdb用的并不熟练，所以调试起来笨手笨脚的，不如直接打log来的方便与显然（

另外，有一些lab并不是只靠我一个人完成的，我是适当地参考了一些其它人的做法。特别是2020年的页表那个实验，我发现我的写法和网上很多人都不一样，导致就算看别人的也没办法把自己的bug调试好（

不过最终也是赶在学校的破实验课开课前把除了network的xv6 lab都过了一遍，收获挺大的，算是对os有了初步的理解。至少给我一些名词，例如进程、线程、页表等，我都能从xv6的例子中进行联想。

后面会通过这个系列深入xv6源码：https://www.youtube.com/playlist?list=PLbtzT1TYeoMhTPzyTZboW_j7TPAnjv9XB

摆烂

这几周，除了自学这个课程，感觉就没做什么了。

可能，打了一些比赛

校赛，虽然acm退役了，但是打了rk4，仅次于三位noi选手

csp，455，虽然发挥不太好

蓝桥杯，一般般吧，国赛懒得去了

天梯赛，国一，但是我比赛期间（不知晓具体规则的情况下）本能地去头文件查了api，感觉要被查作弊了

codeforces，摆烂了，不想打，只打atcoder，然后1600还没上

学了点java

感觉，学国外的公开课，收获确实挺大

做对应的lab，居然会有点网瘾的感觉

但是现在却没有当初网瘾的动力了

好在，认识了一个非常好的人

所以这几周过的也是非常有意义

发表于 Disqus：

JAVA速成Day5——策略模式

源自于Head First 设计模式 第一章

具体的idea是将一组算法封装到一个对象中。一个常见的例子是之前接触过的 Comparator ：

1
2
3
4
5
6
7
Comparator<Integer> cmp = new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            Integer val = o2 - o1;
            return val.intValue();
        }
    };

自己实现策略模式的排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Main {
    public static void main(String[] args) throws InterruptedException {
        String[] array = { "apple", "Pear", "Banana", "orange" };
        sort(array, String::compareToIgnoreCase);
        System.out.println(Arrays.toString(array));
    }

    static <T> void sort(T[] a, Comparator<? super T> c) {
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (c.compare(a[j], a[j + 1]) > 0) { // 注意这里比较两个元素的大小依赖传入的策略
                    T temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
    }
}

而排序的规则，并不直接体现在 sort 内部。这就避免了面向实现编程。

例如，我们要实现不同的排序规则，我们可以首先定义一个接口：

1
2
3
public interface sortStrategy{
	void sort(int[] array);
}

然后可以定义多个排序算法，实现该接口：

1
2
3
4
5
6
7
8
9
10
11
public class QuickSort implements sortStrategy{
	public void sort(int[] array){
		...
	}
}

public class MergeSort implements sortStrategy{
	public void sort(int[] array){
		...
	}
}

要应用策略的话，可以通过多态特性：

1
sortStrategy my_sort = new QuickSort();

如果该接口是一个类的字段，可以通过 setter 方式，很方便地修改其算法行为。这就是策略模式的精髓所在。

发表于 Disqus：

xv6 lock lab

链接：https://pdos.csail.mit.edu/6.828/2021/labs/lock.html

2021和2020是一样的

xv6支持多线程并发。为了保证共享内存中数据的不变性（invariant），需要采用lock机制进行序列化。

但是xv6的内核内部中的一些机制中对lock的使用过于粗粒（coarse-grained），这会导致线程会浪费较多时间在spinlock的自旋上，因此该lab的任务就是细粒化一些功能中的lock机制。

Memory allocator

xv6的内核维护了一个全局的page链表，内部存着尚未被分配的page的物理地址。对于请求/释放内存，xv6为整个链表维护了一个lock。

考虑到可能多个线程会同时请求/释放内存，而链表整体的lock则会序列化这些过程，无法发挥并发优势。因此该任务需要你来细粒化 kalloc.c 中的lock机制。

至于怎么细粒化，其实lab的提示已经给出：为每个CPU分配一个单独的链表，及其对应的lock。

所以直接把 kmem 改成数组：

1
2
3
4
struct {
  struct spinlock lock;
  struct run *freelist;
} kmem[NCPU];

然后同时修改初始化函数 kinit ，该函数只在xv6启动的时候被一个CPU调用：

1
2
3
4
5
6
7
void
kinit()
{
  for(int i = 0; i < NCPU; i++)
    initlock(&kmem[i].lock, "kmem");
  freerange(end, (void*)PHYSTOP);
}

我们考虑一下分配内存的过程。对于每个CPU对应的链表，如果链表为空，则需要从其它CPU的链表中偷取。

具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void *
kalloc(void)
{
  struct run *r;
  uint cid;
  push_off();
  cid = cpuid();
  pop_off();

  acquire(&kmem[cid].lock);
  r = kmem[cid].freelist;
  if(r){
    kmem[cid].freelist = r->next;
    release(&kmem[cid].lock);
  }
  else{
    release(&kmem[cid].lock);
    for(int i = 0; i < NCPU; i++){
      if(i == cid) continue;
      acquire(&kmem[i].lock);
      r = kmem[i].freelist;
      if(!r){
        release(&kmem[i].lock);
        continue;
      }
      kmem[i].freelist = r->next;
      release(&kmem[i].lock);
      break;
    }
  }
  

  if(r)
    memset((char*)r, 5, PGSIZE); // fill with junk
  return (void*)r;
}

这里强调一下，无论是在xv6的lab，还是其它并发编程中（例如C++11内的 std::mutex ），我们都需要对每个lock规定其对应的不变量（invariant）。这个是很重要的，它关系到在设置获取和释放锁的时机，以及防止死锁。

例如本任务，对于每个CPU对应的链表，都有一个lock。因此我们规定该lock维护的不变量为其对应的链表结构。

因此，在发现执行CPU对应的链表为空时，我们就可以释放锁了，因为接下来的工作都对该链表没有任何关系。这种细微的细节应该也算是细粒化工作的重要部分。

然后考虑释放内存，只需要在对应CPU的链表加入元素即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void
kfree(void *pa)
{
  struct run *r;
  uint cid;
  push_off();
  cid = cpuid();
  pop_off();

  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;

  acquire(&kmem[cid].lock);
  r->next = kmem[cid].freelist;
  kmem[cid].freelist = r;
  release(&kmem[cid].lock);
}

Buffer cache

xv6在读/写硬盘IO时，会先检查内存是否存在对应的缓存（buffer cache）。如果存在则直接在缓存上执行操作，然后写入硬盘。

关于xv6在内存中对buffer cache的组织形式，事实上是一个双链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// buf.h
struct buf {
  int valid;   // has data been read from disk?
  int disk;    // does disk "own" buf?
  uint dev;
  uint blockno;
  struct sleeplock lock;
  uint refcnt;
  struct buf *prev; // LRU cache list
  struct buf *next;
  uchar data[BSIZE];
  uint time_stamp; // lru time stamp
  int now_hash;  // hash number
};

// bio.c
struct {
  struct spinlock lock;
  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;
} bcache;

可以发现似乎和上面那个链表似乎很像。但事实上该链表的元素本身也是个结构体 buf ，而不是单纯一个物理地址。

那么我们能不能沿用上个任务的idea，对每个CPU维护一个buffer cache link list呢？

根据lab中的提示，是不行的。给出的原因是每一个buffer cache应当被不同CPU的线程共享。

但是实际上是可以的，只不过我们需要换个角度来看。根据lab的提示，我们应当将原有的大链表进行分割，得到一系列小链表，然后在各自的小链表上并行化工作。

实质是一样的，都是将一个拆分为多个。

如何将block的编号与小链表对应呢？答案是采用哈希函数。这里根据lab，定义13（素数减少冲突概率）个小链表，然后直接将block编号对13取余得到哈希值。

首先，我们需要初始化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct bucket{
  struct spinlock lock;
  struct buf head;
}hashtable[BUCKETCNT]; // 13

void
binit(void)
{
  struct buf *b;
  int i;

  initlock(&bcache.lock, "bcache");

  // // Create linked list of buffers
  // bcache.head.prev = &bcache.head;
  // bcache.head.next = &bcache.head;

  for(i = 0; i < BUCKETCNT; i++){
    initlock(&hashtable[i].lock, "bcache_hash");
    hashtable[i].head.prev = &hashtable[i].head;
    hashtable[i].head.next = &hashtable[i].head;
  }
  
  for(i = 0, b = bcache.buf; b < bcache.buf+NBUF; b++, i = (i + 1) % BUCKETCNT){
    b->next = hashtable[i].head.next;
    b->prev = &hashtable[i].head;
    initsleeplock(&b->lock, "buffer");
    hashtable[i].head.next->prev = b;
    hashtable[i].head.next = b;

    b->time_stamp = 0;
    b->now_hash = i;
  }
  
}

这里我将NBUF个buffer cache平均分配了。如果只分配到一个小链表上，则可能会加大冲突概率。

然后考虑我们如何获得buffer cache。我们首先在自己哈希值上的链表上找，如果没有则去其它小链表上轮换查找。

根据lab提示，我们采用lru策略。因此可以看到我上面给出的 buf 结构体相比于原有的结构体，多了时间戳 time_stamp 字段。

话不多说，直接上code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
static struct buf*
bget(uint dev, uint blockno)
{
  struct buf *b;
  struct buf *lru=0;
  uint hash = blockno % BUCKETCNT;
  uint min_time_stamp = ticks + 114514;
  
  acquire(&hashtable[hash].lock);

  for(b = hashtable[hash].head.next; b != &hashtable[hash].head; b = b->next){
    if(b->dev == dev && b->blockno == blockno){
      b->refcnt++;
      release(&hashtable[hash].lock);
      acquiresleep(&b->lock);
      return b;
    }
  }

  // Not cached.
  // printf("ticks = %d\n", ticks);
  // for(b = bcache.buf; b < bcache.buf+NBUF; b++){
  //   if(b->refcnt == 0 && b->time_stamp <= min_time_stamp) {
  //     lru = b;
  //     min_time_stamp = b->time_stamp;
  //   }
  // }

  for(int i = (hash + 1) % BUCKETCNT; i != hash; i = (i + 1) % BUCKETCNT){
    acquire(&hashtable[i].lock);

    for(b = hashtable[i].head.next; b != &hashtable[i].head; b = b->next){
      if(b->refcnt == 0 && b->time_stamp < min_time_stamp) {
        lru = b;
        min_time_stamp = b->time_stamp;
      }
    }

    if(!lru) {
      release(&hashtable[i].lock);
      continue;
    }

    b = lru;
    b->next->prev = b->prev;
    b->prev->next = b->next;
    release(&hashtable[i].lock);


    b->dev = dev;
    b->blockno = blockno;
    b->valid = 0;
    b->refcnt = 1;
    b->now_hash = hash;


    b->next = hashtable[hash].head.next;
    b->prev = &hashtable[hash].head;

    acquiresleep(&b->lock);

    hashtable[hash].head.next->prev = b;
    hashtable[hash].head.next = b;
    release(&hashtable[hash].lock);

    return b;
  }
  // printf("min_time_stamp = %d\n", min_time_stamp);

  if(!lru)
    panic("bget: no buffers");
  return lru;
}

对于每个lock，我们规定它的不变量为：该lock对应双链表的结构，以及链表内元素的本身结构。

所以你可以发现，当我们从其余链表偷取一个 cache 时，我们先释放了其余链表的锁，然后等把该 cache 内部的值设置完成之后再释放当前hash值链表的锁。

在网上看到有些做法，访问全局变量 ticks 前需要 acquire(&tickslock); 。然而实测是不需要的。

最后考虑一下释放的操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void
brelse(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);

  acquire(&hashtable[b->now_hash].lock);
  b->refcnt--;
  if (b->refcnt == 0) {
    // no one is waiting for it.
    b->time_stamp = ticks;
  }
  release(&hashtable[b->now_hash].lock);
}

可以发现，由于我们规定了lock的不变量，这里我们上的锁就是哈希值对应的锁。（即lock维护b->refcnt 等不变量）

同时，我们需要修改一下其余函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void
bpin(struct buf *b) {
  // printf("!!!\n");
  acquire(&hashtable[b->now_hash].lock);
  b->refcnt++;
  release(&hashtable[b->now_hash].lock);
}

void
bunpin(struct buf *b) {
  acquire(&hashtable[b->now_hash].lock);
  b->refcnt--;
  release(&hashtable[b->now_hash].lock);
}

虽然该lab并没有指出这些函数，但在usertests中是有调用的。事实上函数 bpin 的作用是强制一个buffer cache不被 brelse 掉，这在更新 log block 对应的block时有用到。

最后贴一张完成的图：

发表于 更新于 Disqus：

JAVA速成Day4——字符串

字符串也是ACM里常用的东西，但是java里的字符串我并不是很熟悉，所以这次就稍微速通一下~

String：

首先我们得清楚String类在java中是不可变的。这真的勾八坑爹

  • equals()

比较两个String是否相等，返回boolean

  • compareTo()

比较两个字符串的字典序，返回负数/0/正数

  • substring()

提取子串，左闭右开。第二个参数可选

1
"blackbird".substring(5) // bird
  • toCharArray()

转化为 Char[] 。

StringBuilder

由于String类部是 final 类型，不可变。因此当你使用 + 连接两个String时，事实上会再new一个String对象，这是没有效率的。

所以java提供了一个类StringBuilder，它是可变的。

1
2
3
4
5
6
7
8
9
10
public class Main {
    public static void main(String[] args) {
        StringBuilder str = new StringBuilder();
        str.append("i ").append("love ").append("blackbird.");
        String output = str.toString();
        System.out.println(output);
        str.setCharAt(0, 'u');
        System.out.println(str);
    }
}

顺带一提

这里提到了方法equals() 。事实上，对于所有非基本类型，都应该使用这个方法来判断对象之间是否相等。

基本类型 对应的引用类型
boolean java.lang.Boolean
byte java.lang.Byte
short java.lang.Short
int java.lang.Integer
long java.lang.Long
float java.lang.Float
double java.lang.Double
char java.lang.Character

例如int对应的引用类型Integer

0%