操作系统笔记1——概述

本文最后更新于 2022年02月23日 已经是 463天前了，文章可能具有时效性，若有错误或已失效，请在下方留言。

课程 http://jyywiki.cn/OS/2022/notes/1

什么是操作系统？

操作系统（operating system，简称OS）是管理计算机硬件与软件资源的计算机程序。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入设备与输出设备、操作网络与管理文件系统等基本事务。操作系统也提供一个让用户与系统交互的操作界面。操作系统是计算机系统中最基本的系统软件。

stateDiagram direction LR [*]–>目的 [*]–>发展 [*]–>特征目的–>计算机系统资源的管理者目的–>用户与计算机系统之间的接口目的–>扩充机器发展–>批处理操作系统批处理操作系统–>分时操作系统分时操作系统–>实时操作系统实时操作系统–>网络和分布式操作系统 state 最基本的特征{ 特征–>并发特征–>共享 } 特征–>虚拟特征–>异步

stateDiagram direction LR main.c[文本]–>main.i[文本]:预处理器 main.i[文本]–>main.s[文本]:编译器 main.s[文本]–>main.o[二进制]:汇编器 main.o[二进制]–>main[二进制]:链接器

什么是程序？

计算机程序(Computer Program)，程序也是状态机。计算机程序是一组计算机能识别和执行的指令,运行于电子计算机上,满足人们某种需求的信息化工具。它以某些程序设计语言编写,运行于某种目标结构体系上。

C程序的状态机模型

状态 = 堆 + 栈

初始状态 = main 的第一条语句

Hanoi(汉诺)塔

Hanoi(汉诺)塔，说白了就是一堆大小不一的盘子堆叠在一起，大盘子在下方，小盘子在上方，我们先称之为A柱，我们要讲盘子移动到另一个柱子中，这个柱子叫C柱，每次只能移动一个盘子，此外我们还可以利用一个空柱子B柱。

stateDiagram-v2 note left of 过程 1.大盘子在下方，小盘子在上方 2.每次只能移动一个盘子 end note state 过程{ direction RL A–>C A–>B B–>C C–>A B–>A C–>B state A { direction BT __盘子___–>__盘子__ __盘子__–>_盘子__ } state B { direction LR B空柱 } state C { direction LR C空柱 } }

递归

void hanoi(int n, char from, char to, char via) {
  if (n == 1) printf("%c -> %c\n", from, to);
  else {
    hanoi(n - 1, from, via, to);
    hanoi(1,     from, to,  via);
    hanoi(n - 1, via,  to,  from);
  }
  return;
}

➜  test ./main
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

非递归

如果不太懂先看下面的函数调用相关的

// hanoi-nr.c
typedef struct {
  int pc, n;
  char from, to, via;
} Frame;

#define call(...) ({ *(++top) = (Frame) { .pc = 0, __VA_ARGS__ }; })
#define ret()     ({ top--; })
#define goto(loc) ({ f->pc = (loc) - 1; })

void hanoi(int n, char from, char to, char via) {
  Frame stk[64], *top = stk - 1;
  call(n, from, to, via);
  for (Frame *f; (f = top) >= stk; f->pc++) {
    switch (f->pc) {
      case 0: if (f->n == 1) { printf("%c -> %c\n", f->from, f->to); goto(4); } break;
      case 1: call(f->n - 1, f->from, f->via, f->to);   break;
      case 2: call(       1, f->from, f->to,  f->via);  break;
      case 3: call(f->n - 1, f->via,  f->to,  f->from); break;
      case 4: ret();                                    break;
      default: assert(0);
    }
  }
}

erDiagram Frame { int pc int n char from char to char via }

flowchart TB A[开始接受函数参数 int n, char from, char to, char via] –> B[“定义 Frame stk[64]”] B–>C[“top指针指向stk数组前一个地址”] C–>D[“向（top+1）指针指向的数组成员写入Frame{pc=0, n, from, to, via} top自增1”] D–>E{“(f = top) >= stk”} E–>|满足|F{“f->pc==0”} E–>|不满足|Z[“结束”] F–>|满足|G{“f->n==1”} G–>|满足|H[“打印f->from 移动到 f->to”] H–>X[f->pc++] G–>|不满足|P F–>|不满足|J{f->pc==1} J–>|满足|K[” 向（top+1）指针指向的数组成员写入Frame{pc = 0, f->n – 1, f->from, f->via, f->to } top自增1″] K–>X J–>|不满足|L{f->pc==2} L–>|满足|Q[” 向（top+1）指针指向的数组成员写入Frame{pc = 0, 1, f->from, f->to, f->via } top自增1″] Q–>X L–>|不满足|M{f->pc==3} M–>|满足|O[” 向（top+1）指针指向的数组成员写入Frame{pc = 0, f->n – 1, f->via, f->to, f->from } top自增1″] O–>X M–>|不满足|N{f->pc==4} N–>|满足|P[“top–“] P–>X X–>E

➜  test ./main
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

gdb调试

➜  test gcc -g hanoi-nr.c -o hanoi-nr

➜  test gdb hanoi-nr

(gdb) layout src

(gdb) start

栈帧(Stack Frame)

每一次函数的调用,都会在调用栈(call stack)上维护一个独立的栈帧(stack frame).每个独立的栈帧一般包括:

函数的返回地址和参数
临时变量: 包括函数的非静态局部变量以及编译器自动生成的其他临时变量
函数调用的上下文

栈是从高地址向低地址延伸,一个函数的栈帧用ebp 和 esp 这两个寄存器来划定范围.ebp 指向当前的栈帧的底部,esp 始终指向栈帧的顶部;

ebp 寄存器又被称为帧指针(Frame Pointer);
esp 寄存器又被称为栈指针(Stack Pointer);

函数调用(PUSH Frame)

参数入栈

将参数按照调用约定(基本上是从右向左)依次压入系统栈中; 汇编代码AT&T 格式Linux 汇编语法格式有很大区别这里展示Intel格式

   0x0000555555555149 <+0>:     endbr64
   0x000055555555514d <+4>:     push   rbp
   0x000055555555514e <+5>:     mov    rbp,rsp
   0x0000555555555151 <+8>:     mov    edx,0x3
   0x0000555555555156 <+13>:    mov    esi,0x2
   0x000055555555515b <+18>:    mov    edi,0x1
   0x0000555555555160 <+23>:    call   0x555555555129 <test>
   0x0000555555555165 <+28>:    mov    eax,0x0
   0x000055555555516a <+33>:    pop    rbp
   0x000055555555516b <+34>:    ret

│   4           int main() {                                                                                           │
│  >5                   test(1,2,3);                                                                                   │
│   6                   return 0;                                                                                      │
│   7           }

返回地址入栈

当前代码区调用指令的下一条指令地址压入栈中，供函数返回时继续执行;

代码跳转

处理器将代码区跳转到被调用函数的入口处;

栈帧调整

将调用者的ebp压栈处理，保存指向栈底的ebp的地址（方便函数返回之后的现场恢复），此时esp指向新的栈顶位置；push ebp
将当前栈帧切换到新栈帧(将esp值装入ebp，更新栈帧底部) mov ebp,esp
给新栈帧分配空间 sub esp, XXX

0x555555555129 <test>           endbr64                                                                               0x55555555512d <test+4>         push   rbp                                                                            0x55555555512e <test+5>         mov    rbp,rsp                                                                        0x555555555131 <test+8>         mov    DWORD PTR [rbp-0x4],edi                                                       0x555555555134 <test+11>        mov    DWORD PTR [rbp-0x8],esi                                                        0x555555555137 <test+14>        mov    DWORD PTR [rbp-0xc],edx                                                     
0x55555555513a <test+17>        mov    edx,DWORD PTR [rbp-0x4]                                                     
0x55555555513d <test+20>        mov    eax,DWORD PTR [rbp-0x8]                                                     
0x555555555140 <test+23>        add    edx,eax                                                                     
0x555555555142 <test+25>        mov    eax,DWORD PTR [rbp-0xc]                                                     
0x555555555145 <test+28>        add    eax,edx                                                                     
0x555555555147 <test+30>        pop    rbp                                                                         
0x555555555148 <test+31>        ret