這里會(huì)記錄學(xué)習(xí)MIT6.1810的筆記：
我主要會(huì)記錄一些自己對(duì)每一節(jié)課的理解创泄，方便日后復(fù)習(xí)。
同時(shí)也會(huì)要求自己把每個(gè)課程作業(yè)按照最高要求去完成，會(huì)記錄一些LAB里有難度的地方抑淫。
所有代碼會(huì)維護(hù)在
https://github.com/yixuaz/6.1810-2023
SCHEDULE使用的是如下：
https://pdos.csail.mit.edu/6.828/2023/schedule.html
根據(jù)里面的教程，我在WINDOWS下配置了WSL2來跑LINUX姥闪。
代碼會(huì)維護(hù)在
Lec 1
什么是操作系統(tǒng)始苇？
硬件：CPU、RAM筐喳、硬盤催式、網(wǎng)絡(luò)等
用戶應(yīng)用：如shell（sh）、編譯器（cc）避归、數(shù)據(jù)庫（DB）等
內(nèi)核服務(wù)：如文件系統(tǒng)（FS）荣月、進(jìn)程、內(nèi)存梳毙、網(wǎng)絡(luò)等
系統(tǒng)調(diào)用
kernel
Kernel是計(jì)算機(jī)資源的守護(hù)者哺窄。當(dāng)你打開計(jì)算機(jī)時(shí)，Kernel總是第一個(gè)被啟動(dòng)账锹。Kernel程序只有一個(gè)萌业，它維護(hù)數(shù)據(jù)來管理每一個(gè)用戶空間進(jìn)程。Kernel同時(shí)還維護(hù)了大量的數(shù)據(jù)結(jié)構(gòu)來幫助它管理各種各樣的硬件資源奸柬，以供用戶空間的程序使用生年。Kernel同時(shí)還有大量?jī)?nèi)置的服務(wù)，例如廓奕，Kernel通常會(huì)有文件系統(tǒng)實(shí)現(xiàn)類似文件名抱婉，文件內(nèi)容，目錄的東西桌粉，并理解如何將文件存儲(chǔ)在磁盤中授段。所以用戶空間的程序會(huì)與Kernel中的文件系統(tǒng)交互，文件系統(tǒng)再與磁盤交互番甩。
操作系統(tǒng)的目的是什么侵贵？
- 在多個(gè)應(yīng)用之間復(fù)用硬件
- 隔離應(yīng)用程序, 保證安全，彼此錯(cuò)誤不會(huì)相互影響
- 允許合作的應(yīng)用程序之間共享資源
- 為了可移植性而抽象硬件
- 提供有用的服務(wù)
高效vs易用缘薛。
高效性需要在low-level接近硬件進(jìn)行操作窍育，而易用性需要提供high-level的可移植接口卡睦。因此，實(shí)現(xiàn)既簡(jiǎn)單可移植又高效的接口是個(gè)挑戰(zhàn)漱抓。
強(qiáng)大vs簡(jiǎn)單表锻。
我們也想要提供強(qiáng)大的操作系統(tǒng)服務(wù)來輔助應(yīng)用程序運(yùn)行，但又期望其擁有簡(jiǎn)單的接口以便于程序員理解和使用乞娄。目標(biāo)是提供既簡(jiǎn)單又功能強(qiáng)大的接口瞬逊。
靈活性vs安全性
內(nèi)核具備靈活的接口。我們希望給程序員完全的自由仪或，但是實(shí)際上又不能是真正的完全自由确镊，因?yàn)槲覀儾幌胍绦騿T能直接訪問到硬件，干擾到其他的應(yīng)用程序范删，或者干擾操作系統(tǒng)的行為蕾域。
Lab 1
1. Write an uptime program that prints the uptime in terms of ticks using the uptime system call.
這個(gè)問題只要調(diào)用一下uptime這個(gè)系統(tǒng)調(diào)用即可。
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.
學(xué)習(xí)find里支持REGEX代碼到旦，那個(gè)正則表達(dá)式的理解旨巷，是這道題最有收獲；我會(huì)簡(jiǎn)單講解一下添忘；
#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;
}
當(dāng)然可以采呐。這段代碼主要通過兩個(gè)函數(shù) matchhere 和 matchstar 來實(shí)現(xiàn)對(duì) . 和 * 的支持。
對(duì)于 . 的支持
在 matchhere 函數(shù)中有這樣一段代碼：
if(*text!='\0' && (re[0]=='.' || re[0]==*text))
return matchhere(re+1, text+1);
這里搁骑，re[0]=='.' 是檢查正則表達(dá)式當(dāng)前字符是否為 .斧吐。如果是，或者正則表達(dá)式的當(dāng)前字符與文本的當(dāng)前字符匹配靶病，那么函數(shù)將繼續(xù)比較正則表達(dá)式的下一個(gè)字符和文本的下一個(gè)字符会通。
對(duì)于 * 的支持
* 的匹配比較特殊。在正則表達(dá)式中娄周，* 意味著匹配前面的字符零次或多次涕侈。例如，a* 可以匹配 "", "a", "aa", "aaa" 等煤辨。
在 matchhere 函數(shù)中有這樣一段代碼：
if(re[1] == '*')
return matchstar(re[0], re+2, text);
如果 re[1] 是 *裳涛，則調(diào)用 matchstar 函數(shù)。
在matchstar 函數(shù)中：
do{
if(matchhere(re, text))
return 1;
}while(*text!='\0' && (*text++==c || c=='.'));
這里有一個(gè)循環(huán)众辨，嘗試著匹配 * 前面的字符零次端三、一次、兩次等鹃彻，直到不能匹配為止郊闯。對(duì)于每一種嘗試，都調(diào)用 matchhere 函數(shù)來檢查剩余的正則表達(dá)式是否與剩余的文本匹配。
注意條件 (*text++==c || c=='.')团赁，這里的 c 是 * 前面的字符育拨。這意味著，只有當(dāng)文本的當(dāng)前字符與 c 匹配或 c 是 . 時(shí)欢摄，循環(huán)才會(huì)繼續(xù)熬丧。
3. modify the shell to not print a $ when processing shell commands from a file
這道題實(shí)際上就是要我們實(shí)現(xiàn)一個(gè)isatty函數(shù)；
isatty 是一個(gè)在 POSIX-like 系統(tǒng)中常見的函數(shù)怀挠，它的功能是判斷給定的文件描述符是否與一個(gè)終端關(guān)聯(lián)析蝴。
這個(gè)函數(shù)返回一個(gè)布爾值，如果 fd（文件描述符）與終端關(guān)聯(lián)绿淋，則返回 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);
}
...
}
測(cè)試方法：
之前那些$都消失了
4. modify the shell to support wait
在 shell 腳本中躬它，wait 是一個(gè)內(nèi)置命令腾啥，用于使腳本暫停執(zhí)行并等待一個(gè)或多個(gè)后臺(tái)進(jìn)程完成執(zhí)行东涡。
作用：
同步化：當(dāng)在腳本中啟動(dòng)一個(gè)或多個(gè)后臺(tái)進(jìn)程時(shí)冯吓，你可能希望在繼續(xù)執(zhí)行其他命令之前等待這些后臺(tái)進(jìn)程完成。這樣疮跑，你可以確保某些任務(wù)在其他任務(wù)開始之前已經(jīng)完成组贺。
資源管理：在某些情況下，你可能不希望在之前的后臺(tái)進(jìn)程完成之前啟動(dòng)新的進(jìn)程祖娘。這可以避免過多的并發(fā)進(jìn)程占用太多資源失尖。
因?yàn)檫@個(gè)命令直接和shell相關(guān)，需要讓shell進(jìn)程wait后臺(tái)子進(jìn)程執(zhí)行完成渐苏，所以和cd是一個(gè)level掀潮；
具體實(shí)現(xiàn)方法是，對(duì)于BACKGROUND的命令琼富，F(xiàn)ORK之后仪吧，子進(jìn)程去執(zhí)行實(shí)際命令，父進(jìn)程進(jìn)行wait鞠眉；（這里的父進(jìn)程薯鼠，其實(shí)是shell fork出來的子進(jìn)程）
然后在shell 進(jìn)程沒使用wait 命令時(shí)，我們可以判斷械蹋，這個(gè)cmd如果是個(gè)background的出皇，我們就啥也不做，別的就wait下
然后在shell 的main函數(shù)里哗戈，加上
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);
}
測(cè)試方法：
5. modify the shell to support lists of commands, separated by ";"
本身就支持了郊艘；
6. modify the shell to support sub-shells by implementing "(" and ")"
本身就支持了；
7.modify the shell to support tab completion
這個(gè)題雖然標(biāo)了easy, 但真的要實(shí)現(xiàn)到和linux shell 一樣的效果，還是要寫非常多的代碼纱注，和非常大的思考量步做；而且還需要稍微改下kernel;
要實(shí)現(xiàn)這個(gè)，xv6的代碼有這么幾個(gè)問題
- 我經(jīng)過研究奈附，發(fā)現(xiàn)在讀入命令時(shí)全度，是kernel的
console.c基于行,也就是說除非你打了回車，不然SHELL段是讀不到數(shù)據(jù)的斥滤。所以需要讓\t也要觸發(fā)緩沖區(qū)刷新将鸵。讓shell測(cè)可以讀到數(shù)據(jù) - shell測(cè)拿到數(shù)據(jù)后，判斷如果最后是
\t佑颇；那么就可以根據(jù)是否有空格顶掉，來判斷是命令補(bǔ)全，還是文件補(bǔ)全挑胸；并且判斷是否有多個(gè)選項(xiàng)痒筒；有多個(gè)選項(xiàng)，找到最長(zhǎng)公共前綴進(jìn)行補(bǔ)全茬贵；單個(gè)匹配簿透，就直接補(bǔ)全；沒有匹配解藻，就沒有任何效果老充； - 補(bǔ)全的時(shí)候發(fā)現(xiàn)，直接
write進(jìn)stdin 是不work的螟左；但是如果往stdout寫啡浊，這個(gè)字符是不可修改的。所以這邊也需要修改kernel胶背；具體做法是當(dāng)往stdout寫時(shí)巷嚣，console.c接受到寫數(shù)據(jù)，判斷第一個(gè)是否為\t, 如果是的話钳吟，需要維護(hù)kernel buf的3個(gè)指針廷粒，同時(shí)調(diào)用consputc去模擬用戶的輸入；
所以要實(shí)現(xiàn)這個(gè)功能砸抛，還是比較復(fù)雜评雌；我們來看下3個(gè)模塊的代碼時(shí)怎么改動(dòng)的；
在console.c中：
在console.c的consoleintr函數(shù)中：
在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);
}
...
}
測(cè)試方法
- 打l, 按tab, 看是否可以提示
- 補(bǔ)全的字符直焙，是否可以刪除
- 最長(zhǎng)公共字符串是否可以補(bǔ)全
-
文件名是否可以補(bǔ)全
1697899484120.png
8. modify the shell to keep a history of passed shell commands
如何保存history? 設(shè)計(jì)一個(gè)循環(huán)數(shù)組
如何支持上下的按鍵 跳回到上一條commands?
這個(gè)也要改動(dòng)一下kernel景东，因?yàn)樯希骆I是由3個(gè)字符表示奔誓；所以我們需要在console.c斤吐，維護(hù)一個(gè)狀態(tài)機(jī)搔涝；并且還要改動(dòng)，不能每次只傳一個(gè)字符過來
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 的改動(dòng)和措，
#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,把函數(shù)傳進(jìn)去庄呈，這樣是為了循環(huán)放在內(nèi)部，可以讀到多個(gè)字符派阱，判斷狀態(tài)機(jī)诬留。
