ics内容整理

ICS

十六进制快速查表

十六进制	十进制	二进制
0	0	0000
1	1	0001
2	2	0010
3	3	0011
4	4	0100
5	5	0101
6	6	0110
7	7	0111
8	8	1000
9	9	1001
A	10	1010
B	11	1011
C	12	1100
D	13	1101
E	14	1110
F	15	1111

printf()函数用法

• %f 浮点数
• %p 指针地址

各类型比特数

Shift Operations

• logical shift : Fill with 0’s on left

• Arithmetic shift : Replicate most significant bit on right

• Be careful about1<<2 + 3<<4 means 1<<(2 + 3)<<4

Big/Small Endian（for 0x1234567）

• big endian：01 23 45 67
• small endian: 67 45 23 01

String

• strlen（）不包含结尾空字符

Numeric Range

• Unsigned Values

$$U_{min}=0\newline U_{max}=2^{w}-1$$

• Two’s Complement Values $$T_{min}=-2^{w-1}\newline T_{max}=2^{w-1}-1$$

Casting

• Casting among Signed and Unsigned

  • 关键点是二进制表示不会变
  • If mix unsigned and signed in single expression,signed values implicitly cast to unsigned.

• From long to short

  • unsigned直接在左边+0
  • signed在左边+符号位
• 从short转化为unsigned
  • 先改变大小
  • 再完成有符号数到无符号数的转换

Unsigned Addition

• 加法公式

$$UAdd_w(u, v) = \begin{cases} u + v & \text{if } u + v < 2^w \\ u + v - 2^w & \text{if } u + v \geq 2^w \end{cases}$$

• 检验是否溢出

  /* Determine whether arguments can be added without overflow */
  int uadd_ok(unsigned x, unsigned y){
  	return (X+Y) < X
  }

Signed Addition

• 加法公式

  $$T_{\text{add}}(u, v) = \begin{cases} u + v - 2^w, & \text{if } T_{\text{Max}_w} < u + v \text{ (PosOver)} \\ u + v, & \text{if } T_{\text{Min}_w} \leq u + v \leq T_{\text{Max}_w} \\ u + v + 2^w, & \text{if } u + v < T_{\text{Min}_w} \text{ (NegOver)} \end{cases}$$

• 检验是否溢出

  /* Determine whether arguments can be added without overflow */
  int tadd_ok(signed u, signed v){
  	return (u<0 == v<0) && (u<0 != s<0);
  }

Multiplication

• Unsigned

  $x \ast^u_w y = (x \cdot y) \mod 2^w$

• Signed

  $x \ast^t_w y = U2T_w((x \cdot y) \mod 2^w)$

Addressing Mode

%rip %rsp

• rip是程序计数器，指向下一条指令
• rsp指向堆栈的栈顶

Move data

• mov: 这是一个通用的移动指令，可以根据上下文移动不同大小的数据。
• movb: 这个指令用于移动一个字节（8位）的数据。
• movw: 用于移动一个字（16位）的数据。
• movl: 移动一个双字（32位）的数据。
• movq: 移动一个四字（64位）的数据。这里的注释说明立即数（即直接指定的数值）只能被表示为32位有符号的整数，并且会被符号扩展到目标寄存器的大小。
• movabsq: 这是一个特殊的指令，用于移动一个绝对的四字（64位）数据。在某些架构中，这允许直接指定64位的地址或立即数。

• 大多数这些指令只更新特定的寄存器字节，除了movl。movl在移动32位数据时会将目标寄存器的高4字节置零。

Move with Zero Extension

• Move data instruction
  • movz (move with zero extension)
  • movzbw (move zero-extension byte to word)
  • movzbl (move zero-extension byte to double word)
  • movzbq (move zero-extension byte to quad word)
  • movzwl (move zero-extension word to double word)
  • movzwq (move zero-extension word to quad word)
  • no movzlq, it is implemented by movl

Move with Sign Extension

• Move data instruction
  • movs (move with sign extension)
  • movsbw (move sign-extension byte to word)
  • movsbl (move sign-extension byte to double word)
  • movsbq (move sign-extension byte to quad word)
  • movswl (move sign-extension word to double word)
  • movswq (move sign-extension word to quad word)
  • movslq (move sign-extension double word to quad word)

Data Manipulation

Switch语句

• 案例数量多
• 案例值不稀疏

Invoke callee: call

两个作用：

• 将下一个地址（return address）压栈
• 跳转到函数的起始地址

Return to caller: ret

两个作用：

• 退栈，从栈中取出返回地址
• 跳转到返回地址

Passing Data: Arguments & Return Value

• 如果参数多于6个，那么从第n个到第7个依次压栈（在retaddress前）

Registers: usage convention

caller-save registers

• %rax, %rdi, %rsi, %rdx, %rcx, %r8, %r9, %r10, %r11
• Callee can use these registers freely

Callee-save registers

• %rbx, %rbp, %r12-15
• Saved by callee

Local variable: stack

Why are local variables not stored in registers ?

• No enough registers
• Array and structures (e.g., a[2])
• Need address (e.g., &a)

function

1. Save caller-save registers (%eax, %edx, %ecx)
2. Push rest actual arguments from right to left onto stack
3. Pass first six actual arguments
4. Call instructionSave return addressTransfer control to callee
5. Save callee-save registers (%rbx, %rbp, . . .)
6. Allocate space for local variables

n-3. save return value in %rax

n-2. de-allocate local variable

n-1. Restore callee-save registers

n. Ret instruction

​ pop return address

​ Transfer control to caller

Pointer Arithmetic

• &E[i]-E的取值为long类型，value为i

Nested Array

对二维数组D [R] [C]

D[I] [J]的地址为$x_{D} + L ( C i + j )$

C operators 优先级

Classes of Exceptions

Synchronous exceptions

Traps

• Intentional（故意的）
• returns control to “next” instruction
• Examples: syscall, breakpoint traps

Faults

• Unintentional but possibly recoverable
• either re-executes faulting (“current”) instruction or aborts.
• Examples: page faults (recoverable), protection faults (unrecoverable)

Aborts

• Unintentional and unrecoverable
• aborts current program
• Examples: parity error（奇偶校验错误）, machine check

Exceptions in x86-64 systems

Exception Number	Description	Exception class
0	Divide error	Fault
13	General protection fault	Fault
14	Page fault	Fault
18	Machine check	Abort
32~255	OS defined exception	Interrupt or trap

Asynchronous exceptions (interrupts)

由处理器外部事件引起

通过设置处理器的中断引脚指示

处理程序返回到“下一个”指令。

Examples:

• I/O interrupts

  • hitting ctl-c at the keyboard
  • arrival of a packet from a network
  • arrival of a data sector from a disk

• Hard reset interrupt

  • hitting the reset button

• Soft reset interrupt

  • hitting ctl-alt-delete on a PC

总结

Context Switches

• Context contains
  • the program’s code and data stored in memory
  • Value of PC, register file, status registers
  • user’s stack, kernel’s stack
  • environment variables
  • Kernel data structures
    • Process table
    • page table
    • file table

gpt about

1. 进程的上下文：内核为每个进程维护一个上下文。这个上下文是内核需要恢复被中断进程的状态。它包含了程序在内存中的代码和数据、PC寄存器的值、状态寄存器、用户栈和内核栈、环境变量以及内核数据结构（如进程表、页表、文件表）。
2. 上下文切换的必要性：在一台计算机系统中同时存在许多进程。上下文切换是操作系统执行的一种多任务（时间分片）机制，它是一种高级形式的异常控制流，建立在更低级别的机制之上。
3. 上下文切换的发生时机：当内核代表用户执行系统调用（如read、sleep等）时，这些调用可能会导致调用的进程被阻塞。即使系统调用不会导致阻塞，内核也可以决定执行上下文切换而不是将控制权返回给调用进程。上下文切换也可能由中断引起，如定时器中断。
4. 上下文切换的过程：调度程序（内核的一部分）负责决定是否抢占当前进程。在执行过程中，它会保存当前进程的上下文，恢复之前被抢占进程的上下文，并将控制权传递给这个新恢复的进程。
5. 逻辑控制流：每个进程都有自己的逻辑控制流，不会影响其他进程的状态。并发进程是指在时间上重叠的流程。尽管在时间上物理分离，我们可以将并发进程视为并行运行。

Concurrent processes

• 如果两个进程有交叉，那么就是concurrent
• 如果没有交叉，那么就是sequential

Fork Function

pid_t fork(void);

Returns: 0 to child, PID of child to parent, -1 on error

分离但重复的地址空间：当父进程执行 fork 函数时，它会创建一个子进程。在这个过程中，子进程获得了与父进程几乎完全相同的地址空间的副本。这意味着在 fork 调用之后，父进程和子进程拥有相同的内存布局，但这些内存是分开的，互不影响。父进程和子进程的地址空间是分离的，修改其中一个进程中的数据不会影响另一个进程。

fork 返回时的局部变量状态：以一个具体的例子来说，假设有一个局部变量 x，其初始值为1。当 fork 函数被调用时，在父进程和子进程中，x 的值都是1。这是因为子进程复制了父进程的整个地址空间，包括所有变量的当前状态。但在 fork 之后，父进程和子进程中的 x 是完全独立的，它们位于各自独立的地址空间内。在父进程或子进程中对 x 进行修改，不会影响另一个进程中 x 的值。

waitpid

pid_t waitpid(pid_t pid, int *status, int options);

pid

• pid > 0：等待的子进程的id就是pid
• pid = -1：等待任意一个子进程

options

• options = 0

  • waitpid挂起调用进程的执行，直到其等待集中的子进程终止为止

  • 如果等待集中的进程在调用时已经终止，那么waitpid将立即返回waitpid返回导致waitpid的终止子级的PID

  • 终止的子项将从系统中删除

• options = WNOHANG 如果等待集中的子进程尚未终止，则立即返回（返回值为0）

• options = WUNTRACED 暂停执行调用进程，直到进程终止或停止导致返回的子进程

return

如果没有子进程：

• returns –1
• sets errno to ECHILD

如果被信号打断：

• returns –1
• sets errno to EINTR

unsigned int sleep(unsigned int secs);

• 如果 sleep 函数成功地睡眠了整个指定时间，则返回 0。
• 如果 sleep 函数因为接收到信号而提前被唤醒，则返回剩余未睡眠的秒数。

int pause(void);

• 总是返回-1
• 使调用进程挂起，直到接收到一个信号。

int execve(const char filename, const char argv[], const char *envp[]);

• 如果 execve 执行成功，它不会返回，因为调用进程的映像已被新程序替换。
• 如果有错误发生，比如指定的文件不存在或没有执行权限等，它将返回 -1 并设置相应的 errno。
• filename：要执行的程序的路径。
• argv：传递给新程序的参数列表，是一个字符串数组。argv[0] 通常是程序的名称，数组以 NULL 结尾。
• envp：提供给新程序的环境变量，也是一个以 NULL 结尾的字符串数组。

Signal

pid_t getpgrp(void);

• getpgrp 返回调用进程的进程组ID。在 UNIX 系统中，进程组ID通常是一个非负整数。
• 如果有错误发生，它将返回 -1，并设置相应的 errno。

pid_t setpgid(pid_t pid, pid_t pgid);

参数

• pid：指定要更改其进程组的进程的进程 ID。如果 pid 为 0，则表示当前进程。
• pgid：新的进程组 ID。如果 pgid 为 0，则由 pid 指定的进程 ID 会被用作新的进程组 ID。

返回值

• 成功时，setpgid 返回 0。
• 如果出现错误（例如，指定的 PID 不存在，或者违反了进程组设置的规则），则返回 -1，并设置相应的 errno。

int kill(pid_t pid, int sig);

参数

• pid：指定目标进程或进程组的进程 ID。
  • 如果 pid > 0，信号被发送给指定的进程。
  • 如果 pid = 0，信号被发送给与发送进程相同进程组的所有进程。
  • 如果 pid < -1，信号被发送给 pid 的绝对值所指定的进程组。
  • 如果 pid = -1，信号被发送给发送进程有权限发送信号的所有进程。
• sig：要发送的信号。可以是如 SIGKILL、SIGTERM、SIGSTOP 等各种信号。

unsigned int alarm(unsigned int secs);

调用 alarm 函数会设置一个定时器，当定时器计时到 secs 指定的秒数时，会向进程发送 SIGALRM 信号。

• 参数：如果 secs 为 0，则取消任何之前设置的定时器
• 返回值：alarm 函数返回之前设置的定时器的剩余时间（秒）。如果之前没有设置定时器，则返回 0。

Receive signal

• SIGSTOP和SIGKILL不能被重定义

handler_t signal(int signum, handler_t handler)

参数

handler 可以是用户定义的函数，或者是两个特殊值之一：

• SIG_IGN：忽略指定的信号。
• SIG_DFL：为指定的信号恢复默认行为。

返回值

返回之前设置的信号处理器的地址。如果出现错误，则返回 SIG_ERR。

IO

int open(char *filename, int flags, mode_t mode);

参数

• filename: 指向要打开或创建的文件的路径的指针。
• flags: 指定文件的打开模式，例如只读 (O_RDONLY)、只写 (O_WRONLY) 或者读写 (O_RDWR)。此外，还有一些控制标志，如 O_CREAT（如果文件不存在，则创建它）、O_EXCL（与 O_CREAT 一起使用时，如果文件已存在，则会导致打开文件失败）等。

ssize_t read(int fd, void *buf, size_t count);

参数

• fd: 文件描述符，它是由之前的 open 调用返回的，用于指定从哪个文件读取。
• buf: 指向一个缓冲区的指针，这个缓冲区用于存放从文件中读取的数据。
• count: 指定要读取的字节数。

返回值

• 成功时，返回读取的字节数。这个值可能小于请求的 count，这通常发生在文件末尾或者在遇到错误时。
• 如果到达文件末尾，则返回 0。
• 失败时，返回 -1 并设置 errno 来指示错误原因，例如 EBADF（无效的文件描述符）、EIO（I/O 错误）等。

ssize_t write(int fd, const void *buf, size_t count);

参数

• fd: 文件描述符，它是由之前的 open 调用返回的，用于指定向哪个文件写入。
• buf: 指向要写入数据的缓冲区的指针。
• count: 指定要写入的字节数。

返回值

• 成功时，返回写入的字节数。这个值可能小于请求的 count，尤其是在某些类型的文件（如非阻塞文件）或者在磁盘空间不足时。
• 失败时，返回 -1 并设置 errno 来指示错误原因，例如 EBADF（无效的文件描述符）、EIO（I/O 错误）等。

int dup2(int oldfd, int newfd);

将newfd指向oldfd所指向的地方

参数:

• oldfd: 已打开的文件描述符，它指向一个已经打开的文件或其他文件类型的资源（如管道、套接字等）。
• newfd: 指定要复制到的新文件描述符的值。如果 newfd 已经打开，则 dup2 会先关闭 newfd，然后再进行复制操作。

返回值:

• 成功时，返回新的文件描述符（即 newfd 的值）。
• 失败时，返回 -1 并设置 errno 来指示错误原因，例如 EBADF（无效的文件描述符）、EMFILE（已达到进程可打开的最大文件描述符数）等。

int dup(int oldfd)

参数:

• oldfd: 要复制的文件描述符，它应该是一个打开的文件描述符。

返回值:

• 成功时，返回新的文件描述符。这个新描述符会有同样的文件表项但是有自己独立的文件描述符表项。
• 失败时，返回 -1 并设置 errno 来指示错误原因，例如 EBADF（oldfd 不是有效的文件描述符）、EMFILE（打开文件描述符的数量已达到进程的限制）等。

注意

• dup 生成的新文件描述符总是取用进程可用的最小数值。
• 新的文件描述符与原始文件描述符共享相同的文件位置和文件状态标志；即，如果改变其中一个文件描述符的文件位置，则另一个也会改变。

int fileno(FILE *stream);

• 0: 标准输入（stdin）。
• 1: 标准输出（stdout）。
• 2: 标准错误（stderr）。

Nonlocal Jumps

int setjmp(jmp_buf env);

参数:

• env: 类型为 jmp_buf 的数组，用于存储当前环境（包括程序计数器、堆栈指针等）以供 longjmp 使用。

返回值:

• 当直接从 setjmp 返回时，它返回 0。
• 当从 longjmp 调用返回时，它返回一个非零值，该值由 longjmp 的第二个参数指定。

void longjmp(jmp_buf env, int retval);

参数:

• env: 通过 setjmp 函数保存的环境。env 包含了调用 setjmp 时的栈帧、程序计数器和其他必要的处理器状态，使得程序可以恢复到 setjmp 被调用时的状态。
• retval: 这个值将被 setjmp 返回。重要的是，这个值不能是零，因为 setjmp 在正常执行时返回零。

Scheduling

The turnaround time

turnaround time 就是结束时间-到达时间

Response time

从作业到达系统到第一次安排作业的时间

First In, First Out (FIFO)

Shortest Job First (SJF)

Shortest Time-to-Completion First (STCF)

每当新作业进入系统时，STCF调度程序会确定剩余作业（包括新作业）中剩余时间最少的一个，并对该作业进行调度

Round Rabin

在时间段内运行作业

切换到运行队列中的下一个作业

重复此操作，直到作业完成

MLFQ

许多不同的队列

每个都分配了不同的优先级

准备运行的作业位于单个队列上

规则1：如果优先级（A）>优先级（B），则A运行（B不运行）

规则2：如果优先级（A）=优先级（B），则A&B在RR中运行

规则3：当作业进入系统时，它被置于最高优先级

规则4a：如果作业在运行时占用了整个时间片，则其优先级会降低

规则4b：如果一个作业在时间片结束前放弃了CPU，它将保持在相同的优先级

规则4（细化）：一旦一个作业在给定级别上用完了它的时间分配（无论它放弃了多少次CPU），它的优先级就会降低

规则5：经过一段时间S后，将系统中的所有作业移动到最上面的队列

Floating Point

Numeric form

$$V=(-1)^S \times M \times 2^E$$

• 符号位s决定数字是负数还是正数
• 显著M通常是范围[1.0,2.0）内的一个分数值。
• 指数E按二次幂对值进行加权

Normalize Values

此时$exp \ne 000 \cdots 0$ 并且$exp \ne 111 \cdots 1$

E = Exp - Bias

• Exp：用Exp表示的无符号值

• Bias：偏移值

  单精度：127（Exp:1…254，E:-126…127）

  双精度：1023（Exp:1…2046，E:-1022…1023）

  一般情况下：$Bias=2^{m-1}-1$，其中m是指数位数

$m=1.xxxx \cdots x_2$

• $xxx \cdots x$：是frac
• 取最小值时 是000…0（M=1.0)
• 取最大值时 是111…1 (M趋近于2)

Denormalized Values

exp小

$exp = 000 \cdots 0$

E=1-Bias

$m=0.xxxx \cdots x_2$

• $xxx \cdots x$：是frac

exp大

$exp = 111 \cdots 1$

$exp = 111…1, frac = 000…0$时表示无穷大

$exp = 111…1, frac \ne 000…0$时表示Not-a-Number

Rounding Binary Number

FP Multiplication

Sign s : s1 ^ s2

Significand M : M1 * M2

Exponent E : E1 + E2

如果M≥2，向右移动M，增加E

舍入M以适应精度，必要时增加E

如果E超出范围，则溢出

FP Addition