这里会记录学习MIT6.1810的笔记：
我主要会记录一些自己对每一节课的理解，方便日后复习。
同时也会要求自己把每个课程作业按照最高要求去完成，会记录一些LAB里有难度的地方。
所有代码会维护在
https://github.com/yixuaz/6.1810-2023
SCHEDULE使用的是如下：
https://pdos.csail.mit.edu/6.828/2023/schedule.html
根据里面的教程，我在WINDOWS下配置了WSL2来跑LINUX。
代码会维护在
Lec 1
什么是操作系统？
硬件：CPU、RAM、硬盘、网络等
用户应用：如shell（sh）、编译器（cc）、数据库（DB）等
内核服务：如文件系统（FS）、进程、内存、网络等
系统调用
kernel
Kernel是计算机资源的守护者。当你打开计算机时，Kernel总是第一个被启动。Kernel程序只有一个，它维护数据来管理每一个用户空间进程。Kernel同时还维护了大量的数据结构来帮助它管理各种各样的硬件资源，以供用户空间的程序使用。Kernel同时还有大量内置的服务，例如，Kernel通常会有文件系统实现类似文件名，文件内容，目录的东西，并理解如何将文件存储在磁盘中。所以用户空间的程序会与Kernel中的文件系统交互，文件系统再与磁盘交互。
操作系统的目的是什么？
- 在多个应用之间复用硬件
- 隔离应用程序, 保证安全，彼此错误不会相互影响
- 允许合作的应用程序之间共享资源
- 为了可移植性而抽象硬件
- 提供有用的服务
高效vs易用。
高效性需要在low-level接近硬件进行操作，而易用性需要提供high-level的可移植接口。因此，实现既简单可移植又高效的接口是个挑战。
强大vs简单。
我们也想要提供强大的操作系统服务来辅助应用程序运行，但又期望其拥有简单的接口以便于程序员理解和使用。目标是提供既简单又功能强大的接口。
灵活性vs安全性
内核具备灵活的接口。我们希望给程序员完全的自由，但是实际上又不能是真正的完全自由，因为我们不想要程序员能直接访问到硬件，干扰到其他的应用程序，或者干扰操作系统的行为。
Lab 1
1. Write an uptime program that prints the uptime in terms of ticks using the uptime system call.
这个问题只要调用一下uptime这个系统调用即可。
int
main(int argc, char *argv[])
{
printf("ticks: %d\n", uptime());
exit(0);
}
2. Support regular expressions in name matching for find. grep.c has some primitive support for regular expressions.
学习find里支持REGEX代码，那个正则表达式的理解，是这道题最有收获；我会简单讲解一下；
#include "kernel/types.h"
#include "kernel/stat.h"
#include "kernel/fcntl.h"
#include "user/user.h"
char buf[1024];
int match(char*, char*);
void
grep(char *pattern, int fd)
{
int n, m;
char *p, *q;
m = 0;
while((n = read(fd, buf+m, sizeof(buf)-m-1)) > 0){
m += n;
buf[m] = '\0';
p = buf;
while((q = strchr(p, '\n')) != 0){
*q = 0;
if(match(pattern, p)){
*q = '\n';
write(1, p, q+1 - p);
}
p = q+1;
}
if(m > 0){
m -= p - buf;
memmove(buf, p, m);
}
}
}
int
main(int argc, char *argv[])
{
int fd, i;
char *pattern;
if(argc <= 1){
fprintf(2, "usage: grep pattern [file ...]\n");
exit(1);
}
pattern = argv[1];
if(argc <= 2){
grep(pattern, 0);
exit(0);
}
for(i = 2; i < argc; i++){
if((fd = open(argv[i], O_RDONLY)) < 0){
printf("grep: cannot open %s\n", argv[i]);
exit(1);
}
grep(pattern, fd);
close(fd);
}
exit(0);
}
// Regexp matcher from Kernighan & Pike,
// The Practice of Programming, Chapter 9, or
// https://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html
int matchhere(char*, char*);
int matchstar(int, char*, char*);
int
match(char *re, char *text)
{
if(re[0] == '^')
return matchhere(re+1, text);
do{ // must look at empty string
if(matchhere(re, text))
return 1;
}while(*text++ != '\0');
return 0;
}
// matchhere: search for re at beginning of text
int matchhere(char *re, char *text)
{
if(re[0] == '\0')
return 1;
if(re[1] == '*')
return matchstar(re[0], re+2, text);
if(re[0] == '$' && re[1] == '\0')
return *text == '\0';
if(*text!='\0' && (re[0]=='.' || re[0]==*text))
return matchhere(re+1, text+1);
return 0;
}
// matchstar: search for c*re at beginning of text
int matchstar(int c, char *re, char *text)
{
do{ // a * matches zero or more instances
if(matchhere(re, text))
return 1;
}while(*text!='\0' && (*text++==c || c=='.'));
return 0;
}
当然可以。这段代码主要通过两个函数 matchhere 和 matchstar 来实现对 . 和 * 的支持。
对于 . 的支持
在 matchhere 函数中有这样一段代码：
if(*text!='\0' && (re[0]=='.' || re[0]==*text))
return matchhere(re+1, text+1);
这里，re[0]=='.' 是检查正则表达式当前字符是否为 .。如果是，或者正则表达式的当前字符与文本的当前字符匹配，那么函数将继续比较正则表达式的下一个字符和文本的下一个字符。
对于 * 的支持
* 的匹配比较特殊。在正则表达式中，* 意味着匹配前面的字符零次或多次。例如，a* 可以匹配 "", "a", "aa", "aaa" 等。
在 matchhere 函数中有这样一段代码：
if(re[1] == '*')
return matchstar(re[0], re+2, text);
如果 re[1] 是 *，则调用 matchstar 函数。
在matchstar 函数中：
do{
if(matchhere(re, text))
return 1;
}while(*text!='\0' && (*text++==c || c=='.'));
这里有一个循环，尝试着匹配 * 前面的字符零次、一次、两次等，直到不能匹配为止。对于每一种尝试，都调用 matchhere 函数来检查剩余的正则表达式是否与剩余的文本匹配。
注意条件 (*text++==c || c=='.')，这里的 c 是 * 前面的字符。这意味着，只有当文本的当前字符与 c 匹配或 c 是 . 时，循环才会继续。
3. modify the shell to not print a $ when processing shell commands from a file
这道题实际上就是要我们实现一个isatty函数；
isatty 是一个在 POSIX-like 系统中常见的函数，它的功能是判断给定的文件描述符是否与一个终端关联。
这个函数返回一个布尔值，如果 fd（文件描述符）与终端关联，则返回 1，否则返回 0。
int
isatty (int fd)
{
struct stat st;
if (fstat(fd, &st) < 0) {
printf("Error calling fstat\n");
exit(1);
}
// 1 == CONSOLE
return st.type == T_DEVICE && st.dev == 1;
}
int
getcmd(char *buf, int nbuf)
{
// 0 is stdin
if (isatty(0)) {
write(2, "$ ", 2);
}
...
}
测试方法：
之前那些$都消失了
1697898001757.png
4. modify the shell to support wait
在 shell 脚本中，wait 是一个内置命令，用于使脚本暂停执行并等待一个或多个后台进程完成执行。
作用：
同步化：当在脚本中启动一个或多个后台进程时，你可能希望在继续执行其他命令之前等待这些后台进程完成。这样，你可以确保某些任务在其他任务开始之前已经完成。
资源管理：在某些情况下，你可能不希望在之前的后台进程完成之前启动新的进程。这可以避免过多的并发进程占用太多资源。
因为这个命令直接和shell相关，需要让shell进程wait后台子进程执行完成，所以和cd是一个level；
具体实现方法是，对于BACKGROUND的命令，FORK之后，子进程去执行实际命令，父进程进行wait；（这里的父进程，其实是shell fork出来的子进程）
然后在shell 进程没使用wait 命令时，我们可以判断，这个cmd如果是个background的，我们就啥也不做，别的就wait下
1697897745531.png
然后在shell 的main函数里，加上
else if(!strcmp(buf, "wait\n")){
// wait must be called by the parent, not the child.
int status, pid;
while((pid = wait(&status)) != -1)
printf("%d done, status：%d\n", pid, status);
continue;
}
...
struct cmd *curcmd = parsecmd(buf);
if(fork1() == 0)
runcmd(curcmd);
else if (curcmd->type != BACK)
wait(0);
}
测试方法：
1697897944263.png
5. modify the shell to support lists of commands, separated by ";"
本身就支持了；
6. modify the shell to support sub-shells by implementing "(" and ")"
本身就支持了；
1697898120163.png
7.modify the shell to support tab completion
这个题虽然标了easy, 但真的要实现到和linux shell 一样的效果，还是要写非常多的代码，和非常大的思考量；而且还需要稍微改下kernel;
要实现这个，xv6的代码有这么几个问题
- 我经过研究，发现在读入命令时，是kernel的
console.c基于行,也就是说除非你打了回车，不然SHELL段是读不到数据的。所以需要让\t也要触发缓冲区刷新。让shell测可以读到数据 - shell测拿到数据后，判断如果最后是
\t；那么就可以根据是否有空格，来判断是命令补全，还是文件补全；并且判断是否有多个选项；有多个选项，找到最长公共前缀进行补全；单个匹配，就直接补全；没有匹配，就没有任何效果； - 补全的时候发现，直接
write进stdin 是不work的；但是如果往stdout写，这个字符是不可修改的。所以这边也需要修改kernel；具体做法是当往stdout写时，console.c接受到写数据，判断第一个是否为\t, 如果是的话，需要维护kernel buf的3个指针，同时调用consputc去模拟用户的输入；
所以要实现这个功能，还是比较复杂；我们来看下3个模块的代码时怎么改动的；
在console.c中：
1697898850325.png
在console.c的consoleintr函数中：
1697898895701.png
在shell里添加支持的代码：
char* knowncommands[] = {
"ls","cat","echo","history","cd","wait","sleep","pingpong","primes","find","xargs","uptime",
"wc","zombie","grind","usertests","stressfs","sh","rm","mkdir","ln","kill","init","grep","forktest"
};
char* common_longest_prefix(const char* a, const char* b) {
int len = 0;
while (a[len] && a[len] == b[len]) len++;
char* prefix = (char*) malloc(strlen(a));
strcpy(prefix, a);
prefix[len] = '\0';
return prefix;
}
int
completecmd(char *buf)
{
if (!strlen(buf)) return 0;
int matchcount = 0;
char *match = NULL;
char *fileidx = strrchr(buf, ' ');
// If the buffer contains a space, look for filenames
if (fileidx) {
struct dirent dir;
int fd = open(".", O_RDONLY);
fileidx += 1;
if (fd >= 0) {
while (read(fd, &dir, sizeof(dir)) == sizeof(dir)) {
if (dir.inum == 0) continue;
if (!strncmp(dir.name, fileidx, strlen(fileidx))) {
if (matchcount) {
if (matchcount == 1) printf("\n%s", match);
printf("\n%s", dir.name);
matchcount++;
char* newmatch = common_longest_prefix(match, dir.name);
free(match);
match = newmatch;
} else {
char *copy = malloc(strlen(dir.name));
strcpy(copy, dir.name);
match = copy;
matchcount = 1;
}
}
}
close(fd);
}
}
else { // Otherwise, look for command matches
for (int i = 0; i < sizeof(knowncommands) / sizeof(knowncommands[0]); i++) {
if (!strncmp(knowncommands[i], buf, strlen(buf))) {
if (matchcount) {
printf("\n%s", knowncommands[i]);
matchcount++;
} else {
match = knowncommands[i];
matchcount = 1;
}
}
}
}
char* result;
if (matchcount == 1) {
// If a single match is found, complete the command
result = malloc(strlen(fileidx) + strlen(match) + 3);
strcpy(result, "\t");
strcpy(result + 1, buf);
strcpy(result + 1 + strlen(buf), "\t");
if(fileidx)
strcpy(result + 2 + strlen(buf), match + strlen(fileidx));
else
strcpy(result + 2 + strlen(buf), match + strlen(buf));
} else if (matchcount > 1) {
printf("\n$ ");
int buflen = strlen(buf);
result = malloc(buflen + strlen(match) + 3);
strcpy(result, "\t\t");
strcpy(result + 2, buf);
strcpy(result + 2 + buflen, match + strlen(fileidx));
} else {
result = malloc(strlen(buf) + 2);
strcpy(result, "\t");
strcpy(result + 1, buf);
}
write(1, result, strlen(result));
free(result);
return strlen(buf);
}
int
getcmd(char *buf, int nbuf)
{
if (isatty(0)) {
write(2, "$ ", 2);
}
memset(buf, 0, nbuf);
int idx = 0, cc = 0;
char c;
for(; idx+1 < nbuf; ) {
cc = read(0, &c, 1);
if(cc < 1)
break;
if(c == '\t') { // Tab key
buf[idx] = 0;
idx -= completecmd(buf);
}
...
}
测试方法
- 打l, 按tab, 看是否可以提示
- 补全的字符，是否可以删除
- 最长公共字符串是否可以补全
-
文件名是否可以补全
1697899484120.png
8. modify the shell to keep a history of passed shell commands
如何保存history? 设计一个循环数组
如何支持上下的按键 跳回到上一条commands?
这个也要改动一下kernel，因为上，下键是由3个字符表示；所以我们需要在console.c，维护一个状态机；并且还要改动，不能每次只传一个字符过来
enum {
NORMAL,
ESCAPE_SEEN,
BRACKET_SEEN
} input_state = NORMAL;
...
//
// the console input interrupt handler.
// uartintr() calls this for input character.
// do erase/kill processing, append to cons.buf,
// wake up consoleread() if a whole line has arrived.
//
void normalintr(int c)
{
switch(c){
case C('P'): // Print process list.
procdump();
break;
case C('U'): // Kill line.
while(cons.e != cons.w &&
cons.buf[(cons.e-1) % INPUT_BUF_SIZE] != '\n'){
cons.e--;
consputc(BACKSPACE);
}
break;
case C('H'): // Backspace
case '\x7f': // Delete key
if(cons.e != cons.w){
cons.e--;
consputc(BACKSPACE);
}
break;
case '\t': // Tab key
cons.buf[cons.e++ % INPUT_BUF_SIZE] = c;
cons.w = cons.e;
wakeup(&cons.r);
break;
default:
if(c != 0 && cons.e-cons.r < INPUT_BUF_SIZE){
c = (c == '\r') ? '\n' : c;
// echo back to the user.
consputc(c);
// store for consumption by consoleread().
cons.buf[cons.e++ % INPUT_BUF_SIZE] = c;
if(c == '\n' || c == C('D') || cons.e-cons.r == INPUT_BUF_SIZE){
// wake up consoleread() if a whole line (or end-of-file)
// has arrived.
cons.w = cons.e;
wakeup(&cons.r);
}
}
break;
}
}
void dirintr(int c)
{
switch(c){
case 'A':
case 'B':
while(cons.e != cons.w){
cons.e--;
consputc(BACKSPACE);
}
cons.buf[cons.e++ % INPUT_BUF_SIZE] = '\x1b';
cons.buf[cons.e++ % INPUT_BUF_SIZE] = '[';
cons.buf[cons.e++ % INPUT_BUF_SIZE] = c;
cons.w = cons.e;
wakeup(&cons.r);
}
}
void
consoleintr(int (*getc)(void))
{
int c;
acquire(&cons.lock);
while((c = getc()) >= 0){
switch(input_state) {
case NORMAL:
if (c == '\x1b') {
input_state = ESCAPE_SEEN;
} else {
normalintr(c);
}
break;
case ESCAPE_SEEN:
if (c == '[') {
input_state = BRACKET_SEEN;
} else {
input_state = NORMAL;
}
break;
case BRACKET_SEEN:
// Reset to the normal state for any other character.
input_state = NORMAL;
dirintr(c);
break;
}
}
release(&cons.lock);
}
下面就是shell 的改动，
#define HISTSIZE 21
char history[HISTSIZE][100];
int historySt = 0;
int historyEnd = 0;
int historyPos = 0;
...
void write_shell_stdin(char* buf) {
char *result = malloc(strlen(buf) + 3);
strcpy(result, "\t\t");
strcpy(result + 2, buf);
write(1, result, strlen(result));
}
int
getcmd(char *buf, int nbuf)
{
if (isatty(0)) {
write(2, "$ ", 2);
}
memset(buf, 0, nbuf);
int idx = 0, cc = 0;
char c;
for(; idx+1 < nbuf; ) {
cc = read(0, &c, 1);
if(cc < 1)
break;
if(c == '\t') { // Tab key
buf[idx] = 0;
idx -= completecmd(buf);
}
else if(c == '\x1b') {
char d = 0, e = 0;
read(0, &d, 1);
read(0, &e, 1);
if (d == '[' && e == 'A') {
if (historyPos > historySt) historyPos--;
write_shell_stdin(history[historyPos]);
} else if (d == '[' && e == 'B') {
if (historyPos < historyEnd) historyPos++;
write_shell_stdin(history[historyPos]);
}
}
else {
buf[idx++] = c;
if (c == '\n' || c == '\r') break;
}
}
buf[idx] = '\0';
if(buf[0] == 0) // EOF
return -1;
return 0;
}
void
add_history(char *cmd) {
int size = historyEnd - historySt;
if (size < 0) size += HISTSIZE;
strcpy(history[historyEnd], cmd);
// exchange \n to 0
history[historyEnd][strlen(cmd) - 1] = 0;
historyEnd++;
historyPos = historyEnd;
if(historyEnd == HISTSIZE) historyEnd = 0;
if (size == HISTSIZE - 1) {
historySt++;
if(historySt == HISTSIZE) historySt = 0;
}
}
int
main(void)
{
static char buf[100];
int fd;
// Ensure that three file descriptors are open.
while((fd = open("console", O_RDWR)) >= 0){
if(fd >= 3){
close(fd);
break;
}
}
// Read and run input commands.
while(getcmd(buf, sizeof(buf)) >= 0){
if (strlen(buf) > 1) add_history(buf);
if(buf[0] == 'c' && buf[1] == 'd' && buf[2] == ' '){
// Chdir must be called by the parent, not the child.
buf[strlen(buf)-1] = 0; // chop \n
if(chdir(buf+3) < 0)
fprintf(2, "cannot cd %s\n", buf+3);
continue;
}
else if(!strcmp(buf, "wait\n")){
// wait must be called by the parent, not the child.
int status, pid;
while((pid = wait(&status)) != -1)
printf("%d done, status：%d\n", pid, status);
continue;
}
else if(!strcmp(buf, "history\n")){
for(int i = historySt, j = 1; i != historyEnd; j++)
{
printf("%d %s\n", j, history[i]);
i++;
if (i == HISTSIZE) i = 0;
}
continue;
}
struct cmd *curcmd = parsecmd(buf);
if(fork1() == 0)
runcmd(curcmd);
else if (curcmd->type != BACK)
wait(0);
}
// this line to help xarg not timeout after supporting isatty
write(2, "$ \n", 3);
exit(0);
}
最后kernel/uart.c,把函数传进去，这样是为了循环放在内部，可以读到多个字符，判断状态机。
1697899941042.png
网友评论