MIT 6.824 练习1

Hi, there! 这是一份根据 MIT 6.824(2021) 课程的第 2 课的课堂示例代码改编的 2 个 go 语言编程练习。像其他的编程作业一样，我去除了核心部分，保留了代码框架，并编写了每一步的提示

练习代码在本文的最后面

爬虫

1 单线程爬虫

首先，请为 fakeFetcher 类型实现 Fetcher 接口中的 Fetch() 方法。然后实现串行爬虫 Serial() 函数（递归），并在 main() 中调用它，预期的输出如下：

=== Serial===
found: http://golang.org/
found: http://golang.org/pkg/
missing: http://golang.org/cmd/
found: http://golang.org/pkg/fmt/
found: http://golang.org/pkg/os/

2 多线程爬虫（使用锁同步）

我们定义了 fetchState 类型，用于对 fetched 加锁保护，但是还未实现它的“构造函数”。请先实现它的“构造函数”，名为 makeState()。注意对于结构体，一般返回其指针

然后实现 ConcurrentMutex，实现一个通过锁控制的并发爬虫。提示：

sync.WaitGroup（等待组）是Go语言标准库中的一个并发原语，用于等待一组 goroutine 完成执行，提供了三个主要方法：

• Add(delta int)：增加等待组的计数器。delta 参数表示要添加到计数器的值，通常为 1
• Done()：减少等待组的计数器。相当于 Add(-1)
• Wait()：阻塞调用它的 goroutine，直到等待组的计数器归零

等待组的计数器是一个非负整数，初始值为 0。当计数器的值变为 0 时，意味着所有的 goroutine 都已经完成，Wait() 方法会解除阻塞并继续执行后续代码

最后，在 main 中调用 ConcurrentMutex，预期的输出如下：

=== Serial===
found: http://golang.org/
found: http://golang.org/pkg/
missing: http://golang.org/cmd/
found: http://golang.org/pkg/fmt/
found: http://golang.org/pkg/os/
=== ConcurrentMutex ===
found: http://golang.org/
missing: http://golang.org/cmd/
found: http://golang.org/pkg/
found: http://golang.org/pkg/os/
found: http://golang.org/pkg/fmt/

3 多线程爬虫（使用channel同步）

练习代码中已经提供了 ConcurrentChannel 函数，你无需改动它，只需要实现 worker 和 master 函数即可

// Concurrent crawler with channels
func ConcurrentChannel(url string, fetcher Fetcher) {ch := make(chan []string)go func() {ch <- []string{url}}()master(ch, fetcher)
}

最后，在 main 中调用 ConcurrentChannel 函数，预期的输出如下：

=== Serial===
found: http://golang.org/
found: http://golang.org/pkg/
missing: http://golang.org/cmd/
found: http://golang.org/pkg/fmt/
found: http://golang.org/pkg/os/
=== ConcurrentMutex ===
found: http://golang.org/
missing: http://golang.org/cmd/
found: http://golang.org/pkg/
found: http://golang.org/pkg/os/
found: http://golang.org/pkg/fmt/
=== ConcurrentChannel ===
found: http://golang.org/
missing: http://golang.org/cmd/
found: http://golang.org/pkg/
found: http://golang.org/pkg/os/
found: http://golang.org/pkg/fmt/

kv 存储

client := connect()
err := client.Call("KV.Get", &args, &reply)
client.Close()

Put(subject, 6.824) done
get(subject) -> 6.824

练习代码

// crawler-exercise.go
package mainimport ("sync"
)// Serial crawler
func Serial(url string, fetcher Fetcher, fetched map[string]bool) {// TODO 1
}// Concurrent crawler with shared state and Mutex
type fetchState struct {mu      sync.Mutexfetched map[string]bool
}// TODO 2: implement fetchState's constructorfunc ConcurrentMutex(url string, fetcher Fetcher, f *fetchState) {// TODO 2
}func worker(url string, ch chan []string, fetcher Fetcher) {// TODO 3
}func master(ch chan []string, fetcher Fetcher) {// TODO 3
}// Concurrent crawler with channels
func ConcurrentChannel(url string, fetcher Fetcher) {ch := make(chan []string)go func() {ch <- []string{url}}()master(ch, fetcher)
}func main() {// uncomment them step by step/*fmt.Printf("=== Serial===\n")Serial("http://golang.org/", fetcher, make(map[string]bool))fmt.Printf("=== ConcurrentMutex ===\n")ConcurrentMutex("http://golang.org/", fetcher, makeState())fmt.Printf("=== ConcurrentChannel ===\n")ConcurrentChannel("http://golang.org/", fetcher)*/
}// Fetcher
type Fetcher interface {// Fetch returns a slice of URLs found on the page.Fetch(url string) (urls []string, err error)
}// fakeFetcher is Fetcher that returns canned results.
type fakeFetcher map[string]*fakeResulttype fakeResult struct {body stringurls []string
}// TODO 1: implement Fetch for fakeFetch// fetcher is a populated fakeFetcher.
var fetcher = fakeFetcher{"http://golang.org/": &fakeResult{"The Go Programming Language",[]string{"http://golang.org/pkg/","http://golang.org/cmd/",},},"http://golang.org/pkg/": &fakeResult{"Packages",[]string{"http://golang.org/","http://golang.org/cmd/","http://golang.org/pkg/fmt/","http://golang.org/pkg/os/",},},"http://golang.org/pkg/fmt/": &fakeResult{"Package fmt",[]string{"http://golang.org/","http://golang.org/pkg/",},},"http://golang.org/pkg/os/": &fakeResult{"Package os",[]string{"http://golang.org/","http://golang.org/pkg/",},},
}

// kv-exercise.go
package mainimport ("fmt""log""net""net/rpc""sync"
)//
// Common RPC request/reply definitions
//const (OK       = "OK"ErrNoKey = "ErrNoKey"
)type Err stringtype PutArgs struct {Key   stringValue string
}type PutReply struct {Err Err
}type GetArgs struct {Key string
}type GetReply struct {Err   ErrValue string
}func connect() *rpc.Client {client, err := rpc.Dial("tcp", ":1234")if err != nil {log.Fatal("dialing:", err)}return client
}func get(key string) string {// TODO 2return ""
}func put(key string, val string) {// TODO 2
}type KV struct {mu   sync.Mutexdata map[string]string
}// TODO 1: implement `Get` method for *KV// TODO 1: implement `Put` method for *KV
func server() {kv := new(KV)kv.data = map[string]string{}rpcs := rpc.NewServer()rpcs.Register(kv)l, e := net.Listen("tcp", ":1234")if e != nil {log.Fatal("listen error:", e)}go func() {for {conn, err := l.Accept()if err == nil {go rpcs.ServeConn(conn)} else {break}}l.Close()}()
}func main() {server()put("subject", "6.824")fmt.Printf("Put(subject, 6.824) done\n")fmt.Printf("get(subject) -> %s\n", get("subject"))
}