Darrin's Blog

NTNU CPS Linear System

Sun, 07 Jun 2026 00:00:00 +0800

linear system analysis

$x_1’ = 5x_1+3x_2$
$x_2’=-6x_1-4x_2$
can be solve in linear algebra $$\begin{bmatrix} x_1’ \\ x_2’ \end{bmatrix} = \begin{bmatrix} 5 & 3 \\ 6 & -4 \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$$ we can change $x_1’=ax_1$ to $x_1(t)=Ce^{at}$

and can we do some translation for $$\begin{cases} x_1’= a_1x_1+a_2x_2 \\ x_2’=a_3x_1+a_4x_2 \end{cases}$$ into $$\begin{cases} y_1’= a_ay_1 \\ y_2’=a_by_2 \end{cases}$$ than use $$\begin{cases} y_1(t) \\ y_2(t) \end{cases}$$ ? is it useful?

we can change it first change $$\begin{bmatrix} x_1’ \\ x_2’ \end{bmatrix} = \begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$$ into $$\begin{bmatrix} y_1’ \\ y_2’ \end{bmatrix} = \begin{bmatrix} a_a & 0 \\ 0 & a_b \end{bmatrix}\begin{bmatrix} y_1 \\ y_2 \end{bmatrix}$$

$x’ = Ax$ that A is operator, x is operand

Every vector x in $E$ (n dimension) can be uniquely express as $x=\sum_{i=1}^{n}t_ie_i$
$t_i$ are coordinate of x in the basis $e_i$

Each coordinate is a linear function $E\to R$, the coordinate system is an isomorphism(one-to-one and onto) $R\to E$

eigenvalues of $\begin{bmatrix} a & b \\ c & d \end{bmatrix}$ (A)
compute $Det(A-\lambda I)=0$ $$ Det\begin{bmatrix} a -\lambda & b \\ c & d -\lambda \end{bmatrix}=0 $$ $(a-\lambda)(d-\lambda) - (bc)=0$ $\Rightarrow$ $\lambda_1=\alpha, \lambda_2 =\beta$
$B = \begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix} = \begin{bmatrix} \alpha & 0 \\ 0 & \beta \end{bmatrix}$
$x’ = Ax; y = Qx; x = Q^{-1}y;x’=Q^{-1}y’$
$y’=Qx’=QAx=QAQ^{-1}y=By$
$\begin{bmatrix} y_1’ \\ y_2’ \end{bmatrix} = \begin{bmatrix} \alpha & 0 \\ 0 & \beta \end{bmatrix}\begin{bmatrix} y_1 \\ y_2 \end{bmatrix} = \begin{bmatrix} \alpha y_1 \\ \beta y_2 \end{bmatrix}$

if eigenvalue $\lambda$ of $A$ has i（maginary part）, the system $x=Ax$ can’t solve by $x(t)=Ce^{\lambda t}$

$e^{\begin{bmatrix} a & b \\ c & d \end{bmatrix}}$

$e^T = \sum_{n=0}^\infty \frac{T^k}{k!}$ = $\frac{1}{k_0}T^{k_0} + \frac{1}{k_1}T^{k_1} + \cdots$ where $k_i$ is the smallest integer such that $T^{k_i}$ is linearly dependent on $I, T, T^2, \cdots, T^{k_i-1}$

Proposition: Let $P$, $S$, $T$ denote generators on $R^n$.Then:

if $Q = PTP^{-1}$, then $e^Q = Pe^TP^{-1}$
if ST = TS, then $e^{S+T} = e^Se^T$
if $e^{-S} = (e^S)^{-1}$
if $n = 2$ and $T = \begin{bmatrix} a & -b \\ c & d \end{bmatrix}$, than $e^T = e^a\begin{bmatrix} \cos b & -\sin b \\ \sin b & \cos b \end{bmatrix}$

example $e^B$

$B = \begin{bmatrix} \lambda & 0 \\ 0 & \mu \end{bmatrix}$, find $e^B$
$\Rightarrow e^B = \sum_{k=0}^\infty \frac{B^n}{k!} = \sum_{k=0}^\infty \frac{1}{k!}\begin{bmatrix} \lambda & 0 \\ 0 & \mu \end{bmatrix} ^k = \begin{bmatrix} \sum_{k=0}^\infty \frac{\lambda^k}{k!} & 0 \\ 0 & \sum_{k=0}^\infty \frac{\mu^k}{k!} \end{bmatrix} = \begin{bmatrix} e^\lambda & 0 \\ 0 & e^\mu \end{bmatrix}$

example $e^T$

$T = \begin{bmatrix} a & 0 \\ b & a \end{bmatrix}$, find $e^T$
$\Rightarrow T= aI+B$ where $B = \begin{bmatrix} 0 & 0 \\ b & 0 \end{bmatrix}$
$e^T = e^{aI+B} = e^{aI}e^B (\because (aI)B = B(aI))$
$= e^a\sum_{k=0}^\infty \frac{1}{k!}\begin{bmatrix} 0 & 0 \\ b & 0 \end{bmatrix}^k$ $= e^a e^B$ ($e^{aI} \cdot e^B$ since B is a matrix, so $e^{aI} = \sum_{n=0}^\infty \frac{(aI)^k}{k!}$ = $\frac{1}{k_0}a^{k_0}I + \frac{1}{k_1}a^{k_1}I + \cdots$ , then since it will times $e^B$ then it can don’t need $I$)
$e^B = \sum_{k=0}^\infty \frac{1}{k!}\begin{bmatrix} 0 & 0 \\ b & 0 \end{bmatrix}^k = \frac{B^0}{0!} + \frac{B^1}{1!} = I + B$ $e^T = e^a(I+B) = e^a\begin{bmatrix} 1 & 0 \\ b & 1 \end{bmatrix}$

example $e^T$

$T = \begin{bmatrix} \lambda & 0 \\ 1 & \lambda \end{bmatrix}$, find $e^T$
$e^T = \begin{bmatrix} e^\lambda & 0 \\ e^\lambda & e^\lambda \end{bmatrix}$ (since $T = \lambda I + B$ where $B = \begin{bmatrix} 0 & 0 \\ 1 & 0 \end{bmatrix}$, then $e^T = e^{\lambda I}e^B = e^\lambda e^B$ and $e^B = I + B$)
$= e^\lambda\begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}$

EXAMPLE

if $x = R^n$ is an eignenvector of $T$ with eigenvalue $\alpha$, then $x$ is also an eigenvector of $e^T$ with eigenvalue $e^\alpha$\

Proof

From $Tx = \alpha x$
$\Rightarrow e^Tx=\sum_{k=0}^\infty \frac{T^k}{k!}x = \sum_{k=0}^\infty \frac{1}{k!}\alpha^kx$ $= \lim_{n\to \infty} \sum_{k=0}^n \frac{T^kx}{k!}$
$= \lim_{n\to \infty} \sum_{k=0}^n \frac{\alpha^kx}{k!}$ ($Tx = \alpha x$ so $T^kx = \alpha^kx$)
$= \sum_{k=0}^\infty \frac{\alpha^k}{k!}x = e^\alpha x$

Proposition $\frac{d}{dt}e^{tA} = Ae^{tA} = e^{tA}A$

Part I show that $\frac{d}{dt}e^{tA} = Ae^{tA}$

$\frac{d}{dt}e^{tA} = \lim_{h\to 0} \frac{e^{(t+h)A} - e^{tA}}{h}$
$= \lim_{h\to 0} \frac{e^{tA}e^{hA} - e^{tA}}{h}$ (since $e^{(t+h)A} = e^{tA}e^{hA}$)
$= \lim_{h\to 0} e^{tA}\frac{e^{hA} - I}{h}$
$= e^{tA}\lim_{h\to 0} \frac{e^{hA} - I}{h}$
$= e^{tA}\lim_{h\to 0} \frac{\sum_{k=0}^\infty \frac{(hA)^k}{k!} - I}{h}$
$= e^{tA}\lim_{h\to 0} \frac{\sum_{k=0}^\infty \frac{h^kA^k}{k!}}{1}$ (Loppital’s rule, since $\sum_{k=0}^\infty \frac{(hA)^k}{k!} - I$ is 0 when $h=0$)
$= e^{tA}A$

Part II show that $e^{tA}A = Ae^{tA}$

$e^{tA}A = \sum_{k=0}^\infty \frac{(tA)^k}{k!}A$
$\Rightarrow e^{tA}A = \sum_{k=0}^\infty \frac{t^kA^k}{k!}A$
$= A \sum_{k=0}^\infty \frac{t^kA^k}{k!}$ ($\frac{t^kA^k}{k!} = \beta A^k$, then $A\beta A^k = \beta A^{k+1}$, so $A$ can move to the front of the sum)
$= Ae^{tA}$

Theorem: For $x’=Ax$ ($A\in R^n$), $x(0) = k \in R^n$ the general solution is $x(t) = e^{tA}k$ and the solution is unique

Proof

$\frac{d}{dt}e^{tA}k = Ae^{tA}k$ (from the proposition above)\

Let $x(t) be any solution and let $y(t) = e^{-tA}x(t)$
$\Rightarrow y’(t) = -Ae^{-tA}x(t) + e^{-tA}x’(t) = -Ae^{-tA}x(t) + e^{-tA}Ax(t) = 0$
$\Rightarrow y’(t) = \frac{d}{dt}(e^{-tA}x(t)) = \frac{d}{dt}e^{-tA}x(t) + e^{-tA}\frac{d}{dt}x(t) = (-Ae^{-tA})x(t) + e^{-tA}Ax(t) = 0$
$\Rightarrow y(t) = y(0) = e^{-0A}x(0) = C$
$\Rightarrow y(t) = e^{-tA}\cdot x(t)$ $x(t) = e^{tA}y(t) = e^{tA}C$

Example

Find the general solution of $x’ = Ax$ where $a = \begin{bmatrix} a & 0 \\ b & a \end{bmatrix}$
$\Rightarrow$ The general solution is $e^{tA}k$ where $k = \begin{bmatrix} k_1 \\ k_2 \end{bmatrix}$
from previous example, we know
$e^A = e^a\begin{bmatrix} 1 & 0 \\ b & 1 \end{bmatrix}$
$e^{tA} = e^{ta}\begin{bmatrix} 1 & 0 \\ tb & 1 \end{bmatrix}$
$\Rightarrow e^{tA}k = e^{ta}\begin{bmatrix} 1 & 0 \\ tb & 1 \end{bmatrix}\begin{bmatrix} k_1 \\ k_2 \end{bmatrix} = e^{ta}\begin{bmatrix} k_1 \\ tbk_1 + k_2 \end{bmatrix}$
$\Rightarrow \begin{cases} x_1(t) = e^{ta}k_1 \\ x_2(t) = e^{ta}(tbk_1 + k_2) \end{cases}$

predict the behavior of the system $x’ = Ax$ by looking at the eigenvalues of $A$

$y’ = By$ where $B = \begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix}$

then $y_1’ = \lambda_1 y_1$ and $y_2’ = \lambda_2 y_2$, the solution is for some negative $\lambda_1$ and $\lambda_2$, it will converge to $(0, 0)$ for $(y_1, y_2)$ as time $t$ goes by, for some positive $\lambda_1$ and $\lambda_2$, it will diverge to infinity for $(y_1, y_2)$, for some $\lambda_1$ and $\lambda_2$ with different sign, it will diverge to infinity for some direction and converge to (0, 0) for some direction for $(y_1, y_2)$

three kinds of behavior for $y’ = By$:

$\det(\begin{bmatrix} \lambda_1-a & b \\ c & \lambda_2-a \end{bmatrix}) > 0$ and it will be $\alpha\lambda^2 + \beta\alpha + \gamma = 0$

if $\beta^2 - 4\alpha\gamma > 0$, $B= \begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix}$, it will have two different eigenvalues
if $\beta^2 - 4\alpha\gamma < 0$ ($B= \begin{bmatrix} a & -b \\ b & a \end{bmatrix}$), it will be $\begin{bmatrix}y_1(t) \\ y_2(t) \end{bmatrix} = e^{a t}\begin{bmatrix} k_1\cos b t & -k_2\sin b t \\ k_1\sin b t & k_2\cos b t \end{bmatrix}\begin{bmatrix} k_1 \\ k_2 \end{bmatrix}$, it will be a spiral, if $a < 0$ it will be a spiral sink, if $a > 0$ it will be a spiral source, if $a = 0$ it will be a center
if $\beta^2 - 4\alpha\gamma = 0$, it will have one eigenvalue, $B = \begin{bmatrix} \lambda & 1 \\ 0 & \lambda \end{bmatrix}$, the solution is $\begin{bmatrix} y_1(t) \\ y_2(t) \end{bmatrix} = e^{\lambda t}\begin{bmatrix} k_1 + k_2 t \\ k_2 \end{bmatrix}$, if $\lambda < 0$ it will be a degenerate node sink, if $\lambda > 0$ it will be a degenerate node source, if $\lambda = 0$ it will be a line of fixed points

tune the system behavior

We will change $A$ to $G$ and let it become any kind of converge model. Bring some diverge system to converge system.

system stability

Definition(stability)

Suppose $\bar{x} \in W$ is an equilibrium of the differential equation $x’ = f(x)$, then $\bar{x}$ is said to be a “stable equilibrium” if for every neiborhood $U$ of $\bar{x}$ in $W$, there is a neighborhood $U_1$ of $\bar{x}$ in $U$ such that every solution $x(t)$ with $x(0)$ in $U_1$ is defined and in U fo all $t<0$

if $\lim_{t\to \infty} x(t) = \bar{x}$ then $\bar{x}$ is said to be an “asymptotically stable equilibrium”

from $x’=Ax$ to system control

$\Rightarrow x’=Mx$ where $M = A - []$ and we control matrix $[]$
e.g. A will make system be circle, but we want system to be converge, so we can add some control matrix to make the system be converge, so does deverge.

the state space model (morden control)

damper effect

in the physics, we have know the Hooke’s law $F = k\Delta x$ can apply in spring, and there is another thing called damper（阻尼）
damper is a device that can dissipate energy, it can be used to reduce the oscillation of a system, it can be used to make a system be more stable, it can be used to make a system be more comfortable, it can be used to make a system be more safe

Example: spring-mass-damper system

1
2
3


 -> x(t)
<--f_k(t)-spring--|====| f(t)->
<--f_b(t)-damper--|====|

$f_k(t) = -kx(t)$(Hooke’s law) by spring
$f_b(t) = -b \cdot \frac{d\lambda (t)}{dt}$ ($\frac{d\lambda (t)}{dt}$ is the velocity of the mass, $b$ is the damping coefficient)
$F=ma = m\frac{d^2x(t)}{dt^2}$ we have $f(t) + f_k(t) + f_b(t) = m\frac{d^2x(t)}{dt^2}$
$\Rightarrow m\frac{d^2x(t)}{dt^2} + b\frac{dx(t)}{dt} + kx(t) = f(t)$
$\Rightarrow m\cdot x’’+bx’+kx = f(t)$

define state variable $z_1(t) = x(t)$ and $z_2(t) = x’(t) = z_1’(t)$
Further, let $u(t)$ be system’s input $\Rightarrow u(t) = f(t)$, let $y(t)$ be system’s output $\Rightarrow y(t) = x(t)$

$D \Rightarrow z_2’(t)=\frac{1}{m}u(t) - \frac{b}{m}z_2(t) - \frac{k}{m}z_1(t)$\

$\begin{bmatrix} z_1’(t) \\ z_2’(t) \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ -\frac{k}{m} & -\frac{b}{m} \end{bmatrix}\begin{bmatrix} z_1(t) \\ z_2(t) \end{bmatrix} + \begin{bmatrix} 0 \\ \frac{1}{m} \end{bmatrix}u(t)$
and y(t) = $\begin{bmatrix} 1 & 0 \end{bmatrix}\begin{bmatrix} z_1(t) \\ z_2(t) \end{bmatrix} + \begin{bmatrix} 0 \end{bmatrix}u(t)$

In general, we can write the state space model as
$\begin{cases} z’(t) = Az(t) + Bu(t) \\ y(t) = Cz(t) + Du(t) \end{cases}$ where $z(t) = \begin{bmatrix} z_1(t) \\ z_2(t) \end{bmatrix}$
$A$: state matrix / system matrix (suppose $u(t) = 0 \Rightarrow z’(t) = Az(t) \Rightarrow x’=Ax$)
$B$: input matrix / control matrix (i.e., how the input imapcts the state variables)
$C$: output matrix (i.e., how the state variables affect output)
$D$: direct transfer matrix (i.e., how the input directly affects output)
$z(t)$: state variables (a vector)
$u(t)$: input
$y(t)$: output

apply example

suppose $u = -Kz(t) \Rightarrow Az(t) + B(-Kz(t)) = (A-BK)z(t)$, that $A-BK$ is the $M$ we mentioned before, so we can change the system behavior by changing $K$

state feedback control

Lyapunov stability criteria

Let $\bar{x}\in W$ br an equilibrium for a dynamical system $x’ = f(x)$
Let $V: U\to R$ be a continuous function defined on a neighborhood $U\in W$ of $x$, differentiable on $U - \bar{x}$
such that

$V(\bar{x}) = 0$ and $V(x) > 0$ if $x \neq \bar{x}$
$V(x)\leq 0$ in $U - \bar{x}$, if 1, 2 are true, then the system is stable at $\bar{x}$\
$V(x) < 0$ in $U-\bar{x}$, if 1, 2, 3 are true, then the system is asymptotically stable

asymptotically stable is when give any initial state, the system will converge to the equilibrium point as time goes by, so it is more stronger than stable
since stable only means that the system will not diverge to infinity, but it can still oscillate around the equilibrium point

PID control (classical control)

P: portional, I: integral, D: differential
there are three parameters in P control, I control and D control

For example, spring-mass-damper system, the $K$ in $u = -Kz(t)$ is PD control
we can use LQR(linear quadratic regulator) to find the optimal $K$ for the system

NTNU CPS Real-time System Model

Sun, 07 Jun 2026 00:00:00 +0800

deadline

1
2
3
4
5
6
7


flowchart LR

a[sensing]
b[computing]
c[actuating]
d[environment]
a-->b-->c-->d-->a

where are deadline come from

type of Real-time system

hard real-time system

definition

If producing results after deadline, then it will give seriously bad consequence. e.g. earthquake warning

soft real-time system

definition

If producing results after deadline, then it will give lower utility. e.g. live streaming, online multiplayer game

firm real-time system

definition

If producing results after deadline, then it will be useless.

model

$\Gamma: \text{task set: }{\tau_1 , \tau_2, \tau_3 ,…}$
Tasks have many type, some of them are period task, some just one-time task(only one job), also have other
$j_i$: job in task $\tau_i$
R: Response time of Real time system is finish time - arrival time
$T_i$: time period of job in task
$C_i$: execution time (in the worst case)
$U$: CPU utilization = sum of CPU use time percentage($[ \sum_{i} \frac{C_i}{T_i}]$)

algorithm

optima

if one of the algorithm is schedulable, optima algorithm is also schedulable.
if there is some scheduler can schedule some sub-task, the optima can also schedule those.(not mean it can schedule all task set, but for all of other schedule can)

example

priority $j_i>j_j for i<j$
non-preemptive
schedule according to priority order

$\tau_1 \rightarrow \tau_5, \tau_2 \rightarrow \tau_3 / \tau_4$

1
2


CPU1: j2 j2 j3 j3 j4 j4
CPU2: j1 j5 j5 j5 j5

but if $c_2 = 1$ will become:

1
2


CPU1: j2 j4 j4
CPU2: j1 j3 j3 j5 j5 j5 j5

critical section handle problem(priority inversion)

In the critical section, higher priority task may delay because before higher priority may wait before executing critical section and the lower is executing higher priority task first.

For example(T1 > T2 > T3):

1
2
3
4


c: critical section, w: wait, n: normal, X: no execution
T1: X X X X n n w w w w w w c c c c n n F X X
T2: X X X X X X X n n n n F X X X X X X X X X
T3: n n c c w w c w w w w c w w w w w w w n F

middle priority task that can preempt higher priority task

Rate-monotonic(RM) scheduling

assumption

periodic hard-real-time tasks
deadlines consist of run ability constraint (i.e, implicit deadline)
tasks have no dependency
constant execution time for each job of a task
focus only on periodic hard-real-time jobs (same as 1.)

fix priority preemptive scheduling (FP)

for example, STCF isn’t FP
// with FP, we can have run Queue, and take first job and wait until job finish, then take first again\

worst-case (most challenging case) analysis

we should consider the worst case

critical instant

there is n higher priority tasks, has job release at same time as target task $\tau_i$ did
and we can consider them as 1 higher priority task $\tau_0$ (impact same as n tasks)
we can know that shift the time of $\tau_0$’s job won’t affect response time of $\tau_i$, because it is still inside the response time of $\tau_i$
so the worst case is the $\tau_0$ arrival time same as $\tau_i$

for different priority order, the execution time of longer:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


=: executing, ^: arrive -: idle
t1|^==---^==---^==---^
t2|^--=== --=== --===^

t1|^===-- ----- -----^
t2|^---==^==---^==---^


vvXXXXXincorrectXXXXXvv
t1|^===== ====- -----^
t2|^---XX^---X=^==---^

$\Rightarrow$ task has longer period should have lower priority is better

analysis $T_1$ and $T_2$

suppose $T_1>T_2$

1
2


τ₁|^----- ----- ---^--
τ₂|^-----^-----^-----^

There will be $\lceil{\frac{T_1}{T_2}}\rceil$ arrivals of jobs of $\tau_2$ within two arrivals of $\tau_1$(longer over shorter)
There will be $\lfloor{\frac{T_1}{T_2}}\rfloor$ arrivals of jobs of $\tau_2$ whose deadline fall within $T_1$

If we set $\tau_1$ to be of a higher priority, than fot $\tau_1$, than for $\tau_1$ and $\tau_2$ both be schedulable, we need $c_1 + c_2 \leq T_2 \Rightarrow \lceil{\frac{T_1}{T_2}}\rceil C_1+\lceil{\frac{T_1}{T_2}}\rceil C_2\leq\lceil{\frac{T_1}{T_2}}\rceil T_2\leq T_1$
imply\

If we set $\tau_1$ to be of a higher priority, than fot $\tau_1$, than for $\tau_1$ and $\tau_2$ both be schedulable, we need $\lfloor{\frac{T_1}{T_2}}\rfloor C_2+C_1\leq T_1$\

independent with $C_1, C_2$, only consider with arrival rate

Theorem

Theorem 1

A critical instant for any task occurs whenever the task is requested simultaneously with requests for all priority tasks.

Theorem 2

If a feasible priority assignment exists for some task set, the rate-monotonic priority assignment will be feasible for that task set tool

task set utilization (aka utilization factor of the task set)

$\sum_i \frac{C_i}{T_i}$
$U\leq ln2=0.693\rightarrow schedulable$
$U\leq n(2^{\frac{1}{n}}-1)$
if only two tasks than as long as $U\leq 2(\sqrt{2}-1)=0.83$ than the task set is schedulable using RM(but not mean if higher than 0.83 not schedulable)

proof of the sufficient schedulability test $U\leq 2(\sqrt{2}-1)$

$T_1 > T_2$\

Case 1

$\tau_2$ next job came after $\tau_1$ finish

$C_1 \leq T_1 - T_2 \lfloor \frac{T_1}{T_2} \rfloor \Rightarrow$ The longest possible value of $C_2$ is $C_2 = T_2 - C_1 \Rightarrow U = \frac{C_1}{T_1} + \frac{C_2}{T_2} = 1 + C_1 (\frac{1}{T_1} - \frac{1}{T_2}) = f(C_1)$

if $C_1$ decrease, $U$ increase if $C_1$ increase, $U$ decrease

Case 2

$\tau_2$ next job came before $\tau_1$ finish

$C_1 \geq T_1 - T_2 \lfloor \frac{T_1}{T_2} \rfloor \Rightarrow$ The longest possible value of $C_2$ is $C_2 = \frac{T_1 - C_1}{\lfloor \frac{T_1}{T_2} \rfloor + 1}$ $\Rightarrow U = \frac{C_1}{T_1} + \frac{C_2}{T_2} = \dots = \frac{1}{T_2} \cdot \frac{T_1}{\lfloor \frac{T_1}{T_2} \rfloor + 1} + C_1 (\frac{1}{T_1} - \frac{1}{T_2(\lfloor \frac{T_1}{T_2} \rfloor + 1)})$ $(C_1 (\frac{1}{T_1} - \frac{1}{T_2(\lfloor \frac{T_1}{T_2} \rfloor + 1)})) > 0$

if $C_1$ decrease, $U$ decrease if $C_1$ increase, $U$ increase

summarize

$C_1=T_2 - T_1\lfloor{\frac{T_1}{T_2}}\rfloor$ $\Rightarrow U=\frac{C_1}{T_1}+{C_2}{T_2} = …… \leq 2(\sqrt{2}-1)$\

EDF

EDF is a optimal scheduler, if $U < 1$. But in real world, the dynamic scheduling may have some other cost

real-time servers

a server to handle the aperiodic task, and also try to give good response time for aperiodic task, and also try to guarantee the schedulability of periodic task. that get balance between the two type of task.

aperiodic task and periodic task

For real-time system, we usually have two type of task, periodic task and aperiodic task.
The system should guarantee the schedulability of periodic task, and also try to give good response time for aperiodic task.

periodic task

task that has a job release at regular interval, and the deadline is same as the period.

aperiodic task

also called non-periodic task, task that has a job release at irregular interval, and the deadline is not same as the period.

shipboard computing

Computing on a ship (usually for military), for example, the ship has a radar system, and cannon system, the radar system is periodic task, and the cannon system is aperiodic task.

Aperiodic task may delay the periodic task, so we need to design handle the aperiodic task that can be predictable, and also try to give minimum response time that won’t delay the periodic task to miss the deadline.

key idea

create a periodic task to serve aperiodic task and control their interference to the rest of periodic tasks.

way to serve aperiodic task

Add a periodically scheduled budget of execution time for aperiodic task, and also give a period for the budget.
Once the aperiodic task arrive, it can use the budget to execute, and if the budget is used up, then it need to wait until next period to get new budget.

For the case of example in textbook, we set aperiodic task as lowest priority since we don’t want to delay the periodic task, and just make the aperiodic budget scheduled as a periodic task to make it predictable, and also try to give good response time for aperiodic task.

schedulability test

let $U_p$ be the utilization of all periodic task, and $U_s$ be the utilization of the server where $U_s = \frac{C_s}{T_s}$, $\Rightarrow U_p + U_s \leq n(K^{\frac{1}{n}}-1)$, where $K = \frac{2}{U_s+1}$

then we need $U_p + U_s \leq (n+1)(2^{\frac{1}{n+1}}-1)$ to guarantee the schedulability of all periodic task, and also try to give good response time for aperiodic task.

worst task configuration

assumed 100% workload, from server, $\tau_1$, $\tau_2$ to $\tau_n$s’ period $T_s$, $T_1$… from min to max correspond RM priority，and $C_1 = T_1 - T_s$, $C_2 = T_2 - T_1$… $C_n = T_n - T_{n-1}$ reach 100% workload

1
2
3


Ts|==------|==
T1|--=-------|=
T2|---=-------|=

$\begin{cases} C_{n-1} = T_n -T_{n+1} \\ C_n = T_s - C_s - \sum_{i=1}^{n-1} C_i\end{cases}$
$C_s + \sum_{i=1}^{n-1} C_i = T_n - T_s$
$\Rightarrow C_n = T_s - (C_s + \sum_{i=1}^{n-1} C_i) = T_s - (T_n - T_s) = 2T_s - T_n$

$U = \frac{C_s}{T_s} + \sum_{i=1}^{n} \frac{C_i}{T_i} = U_s + \sum_{i=1}^{n-1} \frac{C_i}{T_i} + \frac{C_n}{T_n} = U_s + \sum_{i=1}^{n-1} \frac{T_i - T_{i-1}}{T_i} + \frac{2T_s - T_n}{T_n} = U_s -n + \sum_{i=1}^{n-1} \frac{T_{i+1}}{T_i} + \frac{2T_s}{T_n}$
$= U_s - n + \frac{T_2}{T_1}+\frac{T_3}{T_2} + … + \frac{T_n}{T_{n-1}} + (\frac{2T_s}{T_1}\frac{T_1}{T_n})$
now let $R_i = \frac{T_{i+1}}{T_i}$ and K = $\frac{2T_s}{T_1}$, we have $U = U_s - n \sum^{n-1}{i=1}R_i + K\frac{T_1}{T_n}$
rate that $\frac{T_n}{T_1} = \frac{T_n}{T_{n-1}} \cdot \frac{T_{n-1}}{T_{n-2}} \cdot … \cdot \frac{T_2}{T_1} = R_{n-1} \cdot R_{n-2} \cdot … \cdot R_1 = \prod_{i=1}^{n-1} R_i$
$\Rightarrow U = U_s - n + \sum_{i=1}^{n-1} R_i + K\frac{T_1}{T_n} = U_s - n + \sum_{i=1}^{n-1} R_i + K\frac{1}{\prod_{i=1}^{n-1} R_i} = f(R_i)$

To find the minimum of U, we can compute $\frac{df(R_i)}{dR_i} = 0$ for each $R_i$
$\Rightarrow \frac{df(R_i)}{dR_i} = 1 - K\frac{1}{\prod_{j=1}^{n-1} R_j} \cdot \frac{1}{R_i} = 0$
$\Rightarrow \frac{K}{R_i \prod_{j=1}^{n-1} R_j} = 1$ for each $R_i$
we choose $R_1 = R_2 = … = R_{n-1} = K^{\frac{1}{n}}$ to satisfy the above equation

$\Rightarrow U = U_s -n + \sum_{i=1}^{n-1} K^{\frac{1}{n}} + K\frac{1}{K^{\frac{n-1}{n}}}$ $=U_s -n + (n-1)K^{\frac{1}{n}} + K\frac{1\cdot K^{\frac{1}{n}}}{K^{\frac{n-1}{n}} K^{\frac{1}{n}}}$ $=U_s -n + (n-1)K^{\frac{1}{n}} + K^{\frac{1}{n}}$ $=U_s + n(K^{\frac{1}{n}} - 1)$# The lowest upper bound for $U_p$ is $n(K^{\frac{1}{n}}-1)$

from $K=\frac{2T_s}{T_1}$ and $U_s=\frac{C_s}{T_s} -1 \Rightarrow U_s+1=\frac{T_1}{T_s}$ $\Rightarrow K = \frac{2}{U_s+1}$

defferable server vs polling server

defferable server

the server will execute the aperiodic task immediately when it arrive, and if the budget is used up, then it need to wait until next period to get new budget.
the response time of aperiodic task is better than polling server, but it may cause more interference to periodic task

polling server

only the there is aperiodic task arrive before the server’s period, then the server will execute the aperiodic task immediately when it arrive, else the server will idle until next period to check if there is aperiodic task arrive.

resource access protocols

the protocols is designed to handle the critical section problem, and also try to get predictable response time.

Multi-criticality Systems with Varying Degrees of Execution Time Assurance

harmonic period

If all the task starting in critical instant, since all the task is the smallest’s period’s integer multiple, so the critical instant will come back again in the same period.

criticality

the criticality isn’t same as the priority
the criticality is about how bad the consequence if the task miss the deadline.

Multi-criticality Systems

In this case, high criticality task will take most execution time and run the complex task, the low criticality task will take less execution time and easy task.\

schedulability analysis

For criticality level $L = {A, B, C, D}$
$C_ij$: execution time of task $\tau_i$ viewed from criticality level $j$
$\tau_1$: $T=D_1 = 2$, $L_1 = A$, $C_{1A} = 2$, $C_{1B} = 1$
$\tau_2$: $T=D_2 = 4$, $L_2 = B$, $C_{2A} = 1$, $C_{2B} = 1$

preemptive fixed priority scheduling

if assign $\tau_1$ with a higher priority $\Rightarrow$ the system is deemed unschedulable.
if assign $\tau_2$ with a higher priority $\Rightarrow$ the system is deemed schedulable.

solution of priority inversion

fix the problem of “pathetic” priority inversion

For all of them are try to reduce the response time. And we use blocking time to explain it.

Non-preemptive protocol(NPP)

put the time that into the critical section into the highest priority, so that won’t cause priority inversion since the critical section will be executed immediately when it arrive. After the critical section, the task return to the original priority, and also give the chance for other task to preempt.

Highest locker priority protocol(HLP)

when a task enter the critical section, it will inherit the highest priority of all the task that enter the same critical section, other part is same as NPP.
so the task that has the highest priority and don’t enter the critical section won’t be affected.

Priority inheritance protocol(PIP)

it will inherit the highest priority that is blocked by the same critical section and wait for it finish critical section now.

This has some situation that make it has higher blocking time than HLP, NPP. so we have the priority ceiling protocol(PCP) to solve this problem.

Priority ceiling protocol(PCP)

$C(x)$: the priority ceiling of resource $x$
We can determine before execution, we ceiling the priority of the critical section, and also ceiling the priority of the task that enter the critical section to the ceiling priority of the critical section.
$C(S^*)$: the ceiling of the semaphore with the highest ceiling among all the semaphores currently locked by other tasks

Which means that when we enter the critical section, we will set the priority of the task to the highest priority of all the task that may use the same critical section. only the task that has higher priority than the ceiling priority or the task that has higher priority than origin priority and is in non-critical section(don’t has any other critical section) can preempt the task that is in critical section.\

in pthread support PIP and PCP

blocking time analysis

、

blocking time: the time that the higher priority task is delay by the lower priority task.

$P_i$: nominal priority level of task $\tau_i$
$P_i(R_k)$: atomic priority level of $\tau_i$ when it enters the critical section that utilizes resource $R_k$
$B_i$: maximum blocking time of task $\tau_i$ due to the priority change of some other tasks

$B_i = max_{j,k}{\delta_{j,k} | Z_{j,k} \in r_n}$ (the longest critical section of $\tau_j$ guarded by section $S_k$); ($\delta_{j,k}$ is duration of $Z_{j,k}$; $Z_{j,k}$ is the longest critical section of $\tau_j$ guarded by semaphore $S_k$ )
$r_i$: the set of all the longest critical sections that can block $\tau_i$
$r_i$: $U_{(j: P_j < P_i)}$ $r_{i,j}$, where $r_{i,j} = {Z_{j,k} | s_k\in \sigma_{i,j} }$, where $\sigma_{i,j}$ is the set of semaphores(used by some lower-priority tasks $\tau_j$) that can block $\tau_i$

NPP: $P_i(R_k) = max_h{P_h}$
HLP: $P_i(R_k) = max_h{P_h | \tau_h \text{ uses } R_k}$
PIP: $P_i(R_k) = max { P_i, max_h{P_h | \tau_h \text{ is blocked on } R_k}}$ (priority inheritance: $max_h$….)

For the PIP, the blocking time is the time that the waiting for other critical section to finish

NTU Computer Network Ch.3 Transport Layer

Mon, 15 Dec 2025 00:00:00 +0800

transport vs network layer

transport layer 是 process-to-process\

transport layer protocols

TCP, UDP, …

TCP

TCP 有 Source Port, IP 跟 Destination Port, IP

reliable, in-order delivery
congestion control
flow control
connection setup

source IP, Dest IP, source port(16 bits), destination port(16 bits), other header fields

UDP

unreliable, unordered delivery
no-frills extension of “best-effort” IP service

multiplexing and demultiplexing

multiplexing

會把不同 socket 的就像高速公路多個閘道匯集到同一條路

demultiplexing

收到會根據 IP address 跟 port number 送到不同 socket 就是類似高速公路路牌的概念

UDP 一個 port 只會有一個 socket（沒有 connection oriented）
TCP 一個 port 會有多個 socket（connection oriente，會根據 source IP 去到不同 socket），另外 server 還會有一個額外的 welcome socket

—-期中範圍—-

UDP

connectionless, unreliable service, best-effort delivery（代表不一定送到，而且順序不確定）

application examples

DNS
SNMP
HTTP/3
streaming multimedia apps 現行大部分的 streaming app 都用 UDP，因為不需要可靠傳輸，反而需要低延遲

UDP checksum

去檢查 transmission segment 出現的錯誤，並且可能可以透過這個修正
把兩個字元當作 16 bits integer，加起來，當溢位時把多出來的 bit 加到最後面，然後 checksum 就是這個和去做 not 的結果
但錯誤檢查能力不強，因為有可能兩個錯誤抵銷掉

reliable data transfer(RDT)

sender 呼叫 rdt_send() 去傳資料 rdt_rcv() 收資料\

rdt 1.0

假設底層傳輸不會出錯
sender 端就是等上層資料，然後再去打包成 packet，並用 udt_send() 傳送
receiver 端就是等 rdt_rcv() 收到 packet，然後把資料送到上層

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


graph TD
 S((sender-Wait for call from above))
 R((receiver-Wait for call from below))
 S-- rdt_send(data)
 packet = make_pkt(data)
udt_send(packet)
-->S
 R-- packet = rdt_rcv()
data = extract(data)
deliver_data(data)-->R

rdt 2.0

有 ACK/NACK 機制去處理 bit error
但有可能 ACK/NACK 本身也會出錯

ACK(acknowledgement)

receiver 收到正確的 packet 後會回傳 ACK 給 sender\

NACK(negative acknowledgement)

receiver 收到錯誤的 packet 後會回傳 NACK 給 sender\

sender side

sender 會等 ACK/NACK 回傳
收到 ACK 就傳下一個 packet
收到 NACK 就重傳剛剛的 packet

1
2
3
4
5
6
7
8
9


graph TD
 S((sender-Wait for call from above))
 W((Wait for ACK/NACK))
 S-- rdt_send(data)
 packet = make_pkt(data)
udt_send(packet)-->W
 W-- rdt_rcv(rcvpkt) && isNAK(rcvpkt)
udt_send(packet)-->W
 W-- rdt_rcv(rcvpkt) && isACK(rcvpkt) -->S

receiver side

receiver 收到 packet 後會檢查有沒有錯誤
沒有錯誤就回傳 ACK 給 sender，並把資料送到上層
有錯誤就回傳 NACK 給 sender，並丟掉

rdt 2.1

解決 ACK/NACK 也會出錯的問題\

sender side

sender 會根據 sequence number 去判斷 ACK/NACK
就是會先傳 sequence number 0 的 packet
收到 ACK 0 就傳 sequence number 1 的 packet
收到 NACK 就重傳 sequence number 0 的 packet
收到 ACK 1 就傳 sequence number 0 的 packet
當傳送 sequence number 1 時也同理
有四個 state send 0, wait for ACK0, send 1, wait for ACK1\

receiver side

receiver 會根據 sequence number 去判斷是不是重複的 packet
收到正確的 packet 就回傳 ACK 並送到上層
收到錯誤的 packet 就回傳 NACK 並丟掉然後繼續等
會有兩個 state，wait for 0, wait for 1

rdt 2.2

把 NACK 拿掉，改成 ACK 上次的 sequence number

rdt 3.0

基於 rdt 2.2 ，並加上 timeout 機制去處理 packet loss 的問題
有 pipeline 的功能，也就是可以同時傳多個 packet\

sender side

除了 ACK 機制外，還會有 timeout 機制
傳送 packet 後會啟動計時器
收到 ACK 就停止計時器並傳送下一個 packet
timeout 就重傳剛剛的 packet 並重新啟動計時器

receiver side

跟 rdt 2.2 一樣

performance of rdt protocols

utilization

假設每次傳送的 packet 大小為 L bits，傳輸速率為 R bps，單程延遲為 d sec
那傳送一個 packet 的時間為 L/R sec
單程延遲為 d sec
來回延遲 RTT 為 2d sec
那 utilization U 為 $U_{sender} = \frac{L/R}{RTT + L/R} (RTT» L/R)$
rdt 3.0 的 performance 很低，所以需要 pipeline 的機制去提升 utilization

pipelining

可以同時傳多個 packet
Utilization 會提升（$N\cdot \frac{L/R}{RTT + L/R}$）\

Go-Back-N(GBN)

sender 可以同時傳送多個 packet，但最多只能有 N 個未被 ACK 的 packet
receiver 只會接受正確且符合 sequence number 的 packet，其他的都會丟掉並重傳最後一個 ACK\

sender side

sender 會維護一個 window，window size 為 N
可以同時傳送 N 個 packet
收到 ACK 就把 window 向前移動
timeout 就重傳 window 內的所有 packet

receiver side

receiver 只會接受符合期待的 sequence number 的 packet
收到正確的 packet 就回傳 ACK 並把資料送到上層
收到錯誤的 packet 就丟掉並重傳最後一個 ACK

TCP

point-to-point, (reliable, in-order byte stream), full duplex data, cumulative ACKs, pipelining, flow control, congestion control\

header

fields	size (bits)
Source Port	16
Destination Port	16
Sequence Number	32
Acknowledgment Number	32
Header Length(Data offset)	4
Reserved(not used)	3
Flags(NS, CWR, ECE, URG, ACK, PSH, RST, SYN, FIN)	6
Receive Window	16
Checksum	16
Urgent Pointer	16
Options	variable
Data	variable

timeout

TCP 用 EstimatedRTT 跟 DevRTT 去計算 TimeoutInterval
EstimatedRTT = (1-α) * EstimatedRTT + α * SampleRTT
DevRTT = (1-β) * DevRTT + β * |SampleRT T - EstimatedRTT|
TimeoutInterval = EstimatedRTT + 4 * DevRTT\

flow control

receiver 會在 TCP 的 Receive Window 告訴 sender 自己的 RcvBuffer 還有多少空間（rwnd）
sender 會根據 receiver 的 Receive Window 去調整自己 unACKed 的傳送速率，避免 receiver 的 buffer overflow

handshake

if 2-way handshake is used

variable delays
retransmitted messages (e.g. req_conn(x)) due to message loss
message reordering
can’t “see” other side 會能因為回傳的封包卡住了，所以重傳，但是等到原本的封包抵達會重複建立連線

3-way handshake

client
- LISTEN
- SYNSENT
- ESTAB
server
- LISTEN
- SYNRCVD
- ESTAB

client 送出 SYN (SYNbit=1, Seq=x)，進入 SYNSENT 狀態
server 收到 SYN，送出 SYNACK (SYNbit=1, ACKbit=1, Seq=y, Ack=x+1)，進入 SYNRCVD 狀態
client 收到 SYNACK，送出 ACK (ACKbit=1, Seq=x+1, Ack=y+1)，進入 ESTAB 狀態
server 收到 ACK，進入 ESTAB 狀態

close connection

兩邊都送 FIN 來關閉連線，然後各自回傳 ACK

congestion control

congestion: “too many sources sending too much data too fast for network to handle”
會造成 packet loss, long delays，與 flow control 不同，flow control 是避免 receiver overload

causes/costs of congestion

scenario 1

one router, infinite buffer, two flows
input, output link capacity: R
no retransmissions needed

當 arrival rate > R/2 時，queue 會無限增長

scenario 2

one router, finite buffer, two flows
input, output link capacity: R
retransmits lost, timed-out packets

application-layer input = application-layer output: $\lambda_{in} = \lambda_{out}$
transport-layer input includes retransmissions : $\lambda’{in} > \lambda{in}$
當 $\lambda’{in} > R/2$ 時，queue 會滿，造成 packet loss, 此時 $\lambda{out} < \frac{R}{2}$

scenario 3

four flows, multi-hop paths, time-outs, retransmissions
當 $\lambda’{in}$, $\lambda{in}$ 上升，會可能把其他 flow drop 掉

approaches to congestion control

Network-assisted congestion control
- router 提供 feedback 給 sender
End-end congestion control(TCP, …)
- sender infers congestion from loss, delay
- 因為不一定擁有 router 控制權，不一定能取得 network 狀態，所以只能靠 end system 去偵測 congestion

TCP congestion control

AIMD

Additive Increase, Multiplicative Decrease
當沒有 congestion 時，增加一個 maximum segment size(MSS) every RTT
當有 congestion 時（3 duplicate ACKs），減半傳送速率

TCP slow start

congestion window(cwnd) 初始值為 1 MSS
每個 RTT，cwnd 加倍
當收到 ACK 時，停止 slow start

TCP timeout

當 timeout 發生時，將 cwnd 設為 1 MSS，然後進入 slow start 直到原先 cwnd 的一半，接下來做 AIMD

TCP CUBIC

對 AIMD 的改良版
CUBIC 的核心思想是記住上一次發生擁塞時的傳送速率，稱為 Wmax（最大視窗）。在速率被砍半後，它會依據一個三次函數（Cubic function）來快速恢復視窗大小，這個函數的圖形像一個 S 形曲線，當前的視窗大小接近 Wmax 時，增長速度會變慢，這樣可以避免過度擁塞。

bottleneck link

在一條路徑中，傳輸速率最低的連結稱為瓶頸連結（bottleneck link）。
congestion control 就會把注重在這邊

delay-based congestion control

讓中間的 pipe 剛好填滿
measured throughput = $\frac{\text{# bytes sent in last RTT interval}}{RTT_{measured}}$（現實 throughput）
uncongested throughput = $\frac{\text{cwnd}}{RTT_{min}}$（理想上的 throughput）
當 measured throughput < uncongested throughput 時，代表有 congestion，cwnd 減少
當 measured throughput >= uncongested throughput 時，代表沒有 congestion，cwnd 增加

BBR(Bottleneck Bandwidth and Round-trip propagation time)

Google 開發的 congestion control algorithm
透過估算 bottleneck bandwidth 跟 round-trip propagation time 來調整傳送速率
避免傳送過多資料到 network 中，減少 packet loss 跟延遲
提升網路效能

ECN(Explicit Congestion Notification)

network-assisted congestion control 的一種
router 會在 packet header（IP 層 ECN bit）上標記 congestion 的訊號，而不是丟掉 packet
receiver 收到標記後會減少傳送速率，然後回傳設定 ECE bit 的 ACK 給 sender
包括了 IP 的 ECN 跟 TCP 的 C,E bits

TCP fairness

當多個 TCP 連線同時使用同一條路徑時，會希望每個連線都能公平地分享網路資源
TCP 的 AIMD 機制有助於實現這一目標，因為它會根據網路的擁塞狀況動態調整傳送速率
當一個連線經歷擁塞並減少速率時，其他連線可以利用這個機會增加它們的速率
隨著時間的推移，這種動態調整有助於達到一種平衡，使得所有連線都能公平地使用可用的網路資源
不過前提是 RTT 差不多的情況下，否則 RTT 較低的連線會有較高的 throughput（增加得較快）

Fairness of internet

UDP

UDP 沒有 congestion control 機制，所以不會理會 network congestion 的狀況

parallel TCP connections

開多個 TCP 連線來增加 throughput
會搶佔到其他 TCP 連線的資源，造成不公平utilization

Evolving transport-layer functionality

different TCP

Long, fat pipes /Wireless networks / Londelay linke / Data center networks / Background traffic flows 都有特定的 TCP “flavors”

UDP-based reliable transport

QUIC (Quick UDP Internet Connections)

建立在 UDP 之上，提供類似 TCP 的可靠傳輸功能
reliability, congestion control, authentication, crypto state
1 handshake，connection establishment, 1 round-trip time (RTT)
有 Error Control, Congestion Control
多個 stream 在同一個 connection 上傳輸資料，避免 head-of-line(HOL) blocking

TCP throughput

TCP throughput equation

$\text{avg. TCP Throughput (in GBps)} = \frac{3}{4} \cdot \frac{W}{RTT}$
W: congestion window size (in bytes)
RTT: round-trip time (in seconds)
avg. window size = $\frac{3}{4} W$\

$\text{TCP Throughput (in GBps)} = \frac{1.22 \cdot MSS}{RTT \cdot \sqrt{L}}$
MSS: maximum segment size (in bytes)
RTT: round-trip time (in seconds)
L: packet loss rate (between 0 and 1)\

NTU Computer Network Ch.4 Network Layer - Data Plane

Mon, 15 Dec 2025 00:00:00 +0800

data plane and control plane

data plane

負責選擇傳送給哪個輸出
local per-router

control plane

負責 end-to-end routing network-wide logic\

approaches to control plane

traditional routing algorithms
- implemented in routers
software-defined networking (SDN)
- control plane 從 router 分離出來，集中在一個 (remote) servers(controller) 裡面
- controller 會有 network-wide 的 view，可以做更好的決策

router architecture

routing process

負責決定封包的路由路徑

high-speed packet fabric

負責快速轉發封包，連接著 input/output ports

input ports

Line Termination
- 負責 physical layer bit-level reception
Link-layer Protocols(receive)
- 負責 link-layer frame 的處理
lookup, forwarding, queuing
- lookup: 檢查封包標頭中的欄位值（在傳統路由器中，這只看目標 IP 位址）。
- forwarding:拿著這個目標 IP 位址，去查詢儲存在輸入埠記憶體中的「轉發表 (forwarding table)」
- queuing: 當 output port 忙碌時，將封包暫存起來（Head-of-the-Line blocking）

Longest prefix matching

當一個封包的目標 IP 位址同時符合轉發表中的多筆規則時，路由器必須選擇前綴最長（也就是最精確）的那一筆規則來轉發封包。

input port queuing

當 input port 的速率比 switch fabric 的速率還快時，input port 會將封包暫存在佇列中，等待傳送到 switch fabric。
Head-of-the-Line (HOL) blocking: 當一個封包在 queue 的最前面，但被其他 queue 的 packet 擋住（像是 output port 被佔用），導致整個 queue 都無法前進。

Switch fabrics

將 packet從 input link 轉移到正確的 output link。

first generation
- Switching via memory
- 封包會先從 input port 被複製到路由器的系統記憶體中，然後 CPU 查詢轉發表，再將封包從記憶體複製到對應的 output port。
- 速度受到記憶體頻寬的限制，因為一個封包必須兩次跨越系統匯流排（一次寫入記憶體，一次讀出），效能較差。
second generation
- Switching via bus
- 封包從 input port 的記憶體，透過一條共享的匯流排（bus），直接傳送到 output port 的記憶體。
- 因為所有封包都必須共用這條匯流排，會產生「匯流排爭用」（bus contention），其交換速度的上限就是匯流排的總頻寬。例如，Cisco 5600 路由器使用 32 Gbps 的匯流排，這對於存取路由器（access router）來說通常足夠。
third generation
- Switching via interconnection networks
- 使用多條平行的匯流排或交錯網路（interconnection network）來連接 input port 和 output port。（但是一個出口 / 入口還是只能同時處理一個封包）

output ports

Buffering

當 datagram 抵達 output port 速率超過 link 的傳輸速率時，output port 會將 datagram 暫存在 buffer 中，等待傳送到 link 上。

Drop policy

當 buffer 滿了，output port 必須決定要丟棄哪個

Datagram lost

Datagrams can be lost due to congestion, lack of buffers queueing (delay) and loss due to output port buffer overflow!

Scheduling discipline

當緩衝區中有多個封包在排隊時，路由器下一個應該先 transmission 哪一個

priority scheduling

根據封包的優先權來決定傳送順序

buffer size

當太大的 buffer 會導致延遲增加，太小的 buffer 會導致封包丟失

RFC 3439 rule of thumb

B=RTT×C

More recent recommendation

N flows,
buffer size = $\frac{RTT×C}{\sqrt{N}}$

buffer management

當 buffer 滿了，決定要丟棄哪個封包

drop-tail

當 buffer 滿了，丟棄新到的封包

priority

當 buffer 滿了，根據封包的優先權決定丟棄順序

marking

當 buffer 快滿了，標記封包，讓接收端知道網路擁塞，然後回傳 ACK 給傳送端，讓傳送端減少傳輸速率\

ECN (Explicit Congestion Notification)
- 當 buffer 快滿了，標記封包的 ECN 欄位
RED (Random Early Detection)
- 當 buffer 滿了，隨機丟棄封包

scheduling

FCFS

First-Come-First-Served

priority scheduling

根據封包的優先權來決定傳送順序，分成不同 queue 去排隊

round robin

每個 queue 輪流傳送一個封包

weighted fair queueing (WFQ)

每個 queue 根據權重輪流傳送封包 $\frac{w_i}{\sum_j w_j}$

Switch Fabric

First Generation router: Switching via Memory

* **Architecture**: 類似傳統 PC。封包進入 **Input Port** 的 Line Card 後，會發出 **Interrupt** 通知 CPU。
* **Mechanism**: CPU 透過 **System Bus** 將封包讀入 **Memory**，查表後再寫入 **Output Port** 的 Line Card 的 Buffer 。
* **Bottleneck**: **Memory Bandwidth**。因為封包要經過 System Bus 兩次（Read + Write），吞吐量 (Throughput) 受限於記憶體速度 。

Second Generation router: Switching via Bus

* **Architecture**: Line Card 加上了 **NFE Processors (Network Forwarding Engine)**（有 CPU 跟 Memory）。
* **Mechanism**: Line Card 可以在本地處理 Header 查詢，不需要 CPU 介入每一個封包。封包透過共享的 **System Bus** 直接傳送到 Output Port 。
* **Bottleneck**: **Bus Bandwidth**。System Bus 是共享介質 (Shared Medium)，同一時間只能有一個封包在 Bus 上傳輸 (Bus Contention) 。

Third Generation: Switching Fabric (Interconnection Networks)

Architecture: 由 $N$ 個 Input 和 $N$ 個 Output 組成的矩陣，中間有 $N^2$ 個 Crosspoints (開關) 。
Pros:
- Non-blocking: 只要 Output Port 不同，所有封包可以同時傳輸。
Cons:
- Scalability Issue: 硬體複雜度 (Complexity) 是 $O(N^2)$。當 $N$ 變大時，成本 (Cost) 和電路面積會爆炸性增長。

Banyan Network

為了降低 Crossbar 的成本，設計出了 Multistage Interconnection Network (MIN)。

Architecture: 多層次的交換網路，通常由 $2 \times 2$ 的 Switching Elements 組成。硬體複雜度降低為 $O(N \log N)$ 。
Mechanism (Self-Routing):
- 使用 Binary Routing Tag。
- 例如 Tag 是 010：第一層走上 (0)，第二層走下 (1)，第三層走上 (0) 。
Critical Problem: Internal Collision (Blocking)。
- 即使 Output Port 不同，兩個封包可能會競爭內部的同一條鏈路 (Internal Link)，導致其中一個被阻擋。

Batcher Network

會根據輸入的兩個值，將 Low 的值送到上方輸出，High 的值送到下方輸出。（沒有輸入視為全為 1）

Architecture: 由多個 Comparator (比較器) 組成的分層結構。
Mechanism:
- 每個 Comparator 接收兩個輸入，將較小的值送到上方輸出，較大的值送到下方輸出。
- 透過多層 Comparator，可以將一組輸入值排序 (Sorting)。

Batcher-Banyan Network

這是一個結合了演算法思維的硬體架構，用來解決 Banyan 的碰撞問題。

Collisions can be reduced if packets are ordered on input ports by their output port number
Pipeline Stages:
1. Batcher Sorter Network:
  - 使用 Comparators (比較器) 組成。
  - 功能是將所有封包依照 Destination Address 由小到大排序 (Sorting) 。
2. Trap Network:
  - 檢查排序後的封包，如果有這兩個封包要去同一個 Output Port (Output Contention)，它會標記並過濾掉後面的封包，只讓一個通過。
3. Shuffle exchange Network:
  - 將封包重新排列 (Rearrange)，以符合 Banyan Network 的輸入格式要求。
4. Banyan Network:
  - 接收已經 Sort 好的封包，執行最終的 Routing。此時保證是 Non-blocking 的。

network layer

path selection and forwarding, IP protocol, ICMP protocol

ICMP

Internet Control Message Protocol
用來傳送錯誤訊息和診斷資訊的協定

IP Datagram format

20 bytes TCP header + 20 bytes IP header = 40 bytes +apps overhead for TCP/IP

IP addressing

IPv4 address

32 bits, 分成 4 個 8 bits 的 octet，用十進位表示法來區分不同 host/router interface

interface

host/router 跟 physical link 連接的地方，通常是一個網卡 (network interface card, NIC)
host 通常一到兩個 interface(wired/wireless)

router

基本上就是有兩張以上的網卡（interface），把不同網路連接起來（n 張網卡就有 n 個不同的網路）

subnet

可以在不通過 intervening router 的情況下 physically connect 的一

mask / CIDR(Classless Inter-Domain Routing)

/24 = 把前面 24 bits 遮住，後面視為同一個 subnet
longest prefix matching: 當一個封包的目標 IP 位址同時符合轉發表中的多筆規則時，路由器必須選擇前綴最長（也就是最精確、mask 最大）的那一筆規則來轉發封包。

動態 IP

192.168.x.x

get IP

hard-coded in config file(/etc/rc.config)
DHCP (Dynamic Host Configuration Protocol)
- host 開機時，向 DHCP server 要 IP address

DHCP

host broadcast DISCOVER message(optional)
DHCP server respond with OFFER message(optional)
host send REQUEST message to DHCP server
DHCP server send ACK message to host

除了 IP address，還會給 subnet mask, first-hop router(default gateway), DNS server address
使用 UDP，有時效（lease）

Hierarchical addressing

當某一個 static IP 是某個大的 ISP 所有的大塊 IP底下，但是換了 ISP，要不改 IP address 會使用將 broad cast mask 的大小增加，因為 router 是 longest prefix matching，會找最大 mask 的 rule，在剩下範圍比較小的 subnet 就會歸到新的 ISP 底下，而不會去找原本的 ISP

ICANN

負責管理全球的 IP address 和 TLD，IP address 分配給 5 個 regional registries

NAT

Network Address Translation NAT 全名是 Network Address Translation（網路位址轉換）。

它的核心概念是：讓整個區域網路（如家庭或公司）內的所有設備，在對外連線時，共用「同一個」公開的 IPv4 位址。

這就像是一間大公司只有一個對外的總機號碼，但內部有數百個分機。

NAT 的運作原理

NAT 路由器透過修改 IP 封包的標頭來運作，具體流程如下（根據您的投影片範例）：

出去 (Outgoing)：
- 當內網的一台電腦（例如 10.0.0.1）要傳送封包到網際網路時。
- NAT 路由器會攔截這個封包，將其來源 IP (10.0.0.1) 和來源埠號 (3345) 替換成路由器的公開 IP (138.76.29.7) 和一個新的埠號 (5001)。
- 這樣，外部世界看到的請求來源就是路由器本身。
紀錄 (Translation Table)：
- 路由器會在內部的 NAT 轉換表 (NAT translation table) 中記下一筆資料：
- {公開 IP: 138.76.29.7, 埠號 5001} <---> {內網 IP: 10.0.0.1, 埠號 3345}。
回來 (Incoming)：
- 當外部伺服器回傳資料時，它的目標會是路由器的 {138.76.29.7, 5001}。
- 路由器收到後，查表發現 5001 對應的是內網的 10.0.0.1:3345。
- 路由器將封包的目的 IP 和目的埠號改回內網的數值，然後轉發給該電腦。

NAT 的優點

節省 IP address：只需要向 ISP 申請一個公開 IP，就可以讓成千上萬個設備上網。這是解決 IPv4 位址枯竭的主要功臣。
安全性：內網的設備對外部網路是不可見的（直接定址），外部無法主動連線到內網設備，提供了一層天然的防火牆保護。
靈活性：更換 ISP（更換公開 IP）時，不需要更改內網所有設備的 IP 設定。

NAT 的爭議與缺點

儘管 NAT 非常普及，但它在網路架構上是有爭議的：

違反端到端原則 (End-to-End Argument)：網路層（Layer 3）的設備（路由器）不應該去修改傳輸層（Layer 4）的埠號資訊。
妨礙 P2P 連線：如果外部的使用者想要主動連線到內網的某個服務（例如 P2P 下載或架站），會因為沒有公開 IP 而受阻，需要透過「NAT 穿透 (NAT traversal)」等複雜技術來解決。

但無論如何，NAT 已經成為現代網路（家庭、企業、4G/5G）不可或缺的一部分。

IPv6

IPv6 (Internet Protocol version 6) 是網際網路協定 (IP) 的最新版本，旨在取代目前主流的 IPv4。

1. 為什麼需要 IPv6？ (Motivation)

主要的推動力只有一個：IPv4 位址不夠用了！

address exhaustion：IPv4 使用 32 位元位址，總數約 43 億個，已經全數分配完畢。
效能優化：除了擴充位址，IPv6 也藉機改進了標頭格式，以加速路由器處理封包的速度（forwarding speed）。
服務品質 (QoS)：IPv6 在標頭中加入了對「資料流 (Flows)」的支援，以利於即時影音等服務。

2. IPv6 與 IPv4 的關鍵差異

IPv6 並不僅僅是加長了 IP 位址，它還 removed 了許多 IPv4 的舊欄位來簡化處理流程：

特性	IPv4	IPv6	改變原因
位址長度	32 bits	128 bits	提供幾乎無限的位址空間。
標頭長度	可變 (20 bytes + options)	固定 40 bytes	固定長度讓硬體處理更快速。
破碎化 (Fragmentation)	路由器可執行	不允許	路由器不再負責切分封包，以減輕負擔。如果封包太大，直接丟棄並通知來源端變小。
檢查碼 (Checksum)	有	removed	現代鏈路層（如乙太網）和傳輸層（TCP/UDP）都有檢查碼，IP 層再做一次是多餘且耗時的。
選項 (Options)	包含在標頭中	removed	改為透過 “Next Header” 指向擴充標頭，主標頭保持精簡。

3. IPv6 封包格式 (Datagram Format)

一個 IPv6 的封包標頭包含以下重要欄位：

Priority (Traffic Class)：用來識別封包的優先順序。
Flow Label：用來標記屬於同一個「資料流」（如視訊串流）的封包。
Next Header：指出上層協定是什麼（如 TCP, UDP），或是指向下一個擴充標頭。
Hop Limit：相當於 IPv4 的 TTL (Time To Live)，每經過一個路由器減 1 。
Source/Destination Address：各佔 128 bits 的來源與目的位址。

4. 過渡策略：隧道技術 (Tunneling)

由於網際網路太大，不可能在一天之內讓全世界所有路由器同時升級到 IPv6（沒有 “Flag days”）。因此，我們需要一種機制讓 IPv4 和 IPv6 共存。

隧道技術 (Tunneling) 是目前的解決方案：

概念：將整個 IPv6 封包當作「資料 (Payload)」，封裝在一個 IPv4 的封包裡面。
運作：當兩個 IPv6 路由器中間隔著一段 IPv4 網路時，它們會建立一個「隧道」。
- 入口路由器把 IPv6 封包塞進 IPv4 封包裡，寄給出口路由器。
- 中間的 IPv4 路由器只會看到 IPv4 標頭，照常轉發。
- 出口路由器收到後，剝除 IPv4 外殼，取出原本的 IPv6 封包繼續傳送。

5. 採用現況

IPv6 的普及速度比預期慢很多（已經推廣超過 25 年）。

主要原因是 NAT 技術延長了 IPv4 的壽命，減少了升級的急迫性。
根據 Google 的統計，截至 2023 年，約有 40% 的用戶是透過 IPv6 存取服務。

flow

每個 router 都會有 flow table，記錄每個 flow 的狀態
flow 本身會從 link/network/transport layer header 來定義

match plus action

對 arrival packet 的 bit 進行 match，然後執行 action

destination-based forwarding

根據 destination IP address 來 forward

generalized forwarding

根據多個 header fields 來決定 action（包括 drop/copy/modify/log packets）
會 match 多個 fields (e.g., src/dst IP address, src/dst port, protocol type)
然後執行 action drop, forward, modify, matched packet or send matched packet to controller
也有 priority，match 多個 rule 時，選擇 priority 高的 rule
還有 counter 記錄封包/bytes 數量

OpenFlow

OpenFlow 是一種通訊協定，它是現代 SDN (軟體定義網路) 架構的基石。

它的核心概念是將網路設備（如switch、路由器）的「控制權」與「轉發權」分離。OpenFlow 允許一個遠端的** controller (Controller)** 直接透過軟體指令，來修改網路設備中的流表 (Flow Table)，從而決定封包該如何被處理。

這實現了我們先前提到的「廣義轉發 (Generalized Forwarding)」。

OpenFlow 的核心結構：流表 (Flow Table)

在 OpenFlow 架構下，每一個流表項目 (Flow Entry) 都包含三個主要部分：

Match：
- OpenFlow 不像傳統路由器只看「目的 IP」。它可以檢查封包標頭中，從鏈路層到傳輸層的幾乎所有欄位。
- 可 Match 欄位：輸入埠 (Ingress Port)、來源/目的 MAC、VLAN ID、來源/目的 IP、IP 協定、TCP/UDP 埠號等。
動作 (Action)：
- 當封包符合上述條件時，要執行什麼動作？
- 轉發 (Forward)：送到特定的物理埠。
- 丟棄 (Drop)：像防火牆一樣直接擋掉。
- 修改 (Modify)：修改標頭欄位（例如 NAT 修改 IP）。
- Forward to controller：將封包封裝後送給 controller，詢問該怎麼處理。
統計 (Stats/Counters)：
- 記錄有多少封包、多少 bytes Match 了這條規則。

OpenFlow 帶來的變革：設備角色的統一

透過 OpenFlow，我們可以使用同一套硬體，透過安裝不同的流表規則，讓它扮演完全不同的網路設備角色：

role	Match	Action
Router	最長 IP Longest prefix match	forward to next-hop link
Switch	目的 MAC 位址	forward or flood
Firewall	IP 位址 + TCP/UDP 埠號	permit or deny
NAT	IP 位址 + 埠號	rewrite address and port

範例：網路編排 (Orchestration)

OpenFlow 最強大的地方在於全網控制。

舉例來說， controller 可以同時設定好幾個 switch（s1, s2, s3）的流表，強制規定：「只要是來自 Host h5 或 h6 的流量，不管目的地是哪裡，都必須強制經過 s1 和 s2 這條特定路徑」。

這在傳統網路中很難做到（傳統路由通常只選最短路徑），但在 OpenFlow SDN 中，這只是 controller 下達幾條規則就能完成的事。

NTU Computer Network Ch.5 Network Layer - Control Plane

Mon, 15 Dec 2025 00:00:00 +0800

Network-layer functions

forwarding

把 packet 從 input interface 送到 output interface 的過程，Data Plane

routing

決定 packet 從 source 到 destination 的路徑，Control Plane

structuring network control plane

per-router control
- traditional
- 每個 router 都有自己的 control algorithm component
logical centralization
- software-defined networking (SDN)
- remote controller

routing protocols

目標是找到一個 “good” path 從 source 到 destination

Routing algorithm classification

又兩個方向：global <–> decentralized, dynamic<–>static

global

“link state” algorithm
所有的 router 都有 complete toplogy 跟所有的 link cost info

decentralized

“distance vector” algorithm
iterative 的過程，每個 router 只知道鄰居的 info（只會跟鄰居交換）

dynamic

routes 的變化很頻繁

static

routes 很少變化

Dijkstra’s algorithm

centralized
- 對所有 nodes，network topology 與 link cost 已知
- link state broadcasts 這些資訊
- node 的 info 都一樣
iterative
- 當 k 次 iteration 結束時，會找到從 source 到 k 個 nodes 的 shortest path
$O(n^2)$ time complexity，可以透過 priority queue 改成 $O(n log n)$
$O(n^2)$ message complexity

Route Oscillations

當有大流量的 traffic 時，link cost 會變高，導致 routing algorithm 重新計算 path
如果所有的 router 都同時重新計算 path，會導致 route oscillations，也就是大家都擠一起，cost 又變高，然後又重新計算 path，如此反覆
通常把 link state broadcasts 的時間 randomize 錯開更新時間，可以減少這個問題

Distance Vector Algorithm

Bellman-Ford equation

$$d_x(y) = min_v { c(x,v) + d_v(y) }$$

$d_x(y)$: 從 node x 到 node y 的最短距離
$c(x,v)$: 從 node x 到鄰居 node v 的 link cost
$d_v(y)$: node v 宣告的從 v 到 y 的最短距離

key idea

每個 node 只需要知道鄰居的 distance vector，就可以計算出自己到其他 node 的 cost，如果 cost 有變化，就把新的 distance vector 傳給鄰居

WAIT for change in local link cost or distance vector from neighbor
UPDATE distance vector
NOTIFY neighbors if distance vector changes

por and cons

pros
- good news travels fast
  - 當 link cost 變低時，會很快被傳播出去
cons
- bad news travels slow
  - 當 link cost 變高時，會很慢被傳播出去，可能會導致 count-to-infinity 問題

count-to-infinity problem

當 link cost 變高時，可能會導致 routing loop，造成 distance vector 不斷增加
example: A-60-B-1-C，A 到 C 的 cost 變成 infinity，但 A 會從 B 那邊收到 cost 61 的資訊，B 會從 A 那邊收到 cost 62 的資訊，如此反覆

link state vs distance vector

feature	link state	distance vector
algorithm type	global	decentralized
information required	complete topology	neighbor’s distance vector
robustness to failures	less robust	more robust
convergence speed	fast	slow
message complexity	$O(n^2)$	exchange with neighbors
computational complexity	$O(n^2)$	slow and not specified

internet approach to routing

autonomous systems (AS)

把 routers 聚集在一個 region 內，稱為 AS(a.k.a. domains)

intra-AS routing
- AS 內部的 routing
- 由 AS 自己決定使用什麼 routing protocol
- “edge” 的 routers 會跟其他 AS 的 edge routers 溝通
inter-AS routing
- AS 之間的 routing 在 local 時，通常會選擇 shortest path
  在 large scale 的部分，只要不要 worst case 就好
  forwarding table 是由 inter-AS 跟 intra-AS 共同決定的

intra-ISP routing

常見的有 RIP(Routing Information Protocol), OSPF(Open Shortest Path First), EIGRP(Enhanced Interior Gateway Routing Protocol)

RIP

distance vector protocol
每 30 秒廣播 distance vector 給鄰居
現在沒什麼用

EIGRP

Distance vector based
Cisco proprietary

OSPF

link state protocol
- 可以有多個 link cost metrics (bandwidth, delay, load, reliability)
- 使用 Dijkstra’s algorithm 計算 forwarding table
IS-IS protocol(ISO standard, not RFC standard) essentially similar as OSPF
是 public available 的 protocol(open)
authentication
heirarchical routing with areas
- 把 network 分成多個 area，由一個 backbone area 連接所有 area
  - Link-State Advertisement (LSA) 只在 area 內或 backbone area 廣播
  - 對其他 area 只知道大方向
- routers
  - Local routers: 只在同一 area 內
  - Area Border Routers (ABR): 連接 area 跟 backbone area
  - Backbone Routers: 在 backbone area 內
  - Boundary Routers: 連接不同 AS 的 routers

inter-ISP routing

BGP(Border Gateway Protocol)

provides

eBGP: neighboring AS 之間的 routing
Policy: 跟據 policy 決定路徑，而不是單純的 shortest path
iBGP: same AS 內部的 routing
Advertise: 透過 eBGP 廣播 network reachability info

basics

BGP session
- 兩個 BGP routers 之間的 TCP connection
- 建立 semi-permanent connection（半永久連線）
advertises
- 當 AS1 跟 AS2 advertise path AS1, X 代表 promise 可以到達 network X 透過 AS1

protocol messages

OPEN: 建立 BGP session
UPDATE: advertise 可達的 networks 以及 path attributes
KEEPALIVE: 當沒有 UPDATE 時，確認 BGP session 還活著，也是 ACKs OPEN messages
NOTIFICATION: 通報 error 跟 close connection 用

path attributes

AS-PATH: 紀錄從 advertise 的 AS 到目前 AS 經過的 AS 列表
- 避免 looping
- policy decisions（可以不要經過某些 AS）
NEXT-HOP: 下一個 hop 的 IP address

Hot Potato Routing

選擇離自己最近的出口 AS，盡快把 packet 傳出去，而不是選擇最短路徑
也就是只管最低 intra-AS cost，不管 inter-AS cost

achieving policy

對 providers 來說， revenue 很重要
當不是 customer 的 AS，不會把自己拿不到 revenue 的路徑 advertise 出去，customer 收到的路徑就是那些可以帶來 revenue 的路徑
對 customers，不會想要免費當 transit：當連接到兩個 providers 時，不會把其中一個 provider 的路徑 advertise 給另一個 provider，避免 provider 把自己當成 transit

selection of BGP routes

local preference value attribute: policy decisions
shortest AS-PATH
closest NEXT-HOP (hot potato routing)
additional criteria

Linux Block layer

Mon, 20 Oct 2025 00:00:00 +0800

Block layer

Block layer is an interface that provides a

software queue

Different from the document and paper, the software queue is only used if q->elevator is not NULL you can see in blk-mq.c

elevator_switch

Reference

Linux Block layer
Linux block IO: introducing multi-queue SSD access on multi-core systems(https://kernel.dk/blk-mq.pdf)

NTU Computer Network Ch.1 Introduction

Mon, 20 Oct 2025 00:00:00 +0800

edge networks

circuit switch

去連接需要單獨建立連線，直到斷掉前都會佔用資源在那邊，但可以保證網路頻寬不會被搶走

packet switching

以 packet 為單位去傳輸資料，會跟其他人搶頻寬，但不會佔用資源，但也有頻寬搶不到時，會有微小機率 drop 掉封包

store-and-forward

要等整個 packet 都收到後才會傳送到下一個節點，會產生 processing delay 跟 queuing delay

processing delay

確定封包要送給誰，要對封包進行處理的 delay

queuing delay

封包在 queue 中等待傳送的 delay（因位進來的封包可以有多個，但出去只有一個）

FDM(Frequency Division Multiplexing)

頻分多工，把頻寬切成很多小頻寬，分給不同的人使用

TDM(Time Division Multiplexing)

時分多工，把時間切成很多小時間，分給不同的人使用

packet switching vs. circuit switching

當使用者數量少時，circuit switching 比較好，傳輸會比較穩定，比較適合 “bursty” data（只在一段時間有傳輸），但會遇到當同時太多人使用，會需要考量 packet delay 跟 buffer overflow 的問題，所以需要設計一些辦法
當使用者數量多時，packet switching 比較好，因為不會因沒有搶到頻寬而需要長時間等待。

example

1 Gb/s link
each user:
- 100 Mb/s when “active”
- active 10% of time

Q: how many users can use this network under circuit-switching and packet switching?

circuit-switching: 10 users
packet switching: with 35 users, probability > 10 active at same time is less than .0004

1. Circuit-switching (電路交換) 的計算

概念：在電路交換中，每個用戶都必須獨佔一條固定頻寬的「circuit」。
計算：
- 鏈路總容量 = 1 Gb/s = 1000 Mb/s
- 每個用戶需要的容量 = 100 Mb/s
- 最大用戶數 = (總容量) / (每個用戶需要的容量)
- 最大用戶數 = 1000 Mb/s / 100 Mb/s = 10 users
結論：在電路交換下，無論用戶是否 active (active 10% of time)，系統都必須為他保留 100 Mb/s 的頻寬。因此，最多只能有 10 個用戶。

2. Packet-switching (封包交換) 的計算

概念：在封包交換中，所有用戶共享鏈路。只有當用戶「active」時，他們才會發送封包並使用頻寬。這利用了「統計多工 (statistical multiplexing)」的優勢。
問題：鏈路容量只有 1 Gb/s (1000 Mb/s)。如果超過 10 個用戶同時 active（例如 11 個用戶），他們總共會需要 $11 \times 100 \text{ Mb/s} = 1100 \text{ Mb/s}$ 的頻寬，這會超過鏈路負荷，導致網路壅塞。
目標：我們要計算的是：如果我們讓 35 個用戶 (N=35) 使用這個網路，發生壅塞（即超過 10 人同時 active）的機率有多低？

這是一個典型的二項分佈 (Binomial Distribution) 機率問題。

$N$ (總試驗次數) = 35 (總用戶數)
$p$ (單次成功的機率) = 10% = 0.1 (單一用戶處於「active」狀態的機率)
$k$ (成功次數) = 同時 active 的用戶數

我們要計算的是「超過 10 人同時 active」的機率，即 $P(k > 10)$。 $P(k > 10) = P(k=11) + P(k=12) + \dots + P(k=35)$

直接計算這個總和很複雜，所以我們計算它的補集（complement），也就是「最多 10 人 (含) 同時 active」的機率，再用 1 去減。 $P(k > 10) = 1 - P(k \le 10)$ $P(k > 10) = 1 - \sum_{k=0}^{10} P(k)$

二項分佈的機率公式為： $P(k) = \binom{N}{k} \cdot p^k \cdot (1-p)^{N-k}$ $P(k) = \binom{35}{k} \cdot (0.1)^k \cdot (0.9)^{35-k}$

我們需要計算從 $k=0$ 到 $k=10$ 的機率總和： $P(k \le 10) = P(k=0) + P(k=1) + \dots + P(k=10)$

（使用機率計算器或軟體計算）

$P(k=0) \approx 0.0253$
$P(k=1) \approx 0.0975$
$P(k=10) \approx 0.0007$

將以上機率相加： $P(k \le 10) \approx 0.99963$

最後，計算我們想要的「超過 10 人同時 active」的機率： $P(k > 10) = 1 - P(k \le 10) \approx 1 - 0.99963 = \mathbf{0.00037}$

這意味著，如果使用封包交換，我們可以讓 35 個用戶共享這條鏈路，而發生網路壅塞（即超過 10 人同時需要頻寬）的機率非常非常低（僅約 0.037%）。這就是封包交換相較於電路交換的效率優勢。

Cable based access

使用 同軸電纜 (coaxial cable) 來提供網際網路服務

須透過 Cable Modem Termination System (CMTS) 與 ISP 核心網路連接
傳輸速率取決於共享使用者數量與 ISP 分配的頻寬

Cable modem

透過 有線電視網路 傳輸

下行頻寬通常比上行大 (asymmetric)
頻寬較寬，但同一區域用戶需 共享頻寬 (可能發生擁塞)
實際速率取決於使用者數量與網路負載

DSL (Digital Subscriber Line)

利用 現有電話線 (twisted pair) 提供數據傳輸

每個使用者有獨立的「最後一哩」線路，不必和鄰居共享頻寬
須透過 DSL Access Multiplexer (DSLAM) 匯入 ISP 網路

ADSL (Asymmetric DSL)

下行速率 > 上行速率 (適合下載需求為主)
頻寬較小，但不會與同區使用者競爭
傳輸速率與距離有關，距離越遠速率越低

VDSL (Very-high-bit-rate DSL)

速率比 ADSL 快得多，但距離限制更嚴格
常搭配光纖到社區 (FTTC) 使用

Wireless access networks

透過 無線電波 提供存取

特性：傳輸速率與傳輸距離、頻率範圍存在權衡

Wireless local area networks (WLANs)

WiFi

Wide-area cellular access networks

3G, 4G, 5G, satellite

data center networks

high-bandwidth links 去連接很多的 server

data center

冷熱通道（舊型）新型通常用水冷式加上氣冷式（新型）如 H100

packets

把資料切成 L bits 的 packet，transmission rate R bps（不考慮其他 delay 的情況下）
packet transmission delay = $\frac{L(bits)}{R(bits/sec)}$ seconds

media

guided media

透過實體媒介傳輸，如 copper, fiber（光纖）, coax（同軸電纜）

Coaxial cable

100 Mbps

fiber

錯誤率只有 $10^{-9} ~ 10^{-12}$，速度快，10~100 Gbps

unguided media

透過無線媒介傳輸，如 radio，目前也有技術是會對指定角度傳輸增價速率跟降低耗電率

radio

錯誤率到 $10^{-3} ~ 10^{-9}$，速度慢，10~100 Mbps

internet core

forwarding

routing 會決定要走哪一條路（透過 routing algorithms），forwarding(switching) 會決定在 router 中要走哪一個 output link 來達成 routing 的決定

core network

internet

network of networks

ISP

Internet Service Providers(ISPs)
hosts 透過 access ISP 來連上 internet

global ISP

ISP 會再去連到 regional ISP，再去連到的 global ISP， global ISP 中間再去透過 IXP（internet exchange point）或是 peering point（兩家關係較好時）連接，不過因為同一家 ISP 中間連線處理的節點較 IXP 或 peering point 多，所以通常相同 ISP 的內部的連接會比較便宜。\

content provider network

跟 global ISP 同一層，像 google 這些，或是可以提供服務 archive 服務在上面的公司

performance

packet delay and packet loss occur(wire networks)

在 packet queue 中排隊會造成 delay，當 queue 滿了就會造成 loss

delay

processing delay

在節點處理封包的時間，包含檢查錯誤、決定路由等

queuing delay

在 queue 中等待的時間

a: average arrival rate (packets/sec)
L: packet length(bits/packets)
R: link bandwidth (bit transmission rate) (bits/sec)

traffic intensity $\rho = \frac{L \times a}{R} = \frac{\text{arrival rate of bits}}{\text{service rate of bits}}$

$\rho \approx 0$: avg queuing delay small
$\rho \rightarrow 1$: avg queuing delay large
$\rho > 1$: 幾乎是 infinity delay

transmission delay

把 L bits 的 packet 傳送到 R bps 的 link 上所需要的時間
= $\frac{L(bits)}{R(bits/sec)}$ seconds

propagation delay

在媒介中傳播的時間，取決於距離和傳播速度 = $\frac{length\ of\ physical\ link}{propagation\ speed\ in\ medium}$ 跟 transmission delay 不同

total nodal delay

$d_{nodal} = d_{proc} + d_{queue} + d_{trans} + d_{prop}$

end-to-end delay

traceroute

測試 delay 的工具，每次送出 3 個封包再往外一個 hub 然後接收回傳（但商用網路有時候不會回），重複直到到目的地（最多往外 30 個 hub）

loss

可能會由前面一個節點、來源重送，或是沒有動作。

throughput

從 sender 到 receiver 的 rate(bits/time)，要考量每個節點中間的傳輸量（取最低） $R_{Server}, R_{Client}, R$ 這三個通常是瓶頸

security

packet “sniffing”

在 broadcast 的網路去抓封包（Ethernet, wireless）

ip spoofing

去偽造 IP src

Denial of Service(DoS)

瘋狂送請求去塞爆某一臺流量

lines of defense

authentication

confidentiality

integrity checks

access restrictions

firewalls

layer

每一層都會加一個 header，可以從 header 判讀是跟哪一層溝通

application

$\rightarrow$message
supporting network applications
ex: HTTP, IMAP, SMTP, DNS

transport

$\rightarrow$segment
process-process data transfer
ex: TCP, UDP

networks

$\rightarrow$datagram
routing of datagrams
ex: IP, routing protocol

link

$\rightarrow$frame
data transfer between neighboring network elements
ex: Ethernet, 802.11 (WiFi), PPP

physical

bits “on the wire”

NTU Computer Network Ch.2 Application Layer

Mon, 20 Oct 2025 00:00:00 +0800

architecture

client-server paradigm

client 連到 server，不會直接跟其他 client 連線， server 始終上線，client IP 可能是 dynamic IP

peer-to-peer paradigm

client 直接跟其他 client 連線，不需要 server，也就是把兩邊皆作為 client 跟 server，會有 client process 跟 server process

Processes communicating

inter-process communication

same host 上的 process 互相溝通會用 IPC 來溝通，像是 pipe

different host

不同 host 上的 process 會用 message 來溝通

sockets

process 跟 transport layer 溝通的介面，用來把 message 跟 transport layer 收發

Addressing processes

每個 process 需要 identifier 去接收 message，所以會需要 IP address + port number

application-layer protocol defines

types of messages exchanged

request, response

message syntax

message format

message semantics

meaning of fields

rules

for when and how processes send and respond to messages

protocols

open protocols

HTTP, SMTP, FTP, DNS

proprietary protocols

Skype, Zoom

TCP service

reliable transport
flow control
congestion control
connection-oriented
does not provide
- delay guarantees, bandwidth guarantees, security

UDP service

unreliable transport
does not provide
- reliability, flow control, congestion control, timing, throughput guarantee, security, or connection setup

Vanilla TCP/UDP sockets

基礎的 TCP/UDP，沒有加密

Transport Layer Security (TLS)

加密 TCP，並在 application layer 實踐，有 data integrity（完整性），並且是 end-point authentication

RTT

一個 packet 從 client 傳到 server 再回來的時間

HTTP

overview

HyperText Transfer Protocol，client-server model，然後是 stateless protocol（不會有之前 request 的資訊）因為要 implement 很麻煩

stateful protocol

會有之前 request 的資訊，會要求一次做完，會需要在收到下一個 request 才會記錄 state

HTTP uses TCP

會向 server 的 port 80 發 request，並且 HTTP message 會在 web browser(client) 跟 web server 之間傳送

non-persistent HTTP

每個 object 都會開一個 TCP connection，下載完就關掉，每送一個 object 會需要 2 RTT（1 RTT for TCP connection, 1 RTT for HTTP request/response）
HTTP/1.0 預設是 non-persistent HTTP

persistent HTTP

在同一個 TCP connection 下載多個 object，全部結束後才關掉，所以最後會趨近 1 RTT（不影響中間丟的 message send/receive 數量）
HTTP/1.1 預設是 persistent HTTP

methods

POST

user input sent from client to server in entity body of HTTP POST request message

GET

include user data in URL field of HTTP GET request message (following a ‘?’)

HEAD

requests headers (only) that would be returned if specified URL were requested with an HTTP GET method

PUT

uploads new file (object) to server.
completely replaces file that exists at specified URL with content in entity body of POST HTTP request message

state keeping

protocol endpoints

從 sender/receiver 去記錄多個 transaction 狀態

cookies

在 HTTP message 的 cookie 去 maintain state

caching

web cache

example

access link rate: 1.54 Mbps
institutional network: 1 Gbps LAN
RTT from router to server: 2 s
object size: 100 K bits
average request rate: 15 / sec $\Rightarrow$ 1.5 Mbps

performance

access link utilization = .97 $\Rightarrow$ 接近 1 所以 loading 很重
LAN utilization = .0015 $\Rightarrow$ loading 很輕
end-to-end delay = Internet delay + access link delay + LAN delay = 2 s + minutes + usecs\

options

buy a faster access link(154 Mbps) $\Rightarrow$ 貴，end-to-end delay = 2 s + usecs + usecs
install web cache $\Rightarrow$ 便宜
假設 40% 的 request hit rate
60% 的 request 會到 server $\Rightarrow$ 1.5 Mbps * 60% = .9 Mbps
access link utilization = .9 / 1.54 = .58 $\Rightarrow$ 較輕
end-to-end delay = $0.6s \times 2.01 0.4 \times msecs \approx 1.2s$ $\Rightarrow$ 較輕

Conditional GET

當有 object 已經在 browser cache 裡面，但是不確定是不是最新的版本
送出 If-modified-since: <date> header，server 會回傳 200 OK 並傳送 data 或 304 Not Modified
HTTP/1.0 就有

HTTP/2

因為 HTTP/1.x 是 FCFS（first-come, first-served），所以會有 HOL (head-of-line) blocking 的問題，也就是當前面有一個很大的 object 時，後面的 object 都要等前面的傳完
減少 multipule object 的 delay，會把 object 切成 frame，在 queue 的 object 會根據順序傳送 1 frame 依序循環。

email

user 跟 mail server 用 SMTP protocol 連接，mail server 之間用 SMTP protocol 連接

mail server

會有 mailbox 存放 email，message queue 存放要寄出去的 email

SMTP RFC(5321)

用 TCP port 25，text-based protocol
會先建立 TCP connection，然後進行 SMTP handshake、 transfer of messages、connection closure\

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


// handshaking
S: 220 mail.example.com // service ready
C: EHLO client.org
S: 250 Hello client.org, pleased to meet you
// transfer of messages
C: MAIL FROM: <alice@client.org>
S: 250 alice@client.org... Sender ok
C: RCPT TO: <bob@mail.example.com>
S: 250 bob@mail.example.com ... Recipient ok
C: DATA
S: 354 Enter mail, end with "." on a line by itself
C: Do you like ketchup?
C: How about pickles?
C: .
S: 250 Message accepted for delivery
// closing connection
C: QUIT
S: 221 mail.example.com closing connection

mail access protocols

IMAP

Internet Message Access Protocol，用來從 mail server 去讀 email

HTTP

Gmail, Hotmail 就是用 HTTP 去讀 email

DNS

application layer protocol，而且是 distributed database（在很多不同的 name server 上面）
hostname to IP address translation

distributed, hierarchical database

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


graph TD
R[root DNS Servers]
C[.com DNS Servers]
O[organization DNS Servers]
E[.edu DNS Servers]
Y[yahoo.com DNS Servers]
G[google.com DNS Servers]
P[pbs.org DNS Servers]
N[nyu.edu DNS Servers]
R --> C
R --> E
R --> O
C --> Y
C --> G
E --> N
O --> P

會照順序從上而下找到 Root, Top-level domain, Authoritative 然後再去找到 subdomain 的 IP address
如 .com $\rightarrow$ yahoo.com $\Rightarrow$ www.yahoo.com

TLD

各個 TLD 擁有者有會有 DNS server

Authoritative

認證的 DNS server，organization 自己會有自己的 DNS server

local DNS

會 cache DNS 資訊一段時間（36 hr 之類的）
基本上都是沒有認證的 DNS，也不會算在 hierarchi 裡面
如臺大每個系所都有 local DNS server、ISP 業者也會有自己的 local DNS

iterated

先問 local DNS，當不知道就會得到說去問 root，在不知道就會從 root 得到去問 TLD…

recursive

問 local 找不到，local 會去往 root 問，然後再往下問，最後把結果回傳給 user，會讓 root DNS loading 很重

DNS records

都會記錄成 resource records (RR)，形式是 (name, value, type, ttl)
ex: (www.example.com, 192.0.2.1, A)
可以用 nslookup，搭配 set TYPE=<type> 以及 domain name 去查詢 DNS record

A type

name 是 hostname，value 是 IPv4 address

AAAA type

name 是 hostname，value 是 IPv6 address

CNAME type

用來找正式 domain name 的別名，name 是 alias name，value 是 canonical(real) name

NS type

name 是 domain，value 是 authoritative name server 的 hostname（如 ntuns.ntu.edu.tw）

MX type

name 是 domain，value 是 mail server 的 hostname（如 mail.example.com）

P2P

每個 user 都是 client/server\

self scalability

當新的 peer 加入除了增加新的 service capacity（容量）之外，還會增加 service demand（需求）

intermittent connectivity

peer 可能會隨時上線或下線以及更改 IP address，管理複雜化

usage

P2P file sharing (BitTorrent), streaming (KanKan), VoIP (Skype)

P2P vs client-server

假設 File size $F$, Server upload rate $u_s$, Number of peers $N$, Peer download rate $d_i$, Peer upload rate $u_i$

client-server

$\frac{NF}{u_s}$（Server 上傳 N 次 file 給所有 user 的時間）, $\frac{F}{\min(u_s, d_{min})}$（最慢的 user 下載完 file 的時間）
所以 total time $\geq \max(\frac{NF}{u_s}, \frac{F}{\min(u_s, d_{min})})$

花費時間根據使用人數成長曲線會是 linear

P2P

$\frac{F}{u_s}$（Server 上傳 1 次 file 給其中一個 user 的時間）, $\frac{F}{d_{min}}$（最慢的 user 下載完 file 的時間）, $\frac{NF}{u_s + \sum u_i}$（所有 user 上傳完 file 的時間，應該是 N-1 但就 approx）
所以 total time $\geq \max(\frac{F}{u_s}, \frac{F}{d_{min}}, \frac{NF}{u_s + \sum u_i})$

花費時間根據使用人數成長曲線會最後趨近一個值

BitTorrent

會把檔案切成 $256 Kb$ 的 chunks

tracker

追蹤所有 peers 在 torrent 內的資訊

torrent

group of peers 去 exchange chunks of a file

peer joining

一開始沒有資料，會慢慢從其他 peer 那邊下載 chunks，並且會去跟 tracker 登記並取得 list of peers，然後會去跟 list 中的部分連接（neighbors）

churn

peers 會隨時上線或下線

list of chunks

會用 bitmap 去記錄自己擁有的 chunks

exchanging chunks

會隨時可能換 exchange chunks 的 peer

requesting chunks

會去跟 peers 要 list of chunks，並且會去下載自己沒有的 chunks（從最少的開始下載）

tit-for-tat

只會上傳檔案給 top 4 peers for currently sending chunks，並且每 $10s$ re-evaluate 一次，然後每 $30s$ 會隨機選擇一個不在 top 4 的 peer 傳送檔案

這樣可以避免只上傳不下載的人，也可以間接得到 higher upload rate 的 peer

selfish/altruistic

當擁有整個檔案即下線的 peer 是 selfish，會繼續上傳給其他 peer 的是 altruistic

multimedia

video encoding

spatial encoding

只有在單張使用

temporal encoding

當前跟下一張去 encode

CBR

Constant Bit Rate，保持固定的位元率

VBR

Variable Bit Rate，根據影像內容的複雜度調整位元率，並去改 spatial 跟 temporal encoding 的量

streaming

encoding + DASH + playout buffering

continuous playout constraint

會希望 client playout time 跟原始的一致
但實務上會遇到 network delay 會變化（jitter）、pause、加速播放…

client-side buffering

會在 client 端預先緩衝一段時間的資料，以應對 network delay 和 jitter 的影響，確保播放的連續性和流暢性

DASH(Dynamic Adaptive Streaming over HTTP)

server

把 video 切成 chunks，每個 chunk 都會用不同 rate encode 去 encoding，不同 rate 儲存成不同檔案，方便選擇。並且會把檔案儲存在多個 CDN 內，在不同 chunks 也會用不同 URL 去處理

client

會根據網路去 estimates bandwidth，並選擇合適的 chunk 進行播放
並且根據 manifest file（會記錄每個 chunk 的 URL、duration、available bit rates）去下載一個 chunk（最符合 bandwidth）
而大部分決策都是在 client 端做的，包括何時 request、哪個 rate、哪個 server（有最高 bandwidth 的 URL）

CDN(Content distribution networks)

把多個資料 copy 分散在多個 geographically distributed sites

request content

server 會給 client manifest file，client 會根據 manifest file 去找 highest supportable rate，並且可能會因為 congestion 去改變 request rate/copies

OTT challenges

從 edge 端解決 congestion，要考量要把 content 放在哪裡，client 要從哪個 CDN node 拿，要用什麼 rate

NTNU OS Concurrency

Sun, 01 Jun 2025 00:00:00 +0800

thread

現代有些 GNU/Linux 可能沒有做 process，使用 thread implement

Process vs thread

	Process	Thread
Address space	different	share

thread 是用 stack 分開來做，heap 是 share 的

pthread

POSIX thread，很多程式語言都是用 pthread 去 implement 內部的 thread

problem

因為 share memory 所以會有 race condition，就要對 critical section 做好防護

x64 RIP register

mutual exclusion(mutex)

mutex 互斥，可以讓一個 thread 進入 critical section 時，其他 thread 不能進入
可以用 xchg 指令來 implement atomic check and set
要硬體才能去控制 context switch 的時機點，所以 atomic 要硬體實做

test-and-set

就是atomic 的上 lock（如 SP），如果不能上 lock 就會等到能上或是直接退出，實做是 spin lock，需要 hadrware-software codesign（hardware: atomic; software: policy）

1
2
3


test lock == 0
set lock = 1
# atmoic

spin lock

一直去 busy waiting 去 test（所以非 blocking）

spining(busy waiting)

如 SP

yielding

就是當確定拿不到就會 block 在那邊，在 schedule 到時，會放棄直接讓給其他 thread，直到拿到條件

sleep wile waiting

就是如 SP 所述，會在 block 在那邊，不會被 schedule 到，直到被 wake up

synchronization primtives

locks

相對 cv 比較 low level，但還是會搭配 cv 使用

condition variables

如 SP 所述，可以用 signal 跟 wait 加上 atomic 來實作

mesa semantics

簡單來說就是 while(condition) cv_wait，比較好實作會先送 signal 喚醒，再去 unlock，而醒來的會先確認 condition 是否成立，成立就進入 critical section，否則繼續睡。

hoare semantics

就是用 if (condition) cv_wait; critcal，且是 atomic 執行 cv_wait 跟 critical，中間不會 context switch 不好 implement

semaphores

可以用這個去 implement lock 跟 cv，會想用來解決 atomic execution, event ordering, producer-consumer
因為是在 thread，所以是把變數存在 heap 來在同一個 adress space 中 share

是藉由觀察某一個變數的操作，有 semaphore wait 跟 semaphore post

unnamed semaphore(memory-based)

就是在 heap 中的 semaphore，會用在 thread 之間的 communication，一般來說 unamed semaphore 不能跨 process，但也有可以用 shared memory 的 semaphore
在 sem_init 有一個 pshared 來決定是否可以跨 address space
也就是有 intra-process semaphore（same process）跟 inter-process semaphore（memory mapped）

named semaphore(file-based)

就是在 file system 中的 semaphore，會用在 process 之間的 communication，有 sem_init 等外，還有 sem_open, sem_close, sem_unlink 等，但就是會比較慢。
有 intra-process semaphore 跟 inter-process semaphore 的特性（for all seasons）

semaphore wait

S– (S is the semaphore variable)
the calling thread will block if S < 0

semaphore post

S++
wake up one of the blocking threads (waiting thread)

deadlock

P(deadlock) $\Rightarrow$ Q(necessory condition) not Q $\Rightarrow$ not P

necessary condition

circular waiting
hold and wait
only loker-holder can unlock
mutual exclusion

circular waiting

A waits for B, B waits for A
唯一在 lock 中可以改變的

hold and wait

hold 1 lock and wait for another lock

non-deadlock bug

atomicity violation

就是在對同一個 critical section 中不是 atomic 的，造成的 race condition

ordering violation

因為執行順序因為 context switch 而反了，造成的 race condition。如先 free 再去 allocate

share memory 在 fork 時還會對應到同一塊 physical memory，不會改，因為在 memory 所以所以會比 file I/O 快，但缺點是要用的需求比較複雜

NTNU OS Persistence

Sun, 01 Jun 2025 00:00:00 +0800

I/O Device

memory-mapped I/O
explicit I/O instructions

DMA(Direct Memory Access)

硬體去做 I/O 的時可以透過 DMA 來把 memory 搬到 I/O 中，不用 CPU 去做，可以用來減少 turnaround time

introduction to FS

process 開啟檔案會產生一個 file descriptor，OS 那邊會有 open file table（oft）紀錄被誰開啟跟對應的 inode，inode 會再對應到 file

Directory tree

就是從 root 的 directory 開始，下面可以連到 directory 或是 file

data vs metadata

metadata

i-node 包含了部分 metadata，裡面有 file size、owner、permission、time stamp、link count、data block address（man inode）所有非 data 本身但是為了取得檔案的資料都是 metadata，包括檔名，所以並非所有 metaadta 都在 inode

name types

regular、directory、symbolic

regular

創建時會有一個 link count 連到自己，當每多一個 hardlink 就會 +1 linkcount

symbolic

本身就是一個 file，應用情境如在 WSL 要從 linux 要去存 Windows FS 的 folder，這時後因為是跨 FS 所以不能用 hard link，這時候就會用 symbolic link，或是用在 directory 上。或是當 package manager 的 libary name 不同，或是沒提供，要自己去用時，可以用 symbolic link 去把它連到正確的地方

hard link

不能跨 file system 且不能用在 directory 上，因為會造成無窮迴圈，會把 link count +1

soft link

file system layout

HDD

每一圈就是 track，然後上面會被切成很多段的 sector，一個 sector 通常是 512 bytes，一個 blocｋ通常由 4 個 sector 組成（2 KB），然後可以分為多個 region（如 inode table、data region）

file system

superblock	i-node bitmap(i-bmap)	data bitmap(d-bmap)	i-node table	data region

bitmap 是用一個 bit 來記錄對應到的位置是 free 還是 used

open

open 會 parse path 去找到對應的 inode 然後生成 fd 並設定 open file table。不管接下來是要 read 還是 write 都會更新 inode，因為 read 也會更新 access time

hard disk time(HHD)

因為 hard disk 讀取很慢，比如說 7200 PRM 這樣最久 8.3ms 才能讀取到，所以需要軟硬體協做如 FFS

disk physical properties optimization(HDD)

可以把 inode 跟 data block 放在同一圈，這樣可以減少讀寫頭動的距離

FFS

把硬碟放資料的位置讓 I/O 時可以減少 seek time 但 SSD 就不適用

xv6 file descriptor application

example - pipeling

就是 pipe （ls | less）這個，會去用一個 ring buffer 來連接 input 跟 output，來達到 FIFO 的效果，並用 fd 去 access ring buffer as file， xv6 實作 command line 的 pipe 是把 fd 1 close 掉然後 dup(fd[1]) 去進行，非 dup2（stdin (fd = 0) 亦同）

ring buffer

在 pipe.c 的 pipealloc 有負責 ring buffer 的實作

pipe write

在 call write system call 時 OS 會檢查是 write 到 file 還是 pipe，來決定要用 write 還是 pipewirte 寫入。 pipewrite 有用 spinlock 來去防止 race condition

fd

在 file 基本上 fd 就是 file descriptor，processstat 裡面 ofile 這個 openfile table 的 array 的 index（見 proc.h）

implementation of write

先 lock 然後會寫到要寫的都寫進去，如果滿了就 wake up the channel 然後 sleep（會同時 release lock），然後等到有空位再去寫入，當有空間則會寫完並 wake up 並 release lock

sleep lock

channel

用來分辨不同 Lock 等待條件，當條件達成時要等的條件，然後當 sleep 時會去對自己的 process 狀態上 lock 再去 relase 指定的 lock 然後把自己的 channel 設定好，並且 stat 改成 SLEEPING，被 waked up 再去 unlock，爲了避免被其他 core 在 sleep 時去改變狀態
如果要 channel 是 unique 的話，multi core 的 channel 是 global，所以也會變成 critcal section，那要 implement 的話就很麻煩，所以就決定讓 channel 不一定得要 unique，就只是用來被叫醒的 interger ID，如果撞到的話被叫醒再去 sleep 就好。

context switch

當 sleep 時，會 call sched context switch 到 scheduler thread

sched vs scheduler

sched 會 context switch 到 scheduler thread
scheduler 會 context switch 當前的 thread 到 ready queue 的 thread

spin lock vs sleep lock

spin 雖然比較耗資源（busy waiting），但是不會遇到被永遠睡下去的問題

maintaining crash consistency

crash inconsistency

file truncate 當要縮小 file 時，需要做 update bitmap 去把沒用到的 data block 設成 free，然後更新 inode 的 addr 跟其他資訊，但是這兩個不是 atomic，所以萬一做一個然後系統 crash 會造成 space leak(更新好 inode 但還沒更新 bitmap)，或是 double reference（更新 bitmap 但還沒更新 inode）因為 bitmap 那邊是空的，所以其他也可以用到，這時就會有兩組 inode 有相同的 data block 的控制權

solution(logging/journaling)

把這兩個動作做成一個 transaction，從軟體面下手，先去寫接下來要做的計劃寫到 disk（log region），然後做完再去 commit 來把 transaction 標註為完成（加到 log 後面的一個 block），當 reboot 時，就把沒有 commit 的 transaction 做一遍，但不保證不會 data loss

xv6 implementation

只有一組 transaction，不過是 group transaction 放在 log region，整組裡面有一塊 header 區塊，標注後面的 transaction 的數量（包成一個 group transaction 一次操作，裡面有很多個 system call 的步驟），然後完成一個後就會 + 1，這樣就可以從第 i 個 transaction 開始復原，做完就會 commit 把 group transaction 清空

run in xv6

有一個 global 的 number of outstanding system call 用來記錄寫入，當開始寫入就 +1，完成後 -1，當歸零可以知道沒有任何 thread 在寫入，這時候就會去 log commit(log.c: start\op & end_op) 清空 log，不同 thread 也會在同一個 log 裡面，就是裡面步驟可以是不同的 thread 對不同檔案操作。

in hardware

有一塊 memory 作為 block cache(bcache) 對應到 disk 的 block，在 xv6 中確保一定是 1 to 1，一個 memory cache block 不論 readwrite 只會對應到一個 disk block，來確保 consistency，如果在 log write 時發現這個 block 已經在 log 的話就會只更新那個 log 來增加效率

file descriptor	pathname	directory	inode	logging	buffer cache	disk

buffer cache

也就是一個有 buffer structure array，裡面是用來放 linked-list 的 node ，來讓 buffer 這個 linked-list 不用 allocate ，然後也有一個結構是會指向 LRU 的 head 然後有一個 head 作為 dummy node

1
2
3
4


bget
bread
bwrite
brelse

有這些可以對 buffer 進行操作

bget

會去檢查 buffer cache 裡面有沒有這個 block，如果有就直接回傳，沒有的話就會去 disk 上面讀取，然後放到 buffer cache 裡面

bread

會 bget，然後會把 buffer cache 的內容 locked 後 return

bwrite

會把 buffer cache 的內容寫入到 disk 上面，最好要對 locked 的 buffer cache 寫入

xv6 virtual memory

high-radix tree

EXT	L2	L1	L0	offset
25	9	9	9	12

L2 L1 L0 是用來構成 high-radix tree，用來切個第幾大塊的第幾小塊的哪一塊（L2 大 $\rightarrow$ L0 小），也就是分成三層去 index，當該分層的沒有用到，就可以不用寫到 disk

要確保每個 Page Directory 大小要跟 page table 對齊，所以 4KB，造成 12 bit 的 offset，所以 39 - 12 = 27，

satp register

裡面有一塊就是 PTBR

PDE

在裡面有 PPN 跟 flag，用來表示是不是最後結果跟其他資訊，flag 因為儲存資訊的關係，會是 10 bit，然後因為會是 8 byte (64 bit) 作為總長度，$4KB \div 8B = 2^{12} \div 2^3 = 2^9$，所以 L2, L1, L0 都是 9 bit

PPN	flag
44	10

PTE

PPN	offset
44	12

$2^{56}$ = 64 PB，所以 xv6 的 physical memory 最大可以用到 64 PB

SV39 in RISC-V

在 RISC-V Address space 是 39 bit，也就是 2^39 = 512 GB

NTNU OS Virtualization

Mon, 07 Apr 2025 00:00:00 +0800

memory virtualization

現代因為安全化的關係將 variable 在 vm 的 address 隨機化，ALSR
可以用 setarch 來模擬沒有 ALSR 的程式

1

setarch $(uname -m) --addr-no-randomize <program>

但不同 process 的 vm 是「理論上」分離的，且不能存取其他的（詳見 SP Process control）

CPU Virtualization

用 context switch 來可以多個 process 共用

mulitasking

ready state (Ready queue)
running state
blocked state (Event queue) Blocked state 是透過 DMA 這個元件去處理 I/O
SP p.43
沒在做事時就會把 idle process

Process in CPU

direct execution

直接在 CPU 去進行執行

problems:

如果當 process 在 CPU 跑，可以直接獲取 CPU 的完整控制權
要如何去切換到其他 process

可以用 restricted operations 解決第一項，用 context switch 解決第二項

mechanisins(how to choose) => restricted operation & context switch
policyes (which process to choose in ready state) => algorithm

restricted operation

user space & kernel space

mechanisins

example-RISC-V

user mode(U-mode)
supervisor mode(S-mode)
machine mode(M-mode) S-mode 跟 M-mode 都可以跑 instruction，U-mode 則是不行

CSR register(mstatus)

其中兩個 bit 是紀錄權限（MPP）

U-mode 00
S-mode 01
M-mode 11 同時也是 privilege 的排序

space

U-mode 都在 user space
另外兩個都在 kernel space
當需要控制硬體時就會去進到 kernel mode When the system boots up, it will run entry.s to initialize the stack pointer, then run start.c, sets some bits of the mstatus register (such as setting MPP to supervisor mode (0b01)) to allow the mret instruction to trap and return to supervisor mode. It also sets the mepc register to the address of the main function. So start.c will use mret to trap into supervisor mode and run main.c. In main.c, it will initialize various subsystems, including memory paging, process table, inode cache, buffer cache, etc. It sets the epc register (program counter) to 0 (initial user PC) and also sets the stack pointer. Then it calls the userinit() function to set up the environment of the init process in user mode. Finally, it runs scheduler() to become the scheduler process and let the system run the first user-space process, init process.

boot-up

一開始會是 M-mode，然後會跑開機的 machine code 來 Introlization 跟重要的 table
接著會設定 CSR 提升到 S-Mode
然後會去跑第一支程式接著會去 raise mstatus MPP 到 U-mode

在 boot-up 完第一個跑的 U-mode 程式是 shell

system call

如 SP 所述
System call 就是個功能讓 User mode 可以存取 kernel mode 的功能

trap

save state(PC, registers)
raise privilege level
jump to correct kernel code

return:

lower privilege level
reduce states of calling process
jump back to PC after trap in user code

exception vs interrupt

exception 是 sync，錯誤產生的中斷
interrupt 是 async，外部要求

switch in diffrernt process

Process A trap in system
call switch() to Process B(context switch) 同時也會把 kernel 狀態存起來
return from trap

kernel space

直接控制硬體

policy(schedualing)

Performance metrics
schdualing policies (algorithm)
- FIFO
- SJF
- STCF
- RR
- MLFQ

assumptions

set of processes all arrive arrive at once.(所有 process 同時抵達)
each just use CPU
each has some execution time
know execution time

turnarround time: time process start to finish
turnarround time > execution time(CPU time)
response time: time process start to start execute

alogrithm

這邊都是不考慮 I/O time，所以 I/O 要不要 context switch 是看 implementation
Linux implent 可以看 sched 的 manual

FIFO algorithm

如其名，First in First out，執行完才會換下一個
在執行時間差很多的情況，很容易造成平均時間增加（因為後方要等待較長執行時間的 process 的 turrnarround time 也會被拉長

SJF

Shortest-job first
因為是照著執行時間排序，所以這會是 average trunarround time 最短的演算法
但是在 arrive time 不同的情況下，如果先跑到執行時間長的 process，中途來執行時間比較短的 process 會造成 average turnaround time 上升

STCF

shrotest time-to-complete first
就是有 process 進來就比較執行時間看要不要 context switch

RR

Round Robin
就是用 time slice 的 algo
amotise（均攤），time slice 要設定多少，會決定 responce time 跟增加的 context switch 時間

MLFQ

Multi Level Feedback Queue
通常是 framework，可以根據上面的演算法去細調其中一個想法

Idea: start with RR
- 分成多個 waiting queue，然後會從高 priorty 到低 priorty，當被從 running state 踢出時就會降低他的 priorty 丟到較低 priorty 的 queue，跑一段時間就會 reset 來把所有 process 丟回 high priorty 的 waiting queue

lottery scheduling

example:

Process A (40% CPU time)
Process B (60% CPU time) draw a lot(抽籤) 如 0~100，在每個時間抽個籤，如果是 40 以下就去跑 A，否則跑 B，當有新的 process 進來就重新分配比例然後繼續抽籤
實作中可以用 linklist 來編號出每一個點，然後抽到哪個點就可以知道是要跑哪個

stride scheduling

devide a large number by the number of ticketd for process
然後從距離起比較近的去做 example:

Process A (40% CPU time)
Process B (60% CPU time) A: 3600/40 = 90
B: 3600/60 = 60
A 每次跑走 90，B 每次跑 60
A(60) => B(90) => A(120) => B(180) => A(180) => A/B

performance matrics

proportional share(fairness)

分配不同重要程度的 CPU resource/time usage

Memory Virtualization

motivation

easy to use

mechanism

address space P1(base 1024 for physical memory)

1

ld 100, r1

address = base + offset = 1K(1024) + 100 = 1124 P2(base 2048 for physical memory)

1

ld 100, r1

address = base + offset = 2K(2048) + 100 = 2148

if P1 want load 1200 to read P2’s Virtual memory，OS will know because of the address out of P1’s range

會有兩個 register 一個存 base，一個存 bound，當 context switch 時就會存到 PCB 中

strategy

segmentation

不用太注重細節，因為現在沒有人在用
把 memory 分成不同的 segment，每個 segment 有自己的 base & bound，用 index 來存取
internal fragmentation：當 memeory 的某 page 塞下某個 process 然後還有剩餘的空間
internal fragmentation：當 memeory 的 pages 剩下的空間小於能使用的部份

bast fit
- 找當前剩餘空間最小且可以放入目前 segment 的 memory pages
worst fit
- 找最多空間得來放入
first fit -找到第一個有辦法某塊 segment 放入的 memory，用 data structure 如 link-list 搭配演算法來去找哪個 segment 最適合放入

paging

PMP(Physical memory Protection) register，會存 page bundery，然後有多個 register 存 page table 如果要存取某一塊 page 就會找那個上下的 PMP regiser，一個作為 base，一個作為 bound
這樣就可以達到 Physical memory Protection
每一塊 fragment 都是一樣大小的 page

memory paging

address translation

會有 valid bit 來判斷這個 page 是不是有被使用，沒有使用就會被設成 invalid(0)，可以省空間。

part of Hardware involvement

extract VPN from virtual address (fast)
compute address of PTE using PTBR (fast)
fetch PTE (slow)
exract PFN and form physical address (fast)
fetch physical address to register (slow) 這樣看起來會比 Base & Bound 慢，因為 Base & Bound 只需要一次 fetch，但是 paging 需要兩次，但是可以用 cache 來解決

part of OS involvement

new process
grow process
process termination
context switch(update PTBR)

example

example: 64 byte Address space, 16 byte pages
Virtual page

Adress Sapce	address	VPN(Virtual page number)	offset
code	0(16)	0	0~15
data	16(32)	1	16~31
	32(48)	2	32~47
stack	48(64)	3	48~63

PFN == Page Frame Number == Physical Frame Number
physical memory

Physical memory	PPN(Physical page number) / PFN (Physical frame number)
	0
code	1
	2
heap	3
	4
stack	5
	6
…	…

Content in the virtual page(VPN = 0)

每個 virtual page 需要 4 bits 來表達地址（2^4 = 16）
所以 64 byte 的 address space 需要 6 bits
在 VPN = 0 所以前兩 bits 是 00
後面 4 bits 是 0000 ~ 1111，所以 16 個 address
也就是

VPN
- Virtual address 前兩個 bits
offset
- Virtual address 後面 4 bits

translate VPN to PFN

VPN = 0 => PFN = 1
VPN = 1 => PFN = 4
VPN = 2 => invalid
VPN = 3 => PFN = 5

mapping table in risc-v:

VPN	PFN	otherinfo(3 bits for rwx (PTE(page table entry)) in risc-v)
0	1	5
1	4	7
2	invalid	0
3	0	7

1

load 17 R1

17 = 010001
=> VPN = 1, offset = 0001
in page table |1|4|7|
=> PFN = 4
=> physical address = |PFN|offset| = |0100|0001| = 65

TLB(Translation Lookaside Buffer)

TLB content

VPN	PFN	other bits	valid bit	ASID(address space)
1 (process 1)	A	..	1	1
1 (process 2)	A	..	0	2

TLB 的 valid 跟 Page Table 不同（是 allocate 好了的意思）
TLB 的意思是其他人可寫入，減少清空的時間（1 不可用，0 可用）

extract VPN from VA
check TLB a. have value Valid mapping(TLB hit) (1). fetch PFN form TLB and form PA (2). fetch PA to register b. don’t have valid mapping(TLB miss) (0). raise some expception trap into OS (1). use PTBR to locate PTE (2). fetch PFN from PTE (3). update TLB with translation info (4). retry the local instruction

locality

temporal locailty: 短時間內會動到同樣的位置
spatial locality: 附近的位置會被再次存取
因為 programer 的習慣，TLB 會很有效 amotized analysis（均攤複雜度）後會很有效

OS involvement

空間不足時需要清掉
context switch VPN 就不同，需要移掉

flush

當空間不足，會需要清掉

memory size affect

32 bit 電腦因為 register 只能存 4GB 的位址（4 * 2^30），所以 Physical memory 會最多 4GB

example

32 bit address space
32 bit computer

why not 8 bit AS

因為這樣最多只能放 256 byte 的 data

然後 4KB page（經驗法則）
offset 是 12 bits（4KB），20 bits VPN(32-12)
也就是會有 2^20 個 page = 1M number of virtual page
1M * 4 (for 32 bit int -> 4 byte)
=> per process need 4MB for page table 我們這樣 500 個 process 就要 2GB 用在 page table => 需要改善

MiB vs MB

MiB 是 (Mebi byte) 中間 i 是代表 binary
雖然說應該要用 MiB 但是 MB 比較好稱呼，所以通常就默認 define MB MiB

linear page table

每一個 address space 的 virtual page 都會有一個 physical page

multi-level page table

把 page table 切成多個 unit，當那一塊 unit 沒有被使用就不會存到 memory 中
（unit number != page number）現在第一個步驟不是 PTBR 了，會先去 page table directory，然後再去 page table
然後不用 PTBR 而是用 page table directory 的 base address，稱作 PDBR(Page Directory Base Register)

簡單來說就是前面的 page number 現在可以分成好幾塊，第一層是第一個 page directory 去獲得下一層 page table 的位置，最後一層是 page table 裡到指定 memory page 的位置，概念就像是 multi-level 的 i-node table。然後 page table directory 還是有 valid bit 來判斷是否有被使用

PDE addr = PDBR + (PDE index $\times$ size of PDE)
PTE addr = (PDE.PFN « (SHIFT)) + (PT index $\times$ size of (PTE))
PA = (PTE.PFN « (SHIFT)) + offset

也有 valid bit，用來判斷該 entry 對應到的 page table 裡的 page 是否有被使用。

功能是因為每個 page 都需要有 page table，而光是花在 page table 就會需要很多空間。不過用這個方法就可以省下那些閒置的 page table，又因為是第二層或更多，所以所需要的數量就更少。

page table directory

PDBR=6

valid	PFN(Page Frame Number)
1	7
0	-
0	-
1	10

page table PFN = 7

VPN	PFN

example

32 KB Adress space
64 byte pages
4 byte PTE

$32KB = 2^{15} = 15 bits$
15 - 6 = 9 bits for VPN
$2^9$ virtual pages = 512
page table size = $512 \times 4 = 2^{11}$ = 2KB
number of page table entries = $2^{11} \div 2^{6} = 2^5$
$\Rightarrow$ page dir index = 5 bits
$\Rightarrow$ PT index = 4 bits
$\Rightarrow$ offset = 6 bits

VA(15 bits)

VPN (page dir index) (5)	VPN(page table index) (4)	offset(6)

-> page dir index -> Page table dir

Adress space


VA

phy memory




PA

page table

VPN	PFN	page table unit
0	1	1
1	5	1
2	4	1
3	2	1
4	3	2
5	9	2
6	8	2
7	7	2
8	10	3
9	11	3
10	6	3
11	15	3
12	12	4
13	14	4
14	13	4
15	16	4

page table directory
PDE(Page Directory Entry) 整欄

valid	PFN
1	1
1	2
1	3

memory replacement

mechanism

Hard Disk 會切一塊給 OS manage 的 swap space

PFN	Phy memory
0	$P_2$ $VPN_0$
1	$P_1$ $VPN_2$
2	$P_2$ $VPN_3$
3	$P_1$ $VPN_1$

Block	swap space in HD
0	$P_2$ $VPN_1$
1	$P_1$ $VPN_0$
2	$P_2$ $VPN_2$
3	$P_1$ $VPN_5$

extract VPN
check TLB for VPN a. hit (1). fetch PFN from TLB form PA b. miss (1). caculate addr for PTE (2). check is in hard drive in PTE

PTE

PFN	valid	prot rwx	present

way handle page fault

1
2
3
4
5
6


PFN = FindPhysicalPage()
 if (PFN == -1) # no free page
 PFN = evictPage() # kick out some page from memory
DiskRead(PTE, DiskAddr, PFN)
PTE.present = 1; PTE.PFN = PFN
RetryInstruction() # give a TLB miss

就是如果去 page table 裡面找 target page，valid bit 是 0（page fault）且 phyical memory 滿了，就會去把一個 victim page 從 physical memory 踢到 disk（evict page），然後把要找的 target page load 到 physical memory 中，把 Page table 的 target page 的 valid bit 設為 1，victim page 的 valid bit 設為 0。
然後 evict page 是如果 victim page 的 dirty bit 是 1（不在 disk 時有被改過，像 code 就會是 0）就會把 victim page 去寫回 disk，可以減少 I/O time

page-buffering algorithm - water marking

會有 watermark 分別是 Low, High 來標註 memory 使用的程度
當 memory 使用超過 High watermark 就會開始 evict page
當 memory 使用超過 Low watermark 就會開始 evict 一些少用的 page
用來降低 page fault rate

policy

view point

conception framework of page replacement

phy mem $\xrightarrow{backup}$ swap
phy mem $\xleftarrow{cache}$ virtual mem

AMAT (Average Memory Access Time)

AMAT = (Time for cache hit) $\cdot$ (probability of cache hit) + (Time for cache miss) $\cdot$ (probability of cache miss) = $T_M + P_{miss} \cdot T_D$
D for disk
if $ \begin{aligned} T_M = 100 \text{ ns} = 10^2 \text{ ns},\ T_D = 10 \text{ ms} = 10^7 \text{ ns} \end{aligned} $

if miss rate = 10 % $\Rightarrow$ $P_{miss} = 0.1$
AMAT = $10^2 + 0.1 \cdot 10^7 \approx 1ms$
now if miss rate = 0.1 % $\Rightarrow$ $P_{miss} = 0.001$
AMAT = $10^2 + 0.001 \cdot 10^7 \approx 10^4 ns$

不過如果換成 SSD 可以降低 $T_D$ 25 % 到 50 %

Belady’s anomaly

理論上應該 miss rate 會隨著 cache size 增加而減少，但在某些演算法的特定情況下，會出現 miss rate 增加的情況

optimal

理論上的演算法，就是會去把最久沒有被使用的 page 踢出去
example 中，hit rate = 6/11，miss rate = 5/11，
但是大部分情況基本上不知道未來的狀況，除非有特別去預測
會被視為最佳的情況，用來比較用

FIFO

新開一個 replace queue，紀錄 page 進入的順序，當 memory 滿了就會把最早進入的 page 踢出去

secode-chance

為了記錄最近使用的 page，又不想新增太多空間，會在 PTE 有一個 use bit
硬體：每次使用就會去把 use bit 設為 1
OS： lazy approach: if use bit = 1, clear bit = 0 increase the the clock pointer; else evict the page, set dirty bit
就是跟 FIFO 很像，但有一個 use bit(referece bit) 來記錄最近使用的 page。會去從最舊的開始找，如果 use bit 是 1 就會把 use bit 設為 0，然後把 clock pointer 往下移（移到最後面），然後繼續找，如果 use bit 是 0 就會把那個 page 踢出去，當跑完一圈還沒有找到就重新跑一次，這次就會找到。
也會去在一段時間把所有 use bit 清掉重來

random

就 random 選擇一個 page 踢出去，有時候會有效率

LRU(Least Recently Used)

把最久沒用到的 page 踢出去
沒有 Belady’s anomaly（因為 n - 1 的會是 n 的 subset）

count implementation

每個 page 有一個 counter，每次使用就會把 counter 設成 clock
當 memory 滿了就會去找 counter 最小的 page 踢出去
但這樣需要遍歷 page table，所以會很慢，而且如果要紀錄時間，會需要精度很高，所以空間需求很大

stack implementation

用 link-list stack 來記錄最近使用的 page，每次使用就會把用到的 page 放到 stack 最上面
當 memory 滿了就會把 stack 最下面的 page 踢出去
會需要 6 pointer 的轉換，有點慢

LRU-aprrox implementation

當有被用到時，就把最前面的 bit 設為 1，指定每幾次操作進行一次 »，然後有指定紀錄的是幾個 bit，當 memory 滿了就會去找數值最小的 page 踢出去。
1, 5, 7, 2, | 4, 5, 3, 2

page number	reference bit (t=0)	reference bit (t=1)
1	1000	0100
2	1000	1100
3	0000	1000
4	0000	1000
5	1000	1100
6	0000	0000
7	1000	0100

counting-based replacement algorithm

LFU (Least Frequently Used)

LFU 會去找最少使用的 page 踢出去，但是會有一個問題，如果有一個 page 一直被使用，但是在某個時間點不再使用，但是因為一直被使用，所以 counter 會一直增加，所以會一直被留在 memory 中

MFU (Most Frequently Used)

MFU 會去找最多使用的 page 踢出去，效果並不好，因為在 temporal locality 的情況下，會一直 miss

locality

temporal locality: 最近使用的 page 會在未來被使用
spatial locality: 附近的 page 會在未來被使用
這兩項可以增加 hit rate

example

4 VPN, 3 cache entries(phy mem)

page fault(not in cache yet)

time line from top to down

page access	hit / miss(page fault)	evict	resulting cache state
0	miss	-	0
1	miss	-	0 1
2	miss	-	0 1 2
0	hit	-	0 1 2
1	hit	-	0 1 2
3	miss	2(optimal)	0 1 3
0	hit	-	0 1 3
3	hit	-	0 1 3
1	hit	-	0 1 3
2	miss	3(optimal)	0 1 2
3	hit	-	0 1 2

policy 就會在丟進去時，原本的已經滿了，會要決定要丟哪個 page 在 loop 中 LRU 跟 FIFO 都沒有用，因為會在回去之把第一個丟掉，所以會一直 miss

NTU SP Chapter 00 - Introduction

Sun, 15 Dec 2024 00:00:00 +0800

ISA Instruct/kereerererererion Set Architecture 用來在 Machine Language 跟 microachitecture 溝通
作業系統主要是用 C 寫的
以前的 OS 是用組合語言寫的，為了可以對應到不同平臺
廣義的系統程式包含 OS, Compiler, Editor, Command interpreter

kernel 指的就是作業系統

system calls 就是 API 用來從 application 跟 OS 溝通
要用 system calls 來跟 kernel 溝通
POSIX 是在訂定 system call 規定

gcc -Wall 很重要（但習慣 -Wall -Wextra）
system call 主要就是 call OS 的 function
不同 OS 有相同的 system calls 的標準，就是為了 application layer 可以跨平臺

function call vs. system call

porcess

一個執行檔執行下去就是一個 process，process 就會吃資源，而在同一 process 就會有一樣權限

function call

可信度在 User 跟 function 相同，因為在同一個 process

system call

在 call 的時候會跳到 OS 那去執行 OS 的程式
OS 的 function 是可信的，但 User 不一定，因為 OS 不可信就不該用那個 OS
OS 權限比較高，但 User 碰不到（只有 OS 直接碰得到硬體）
資源基本上就是 OS 給的權限

mode

OS 基本上就是要有至少兩個 mode 可以區分權限
如 non-privileged(User mode) & privileged(kernel mode)
而 User mode 會要分離不同的 User 存取權
User mode 不能存取其他 process，只能存取 user space

mode switch

平常就在 User mode
System call 會進到 kernel mode 然後檢查權限，有則執行，無則丟回 User mode

space

在 user mode 跑的 process 可以 access 的記憶體就是 user space，不論在記憶體的哪
只能在 kernel mode 可以 access 的 space 是 kernel space

malloc 是 call sbrk 來進行 memory 的操作

User CPU time 是指說在 User mode 所在 User CPU 執行的時間，會比較快
Sys CPU time 是在 kernel 那邊 CPU 執行的時間
Real time 是在從 enter 按下去到跑完的時間，>= User + sys 因為有 I/O, be forked & exec

System call 在 UNIX 會做適當的保護，所以不會因權限提升造成 crash

有時候優化可以去看 CPU time 是否造成執行時間是否過長可以用一些 system function 來減少 CPU 的浪費

在 C system call 是從尾端的參數開始 push，然後才 call，接下來丟到 register，然後 trap（中斷），接下來儲存狀態來預備 rollback ，之後切到 kernel mode，接著進行檢查權限，再進行執行，接著 return 回 User mode，所以吃的資源比較多，接下來 return 後就從 stack 裡 pop 掉
C 有些 function 就是提供 system call

OS

垂直面

負責提供 interface 使得可以比較可以容易操作
擋住麻煩的部分使得可以安全的執行及提供服務

水平面

管理資源包括 CPU, memory, I/O device…
管理程式使用資源的時間（CPU）以及空間（memory）

Service for Application Programs

user identification, process management, memory management, inter-process Cummumication, Signal, I/O Management(Terminal, Network…)…

OS Kernel

CPU Scheduling, Virtual Memory, File System, Protection, Security, Synchronization, I/O Control…

Unix Architecture（結構）

user interface	users
system call interface	Shells, Compilers, Application programs, …
UNIX Kernel	CPU scheduling, signal handling, virtual memory, paging, swapping, file system, disk drivers, caching/buffering…
Kernael interface to the hardware	terminals, physical memory, hard disks, printers…

NTU SP Chapter 01 - Services for Application Programs

Sun, 15 Dec 2024 00:00:00 +0800

User Identification

Logging in

記在 /etc/password
每個 row 代表一個 User，第一項是 user name，第二個是 password，第三個是 user ID，第四個是 main group ID,，第五個是 comment，第六個是 home dir，最後一個是 shell。

1

root:x:0:1:Super-User:/root:/bin/bash

UNIX 下認 ID 不認 name
可以用 finger 來看 user 資料
以前 /etc/password 是有放 hash 後的密碼
現在因為安全性問題不存在那，並且有些工作站為了方便，會存在 NIS DB 以方便同步密碼

可以使用 passwd 來改密碼

帳號可以不去用 shell，把它設定為 Null 或 None，又或是設定成 no login 只用來設定權限使得可以指定好定程式所需權限，用 su 來附加到指定的 user 上

密碼是用時間產生 salt bit 加進去 crypt() 後再把 salt bit 加到最前面再存起來
避免可以透過改自己密碼來去對應
UNIX 密碼是 13 個字元，前兩個是 salt bit

Process Management

一個 program 可以跑一堆 process，process 有自己的 pid，可以用 ps top 看

CPU scheduling

一個 CPU core 可以跑一個 process，不同 core 可以 share memory
nice 指令在 n-user 可以調低 process 的優先度，root 才能任意調

multitasking

為了使 response time 不要有一些 process 出現有太久的情況，所以在 CPU 夠快，可以一個處理完一部分再處理一個，中間沒感覺有跑到其他程式
第一步是先進到 ready queue
ready queue 要在要執行的在 memory 才會進去，否則就是在 event queue 去排 event(I/O) 的處理
整個 loop 就是 Ready Queue -> CPU -> (Time Slicie（吃太久 CPU，超過 time slice）) / (Event Queue -> Event) -> Ready Queue

Context Switch (*)

context switch: CPU 在換人執行的過程，儲存或恢復執行的狀態，在 kernel mode，問題有時候會出在這

state

Ready State: 在 CPU 執行的時候，離開會因為要 Exit、超過等待時限，要跑等待 Event 這種跑比較慢的部分
Block State: 在 Event Queue 的狀態
Ready State: 在 Ready Queue 的狀態
（start 跟 exit 有時候也會當成各一個 state）

Shell

也是一隻 Process，shell process 再吃到指令時會去 fork 出一個 child process，而 parent process 會 wait child process exit，若沒有 wait 則會有很多 zombie process
process 會像一個樹，最上面是 init 的 process

Common UNIX Shells

Bourne shell
- /bin/sh
- Bell Labs
C shell
- /bin/csh
- Berkeley
- Commmand-line editing, history, job,control,…
KornShell
- bin/ksh
- successor of Bourne shell
- Commmand-line editing, job,control,…

pipe

| 把 stdout 轉到 stdin 接著跑另一個
通常會在 pipe 後面加入 filter command 如 more, grep
more 可以把輸入分頁

Memory Management

access 到的基本上都是 virtual memory，每一個 process 都有自己的一塊 virtual memory
系統會在 virtual memory 處理 call stack 跟 heap 還有 initialized，而之後會在 ch7 說明

File/Directory Management

Dir 都是一個樹

File Permission

Filtype-Permissions	X	Owner	Group	Size	ModifyDate	FileName
lrwxr-xr-x	1	test	user	18	Aug 28 13:41	home -> /usr/people/maria

FIleName 有 -> 是連結
Permision 前三個是 Owner 中三個是 Group 後三個是 Other 的權限

chmod 其實是有四個區塊，但第一個是有關 security (set-UID, set-GID, sticky bit)

mode switch 只會在 system call 出現
mode switch 跟 context switch 完全不相關

multitask 會因為造成了多次的 context switch 所以會比 unitask 還要慢

NTU SP Chapter 03 - File I/O

Sun, 15 Dec 2024 00:00:00 +0800

ANSI C

在跟作業系統無關，希望在各個 OS 都可以運行的

POSIX

通常跟作業系統有關，希望可以在各個 OS 可以動

Unbuffer I/O

不是沒有 buffer 的 I/O，每次都會進行一次 system call，是沒有在 C lib 幫忙 allocate 的 buffer
call read 到 kernel 然後如果沒有在記憶體就到硬碟拿，每拿一次都要 trap in system

HDD

track 是每一個碟盤中內部儲存資料的一圈結構，裡面由 sectors 組成，而數個 sectors 組成 cluster
cost 最高的是讀寫頭的運動（seek time）
轉的可以很快所以影響不是最大（Rotation Latency）
因為只為了一個 byte 去進行讀寫頭的移動跟 disk 轉動 cost 太大，所以一次做至少要一個 block（數個 cluster）

SSD

也是一個 block 一個 block 在讀
但最小單位是更小的 page
但寫入在 page 上 cost 很高，因為除非那個 page 沒資料，不然要把整個 block 清掉，所以通常開一塊新的然後 mapping

buffer cache

也是一塊記憶體
把 read 過的東西，讀完後先在 kernel 存在 buffer，之後如果需要就不用進行一次 I/O（太花時間） read 執行步驟：先 call read system call ，因為一開始為在 kernel 的 buffer cache 什麼都沒有，所以就去硬碟讀，之後放到 buffer cache，接著 copy buffer cache 的資料到 memory，接著 retuen N（讀到的 byte 數），之後如果 buffer cache 有就會從那邊拿，所以即使 trap in system 也不一定會碰到 disk，所以這樣從 buffer cache 拿不需要 context switch

per FILE object	per process	kernel(only one)	disk
buffer I/O	unbuffer I/O	unbuffer I/O	unbuffer I/O
FILE * fp file object(file descriptor, buffer（unbuffer 指的 buffer）) C standard I/O lib.	Open file desc. table	Open file table, i-node table, buffer cache	disk

meaning

unbuffer I/O 因為那些 I/O, API 沒有 C Lib 幫程式 create 的 buffer

UNIX 裡所有都視為 file
在一開始就有把 stdin stdout stderr 開好了
處理 file descriptors

open file desc. table

預設會從 parent process 繼承，所以基本上長得很像，是位在 kernel mode 且是每個 process 分開

open file table

open file table 只要每 open 一次就會有一個 entry
被指到一次就會 + 1，歸零就會消失
content 會存在 buffer chache
Reference Count(RC) 在 Open file table 跟 i-node table 裡的每一項都有，紀錄被指到的地方，當歸 0 就把他砍掉

buffer I/O 是只說不用 trap in system，不用 system call 的處理，如 C 的 fread，所以速度更快
virtual memory 有 user space 跟 kernel space

file desc

最開始的 file descriptor 一般會是 3，因為 0 1 2 是 stdin stdout stderr（約定成俗）
最多開到 OPEN_MAX(compile-time limits)
檔名不屬於 metadata 也不屬於 content，是位在 dir block，裡面是 i-node number 跟檔名
referenced by the kernel
per-process base
shell fork 出你要執行的程式，而 0 1 2 是 shell 開的
file descriptor 是在 file descript table，每一個 process 就會有一個
每個 process 的 file descriptor 都是分開的

Open Openat

1

int open(const char *pathname,int oflag,.../* mode_t mode */)

每個程式會開 cwd（紀錄現在 program 位置的 func）

每個檔案開一次，在同一個 process 裡也會用不同的 system file table，但是會是在同一個 i-node

umask 是個參數可以在進行前設定好不想要被開的權限設定好，可以避免不小心開錯

O_RDONLY O_WRONLY O_RDWR O_EXEC file access mode
O_CREAT O_TRUNC O_EXCL file creation (TRUNC 是會初始化，EXCL 是檔案不存在會 error)
O_APPEND append to the end in each write
O_NONBLOCK non-blocking
O_DSYNC O_RSYNC O_SYNC

openat 要先帶一個 dirfd （open dir 拿到的 fd*）
time-of-check-to-time-of-use(TOCTTOU)
第三版課本有的一些 at func
在 openat 這類保證 TOCTTOU 一定相同

prefetch

就是在把要讀的地方的整個 page 都讀進 buffer cache
Open 可以設定要不要 block mode，預設開啟
block mode：把要求的的讀完才 return，但是可能在 buffer cache 沒有，所以可能會因為要讀資料所以會被踢出 CPU
non-block mode：不要因為要讀資料所以被踢出 CPU，只讀在 buffer cache 的資料
Synchronized I/O：一定要寫進 disk 才 return

Open file table

會記錄 file status flags(read, write, appenf, sync, nonblocking) 像是 read write 就是開了不能改
也有 file descriptor flag
fork 出 child process 預設會指到相同的 open file table，所以會共用 file status flags, current file offset, v-node pointer
open file table 也有 reference count
同一 process open 多次同一個 file 會指到 system file table 的不同位置。

i-node

disk 上的 metadata 在被 open 時的時候會搬來 i-node table 的 entry
buffer cache 是 cache file content
v-node 是在對應到 file sys 的虛擬層有的統一介面，由 bell lab 當初搞的
Linux 下沒有 v-node，用的是硬體上的 i-node
i-node table 是針對檔案，所以多個 process open 同個 file 在 i-node table 只有一個
open file table 會從 fork 出 child process 繼承（未特別設定），而對應到的是同一個 system file table，所以 system file table 會可能有多個 referneces
也會有 refernce count
而被指到的 system file table 在 UNIX 可以重新導向，如用 >
檔案長度及其他除了檔名的 metatdata 都記在這
metadata(or attributes)
v-node table == i-node table 專門在放 metadata 的 entry，只要一個檔案 open 就會被存 metadata 在那，不論 open 幾次都會只會有 1 個 entry
i-node 的 i 是 index
每個 i-node table 的 entry 都是一個 i-node

lseek

有些東西不能 random access（隨意讀取）如 pipe, FIFO
有些會允許負數的 offset，通常是開的 file 是記憶體，有些是因為把第一個 bit 當作 User/kernel 的 bool

system call return >= 0 都會是成功
/etc/motd 是 login 的歡迎訊息

在把有洞的 file redirect 到另一個 file 會把 null 填成 ‘\0’ 到另一個檔案，所以會增加 hole 的空間
創造有洞的 file 方法：用 lseek 跳到後面 write
在 ls -ls 裡面可以看到有洞的 file 的 disk block 會用得比較少

terminal 是要 enter 按下去才會輸進去
建議 file 讀失敗(-1) 就要去看 errno

goto 在不傷到編譯後的最佳化的情況下可以放心用

delayed write

會先把 read write 的處理先在 kernel buffer cache 處理，所以在寫入時可以減少 Disk I/O，而 UNIX 的 update daemon 會定期去把 buffer cache 讀寫進去 disk

I/O Efficiency

> /dev/null 可以把 output 丟到一個無底洞
read 的 buffer size 要開大一點，可以減少 context switch，但有極限（一個 page）
STDIN 跟 STDOUT 當作讀寫的作用再進行轉向會比較有彈性
Disk 讀出來可以算在 System CPU time，也能不算，因為現在有 DMA 技術不會動到 CPU 所以傾相不算
因為不保證 kernel buffer cache 一定連續，所以一次搬的會是一個 page 的大小，不會再降下去
系統的 CPU time 下降趨勢要看下降比例是否一樣
clock time 下降到一定程度就停了，而在 User + sys CPU time 跟 clock time 差距越來越大，因為來不及先幫忙去處理 prefetch 的效果消失

Atomic Operation

目的：不要有與預期不同的狀況產生
如果寫了兩個 seek 到最後面寫 10 byte 的程式
因為 context switch 不能控制，所以萬一在 lseek 後跳到另一隻程式進行 lseek 並寫入，再去寫第一個的，會覆蓋掉
SP 的測試要把 loading 拉很重如 10000 process 才可能發生

所以要 atomic operation 確保 TOC TOU 相同，保證不會被切掉
pread/pwrite
另一種被切掉就停掉

1
2
3
4
5


if ((fd=open(pathname, O_WRONLY)) < 0)
 if (errno == ENOENT) {
 if ((fd = creat(pathname, mode)) < 0)
 err_sys(“creat err”);
} else err_sys(“open err);

dup dup2

dup2 是可以把 fd 的指向 copy 到另一個 fd 上，所以會指到同一個 system file table 的位置，也就是 fd 進行移動 newfd 也會跟著

1

dup2(fd,newfd);

而 dup 跟 dup 2 會是 atomic operation

sync

可以在 open 的時候設定，每次 write 都寫進去 Disk ，或是每幾次寫下去

when Open

O_DSYNC 是只顧 content，metadata 在被影響到才會寫進
O_SYNC 會把 content 跟 meatdata 去寫進去
O_RSYNC 是在 read 的時候 sync
寫完才會 return

sync fsync fdatasync

在 write 完 call，會把 buffer cache 丟到 disk 寫入的 waiting queue 就 return
sync 是把全部的 data 跟 metadata 都寫進去
fsync 是把指定的 fd 的 data 跟 metadata 都寫進去
fdatasync 只寫指定的 fd 的 data，不寫 metadata

update daemon

會定期 call sync (defalt 30s)

實驗會考

fcntl

會去動 open file desc. table, sysytem file table 等地方的 file status flag 跟 file descriptor flag
可以用 F_DUOFD 去做 dup 的 command

ioctl

可以對很多東西 control，如 disk, mag, socket, terminal

/dev/fd

可以對已經 open 的檔案進行 open，但權限不能凌駕原本檔案

1
2
3


fd=open(“/dev/fd/0”,mode)
// ==
fd=dup(0)

NTU SP Chapter 04 - Files & Directories

Sun, 15 Dec 2024 00:00:00 +0800

主要在講檔案屬性跟 directory tree

type.h stat.h

`stat(const char pathname, struct stat buf)`

把 i-node 的東西讀出來

`fstat(int filedes, struct *buf)`

用 file descriptors 打開

`lstat(const char pathname, struct stat buf)`

可以用來讀捷徑檔這種（用 stat 會讀到目的的 i-node 位置）的檔案，會讀捷徑檔本身

struct stat

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


dev_t st_dev // Device ID of device containing file.
ino_t st_ino // File serial number.
mode_t st_mode // File type & mode(permissions)
nlink_t st_nlink // Number of hard links to the file. 多少檔案指到這個 i-node
uid_t st_uid // User ID of file.
gid_t st_gid // Group ID of file.
dev_t st_rdev // Device ID (if file is character or block special).
off_t st_size // For regular files, the file size in bytes.
time_t st_atime // Time of last access.
time_t st_mtime // Time of last data modification.
time_t st_ctime // Time of last status change.
blksize_t st_blksize // A file system-specific preferred I/O block size for this object. In some file system types, this may vary from file to file. 檔案在作業系統的最佳 block size
blkcnt_t st_blocks // Number of blocks allocated for this object.

`st_mode`

mode

有記錄 file type
在 <sys/stat.h>
有 MACRO 可以去確認檔案形式

`S_ISREG()`	`S_ISDIR`	`S_ISCHR`	`S_ISBLK`	`S_ISFIFO`	`S_ISLNK`	`S_ISSOCK`
regular file	directory file	character special file	block special file	pipe or FIFO	symbolic link	socket

是對 st_mode 做 & 運算

mask

有 S_(W | R | X 進行組合)(USR(U) | GRP(G) | OTH(O)) 的 macro
檔案的讀寫執行權限很好理解，就很直觀

`st_uid` / `st_gid`

處理如要更改如 passwd 的檔案，但是不能改其他人的部分，這時候就要去借其他人（如 root）的權限去讀寫程式，所以 passwd 只需要 root 有 rw，其他都只需要 r
set_uid 是在處理把 user 權限借給其他 user 的 process 的部分

who you really are(process ownser 就算拿到其他 e-UID 用 exec 去執行其他程式，還是原本的 r-UID)
- real user ID
- read group ID
used for file access permission checks
- effective user ID
- effective group ID
- supplementary group IDs （因為 user 可以有很多 group，這是 sub-group）
saved by exec functions（用來存 effective 的 UID GID）or super user use setuid（沒辦法用 system call 得到）
- saved set-user-ID
- saved set-group-ID EUID 是透過 system call 來讓 kernel space 處理，所以 kernel space 的原理跟 effective UID 無關。

set-User-ID

在執行檔的 permission 的隱藏（user 的 rwx 前面）bit 如果 on 起來就會把 effective uid 變成執行檔的 owner
int setuid(uid_t uid); 如果是 superuser 就會把 r-UID, e-UID, save set-UID 設成 uid，否則就只能把 uid 設定成 real-UID 或是 save set-UID，不然會噴 error (errno == EPERM)

BSD 以前在沒有 save set-user ID 有用 int setreuid(uid_t ruid, uid_t guid) 跟 int setregid(uid_t rgid, uid_t egid) 交換 r-UID 跟 e-UID，後來 save set-user ID 出來後也可以交換 e-UID 跟 save set-user ID

int seteuid(uid_t uid);
int setegid(uid_t gid);
可以去設定 e-UID，對 N-user 跟 setuid 一樣，但對 superuser 是可以只設定 e-UID

set-Group-ID

與 set-User-ID 同理，是在處理 main group 的權限

權限最前面 3 bit

第一個 bit 是 set User ID，第二個是 set Group ID，第三個是 sticky bit（之後講）
如果 on 起來，在原本 user/group x 的位置會變成 s，如果可以執行，那就會是小寫 s，不行就是大寫 S，sticky bit 則是 t，s 通常是代表 security

可以運用這個功能讓執行檔案設定其他人的權限有 set UID，目錄只開 x，這樣只有知道目錄的人可以執行，也可以在程式中加一層密碼防護

access permission

權限在打開後就不會再檢查，所以只要在權限關掉前 open 檔案，還是可以對檔案進行操作
在檢查 user/group 只檢查 effective 和要操作檔案的要求是否相同

`int access(const char *pathname, int mode)`

會去檢查 process 的 r-UID 是否對 mode 有權限，如果有就 return 0，否則 return -1
mode 是 R_OK, W_OK, X_OK, F_OK
F_OK 是檢查檔案是否存在

新增檔案的 ownership

UID 是 process 的 E-UID

GID 則不一定，有些看 process E-GID，有些是看 dir 的 GID or dir 是否有開 set-GID，有就去繼承 GID，裡面也有分為要檢查 dir 的 set-GID 跟不需要
另外，有些系統會是把 set GID 開起來然後把 x 關掉，有 mandertory lock 開起來的功用
這些設定每個系統都不一樣

`umask(mode_t cmask)`

把 off 掉想要擋掉的 rwx，在 create mode 前先用 umask 歸零比較不會出問題
process 只會改到自己的 mask，child process 會繼承 parent process 的 mask
umask 會是個 built-in(internal) command 在 shell，因為要使得 shell 的值也會跟著改，但在其他地方會是 external command（不會改到其他 process）
umask 用完要記得還原成 0

1
2


umask(S_IRGRP | S_IWGRP )
create("bar", S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP)

會創一個 -rw——- 的檔案

chmod fchmod

chomd 只會動 i-node table 的資料，所以不會動到 disk
如果用 chmod 對檔案開啟 set-GID/set-UID ，且檔案的 GID 與創檔案的 e-GID 不同，系統會把 set-UID 關掉，但不會報錯

sticky bit(saved-text bit)

以前是用來管是否在 memory，可以加速，現在因為有 virtual memory 然後檔案讀取也變快，所以已經無此功能
以前的用意是把它 swap 一份到 memory

現在的功能是在 dir 上 on 起來會使得要對底下檔案進行刪除檔案，除了要有 wx 還需要是（資料夾的 owner | 檔案 owner | root）
tmp 目錄就是例子

有沒有 sticky bit 可以看 other 的 x 是不是 t

chown fchown lchown

l 就是不會 follow symbolic link

limit of ANSI C, POSIX, XPGS3, FIPS

ch.2
用 macro 來看有沒有定義，如果沒有，就要去在 runtime 看有沒有辦法得到，再不行就自己猜

owner

只有 root 可以更換

group

只能更換到自己所屬的 group

File size

`st_size`

regular files: 0~max(off_t)
directory files: 16 / 512 的倍數
Symbolic links: pathname length

實際大小在有 Hole 的會比邏輯大小小，而 du -s 出來的是實際大小，ls -l 出來的是邏輯大小
當然實際大小也可能比邏輯大小大

truncate ftruncate

把檔案尾巴砍掉，輸入是要留下的長度
在有些系統也可以把的大小輸入的比目前大小大，可以製造 hole

fctnl 允許用 F_FREESP 把檔案的某些地方 free 掉，來製造 hole

當 funtion call 不管用可以用 fcntl，再不行用 IOcontrol

UNIX File and Directory

File

sequence of bytes

System V

disk 裡面有不同的 partition
裡面有 file system 裡面開頭有 boot blocks 跟 super block 後面接著很多個的 Cylinder group
Cylinder group 裡面開頭是 super block 的 copy、cg info、i-node map、i-nodes、Data blocks

i-node and data blocks

i-node

除了檔案的 metadata 外，還有很重要的一點是要記錄檔案所在的 data blocks
檔案資訊除了檔名外，還會在最前面有 hard link 到 i-node 的 i-node number，然後 i-node 會有 reference count 紀錄有多少檔案連到它

soft link 是捷徑的 link

檔名跟 i-node 也存在 dir block 中
在格式化的 cylinder 裡面可以設定上限的 i-node 數，而這也可能造成 i-node 滿但是 data blcok 還沒滿，所以設定 i-node 是一門學問
ls -i 可以看 i-node number
每個 dir 至少會指到兩個 hard-link . 跟 ..
current path 只需要記 device ID 跟 i-node number

move file

在同一個 file system 內，只需要移動 entry，把 hard link 移動過去

可以把 i-node 串 i-node table 這樣可以增加小檔案能存放的數量，且因為讀取第二層 i-node 會把 data 一起存到 buffer，所以也不會特別慢

hard link vs soft link

hard link

hard link 需要有一個名字跟著
只有 superuser 可以去創一個連到 dir 的 hard link，N-user 只能創指到 file 的 hard-link
不能跨 file system

soft link(Symbolic link)

捷徑檔
不限制能指到的地方
可以跨 file system
是絕對路徑到指定檔案
被指到的不知道有沒有被指到，所以可能造成 diangling link
在系統沒限制的時候可能造成 cycle 無窮迴圈

link unlink rename remove

link 跟 unlink 是在處理 hard link

檔案刪除的條件

當 reference count 降到 0 且沒有被 open 才會被刪掉
暫存檔可以運用這個特性把檔案 open 完 unlink，可以使得檔案無法被 ls 到，且程式結束後會自動刪除

rename

如果遇到新檔名的檔案已經存在，且有 wx 權限：
舊檔案和新檔案都是檔案，會先 unlink 掉舊檔案，再去 rename 新檔案
舊檔案和新檔案都是目錄，且舊檔案是空目錄（只有 . & ..），會先 unlink 掉舊目錄，再去 rename 新檔案，新檔名不能是舊檔名的 prefix（父資料夾）

symbolic links

sybolink readlink

unistd.h
有些 system link 會 follow link 有些不會，open 就會（連帶 read write 也會）

file times

Field	Description	Example	ls-option
`st_atime`	last-access-time	read	-u
`st_mtime`	last-modification-time	write	default
`st_ctime`	last-i-node-change-time	chmod chown	-c

`int utime(const char pathname, const struct utiimebuf times)`

utime.h

當 times 設為 NULL，會設定成現在時間，否則設定成的要設定的時間
當 times 是 NULL 只需要 (E-UID == file owner UID) or w 權限
但設定成指定時間要 (E-UID == file owner UID) and w 權限
在 time_t 是 32bit int 所以在 2038 會遇到年份可以記錄的極限
i-node 的時間無法在這更改

mkdir rmdir

dir 無法使用 open 的手段還原，因為當可以用 rmdir 已經是空的了

opendir readdir rewinddir closedir

dirent.h
DIR *opendir(const char *pathname) 可以開啟一個遍歷 dir 的 cursor，但沒有規定一定會對開啟時的外部更改有反應
struct dirent *readdir(DIR *dp) 當遍歷完會 return 通知，因為 dir 是 set 所以不會照字典順序
rewinddir 會回到開頭
最好確保 dir 不會動

chdir fchdir getcwd

如前面所說，cwd 只是記錄 device ID 跟 i-node number
cd 必須要是 bulit-in command 才能更動 shell 的 cwd
chdir 在遇到 symbolic link 會被影響，而 getcwd 因為是 follow hrad link 往上走，所以不會被影響
當 cd 到 /usr/a/test 但是 /usr/a 是個 symbolc link 指到 /var/b，那這樣 cwd 會變 /var/b/test

`st_ino`(i-node number)

可以去看 i-node number

NTU SP Chapter 05 - Buffer I/O

Sun, 15 Dec 2024 00:00:00 +0800

Standard I/O Library

定義在 ANSI C 的標準，所以不管 OS

File I/O

會得到一個 FILE & fp 指到 FILE object 在 virtual memory 中，最後還是要透過 Unbuffer I/O
有 file descriptor, pointer to buffer buffer size, remaining chars, error flag, EOF flag…
可以在 Linux 下在執行檔前面加 strace，會 trace 所有 buffer I/O 會對應什麼 unbuffer I/O

Buffer I/O

C allocate 在 heap 的 buffer，使用者不會知道，在 User space，在 standard I/O 的操作會在這邊（standard I/O buffer）拿
把字串分次 printf 出來對 sys CPU 沒影響，但對 user CPU 有影響

freopen

類似 dup

fdopen

可以把 unbuffer I/O 的 file descriptor 丟進去 associate 一個 subset 的 file pointer(buffer I/O)

buffering

本章所指的 Actual I/O

只是讀寫 Unbuffer I/O 何時產生，並不需要去在意 disk

types

fully buffered

基本上所有 I/O 都是 fully buffer
意思是 buffer 滿了才去進行往外讀寫
當讀到空的東西，才去把東西讀進來
寫到 buffer 滿了才去寫入

line buffered

terminal 通常是這樣
讀到換行才去輸入輸出，或是 buffer 滿，又或是收到 request 把東西 flush 出去
flush: 把東西掃出去
如 terminal print 出 $ 後再接收輸入

unbffered

沒有 buffer，即時輸入輸出，通常 stderr 就是這種

ANSI C requirements

stdin stdout 只要不是 terminal 就是 fully buffered（如重新導向之類的），否則就不是 fully buffered
通常慣例是 terminal 會寫成 line buffered
stderr 不能是 fully buffered
慣例是 unbuffered

synchronize data

要把東西寫到 disk 要先用 fflush() 寫到 kernel buffer cache，再用 fsync() 同步檔案跟 metadata 或用 fdatasync() 只寫 metadata 到 disk，又或是 sync() 把寫入的動作進行排程

自己建 C 的 buffer

在還沒做 read write (I/O) 前要做處理

setbuf(FILE fp, char buf)

如果 buf 不是 NULL 就至少要 BUFSIZE 的大小（stdio.h 定義），而種類看導向哪裡，如檔案就是 fully buffered
buf == NULL 就是 unbufferd

`setvbuf(FILE fp, char buf, int mode, size_t size)`

可以設定 buffer type 跟 buffer size
假設是 _IOFBF 或 _IOLBF 且 buf 是 NULL，Disk 會幫忙開一個 block 的 buffer
在還沒 read write 前可以設定

buffer seek

fseek

binary file 不支援 seek SEEK_END 因為有些系統會因規定某些檔案的大小要多少的整數，剩下填 NULL，所以不一定能找到實際的結尾
text file 只能用到 SEEK_SET，只能移動到 ftell 回傳的那個值(???)

`void rewind(FILE *fp)`

把 offset 移到最前面

`long ftell(FILE *fp)`

回傳 offset，在 lseek 要用 lseek 把 offset 設成 0，SEEK_CUR 的回傳值來找
lseek 沒有同樣的功能，要用 lseek(fd, 0, SEEK_CUR) 的 return 來找

Standard I/O Lib type

Unformatted I/O

沒有 type 的 I/O，可以一次讀一個 char, line, Direct I/O

Direct I/O

int getc(FILE *fp) 可能會是一個 MACRO
int getchar(void) == getc(stdin)
char 有可能是 signed 或 unsigned，所以 getc 最好用 int 來接，char 不管是 signed 或 unsigned 都會有可能造成問題
int unget(int c,FILE *fp)，可以把讀到的東西放回去，但不一定要放原本的字元，但不能是 -1(EOF)，可以用來檢查文字是否為中文（2~3 byte）

Memeory aligment

會透過 address decoder 一排一排拿，所以 struct 考慮到 row 的大小（8 byte）會提升效率，所以有些系統會加一些 aligment，所以在 binary 的 I/O 有時候會造成問題

snprintf 比較好（如程設所述）

interleaved R&W restrictions

multibyte file

可以在還沒 read write 時或還沒設定時可以設定，決定一次讀進來的字元寬度，有其他有 w 的相關 function 如 fwprintf

NTU SP Chapter 07 - Process Environment

Sun, 15 Dec 2024 00:00:00 +0800

intro

two key atrribute

Logical control flow
- 每一個 process 看起來是獨自使用 CPU
- impliment by context switch(multitask)
Private address space
- main memory 只有自己可以處理
- impliment by virtual memory

main function

strating point

對 programmer 來說 C 的 staring point 是 main（但在 windows 有時候在特殊環境下要稍微改名）
對 System 的 starting point 是 start-up routine

start-up routine

compiler 去寫的，會由 compiler 的 linker 連起來
main start 是 start-up routine 去 call，return 也是給 start-up routine
start-up routine

1
2
3
4
5
6
7


initialize
Get Environment Vars
 Command-line
 arguments
Call to main
 > main
Clean up

_start 會去 call main()

nm

nm 是個 command 可以看 object file 的 symbols
symbol 包括 function, variable, setcion(code, stack…), linked lib
-g 是只有 external symbols

readelf

顯示 ELF 檔的資訊
ELF 的 magic byte 代表是執行檔
可以用 -a 列出所有資訊
可以看到 Entry point address 是 _start 的 address

objdump

顯示 object file 的資訊
-d 可以反組譯（disassemble）
Opcode 是 CPU 看得懂的語言，會在 ISA 中
machine code 會對應有自己的 assembly
compiler 用相對位置比較不會出錯，所以會在 jmp 時用一個位址 + 相對位址，同時也是因為在 link 時會比較好處理

process termination

Normal termination
- retrun from main() (exit(main(argc,argv));)
- call exit()
- call _exit(), _Exit
- return of last thread（基本上就是 main thread） from its start routine
- call pthread_exit from last thread
Abnormal termination（都跟 signal 相關）
- abort()
- terminate by signal
- last trhead get a cancellation request

ELF(Executable and Linkable Format) file

Standard library format for object file

Relocatable object files (.o)
Executable object file （執行檔）
Shared object files (.so) Generic name（通稱）：ELF binaries
以前 a.out 也是個 format，ELF 相對擁有更好的 support 給 shared libraries

format

ELF header
program header table
.text section
.data section
.bss section
.symtab
.rel.txt
.rel.data
.debug
Section header table(require for relocatables)

ELF header

Magic number(\177ELF)
Type(.o/.so/exec)
machine
byte ordering(endien)
entry point
size etc.

program header table

page size
virtual addresses memory [segments/sections]
segment size 就是記接下來 section 的資訊
section 通常是在指 ELF file，segment 通常是用在 VM

.text

放 function code 的位置

.data

intitialized (static/global) data 會放這邊

.bss

uninitialize (static/global) data 會放這
Block Start by Symbol 所以簡稱 bss，又被笑稱是 Better Saved Space
就算有資料也是 ELF file 要用，因為沒有初始化，所以也不用存在 ELF 檔案中，所以不用空間

.symtab

variable names, procedures names, section names 跟 location 都在這邊紀錄
這邊每一區以及其他的東西都是 symbol，用 nm 可以去看
可以知道 symbol 在執行時 virtual memory 中的位置，以及在 ELF 的 address
也就是紀錄 .text section 中每個 symbol 的位置都會在這邊
在 compiler 中最麻煩的部份

.rel.text

.text section 的 relocation info
有些東西 address 會是解不開（assebly 中會放 0 作為 address，以後 link 時再去解）
就是紀錄 relocation （有哪些是填 0 的）的，之後 link 時會去找對應的 address
for code

.rel.data

.data section 的 relocation info
有些東西 address 會是解不開（assebly 中會放 0 作為 address，以後 link 時再去解）
就是紀錄 relocation （有哪些是填 0 的）的，之後 link 時會去找對應的 address
for variable

.debug

放 debug information
如 gcc -g 的資訊就放這

linking example

變數有兩個資訊 definitions 跟 references
definitions 就是在檔案中直接定義就是
reference 就是外面連過去，有 local 跟 extern 兩種方式，local 基本上就是在同一個檔案就看得到 definition，extern 則是在其他檔案連過去（在 .h 用 extern 來導入其他 .c 的變數或是直接在 .c 寫 extern）這在檢查一開始不會有資訊，在 relocate 才知道，就只能 check prototype
通常全域 definitions 的通常就會宣告成 static 來避免被外部使用
refernces 在 compile 時就需要 relocation

relocate

就是在 compile 時不知道 address，所以會放 0，等到 link 時再去解
在 link 前會分開成不同 .o 檔，然後 link 時會依據 section 去拼成一個完整的 executable ELF file
解不掉就會出現 undefined reference

compile

C preprocessor
C compiler
Assembler
Linker

preprocessor

gcc -E
會得到 .i 檔
就是會把 include 的東西都貼進去還有 MACRO 解開

compiler

gcc -S
會得到 .s 檔
把 c file compile 成 assembly

assembler

gcc -C
會得到 .o 檔
把 assembly 編成 .o 檔

linker

把 object file 跟 library link 起來
除非是 dynamic linking，就要把所有 reloaction info 解掉
把各個 .text, .data, .bss 的資訊取出來合成一份新的完整 ELF 檔（結構參照上面）

static library

static library 會透過 linker 連到 executive file
static libary 在 Linux 都是 .a
優點是可以直接跨電腦執行，缺點是檔案大小太大跟更新都要重新編譯
可以用 ar 把多個 .o archive 成一個 static libarary file (.a)

不同的程式 call 的都是同一份
會在執行時一啟動就會連過去
缺點是在執行時去連的時候 cost 比較高
gcc 會去優先找 shared library
gcc 對 share libaray 優先是用 dynamic link，要 static 就要加 -static
有兩種 load 的方法，一種是啟動時就會 link，一種是用到 funtion 再把用到的 library link 進來
如果要 compile 成 share libary 在 compile 時 gcc 除了 -c 還要 -pic 設定成 position independent code，最後會連成 .so
在 dynamic link 時會有內建的尋找順序，然後也可以用參數加上要去找的地方
可以用 system call dlopen 來自己去找 share library
load 完基本上就會去放在記憶體
通常會用 mmap 做

Virtual Memory

Virtual Memory
(High Address)
kernel space
argc, argv, env (in stack)
Stack
↓
(share lib, mmap)
↑
Heap
un-initialized data(bss)
initialized data
text
(Low Address)

Text segment

來自 ELF file 的 .text section
exec 時會 Copy .text section 的值
Read-only usually & sharable（fork 時）
放 Code 的地方

Initialize Data segment

來自 ELF file 的 .bss section
exec 時會 Copy .bss section 放已經 init 好的資料

Uninitialize Data segment

在 exec 時會把原本空的開出一塊然後 init 成 0

Stack frame

Call function 就會長出一塊
裡面要記 return address, passesd parameter（傳遞的參數）, local variable 跟 CPU 裡面要用的 saved registers
兩個沒有 local variable 然後還沒 return 的 function 吃同一塊 stack（setjmp 達成）不會出事
jmp 時會儲存的只有在 register 的也就是當 compile 完假設 normal(automatic) 跟 register type 是有限的資源時才會存在 setjmp 的 jmp_buf
alloca 是可以在 stack frame allocate 的 system call，也就時不用 free
stack 最上方會放 command line arguments 跟 enviroment variables，因為 main 會吃這些
main 最後一個參數的 char **envp 指向的是個 string list(array for pointer)，會放 Enviroment variable，裡面的沒有正式定義，都是約定成俗
char *getenv(const char *name) 可以去拿某個 name 的 env string
int putenv(const char *name-value)
int setenv(const char *name, const char *value, int rewrite) rewrite == 0 是不會去改已經有的 name，rewrite == 1 是會對已經存在的 overwrite
int unsetenv(const char *name) 去拿掉某個 name，如果沒有那個 name 不會有 error msg
如果改了 envp 連到的 env string 就會把去改使得大小變大的東西移到 heap，如新增一項 env 就會把 envp 移到 heap，把 env string 的改長就會把那項移到 heap 然後改 envp 上的 pointer
env 的格式都是 Name=value

heap

dynamic allocate memory
allocate 時通常會考慮 aliment
在 allocate 時會去要一大塊，然後由 C 去維護 malloc pool
真正要 heap 的是 sbrk() 這個 system call 去條大條小 heap 大小
reallocate 可能會調整 pointer，因為可能後面有東西要換位置基本上 free 也不會還給系統，會存起來用

stack & heap 中間

mmap 跟 share library 就會放這

loader

執行時會把檔案 load 到 memory
UNIX 會是 ld.so 這隻程式去進行

physical memory

一開始會把一些 physical memory 給 OS 自己用
每個檔案 4G 這樣多個 process 不可能就使用如此之多的空間，所以會去切成多個 pages
physical page 跟 virtual 要等同
不同 process 的個別 virtual page 可能會共用 physical page
OS 會 Control 怎麼把 virtual memory address 用 page table 來 mapping 到 physical memory address
因為 virtual memory page 一定遠大於 physical pages，所以不會是一對一
在 physical page 不夠時，有時後會在 page table 把 virtual page 指向 disk
過程是會在發現 physical page 不夠時，會把之前的某塊掃到硬碟，接著使用那塊，要用再去掃回來

address transltion

virtual address 轉成 physical address 會透過硬體跟軟體合作
硬體存取 page table 本身，軟體去管理內容
page offset 是紀錄 address 是在 (physical?) page 中要 offset 多少
每塊 virtual address 最後會留一塊給 page offset，會根據整塊的大小來決定幾個 bit，如 4K = 2^12 就會是 12 bit，指的是 page 的 offset
page offset 在 virtual address 跟 physical address 都會有
兩個 address 的長度不一定一樣大
page table 就是 virtual address 長度扣掉 page address 的長度，如 32bit - 12 bit(4K per page) = 2^20
virtual address 的前面就是紀錄在 page table 的位置，也就是 Virtual page number(VPN)
physical address 的前面就會紀錄 physical page number(PPN) 跟 page offse，PPN 的大小就是 physical address 長度扣掉 page address 長度，如 30bit - 12 bit(4K per page) = 2^18
在 page table 的每一塊會有 valid, access, 跟 PPN
vaild 是紀錄在 VM 中是否有效（有被用）或是有沒有 map 到硬碟,access 是紀錄權限 rwx，然後就可以用 PPN 算出 physical address 的位置

有時候會宣告變數是 atomic 如 sig_atomic_t 也就是不會跨 page?

NTU SP Chapter 08 - Process Control

Sun, 15 Dec 2024 00:00:00 +0800

process ID

從 0 到 max prcess ID，然後再 recycle 回來
ID 回收後不會立刻發放，短期內就不會去發放那個 pID

tmpnam 去要一個不會跟他人衝突的暫存檔名，可能會把 pID 放在其中

Bootstrapping

process of starting up computer 會把電腦 cold boot
init 所有元件 (ROM 的 code?)
把 Read Only Memory(ROM) 裡的 boot program 讀起來
boot program 開始接手（作業系統開始接手）
把開機必須要的 kernel process 開起來
kernel process 去檢查硬體
kernel process init system process
把系統開成 single user mode(root)
設定系統資訊（如 hostname, 時間）
開啟 multi user mode
開啟 init process

init process 會長出所有 process
init 是 root 的 process 且是 user space 的 process

PID 0 Swapper or Scheduler

不同 UNIX 下不一樣，有些是 swapper 有些事 Schedular
Swapper: memory 不夠把東西移到 disk
Schedular: 去決定哪個 process 先跑

PID 1 init

由 PID 0 開起來
root 的 process
bring up multi user
有很多功能

常見功能

N User 要在開機時跑起來的東西也會由 init 跑起來

通常會 fork inetd 來去管網路連線，所有網路基本上都是由 inetd 去 fork 出 process 去長
不管是 remote login 還是 consol login 都會長出 shell，可能是 inetd 的 child process 去開或是 dtlogin 的 child process

Process Control Block PCB

process table 上面就是有 PCB
裡面會有第一章提到的 process state
program counter （紀錄 program 跑到哪）
CPU registers（紀錄 process 被踢出前的狀態）
CPU Scheduling Info（有沒有 priority）
Memory-management information（memory 要管的 data structure, 去紀錄程式在 memory 的哪裡）
Accounting information（CPU time, real time）
I/O status information（open file, open device）

都是為了執行 process 所需要記的東西，可以說是 process 的 metadata
sys/proc.h 的 proc(C structure) 裡面就是 PCB

proc 只有記 process 的 parent process，沒有記 child，因為不一定是固定的，所以要宣告成靜態的固定大小 array 這樣會浪放記憶體空間
所以要找 child process 要遍歷所有 process，去檢查 process 的 parernt

CPU process switch

在 context switch 時把 state 記到 PCB，並且把要去跑的 process 的 PCB 讀進去，中間 CPU 是沒在執行東西
processs(其 PCB) 可能會同時在不同的 queue(Job, Ready, Device) 裡面

Process scheduling queue

Job queue: 所有 process 的 queue
Ready queue: 可以執行的 process
Device queue: 等待 I/O 的 process

Process 的 metadata & content

Metadata 就是 PCB
content 是 virtual memory
program counter 也是個 register 但是比較特別的 register 會去記 Virtual memory 的 text 裡面程式碼跑到哪裡，register 則是指到 virtual memory 的 stack top

Process control system call

這邊的 function 不能出錯，所以一定不會 return -1 的情況

1
2
3
4
5
6


pid_t getpid(void)
pid_t getppid(void)
uid_t getuid(void)
uid_t geteuid(void)
gid_t getgid(void)
gid_t getegid(void)

Process Creation & Termination

fork 出一個 child process，通常就是要用 wait 等到 child process terminate 才會繼續
child process exit 完 UNIX 會送一個 signal 給 parent process，wait 就會被喚醒
child exit PCB 還會留存，要等到 parent wait 完才會結束，所以當 parent 不 wait 或是 parent exit 會出現 zombie process 的問題

1
2
3
4
5
6
7
8
9


if ((pid=fork()==0))
{
 // child process
}
else
{
 // parent process
}
exit(0);

fork() return > 0 會拿到 child 的 pid， return = 0 會是 child process
fork 完會 child 會從 fork 處開始跑
PCB 不會繼承，Virtual memory 會複製
PCB 會複製部分資訊
上面的程式碼哪個會先跑不會知道

process 在硬體上

process 的 VM 在 block 上會指到 Physical Memory 某個 page 上，只需要有用到的部分指到 PM 上
page 是在硬體上習慣的單位
fork process 的 VM 會跟原本的 VM 用 copy on write 指到同一個 page 上來，在 write 才寫到新的 page 上，來降低 cost，同時也可以使得一些 read-only 的資料不用 copy

fork 完的程式如果在 fork 前有程式 printf，但是把輸出轉向，會因為不是 terminal 所以會變成 fully buffer，所以 buffer 也被複製過去，此時裡面還有東西，所以 printf 的東西也會在 child 的檔案中
kernel space 不會去記 user space 有多少個東西指到它，所以 open file desc. table 只會有一個指到
parernt 的 stdout 也會繼承給 child

fork 特性

normal case

parent 會 wait 到 child complete
each go their own way

inherited

real UID Effective UID, working dir, set uid/gid flag… Real uid, effective uid, real gid, effective gid, supplementary gid, process group id, session id, controlling terminal, set[ug]id flag, current working dir, root dir, file-mode creation mask, signal mask & dispositions, close-on-exec flag, environment, attached shared memory segments, resource limits

不會繼承

1

Returned value from fork, process id, parent pid, tms_[us]time,tms_c[us]time, file locks, pending alarms, pending signals

CPU 時間就不會繼承，signal 的對象是 process，所以會是不會繼承，PID 也當然不會繼承，lock 不會繼承也很重要

fork fail 原因

太多 process
超過 read uid 的 process limit（CHILD_MAX）

fork usage

同時跑不同部分的 process 如 networking 可以用到
spawn(exec + fork)

`vfork`

在還沒有 copy on write 跟 VM 的時代 BSD 派的產物
讓 child 跟 parent 用同一個 page（也就是 VM 相同）
Vfork 完 child 要先執行，執行完 exit() 或 exex() 才能去跑 parent
現代除非要 share memory，因為有 copy on write ，所以否則不會去用這個指令，因為太多東西共用，很容易會不小心造成問題
vfork 建議要用 _exit(0) 關閉不要用 exit()，因為 exit 會把 file object close 掉，因為是共用記憶體，所以也會把 file stream 順便 close 掉

open source 常在 select 完 non-blocking 為了防止 context-switch

deadlock

兩個以上要取用對方擁有的資源，造成卡死
但其實有四個條件同時滿足，才算 deadlock
vfork 會有機會造成 deadlock，如 vfork 的 child 要等到 parent 達成某一個條件才會跳出，但 vfork 要等 child exit。

process termination

Normal termination

return from main() (exit(main(exit(argc,argv))))
call exit
call _exit _Exit
start routine 的最後一個 thread return
最後一個 thread calling pthread_exit

Abnormal termination

abort() 會送 SIGABRT 給自己
terminal signal 只能由 UNIX 送
異常終止只要是收到 signal 終止就算是，無論是自己要求，還是別人送過來

C program start and termination

從 exec 開始執行
在 exit() 的時候會去 call exit handler call，跟 standard I/O cleanup
_exit 則是直接 exit 不做處理
exit 跟 _exit 不會 return

zombie process

當 child process return 但是 parent 沒有用 wait 或者是離開，導致 child 的 PCB 沒有人拿，這時候就是 zombie process

`atexit()`

題外話：要引用別的檔案的變數要用 extern 引用，static 不能被用
註冊在 exit() 後會去執行的

`wait` `waitpid`

把結束的 child process 從 Z(Zombie process) 離開，child process 只要結束就會變成 Z
wait 是 block mode
waitpid 是可以設定成 non-blocking
default 會是 ignore

calling wait/ waitpid 的 state

Block（等待 return）
Return with the termination status of a child
Return error

wait 的 return 條件

是在等待狀態改變

程式結束
變成 stop 之類的（如在背景跑，然後是 scanf）

`pid`

pid == -1: wait any child
pid > 1: wait for the child with pid

`op`

op = WNOHANG
就是不去等待，可以搭配 SIGCHID 去檢查有沒有收到訊號，但會有 TOCTOU 不同可能會造成問題的問題

zombie & orphan process

zombie

The process has terminated, but its parent has not yet waited for it.
所以在 child terminate 當下瞬間會是 Zombie
會留存最少需要的資訊，(e.g., process ID, termination status, and CPU time taken) 用來 retunrn 給 parent
會吃少量資源（PCB），但是當有大量的話會造成有一堆 loading，另外有可能會因此佔掉一堆的 process 的名額，導致 loading 沒有很多，但是沒辦法新增 process

orphan process

process 的 parent terminate 的話就會變 orphan process
init 永遠會去接手 orphan process 使得 parent process 變為 1(init)
init 會在 child process 變為 zombie 的時候去 wait 來使得 zombie process 基本上不會在 init 的 child 出現

zombie state

因為要使得 parent process 知道 child 的 termination status
而且要知道 child process 的狀態（使得不會出現 child process terminate 後，其他的 process 與 child 相同 pid，使得 parent 卻去接收該 process 的資料）

trouble of zombie

會佔用 pid 的額度

double fork

一個使得 process 不用去 wait 也不會產生 zombie process
先 fork 一個生 process 的 child process 再讓 child 去 fork 出 grandchild(second child)
接下來 child process terminate，grandchild 的 parent 會變成 init
記得還是要 wait child process
因為不能確定 child 先 exit 還是先 grandchild 執行完 exit，所以建議先讓 grandchild 先一直 while(getppid != 1) sleep

在 open source 會很常出現一開始就 fork 完 exit
另外

1
2


$ ./a.out &
會顯示 pid 後在 backgroup 跑

session & group 在 ch.9 有，但課上不到

`wait3` `wait4`

可以拿到 PCB 的所有資訊
wait3 是可以拿到所有 PCB 資訊的 wait
wait4 是可以拿到所有 PCB 資訊的 waitpid

race condition

多個 process 要去對同個資源做事，會出現照執行的順序對資源操作
基本上就是要根據 context switch 去思考是否有 race condition

`exec`

把程式寫入到 memory 的 text 區段，然後把 global variable 重新設定，並把 stack 跟 heap 清掉
不會動到 PCB

1

main(int argc, char **argv, char **envp)

envp 是可以把 .env 的傳進去，傳進去的 string 像是 HOME=/home/a\0, PATH=/bin:/usr/bin:/usr/local/bin:.\0
PATH 推薦把 . 放進去，然後要放到最後面，因為會照著順序找，所以不會把系統預設 command 吃掉
會記錄 .env 的在 stack 的上方區塊，這在 exec 不會清掉，會被繼承
env 新增會在 heap 中去找一個區塊去放新的 table，然後更改 memory 記的 envp
但因為如果在 main funtion 丟進去的 envp 在 stack 中不會改，所以在 env 在執行時更改時會出問題
出錯才會 return

`execl`

用 pathname
把 arg 用 list 的方式傳，最後用 (char *) 0 結尾

`execv`

把 arg 用 vector 的方式傳，最後用 argv[]

`execle`

有 envp 版本的 execl

`execve`

有 envp 版本的 execv

`execlp`

用 filename

`execvp`

用 filename

如果沒有設定 exec 要傳的 env 就會把自己的 env 傳過去

1
2
3
4
5


execlp execl execle
 |build argv |build argv |build argv
 V try each V use V
execvp -> execv -> execve
 PATH prefix env

Inherited from the calling process

pid, ppid, real [ug]id, supplementary gid, proc gid, session id, controlling terminal, time left until alarm clock, current working dir, root dir, file mode creation mask, file locks, proc signal mask, pending signals, resource limits, tms_[us]time, tms_cutime, tms_ustime

`FD_CLOEXEC`

可以對每一個 fd flag 記錄要不要在 exec 時 close open 的 file
預設是 0（不會去 close）
exec 唯一可能動的 kernel space

Requirements & Changes

Closing of open dir streams, effective user/group ID
可以在執行 exec 前做這些事

UID

如 ch4 所說 save setuid 的功能

ID	exec & set-UID bit off	exec & set-UID bit on	setuid(uid) & superuser	setuid(uid) & N-user
real user ID	unchanged	unchanged	set to uid	unchanged
effective uer ID	unchanged	set from user ID of program file	set to uid	set to uid
save set-user ID	unchanged	copied from effective user ID	set to uid	unchanged

要拿 save set-UID 有一個方法是在 exec 完就去檢查 effective user ID

utility of saved set-user ID

example `tip`(BSD) or `cu`(SV)

tip 跟 UUCP 都會透過數據機，一個是去 access 遠端的系統，一個是 copy 遠端的檔案
因為 tip 要去搶 owner 是 uucp 的 lock，所以要去 setuid 在存取 lock 時更換 e-UID

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


step 1: exec tip
 r-UID == Our uid
 e-UID == uucp
 save set-user id == uucp
step 2: access filelock:
step 3: setuid(getuid()) 來回到一般的 permission
 r-UID == Our uid
 e-UID == Our uid
 save set-user ID == uucp
step 4: call setuid(uucpuid) 改 e-UID
 r-UID == Our uid
 e-UID == uucp
 save set-user ID == uucp
step 5: release lock

如果在 step 3 去 spawn 一個 shell save set-UID 會是 Our uid，另兩個也是，因為 exec 了

Interprete Files

檔案第一行有 #!<'執行檔絕對路徑> <參數> 就是個 Interpreter File，是個明文執行檔，絕對路徑的就是 Interpreter
# 在 interperter file 代表註解

1

#!/bin/sh

shell script 就是其中一個
第一行的長度在不同系統所允許的最大長度不同
對 exec 來說是個不能執行的執行檔，要執行要用 p 的版本如 execlp
用 execl 因為系統看不懂所以吃 #!後面的東西（interpreter），然後，接下來丟 Interpreter 的參數，把在 exec 的 argument 一個個丟進去，第 0 個 argument（execl 的第二個 aargument，shell 裡面第一個）會把他帶成相對路徑，剩下的塞進去 argument

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


a.sh x y
---
#!/bin/sh
echo "Hello, World!"
---
exec 的話就會長得像：
execl("/path/to/a.sh","a.sh", "x", "y", (char *)0);// 第二個參數 a.sh 會被解成 /path/to/a.sh
在 shell 就會解成
/bin/sh /path/to/a.sh x y
也就是會在 exec 時用 /bin/sh 執行 a.sh 然後參數帶 x y
第一行因為有 # 所以在 執行時又會被視為註解，所以不會再去執行
UNIX 從頭到尾就不用知道語言是怎麼處理
所以像是 awK 就會用 `#!/bin/awk -f` 因為 awk -f 是會去執行 awk program
---
#!/bin/awk -f
{print $1}
---
./a.awk x y
argv[0] = /bin/awk
argv[1] = -f
argv[2] = /path/to/a.awk
argv[3] = x
argv[4] = y
然後一樣丟到 exec 裡面
execl("/bin/awk", "awk", "-f", "/path/to/a.awk", "x", "y", (char *)0);
就會變成
/bin/awk -f /path/to/a.awk x y

pro

可以指定執行的方式
同時也造成比較有效率，因為不用經過先從 /bin/sh -c 執行然後到看不懂的去 fork & exec，可以直接從 fork & exec 那邊開始
不會只能用 bon shell，因為 execlp 只任 bon shell，可以用 awk language 或是其他種的 shell languages

against

額外還要去辨認 #! 的 interpreter
但相對好處這微不足道

system(cmd)

1
2
3


fork();
execl("bin/sh", "sh", "-c", cmd, (char *)0);
wait(); or waitpid();

可以看課本知道 signal 怎麼處理

time

process time

測 process 執行時間
clock_t times(struct tms *buffer);

1
2
3
4
5
6


struct tms{
 clock_t tms_utime; // user CPU time
 clock_t tms_stime; // system CPU time
 clock_t tms_cutime; // user CPU time terminated child
 clock_t tms_cstime; // user CPU time terminated child
}

會是相對某一點的相對時間，所以不論是 reseponse time 或計算經過時間，都要用減的
算的是 clock ticks

calender time

會算 1970 1/1 UTC 0:00 到現在過的秒數
用 time_t
有很多內建 function 處理日光節約時間、時區、閏年、閏秒問題
time_t time(time_t *calptr)
可以用 gmtiem 轉成 struct tm 然後用 fuction 進行轉成 string 或 format string 的處理，也可以用 mktime 轉回來

NTU SP Chapter 10 - Signal

Sun, 15 Dec 2024 00:00:00 +0800

system call 在某些條件下結果可能會不如預期

what is signal

無論是自己或是他人要求的，都是透過 OS 送的
像是 Ctrl + C 或是 SIGPIPE 都是 signal 的一種也算一種 IPC 的方式

signal v.s. interrupt

interupt（狹義）

對 CPU(Hardware)
內部指令可能會間接或者本身就想要去直接中斷，或是外部硬體接腳如 PIC(Programable interrurpt controller) 這邊就是連到很多周邊 device 並接收 request 再接收 IRQ 去中斷 CPU
CPU 被中斷會 run ISR(interupt service routine) 是用來記錄 event

signal

對 process
會去處理 ISR 記錄的 event，由 OS 去解釋 event（不一定會是單一個 signal
signal == 0 是 NULL signal
signal 會是正整數
不同系統會有不同 signal number
OS 等有空會去處理紀錄的 Event 然後轉換成 signal 傳送到 process
signal 的定義是來自 kernel，也是由 kernel 送給 process，不論 event 是什麼，解釋權都在 signal

Synchronous v.s. asynchronous signal

Synchronous 同步

因為執行某個 instruction 就發生
只要一發生就會產生，如 divided by zero 或 segmentation fault

Asynchronous 非同步

不知道 run 到什麼會發生
如 killed by other process, SIGCHILD(child termination)

Generate Signal

Terminal-generated signals

DELETE key

SIGINT(2)

Ctrl-C

Signals from exceptions

SIGFPE(8)

divided by 0

SIGSEGV(11)

illegal memory access

Fuction kill

(need owner or superuser)

Shell command kill

SIGKILL(9)

kill -9 pid

Signals because of software conditions

SIGPIPE

reader of the pipe terminated

SIGALRM

expiration of an alarm clock

對 Signal 的反應（action）

SIGKILL and SIGSTOP 不能被設定反應

設定 Ingore signals

SIGKILL and SIGSTOP 不能被 ignored
有些 signal 沒有設定對 ignore 的反應，所以當設定成 ignore 的後果要自負，如 SIGFPE

設定 Catch signals

SIGKILL and SIGSTOP 不能被 catch
當 signal 來要 call 哪個 function
call 的 function 就是 signal hadler 如 waitpid 就是

Apply the default action

Terminate（多數） or ignore or stop
沒有設定就會去變成 default

Example of Signals

w/core 指到是 core dump 就是終止後會把 memory copy 一份下來

1
2
3
4
5
6
7


Terminate w/core – not POSIX.1
No core file:
non-owner setuid process
non-grp-owner setgid process
no access rights at the working dir
file is too big (RLIMIT_CORE)
core.prog (4.3+BSD)

SIGABRT

terminate w/core call abort() 來自己終止自己，會送 SIGABORT 給自己

SIGALRM

terminate Call setitimer(), alarm() 這兩個是用來設定每幾秒就會送一個 SIGALRM 訊號過來，如果沒設為 catch 去處理，會使得程式終止

SIGBUS

terminate w/core Hardware 去 implement 的情形

SIGCHLD

ignore sent to the parent whenever a child process terminates or stops

SIGCONT

continue/ignore Continue a stopped process

SIGFPE

terminate w/core Divid-by-0, floating point overflow, etc.

SIGHUP

terminate 以前是實體接線斷掉，會接到 SIGHUP
通常 deamon(background process) 會有 comunication file（組態檔）來根 process 溝通
現在是對 deamons 更改組態檔後通知 deamons 要進行重新讀取組態檔有關（因為通常不會隨邊停止）

SIGINT

terminate DELETE key or CTRL-C

SIGIO

terminate/ignore 跟做 asynchronous I/O 的 event 有關
比如說要一直讀，讀到 buffer 去，作業系統在讀完把 data copy 過來後就會收到

SIGPIPE

terminate reader of the pipe/socket terminated

SIGPROF

terminate A profiling timer expires (setitimer)

SIGPWR

ignore (SVR4) 當沒電 UPS 運作時會 call 這個 signal 給 init

SIGQUIT

terminate w/core CTRL-\ triggers the terminal driver to send the signal to all foreground processes

SIGSEGV

terminate w/core Invalid memory access

SIGSTOP

stop process (like SIGTSTP) Can not be caught or ignored

SIGSYS

terminate w/core Invalid system call

SIGTERM

terminate Termination signal sent by kill command

SIGTSTP

stop process Terminal stop signal (CTRL-Z) to all foreground processes

SIGURG

ignore Urgent condition (e.g., receiving of out-of-band data on a network connection)

SIGUSR1

terminate User-defined

SIGUSR2

terminate User-defined

system call of set signal

1
2


#include <signal.h>
void (*signal(int signo, void (*func)(int)))(int)

以前註冊只有一次有效
設定 signo 的對應要用哪一個 function 處理
return 會是回傳之前的 function address
輸入輸出的 function 都要是 void func(int signo) 的格式
func 有由系統 define address 是 -1 是 SIG_ERR 0 是 default SIG_DFL 1 是 ignore SIG_IGN，因為不會有 address 那麼前面因為可以很多個 signal id 共用同一個 function 所以會接去判斷接到的 id ，會大概長得像

1

void function(int signal)

pause() 會等到收到沒有被設定為 ignore 的 signal
可以使用 signal() 去確定設定的種類，就是設定成想確認的結果就會知道之前是什麼

1
2
3


int sig_int();
if (signal(SIGINT, SIG_IGN) != SIG_IGN)
signal(SIGINT, sig_int);

exec

呼叫 exec 會把所有 signal 的設定條回 default，除非該項被設為 ignore

tips of signal

系統會自動把 backgroup process 的只有 foregroud 接收到相關資訊的 signal 設為 ignore

interrupt

可以在 slow systemcall 會被 forever block 的情況可以被 interrupted
errno 會是 EINTR
所以可以用這點來打斷 forever block
BSD 有設計被 interuptted 就會自動 restart
不同系統有些可以設定，或是寫死，或是不會 autorestart

reentrant function

有正面表列出 reentrant 的 function

call twice

有時候處理 signal 的 function 用到被 interrupt 的 function，裡面又有 static 出現，會出現問題
static 會被 compiler 放在 global variable，但存取會被 compiler 擋住

non-reentrant function

不能被 call twice 的 function，如裡面有 static, global, heap
也就是不會在 call twice 遇到被存取到相同位置

Example of non-reentrant function

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Those which use static data structures
Those which return a pointer to static data
Those which call malloc() or free()
Those which are part of the standard I/O library – usage
of global data structures (e.g., printf(), ctime(), gmtime())
Those which are POSIX.1 system database functions
(e.g., getgrgid(), getgrnam(), getpwuid() & getpwnam())
and POSIX.1 process environment functions (e.g.,
getlogin(), ttyname())
Those which call non-reentrant functions

signal 去對 errno 的防止 reentrant 的方法是，會先去存 errno，並在 handler return 前回復
longjump 也是 non-reentrant
如 printf 是 non-reentrant 但因為發生機率極低，所以還是用它來 debug

reentrant function solution

把要用到的變數由使用者提供 pointer 來存取，這樣在 reentrant 時就不會改到另一個 call 這個 function 那邊的變數

reliable signals

unreliable signals

signal could get lost
指的是感覺沒有 catch 到
像是因為以前 signal 只有註冊一次有效，而在處理前再次設定前又收到一個，所以就以預設處理
或是先把收到訊號用 global variable 去存起來，之後再處理，會遇到當開始去確認有沒有訊號時還沒有訊號，但是此時 context switch 收到，然後接回等待 signal(pause) 時，就等不到 signal 造成 deadlock
也就是 non-atomic 有 Race condition 造成問題

reliable signal 的做法

signal generated 時會先 set flag 然後等排到 CPU 才會去把 signal deliver 給 process，中間的時間就被稱為 pending
通常是在 context switch 間的時間去 generate
可以有很多 process 認領 signal 但至少要一個
reliable signal 的處理方式是在 deliver 的時候 block 住，等到 unblock 或 ignore

`sigpending()`

可以去看哪些 signal 被 block

signal mask

和 cwd 跟 umask 一樣在 process 中記錄

deliver times

標準沒說多個相同的 signal 會怎麼在 unblock 時去 deliver，通常實作是只會一次
多個不同的則會去把最嚴重的先 deliver

kill and raise

#include <sys/types.h> #include <signal.h>

`int kill(pid_t pid, int signo)`

會把 signal 送給指定 process
pid == 0 會給所以有 process 有相同 gid
pid < 0 則是送給所有 gid = |pid| 的
pid == -1 broadcast signals under SVR4 and 4.3+BSD
如 Worktation shutdown 前可以送 signal 到所有線上 User
r-UID 或 e-UID 要一樣才能送，也有些系統會去確認 r-UID 或 saved set-UID
signo == 0 (NULL signal) 是用來確認知道 process 是不是 alive 但會有 TTC != TTU 的問題，如果不是 alive 會 return -1
signal 送給自己且沒被 block 會在 return 前去 check 有沒有被 pending 的狀態（包含剛剛送的 signal），直到至少一個 deliver 才會 return

`int raise(int signo)`

送 signal 給自己

alarm and pause

#include <unistd.h>

`unsigned int alarm(unsigned int secs)`

幾秒要送一個 SIGALRM 給自己
會把之前設定的 alarm 取消掉
會把前面鬧鐘剩餘秒數 return
會比設定的多一些時間，所以設定要保守些
alarm(0) 可以 reset
要設定接收的反應，因為預設是 termination

`int pause(void)`

會暫停直到收到沒被 blocking 也非 ignore 的 signal
都會 return -1，errno = EINTR

setjump and longjump

#include <setjmp.h>
可以 non local goto

Stack Frame

fucntion 的那塊區域
每 call 一次 funtion 就會出現
會存 return address, passed parameters, save registers（CPU 之前的狀態）, local variable
return adress 的概念基本上就是會落在 call fuction 的下一行
裡面的 local variable 如果有做初始化，會由 compiler 產生的組合語言把它填成設定的值
compiler 會去優化跟預測接下來的行為來最佳化，所以亂用 goto 會讓 compiler 的預測效率降低
沒有 initialized 的 global variable 在 exec 會把整塊清零
設定 local variable 是 compiler
return 完 pop 掉其實不會被真正刪掉，只會動 pointer，但在重新 push（不論是不是同一個）時會重新設定
所以當 set file pointer 的 buffer 在 function 中宣告，會出現又 call function 時會出問題，但是不會有 error

`jmp_buf`

是 machine-dependent
通常會包含 CPU registers, stack pointer 以及 return address

`int setjmp(jmp_buf env)`

會 return 0 當 call 自己，當被 longjmp 會 return longjmp 的 val
通常會把 env 設為 global variable

`int longjmp(jmp_buf env, int val)`

jump 到有 setjmp 為 env 的 function 並在那邊 return val
可以用來一次跳回很多層，但是 stack 的 local vairable 基本上是不會回復
不能回到已經 return 的 function（要在 VM 的 stack 中）

sleep2 實驗

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


static void sig_alrm(int signo)
{
 longjmp(env_alrm, 1);
}
unsigned int sleep2(unsigned int nsecs)
{
 if(signal(SIGALRM, sig_alrm) == SIG_ERR)
 return(nsecs);
 if(setjmp(env_alrm) == 0)
 {
 alarm(nsecs);
 pause();
 }
 return(alarm(0));
}

先註冊 signal 然後當 alarm 響了會跳到 sig_alrm，不管 pasue 是否執行到，會到 if 所以不會被 pause 影響到（不會從 pause return）
可以解決 race condition，因為不論是什麼情況都會跳回 return
假設收到 SIGINT 也會中斷
但會造成中間假設有在處理其他的 signal hadler，會被中斷，然後假設處理到一半，因為處理 SIGALRM 的 longjmp 使得另一邊的 signal hadler 還沒跑完就結束了。
還是有 open source 會用，因為以邏輯上沒出錯，然後對於這個問題不重視（如 error number 沒被還原）

slow system call 遇到 signal

read 遇到 alarm

如果還沒 read 到東西，收到 SIGALRM 會使得 read return -1，errno == EINTR

auto restart

BSD 有提出一些 slow system call 被特定 signal interrupt 會 auto restart
所以遇到需要自己設定 timeout 會需要確定系統沒有對用到的 system call 沒有 auto restart

Signal Mask

每個 process 有自己的 signal mask
是一個類似 bit string 的東西
希望有一段時間可以把 signal block 住，因為那時處理的事情會跟 signal handler 衝突
預設都是 0

signal sets

#include <signal.h> sigset_t 是用來存 signal numbers 的變數型態

1
2
3
4
5


int sigemptyset(sigset_t *set);
int sigfillset(sigset_t *set);
int sigaddset(sigset_t *set, int sig_no);
int sigdelset(sigset_t *set, int sig_no);
int sigismember(const sigset_t *set, int sig_no);

`int sigprocmask(int how,const sigset_t set, sigset_t oset)`

如果 oset 不是 NULL 會先把目前的 sigset 複製到這
再來 set 如果不是 NULL 會去 check how 是什麼，set 是用來傳參數的 mask
然後會把 return 前所有 unblock 的 pending signal 至少 deliver 一個後再去把 set 設定到 sigset 中然後 return
所以如果 unblock 的話會立即去處理 signal

`SIG_BLOCK`

把 set 的跟 sigset 做聯集後去設定到 sigset

`SIG_UNBLOCK`

做交集

`SIG_SETMASK`

直接 replace

`int sigpending(sigset_t *set)`

會把 set 設定成正在 pending 的 signal
不一定會是 block 的 signal，可能是沒被 block 單純只是還沒被 deliver
但通常單純的 pending 不會太久，所以通常還是 block

inherited

fork

signal mask 跟 dispositions（signal 的 signal handlers）會繼承
peding signal 跟 alarm 因為對象是 process 所以不會繼承

exec

signal mask, pending signals, alarm 的 time left 會繼承
diposition(signal handler) 因為會把原本的程式區塊清掉所以不會清掉

`sigaction(int signo, const struct sigaction act, struct sigaction oact);`

用來取代 signal()，改正了不能確認之前的設定跟在處理時額外 block 的效果，也可以一次註冊多次有效
如果 act 不是 NULL 會改 signal hadler
如果 oact 不是 NULL 會回傳現在註冊的狀態
現在 signal 會用 sigaction implement

`struct sigaction`

1
2
3
4
5
6
7
8


struct sigaction {
 void (*sa_handler)(int);
 sigset_t sa_mask;
 int sa_flags;
 /* alternate handler */
 void (*sa_sigaction)
 (int, siginfo_t *, void *);
};

sa_mask 是設定把在跑 sigaction 時會額外 block 的 signal，也會再去 block 住自己的 signal
sa_flag 是可以設定要怎麼處理
sa_sigaction 是可以用不同參數的 signal handler 可以用特定 sa_flag 啟用

`sa_flag`

`SA_INTERRUPT`	`SA_NOCLDSTOP`	`SA_NOCLDWAIT`	`SA_NODEFER`	`SA_ONSTACK`	`SA_RESETHAND`	`SA_RESTART`	`SA_SIGINFO`
被 interrupt 的 sysytem call 不會 auto restart	不會去接收產生的 `SIGCHILD`	自己的 child 不會變 zombie，用 wait 時，要所有的 child 才會 return，等同 SIGCLD	不會在呼叫時把自己用 mask block 起來		呼叫一次 sigaction 一次有效	會 auto restart 被 signo interrupt 的 system call	使用 `sa_sigaction` 當作 signal handler

System V 有一個 SIGCLD 是可以不用 wait，然後 wait return 是所有 child 的結束才會 return

`sa_sigaction`

接收的 siginfo_t 可以接收資訊每個版本不一樣，但可以列出一些大家都有的

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


 struct siginfo {
 int si_signo; /* signal number */
 int si_errno; /* if nonzero, errno value from <errno.h> */
 int si_code; /* additional info (depends on signal) */
 pid_t si_pid; /* sending process ID */
 uid_t si_uid; /* sending process real user ID */
 void *si_addr; /* address that caused the fault */
 int si_status; /* exit value or signal number */
 long si_band; /* band number for SIGPOLL */
 /* possibly other fields also */
};

signal implement by sigaction

後面很多 signal 就是使用 sigaction impement 的

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


#include "apue.h"

/* Reliable version of signal(), using POSIX sigaction(). */
Sigfunc *
signal(int signo, Sigfunc *func)
{
 struct sigaction act, oact;

 act.sa_handler = func;
 sigemptyset(&act.sa_mask);
 act.sa_flags = 0;
 if (signo == SIGALRM) {
#ifdef SA_INTERRUPT
 act.sa_flags |= SA_INTERRUPT;
#endif
 } else {
#ifdef SA_RESTART
 act.sa_flags |= SA_RESTART;
#endif
 }
 if (sigaction(signo, &act, &oact) < 0)
 return(SIG_ERR);
 return(oact.sa_handler);
}

sigsetjmp & siglongjmp

1
2


int sigsetjmp(sigjmp_buf env, int savemask);
void siglongjmp(sigjmp_buf env, int val);

會可以設定之後恢復 sigmask 不管是不是 empty
把 sigmask 存在 env 當 savemask != 0

jmp 的處理

當 signal handler 設定會 jmp 到 setjmp 但此時收到時 setjmp 還沒設定好會出問題
有時候就會設定 global variable 來去在 longjmp 前確認 set 了沒，然後在 setjmp 完設定

`int sigsuspend(const sigset_t *sigmask)`

把 sigprocmask 跟 pause 做成 atomic
也就是會把 sigmask 設定成輸入的值然後 wait
一定會 return -1 然後 errno == EINTR
return 會恢復成之前的 sigmask
所以如果在 sigsuspend 前設定了 sigprocmask 來擋 critical reigion 的話（sigsuspend 開始等），要記得用在 sigsuspend 後把原本怕被 call 的 signal 從 sigmask 中移除後重新設定

critical reigion

signal 絕對不能被 deliver 的區塊

signal IPC

如果有需要在一開始先去 block 住 signal 的話，要在 parent 的 sigmask 設定好後再 fork 使得 child 繼承，才不會出現在剛 fork 完就收到 signal 的狀況

sleep

因為要不要保留前面的 alarm 秒數是 implementation issue，所以這邊不處理
會把前面的 signal handler 暫時存起來，再去 set alarm 然後處理，當中間被叫醒就把回傳值設定成剩下秒數，最後再把把之前的 signal handler 恢復，也就是假設有之前的 alarm 的 hadler 會不處理

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


#include "apue.h"

static void
sig_alrm(int signo)
{
 /* nothing to do, just returning wakes up sigsuspend() */
}

unsigned int
sleep(unsigned int nsecs)
{
 struct sigaction newact, oldact;
 sigset_t newmask, oldmask, suspmask;
 unsigned int unslept;

 /* set our handler, save previous information */
 newact.sa_handler = sig_alrm;
 sigemptyset(&newact.sa_mask);
 newact.sa_flags = 0;
 sigaction(SIGALRM, &newact, &oldact);

 /* block SIGALRM and save current signal mask */
 sigemptyset(&newmask);
 sigaddset(&newmask, SIGALRM);
 sigprocmask(SIG_BLOCK, &newmask, &oldmask);

 alarm(nsecs);

 suspmask = oldmask;
 sigdelset(&suspmask, SIGALRM); /* make sure SIGALRM isn't blocked */
 sigsuspend(&suspmask); /* wait for any signal to be caught */

 /* some signal has been caught, SIGALRM is now blocked */

 unslept = alarm(0);
 sigaction(SIGALRM, &oldact, NULL); /* reset previous action */

 /* reset signal mask, which unblocks SIGALRM */
 sigprocmask(SIG_SETMASK, &oldmask, NULL);
 return(unslept);
}

abort

會送一個 SIGABRT
當 user 有註冊 SIGABRT 的 signal handler 會先執行然後還不會 return，然後再換成 default call SIGABRT 來結束程式（不 return）
會出現問題在 longjmp 到其他地方（因為就不會繼續往下跑）、exit（因為要異常 terminate 變正常 terminate）
ANSI C 是說 file stream flush 跟是否要砍掉暫檔是 implementation issue
POSIX 是定義不允許 block 跟 ignore SIGABRT，且會 flush file stream
abort 在原先 signal handler 有 longjmp 的話會逃掉

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


void
abort(void) /* POSIX-style abort() function */
{
 sigset_t mask;
 struct sigaction action;

 /*
 * Caller can't ignore SIGABRT, if so reset to default.
 */
 sigaction(SIGABRT, NULL, &action);
 if (action.sa_handler == SIG_IGN) {
 action.sa_handler = SIG_DFL;
 sigaction(SIGABRT, &action, NULL);
 }
 if (action.sa_handler == SIG_DFL)
 fflush(NULL); /* flush all open stdio streams */

 /*
 * Caller can't block SIGABRT; make sure it's unblocked.
 */
 sigfillset(&mask);
 sigdelset(&mask, SIGABRT); /* mask has only SIGABRT turned off */
 sigprocmask(SIG_SETMASK, &mask, NULL);
 kill(getpid(), SIGABRT); /* send the signal */
 /*
 * 因為 kill 會在 return 前至少 deliver 一個包含自己剛剛送出的 non-block & non-ignore signal 才會 return
 * 所以把其他都 block 掉，然後等待 SIFABRT 抵達
 */

 /*
 * If we're here, process caught SIGABRT and returned.(not default handler)
 */
 fflush(NULL); /* flush all open stdio streams */
 action.sa_handler = SIG_DFL;
 sigaction(SIGABRT, &action, NULL); /* reset to default */
 sigprocmask(SIG_SETMASK, &mask, NULL); /* just in case origin handler block it again */
 kill(getpid(), SIGABRT); /* and one more time */
 exit(1); /* this should never be executed ... */
}

ANSI C

如果成功跑完會 flush buffer 然後 delete 所有 temp file

POSIX

如果成功終止程式，會 fclose 所有 file

implement

如果原本 SIGABRT 是 ignore 會把它設定成 default 然後 fflush

variable type（補充）

normal

就是一般的變數，在最佳化可以被操作

static

在 function 內部時會把值在跳出時依然存下來（用全域變數實踐）
在 module（c 檔）中作為非 body(function) 變數不能被外部存取（區域變數）

const

常數，只可讀不可寫

register

推薦放 variable 到 register，但只有不要放在 register 的才能絕對確定
當 register 有空會放到 register，但就會沒有 address

volatile

宣告說不論在哪邊改數字，跟判斷中間可能都會被更改（不要放到 regiter 去）
也就是讓 compiler 知道部會只看 function 直接跑
一定有 address，且不能被 compiler 自行判斷有關這個的結果因爲前面結果而取消

1
2
3
4
5
6
7


static int foo;
void bar (void){
foo = 0;
 while(foo != 255)
 ;

}

可能會被 compiler 優化改成

1
2
3
4
5
6
7


static int foo;

void bar (void){
 foo = 0;
 while(true)
 ;
}

如果是中間接到 signal 改了 foo 會出問題

restrict

指的 source 是不能被用兩次，目前是給 programmer 看，compiler 不一定要實作也就是不能有 overlaping

NTU SP Chapter 11 - Thread

Sun, 15 Dec 2024 00:00:00 +0800

what’s thread

用同一個 Virtual Memeory
可以平行執行
被稱為 lightweight process
除了不同的 process 會 contecxt switch，在 thread 也會有

pre thread item

progtam item
register
stack
scheduling policy
errno process
signal mask

process vs. thread

process

通常是不同 user own
因此考量到安全性，會不太能share resource(memory)
用 fork 這個 expensive 的來 create new process
context switch cost high

thread

own by same user
shared resource，所以要自己保護
所有 thread 是平等關係除了 main thread
cost of thread creation and switch is low
通常稱作新增（等同在 process fork+exec）的動作叫做 spawn

memory(stack)

有一種做法是把 stack 分成一小塊一小塊，分給不同 thread，每個 stack 的就是只能用到那塊的底部

特性

beneft

asynchronous event(如 signal) 處理上就很容易
處理要 share 的 memory 會很方便
可以在 blocking system call 更方便
thrughput（單位時間可以處理的工作量）在把問題切得很多部份可以 improve
可以降低在處理 block system call 就被 suspend 的狀況，可以降低 response time

drawback

要避免 memeory race condition
不好 debug 因為不會一行行跑
效能的運用會比較差，假設沒有足夠的 CPU core，

OS

對 OS 來說還是同一個 process，分不出不同 thread

user-level thread

就在 user space 的 prcess 中有一個 run-time system
run-time system 會 schedueling thread
每個 run-time system 有 thread table 裡面會記 TCB(thread control block)

implement

要對於 read 這些 blocking system call 要處理，避免整個 process suspend
通常會在 run-time system 攔截 read 之類的 system call
要擁有 preemptive，實作上可以用 signal 的 interrupt 特性來寫，

preemptive

OS 會擁有強制中斷 process 執行的能力，通常都是這種，為了做 context switch

non-preemptive

系統無法強制中斷 process 在 CPU 中執行，windows 3.1 3.2 就是

kernel-level thread

kernel space 除了 process table 還有 thread table Windows XP 2000 就是這種切換 thread 的 cost 就會比較高所以通常結束 thread 不會把那塊 TCB 還回去，而是 unmark 來使得之後要使用的時候不用再要一次，且可以減少刪除的 cost

hybrid thread

在 process 中有 kernel thread 然後，kernel thread 裡面也有 user thread Solaris

POSIX thread

其他系統如 Windows 有自己的 Win32 thread
是在 user-space implment 所以不是 system call
如果沒有去建立就會是 single thread，從 main 開始跑，然後會是 main thread

per thread their own

Thread ID, stack, registers, signal mask, errno value, scheduling properties, thread specific data

creation

return < 0 都是有問題，且不止 -1
int pthread_create( pthread_t *tidp, pthread_attr_t *attr, void *(*start_rtn)(void *), void *arg )

tidp: pointer for thread id/handle
attr: customized thread attribute (NULL: default)
start_rtn: starting function for the created thread 輸入是任意指標，輸出也是任意指標
arg: argument for the starting function pointer to a structure 丟進去的那項指標 arg 任何 thread 都可以接收 terminate thread 的 TCB
main thread terminate 會結束一切
create 完誰先跑跟 fork 一樣是看 CPU scheduling

thread id

pthread_t pthread_self ( void ) 可以拿到 thread id(非 pointer) int pthread_equal ( pthread_t tid1,pthread_t tid2 ) 可以比較不同 thread id 是否相同

thread attributes

int pthread_attr_init(pthread_attr_t *attr); int pthread_attr_destroy(pthread_attr_t *attr); 設定屬性在 create 時用
要先 allocate 一個 pthread_attr_t 的變數
規定 init 的 atrribute 一定要 destroy，因為可能會去額外 allocate resource
init 會把 pthead_attr_t 設定成 invaild 來避免誤用。

detachstate 比較常見，設定成 detatch 的話不用回收 terminated status
guardize 設定 thread stack 的 end 後的一塊 buffer 用來防止壓到其他 stack
stackaddr 可以設定 thread 在 stack 中的 thread stack 的 low address
stacksize 可以設定 thread 在 stack 中的 thread stack 的 size int pthread_attr_setdetachstate(pthread_attr_t *attr, int detachstate); int pthread_attr_getdetachstate(const pthread_attr_t *attr, int *detachstate);

detatch

int pthread_detach(pthread_t thread);
可以用 function 設定指定 id 的 thread（含自己）的 detach stat
除了 create 時設定跟用 pthread_detach 外，也可以用 pthread_join() 去回收 terminated 的 tcb

有些 implementation 會用 light process implement 所以有時候會有 share problem
正常是使用時的時候會最好不要有 share resource 的問題，因為會共用
如果遇到傳入參數的要避免被 return 所以 invalid
不同 thread 最好也不要共用參數，因為不知道哪個先執行

terminate

whole process

在以下任一條件，process 會結束

任一 thread call exit 系列
收到會 terminate 的 signal
main thread 的 main() return

only thread

從 start routine return
call pthread_exit
被其他 thread cancel（異常死亡）

`void pthread_exit(void *retval);`

不會 close file 跟 flush
retval 是可以設定 return value，等同於 start routine return
main thread 如果使用會 block 直到所有 thread 結束
main 也可以在結束所有任務，但其他 thread 還要 run 的時候可進行 pthread_join 來去等其他 thread terminated
return 也可以把 int 轉成 (void *) 在接收時傳回去，在 open source 也很常見
回傳也要注意不要傳 local variable 的 ptr

join

int pthread_join(pthread_t tid, void **rval_ptr);
異常死亡也要去 join
只能去等 non-detach 的 thread，並且會 block 直到該 thread terminated
如果拿到 canceled thread 會收到 PTHREAD_CANCELED
如果是去拿 detached 的 thread 會 return EINVAL
rtval_ptr 設定成 NULL 帶癟不回收資訊
回收完會 detach，所以假設另一個 thread 要去 join 就會失敗
int pthread_timedjoin_np(pthread_t thread, void **retval, const struct timespec *abstime);
是 non-block 的版本，超過時間就會 return ETIMEDOUT
int pthread_tryjoin_np(pthread_t thread, void **retval);
是除非可以回收否則就是回傳失敗

cancel

int pthread_cancel(pthread_t tid);
效果如同 tid 的 thread 去 call thread_exit(PTHREAD_CANCELED)
要記得 join 或 detach 來使得 tcb 回收
是會丟一個 request 給 tid
要知道成功完成 cancel 可以用 join 來知道

int pthread_setcancelstate(int state, int *oldstate);
可以設定自己要不要被 cancel

PTHREAD_CANCEL_ENABLE(default)
- 不會馬上 terminated
- 執行到 cancelation point 才會 cancel
PTHREAD_CANCEL_DISABLE
- 會 pending cancel request 直到被設定成 enable 然後是 cancelation point 才會 cancel cancelation point 通常是 system call

int pthread_setcanceltype(int type, int *oldtype);
設定 cancelability type

PTHREAD_CANCEL_DEFERRED(Default)
- 到 cancelation point 才 cancel
PTHREAD_CANCEL_ASYNCHRONOUS
- 收到立刻結束

cancelation point

void pthread_testcancel(void);
等同於 cancelation point
因為 asynchronously cancel 會對一些存取 share resource 的狀況出問題，可以用加上 lock 來處理
通常 cancelation point 都是 block system call

cleanup

就是像是 atexit 的作用
void pthread_cleanup_push(void (*routine)(void *), void *arg); void pthread_cleanup_pop(int execute);

pthread_exit
canceled
call pthread_cleanup_pop()，且 argument 不為 0，只會執行最上面的 function

兩個一定要成對出現不然會出錯
return from start routine 不會執行，因為代表該執行的都執行完了

thread synchronization

兩個 thread 做 i++，因為實際上是很多動作，所以有可能會是 A 先 +1 然後 context switch 到 B 然後 + 1 ，這樣兩個值在使用時都會變成 i+2 => race condition
有三個方法可以解決：

Mutex lock
readers-writer lock
condition variable memory lock 會需要跟著 lock 的 memory

Mutex

Mutual-exclusion interfaces
advisery lock
lock memory 的 resource
用之前要 lock，用完要 unlock
如果要用的被 lock 會 block
本身就是個 object
在存取的東西 unlock，其他所有要存取同樣資源 block 住的資源的 thread 就會變 runable 然後被丟到 ready queue 從請求 lock 繼續，先 schedule 到的會拿到，其他在執行時又會 block
child process 會繼承，因為是 VM 分開
要防止 deadlock 的一個方法是用 non-blocking 、排 order 、granukarity（多個情況共用 lock）或是用 condition variable
怎麼去分配 lock 數是個學問，因為太多 lock 雖然可以增加平行化，但一直請求 lock 會造成 performance 降低，且有 dead lock 的問題

init and destroy

int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *mutexattr);
也可以 static allocte: pthread_mutex_t mlock = PTHREAD_MUTEX_INITIALIZER設成 default attribute（但是 static 就不能改）
dynamic allocate 就是用 init 然後記得要 destroy，因為可能會額外 allocate
int pthread_mutex_destroy(pthread_mutex_t *mutex);
有 process-shared attribute 跟 type attributeL，設定為 NULL 就會設成 default
在三種可以解決 share resource 的方法中只有 mutex 有 type attribute

attribute

int pthread_mutexattr_init(pthread_mutexattr_t *attr);
int pthread_mutexattr_destroy(pthread_mutexattr_t *attr);
也是要動態宣告跟 destroy
可以在這邊設定可以跨 process 存取同一塊 memory

PTHREAD_PROCESS_SHARED 可以跨 process share memory
PTHREAD_PROCESS_PRIVATE (default) 不行跨 process share memory 而可以用 MACRO 在 compile time check 有沒有提供這個功能，或是在 runtime 用 sysconf（check 跟 file 無關的，跟 file 有關就是 pathconf）來 check 用各個 function 去改
type attribute 有四種
normal
- 不會 error check 跟 deadlock detection
errcheck
- 會 error check 跟 deadlock detection
recuresive
- 單個 thread 可以多次 lock，但也要用相同次數的 unlock（有 lock count），也會 error check 跟 deadlock dection
default
- 看系統（大部分是 Normal）可能的 error 如 lock 住自己 lock 過的，會 deadlock、unlock 別人的 lock(undefine)，unlock 已經被 unlock 的

1
2
3


int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_trylock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);

trylock 就是 unblock mode 的 lock
比 readerwriter lock 好 implement，效率較高，但只能同時讀寫一個

ReaderWriter lock

可以多個去拿 readlock，write lock 只能有單獨一個，就是跟 file lock 的概念一樣
只有一個 attribute 就是 process-share
attribute 的宣告也有 static 跟 dynamic
一樣有 init, destroy, unlock
lock 跟 trylock 有 rdlock 跟 wrlock 兩個版本

Thread Pool

有個 work queue 會排很多 job，Master thread 會去 update
程式會 maintain 一個 pool 裡面有 worker threads，稱之為 thread pool
worker thread 當作完事情，會去 work queue 看有沒有跟目前閒置的 thread id 符合的並領取，然後去把 work queue 上的那個 job remove
job queue 通常是 link-list
有一個方式是上 read lock 去確認，有了再去用 write lock 更新，可以比 mutex 增加平行度，但會有當 queue 空了的話會 busy waiting 的狀況
更好的方式是用 condotion variable

condition variable(cv)（一定會考）

*-free 代表沒有什麼
會是 race-free（不會不定期的一直 recheck，減少資源的競爭）用來解 job queue 空，但每個 thread 都在 busy waiting 來去查找 jib queue
一定會搭配 mutex 用
允許一個明確的通知事件（exclicit event notification）
動 condition 一定要取得 mutex
基本上就是兩個概念：wait 跟 signal
int pthread_cond_init(pthread_cond_t *cond, pthread_condattr_t *cond_attr);
int pthread_cond_destroy(pthread_cond_t *cond);

attribute

只有 PTHREAD_PROCESS_SHARED 會用到

func

int pthread_cond_signal(pthread_cond_t *cond);
是可通知單個在 wait 的 cv
int pthread_cond_broadcast(pthread_cond_t *cond);
通知所有在 wait 的 cv 然後看誰先搶到 mutex 誰就先 return，其他人則是會去等 mutex lock

int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);

sleep 直到收到 cv signal
睡前 relese mutex lock（以上為 atomic
去拿 mutex lock 然後 return（等到 lock 才會 return） int pthread_cond_timedwait(pthread_cond_t *cond, pthread_mutex_t *mutex, const struct timespec *abstime);
有 timeout 的版本，但是是要帶時間點進去，也就是要在 gettimeofday() 的 return 去加上要等的時間

usage

拿 mutex lock 對要查的 condition
看 conditon
用 condition wait 來放掉 mutex lock 然後 sleep，並且使用 condition variable
當其他人發現條件達成，用 codition signal 通知指定 cv，然後當是被叫的那個的話就拿回 mutex lock 再 return
做事然後最後 unlock mutex lock

在 2. 通常會是用 while 來避免當通知前，通知的 thread 放掉 mutex 然後被改了，可以繼續睡下去

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


// Waiting for x==y condition
pthread_mutex_lock(&m);
while (x != y) // 用 while 很重要
 pthread_cond_wait(&v, &m);
// do something here if necessary
pthread_mutex_unlock(&m);

//Notifying waiting thread that x is incremented
pthread_mutex_lock(&m);
x++;
pthread_mutex_unlock(&m);
// 可能中間 context switch 造成 x != y
pthread_cond_signal(&v);

opensource 通常會先 signal 再去 unlock，不過反過來在一些狀況也不會影響
這樣做是因為 wait 會先解除 sleep 然後再去 wait mutex lock，假設是 signal 完 context switch 就會變成 wait 的在那邊等 lock 然後送 signal 的 thread 再去 unlock mutex，這樣條件再沒有其他人先去請求 mutex 的時候就會就不會被改到
反過來先 unlock 再送 signal 的話在一些有 priorty 的 thread pools 會出現問題

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


priority A > B
A 在等工作然後拿 mutex 之後執行 wait 把 mutex 放掉
此時 main thread 拿 lock 直到 work queue 空了 unlock
然後 B 做完事情去拿 mutex lock 拿到了
main thread signal
A 接收到但卡在 mutex
B 這時候就會在 while 那邊因為條件達成。所以直接去執行變得 B 會比 A 先

如果是先 signal 再 unlock 的話，A B 都會在等 mutex 的狀況
這時因為 priorty A 比較大，所以進到 ready queue 時會是 A 拿到 lock 先開始執行

memory mapping(ch 14.9)

除了 shmget 的另一個方法
把檔案 map 到記憶體
好處是不用像 buffer/unbuffer I/O 一樣搬來搬去
會把檔案 map 到 physical memory 然後再 link 到 VM stack 跟 heap 中間

void *mmap(void *addr, size_t len, int prot, int flags, int fildes, off_t off);

為了對應到 page 的開頭，off 通常會希望是 page size 的倍數，在 VM 上的 start addr(addr) 也是，len 也通常會是，page 大小可以用 sysconf 來取得，通常 addr 會設定成 NULL 讓系統決定
系統會希望剛好 map 到剛好完整在 physical memory 的 page 上，也就是會在 page 的開頭，所以通常會開到整數的 page 數，剩下空的補 0
prot 會設定無跟讀寫執行的權限，用 OR 開
mmap 可以設定 flag 成 MAP_SHARED 來使得兩個 process 可以 shared 同一塊 mapping 的記憶體（physical memory），也可以設定成 MAP_PRIVATE 來限制
performance 的分析會根據系統不同
可以開一個不存在的檔案拿到 fd mmap 來造成 memory shared 的效果，如 /dev/null，然後 fork 來讓兩個 process 來 share memory
或是可以 mmap fd = -1 然後 mmap 參數加上 MAP_ANOYMOUS 來使得沒有檔案沒有關係
多次呼叫 mmap fd = -1 不會有問題，就是開多塊 memory

Virtual memory

gcc 預設是 dynamic link
一般的程式碼是 static link
dynamic 的存放位置會 load 在 stack 跟 heap 中間的區域
UNIX VM 通常習慣 1G 給 kernel 3G 給 user
thread 執行時也會用到 stack 跟 heap 中間的區域

Thread vs. fork()

fork 完假設有 memory lock 在原本的 VM 中在 fork 時會被繼承，但是 thread 會被清空，所以會造成 dead lock
exec 完因為會清掉 VM 所以會把 memory lock 清掉
fork 完 child 剩下的 thread 就是 fork 它的 thread

int pthread_atfork(void (*prepare)(void), void (*parent)(void), void (*child)(void))
prepare 是在 call fork 時會去執行的，child 是在 child process fork 完 return 前會執行的，parent 是 fork 完 return 前會去執行的
可以在處理 fork 時用 prepare 把所有的 memory lock 上上去，再去 fork，並且在 child 可以在執行前先把所有東西 unlock，確保不會在 fork 時造成有無法解鎖的 lock
atfork 執行的順序在 prepare 是 stack，child 跟 parent 是 queue，是因為了可以對稱，比如說 lock 跟 unlock 就會成對

thread signal

sigaction 對所有的 thread 都是一樣，所以不論是 ignore 或是設定 signal handler 都是整個 process 的 thread 都有效
signal mask 每個 thread 分開
signal 在 thread 一般來說不像 process 那邊是 asynchronous，因為是多半是平行化跑，不會有被中斷的問題，所以會是 synchronous
thread 的 context 是 signal handler 本身
通常會是一個或多個 thread 去處理，然後通常會用 while 去不停 wait
如果宣告了 sigaction（process handle）然後同時又用了 sigwait（thread handle）會由系統決定誰去處理，通常不會這樣找麻煩

generate

synchronously
- 執行了一定會發生
- system 因 excpetion 而產生
  - 應該要 debug
- 某個 thread(internal) 用 kill 送給另一個 thread
  - 該個 signal 收
asynchronously
- 外部 (external) 的 process 用 kill 送的（包括 ^C）
- 系統任挑一個沒有 block 的

dedicated signal handling thread

特定用來處理 signal 的 thread
把其他 thread 對要處理的 signal block 起來，只讓要處理的 thread unblock

inherit

signal mask 會繼承 spawn 出自己的 thread 的 mask

mask

int pthread_sigmask(int how, const sigset_t *set, sigset_t *oldset);
要去處理就會呼叫，參數跟 sigpromask 一樣

int sigwait(const sigset_t *restrict set, int *restrict signop);
跟 sigsuspend 概念一樣，可以去改 mask 然後 wait，但是參數不一樣
參數不像 sigsuspend 是替換 mask（block 的 signal），sigwait 是放要等的 signal（unblock 的 signal）
因為 signal handler 是 thread 本身，所以不會 handler call 完才 return，會在 signal 來就 return
return 完接著就會去處理 signal
會 atomic 的處理 mask 跟 pause 然後 return 前會恢復 sigmask，然後把接到的 signal 寫到 signop

implement

在操作時通常會讓 spawn 前先把 mask 關好，等處理好初始狀態再交給 thread unblock
一開始就是處理給 sigwait 用的 signal mask 跟其他東西，然後再去用 while loop 包住 sigwait 跟 signal handler 的程式，因為 sigwait return 前會還原 mask 所以會有跟 sigaction 在 handler 執行時 block 住 signal 相同的效果。

thread safe/atomic I/O

因為 fd 是共用的，所以不能用一般的 read write & lseek
ssize_t pread(int fildes, void *buf, size_t nbyte, off_t offset);
ssize_t pwrite(int fildes, const void *buf, size_t nbyte, off_t offset);
pread pwrite 是 atomic 所以在 unbuffer I/O 要用這個

thread-safe function

因為要避免在 function 到一半因為要跑其他 thread，然後又被呼叫一次造成的問題條件是 thread 不能有 static variable
通常是在 function 後面加上一個 _r 來代表 thread-safe

thread-safe vs. async-signal safe

在多個 threads 中被中斷時重複呼叫不會出問題 vs. 在 signal handler 中間被中斷時重複呼叫不會出問題
負面表列（但通常還是有另外提供 thread safe 版本）vs. 正面表列
可以在 multi-thread reentrant vs. 在 async-signal handler 可以 reentrant
thread-safe 不代表 async-signal safe：
如 malloc 在裡面上 mutex lock 然後這樣在 thread 中可行，但在 async-signal handler 就會 deadlock
也就是用 mutex 保護的可以 thread-safe 但是在 async-signal 不會是 safe 在沒有惡意處理的情況下（如把 global variable 複製到 local）async-signal safe 通常是 thread-safe

thread-safe FILE object

通常 C 的 Buffer-I/O function 會呼叫 flockfile 使得是 thread-safe
void flockfile(FILE *filehandle);
int ftrylockfile(FILE *filehandle);
void funlockfile(FILE *filehandle);
就是可以把 file stream 上 lock，通常 fprintf, fscanf 會難見呼叫
是 recurive lock（有 lockcount）
為了提升如用 for loop print 一個個 char 的狀況可以用 _unlocked 版本，手動 lock & unlock

NTU SP Chapter 14 - Advanced I/O

Sun, 15 Dec 2024 00:00:00 +0800

blocking vs non-blocking

Blocking 是要等完成後才 return
Nonblocking 就是以待在 CPU 為主，能讀多少就讀多少，寫入時雖然一般來說不會去即時寫入，但是在 buffer cache 滿了的情況
nonblocking 就回傳失敗，除了 time slice 以外基本上不會離開 CPU

slow system calls

可能沒有辦法完成的 system call
read networking 就是例子，就是可能會沒有辦法完成的，所以就要用 system call

stdout 要 ‘\n’ 或 fd 的 buffer 滿了才會輸出，stderr 沒有 buffer 所以會直接輸出

terminal 有兩個 mode ，一個是按 enter 才會動，一個是即時反應（raw mode）

I/O multiplexing

busy waiting

non-blocking 對 CPU 是一個浪費，雖然不會出現要等別人的代價，但就是會比較浪費記憶體

multiing tasking

會造成 CPU 負荷很大

I/O multiplexing

在有人 I/O 等待的時候可以解決

select

先在 select 對於 readfds, writefds, exceptfds 個去開個 set 去看每個有沒有需求進行讀寫，就會是 0 or 1
可以用 FD_ZERO 來把指定 set 進行初始化成 0
要用 FD_SET 去指定要 ON 的 number，FD_CLR 去取消

1

select(nfds, readfds, writefds, errofds, timeouts)

要等到有人 ready 才會 retrun，但沒說有人 ready 就立刻 return
nfds 會在 0 ~ nfds-1 檢查 ready 的數量後 reaturn，所以還需要用 FD_ISSET 去確認
其他參數就是 pointer，timeout 可以設成 NULL 就會等到有回應為止
要注意會把 set 改掉，所以要 copy 一份

poll

select 的改良版

1
2
3
4
5


struct pollfd {
int fd; // file descriptor to check, or <0 to ignore
short events; // bit mask: each bit indicates an event of interest on fd (more than select)
short revents; // bit mask: each bit indicates an event that occurred on fd
}

就是只記錄要用的東西，不會改掉 set

1

poll( fdarray[], nfds, timeout )

結果

只有省在 I/O waiting 的部分

aio_系列

非同步 I/O 的 read write

lock

three way lock

flock 會把整個檔案鎖起來
fcntl 作業要練的
lockf 用 fcntl 來實作的

types of Locks

對於不同 process 才成立，同 process 不成立

shared read lock

可以多個去同時拿，但會把 write lock 鎖起來，不過因為有可能在系統實作時會檢查有沒有人在等 write lock，會使得在那情況使得新的人去拿 readlock 會暫時拿不到

Eclusive write lock

只有一個人可以去拿到

fcntl lock

F_SETLK 如果有辦法就會去拿，沒辦法就 return
F_SETLKW 如果沒辦法就等到拿到為止
F_GETLK 不要再要存取時先去確認，因為不一定同步

Lockptr

1
2
3
4
5
6
7
8


Lockptr
struct flock {
 short l_type; /* F_RDLCK, F_WRLCK, or F_UNLCK */
 off_t l_start; /* offset in bytes, relative to l_whence */
 short l_whence; /* SEEK_SET, SEEK_CUR, or SEEK_END */
 off_t l_len; /* length, in bytes; 0 means lock to EOF ( 會更新到最後 ) */
 pid_t l_pid; /* returned with F_GETLK */
}

process 在結束掉會把 lock 都還回去

lock 跟著 file 跟 proess，跟 file desc. 無關
close 檔案會把 lock 拿掉（不管 file desc.，所以像是同一 process dup 複製 file desc. 到其他 new fd，或是 open 兩次，close new fd 也會把 fd 的 lock 放掉

Advisory lock

fcntl 只能管理透過 fcntl 進行 write 的操作，所以不透過 fcntl 就可以寫入，但是也可以透過檔案權限管理來防止不透過 fcntl 的寫入或讀取，可以兼顧安全跟效率。
因為這樣只要鎖住限制只能透過程式來進行存取，來使得透過指定的帳號進行操作，且使用 fcntl

Mandatory lock

不管怎麼樣 read write 都要去去進到 kernel mode 去確認可不可以寫，但是 cost 很高

NTU SP Chapter 15 - IPC

Sun, 15 Dec 2024 00:00:00 +0800

Intrerprocess Communication(IPC)

ICP types
pipes (half duplex)
FIFOs
Stream pipes(full duplex)
named stream pipes
message queues
semaphores 重要
shared memory 重要，最快
sockets
streams

不同 computer 的通訊

socket
stream

UNIX Pipe

可以跨 process
能用同一個 pipe 的 process 必須要有共同祖先，因為是用 fork 會繼承 fd 的特性
使用 pipe 會傳送到 kernel 的一塊 string 的空間
只能一端寫進去，一端讀出來，不能 random acess，可以多個人寫跟讀
讀完就會被清掉，所以兩 process 不會讀到相同的東西（讀會把東西 pop 掉）
可以用來在 parent 跟 child 間溝通，把 parent 跟 child 的各自其中要關掉的讀 / 寫關掉，就可以用來當作兩個 process 溝通的橋樑
當沒有人讀的時候，寫的人就會收到 SIGPIPE 的 signal
如果寫的人比 pipe 的 size 還要小，寫入的過程一定是 atomic
不用的要記得 close 掉會浪費資源以及會不小心操作到
當寫超過 pipe 的 buffer size 會 suspend
不把不用的東西 close 掉在作業跟考試會扣分

stream pipe

可以雙向的 pipe

name pipe

給予名字，可以突破不同祖先

name stream pipe

集合兩個特點

FIFOs

概念是有名字的 pipe，所以讀完就會清掉
在讀跟寫沒有人 oepn 就會把資料都清掉

`int mkfifo(const char *pathname, mode_t mode)`

mode 是在管理 rwx
會在 pathname 創一個 fifo 檔案
open 時可以設為 O_NONBLOCK

沒有人讀的判斷

在寫入到一個沒有被 open for reading 會收到 SIGPIPE
建議要在送出去的資料前面加入自己 client 的資訊好判斷來源

沒有人寫

會收到 EOF ，所以建議要在讀取是 open for wr

師大資工程式設計期末專題

Sun, 16 Jun 2024 23:00:00 +0800

師大資工程式設計期末專題

Slides

Repo

About

Tue, 16 Apr 2024 00:00:00 +0000

Experience

Instructor, TCFSH CIRC 39th
Student, NTNU CSIE 116
PM of R&D Team & Instructor, NTNU CSIE Camp 2024
Officer, Information Department, 40th NTNU CSIE Student Association
Deputy Officer, Information Department, 41st NTNU CSIE Student Association

師大資工程式設計二期中考解題心得

Mon, 15 Apr 2024 23:00:00 +0800

前言

題目

這次整體難度比上學期期中考跟期末考難度低，加上老師跟助教有提示要先去寫處理 BMP file 的 function，所以寫得很順。

第一題 Matrix Multiplication

第一題是要處理矩陣運算，但不會給你矩陣的大小，所以要先把整個矩陣用 fgets 讀進來再處理，雖然我這題早就有寫好的 vector header 可以用來存矩陣，但因為處理輸入太花時間，所以跳過。

得分：0 / 25

第二題 Text Compression

第二題是要處理字串壓縮，這題我把字元對應的二進製讀進來，並用 strtol 來轉成十進位再丟到開好大小為 $29$ 的 array 裡，然後同時儲存長度來處理開頭是 $0$ 的情況。接下來就是開一個 byte 暫存然後計算暫存長度跟對應到字元的長度是否 $\geq 8$ ，如果是就把暫存的 byte 寫入檔案，然後把暫存的 byte 清空，直到該字元加字串的長度$\lt 8$，中間合併字串就只是單純的位元運算，然後等把字串全部寫完後，再把處理最後的 padding。

得分：25 / 25

 1
 2
 3
 4
 5
 6
 7
 8
 9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174


#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

int main()
{
 char file_name[5000];
 printf("Codebook: ");
 fgets(file_name, 5000, stdin);
 file_name[strlen(file_name) - 1] = '\0';
 FILE *codebook = fopen(file_name, "r");
 if (codebook == NULL)
 {
 printf("No file.\n");
 return -1;
 }
 printf("Input File: ");
 fgets(file_name, 5000, stdin);
 file_name[strlen(file_name) - 1] = '\0';
 FILE *input = fopen(file_name, "rb");
 if (input == NULL)
 {
 printf("No file.\n");
 return -1;
 }
 printf("Output File: ");
 fgets(file_name, 5000, stdin);
 file_name[strlen(file_name) - 1] = '\0';
 FILE *output = fopen(file_name, "wb");
 if (output == NULL)
 {
 printf("No file.\n");
 return -1;
 }

 int32_t encode[29];
 int32_t encode_len[29] = {0};
 for (int32_t i = 0; i < 29; i++)
 {
 encode[i] = -1;
 }
 char code[100];
 while (!feof(codebook))
 {
 fgets(code, 100, codebook);
 if (code[0] == '\n')
 {
 continue;
 ;
 }
 if (code[1] == ':')
 {
 if (code[0] >= 'a' && code[0] <= 'z')
 {
 encode[code[0] - 'a'] = strtol(code + 3, NULL, 2);
 encode_len[code[0] - 'a'] = strlen(code + 3) - 1;
 }
 else
 {
 printf("Invalid codebook.\n");
 goto terminate;
 }
 }
 else
 {
 if (strstr(code, "space:"))
 {
 encode[26] = strtol(strchr(code, ':') + 2, NULL, 2);
 encode_len[26] = strlen(strchr(code, ':') + 2) - 1;
 }
 else if (strstr(code, "comma:"))
 {
 encode[27] = strtol(strchr(code, ':') + 2, NULL, 2);
 encode_len[27] = strlen(strchr(code, ':') + 2) - 1;
 }
 else if (strstr(code, "period:"))
 {
 encode[28] = strtol(strchr(code, ':') + 2, NULL, 2);
 encode_len[28] = strlen(strchr(code, ':') + 2) - 1;
 }
 else
 {
 printf("Invalid codebook.\n");
 goto terminate;
 }
 }
 }
 fclose(codebook);
 int8_t temp = 0;
 int8_t temp_len = 0;
 while (!feof(input))
 {

 char c = fgetc(input);
 if (c == EOF)
 {
 break;
 }
 int32_t code_now = 0;
 int32_t code_now_len = 0;
 if (c >= 'a' && c <= 'z')
 {
 code_now = encode[c - 'a'];
 code_now_len = encode_len[c - 'a'];
 }
 else if (c == ' ')
 {
 code_now = encode[26];
 code_now_len = encode_len[26];
 }
 else if (c == ',')
 {
 code_now = encode[27];
 code_now_len = encode_len[27];
 }
 else if (c == '.')
 {
 code_now = encode[28];
 code_now_len = encode_len[28];
 }
 else
 {
 printf("Invalid input.\n");
 goto terminate;
 }
 if (code_now == -1)
 {
 printf("Invalid codebook.\n");
 goto terminate;
 }
 // fprintf(stderr, "*%d %d\n", code_now, code_now_len);
 while (temp_len + code_now_len > 8)
 {
 temp = (temp << (8 - temp_len)) | (code_now >> (code_now_len - (8 - temp_len)));
 // fprintf(stderr, "%d ", temp);
 fwrite(&temp, 1, 1, output);
 code_now = code_now & ((1 << (code_now_len - (8 - temp_len))) - 1);
 code_now_len = code_now_len - (8 - temp_len);
 temp = 0;
 temp_len = 0;
 }
 temp = temp << code_now_len | code_now;
 temp_len += code_now_len;
 // fprintf(stderr, "(%d %d\n", temp, temp_len);
 if (temp_len == 8)
 {
 // fprintf(stderr, "a%d ", temp);
 fwrite(&temp, 1, 1, output);
 temp = 0;
 temp_len = 0;
 }
 }

 if (temp_len != 0)
 {
 temp = temp << (8 - temp_len);
 temp += 1 << (8 - temp_len - 1);
 fwrite(&temp, 1, 1, output);
 }
 else
 {
 temp = 0b10000000;
 fwrite(&temp, 1, 1, output);
 }
 fclose(input);
 fclose(output);
 return 0;
terminate:
 fclose(codebook);
 fclose(input);
 fclose(output);
 return -1;
}

第三題 Face/Off

這題因為我之前沒準備到縮放的 function，所以是寫完第二題才回來寫，這題因為我之前準備的 header file 裡的 function 是寫讀指定位置那個 pixel 的值，用 fseek 跳來跳去，所以很方便，然後在考試時就趕工寫縮放的 function，因為說是線性縮放，我不確定助教意思是什麼，所以我就直接算比例然後把對應的位置強制轉型成 int32_t 然後去讀取。當我把 header file 的 function 寫完後，這題就只要 for 迴圈跑過整個圖片，把 y 值上下反轉然後再對應的範圍內寫入新的圖片就好。

得分：5 / 25

我居然忘記把高度再往下偏移，也就是抓到的點是左下不是左上，最後只拿到錯誤處理的 5 分。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85


#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include "mybmp.h"

int main()
{
 char file_name[5000];
 printf("cover: ");
 fgets(file_name, 5000, stdin);
 file_name[strlen(file_name) - 1] = '\0';
 FILE *cover = fopen(file_name, "rb");
 if (cover == NULL)
 {
 printf("No file.\n");
 return -1;
 }
 printf("x (in pixel): ");
 int32_t x;
 scanf("%d", &x);
 printf("y (in pixel): ");
 int32_t y;
 scanf("%d", &y);
 printf("w (in pixel): ");
 int32_t w;
 scanf("%d", &w);
 printf("h (in pixel): ");
 int32_t h;
 scanf("%d", &h);
 printf("new: ");
 fgetc(stdin);
 fgets(file_name, 5000, stdin);
 file_name[strlen(file_name) - 1] = '\0';
 FILE *new = fopen(file_name, "rb");
 if (new == NULL)
 {
 printf("No file.\n");
 return -1;
 }
 printf("output: ");
 fgets(file_name, 5000, stdin);
 file_name[strlen(file_name) - 1] = '\0';
 FILE *output = fopen(file_name, "wb");
 if (output == NULL)
 {
 printf("No file.\n");
 return -1;
 }
 sBmpHeader cover_header = read_header(cover);
 FILE *image_write = fopen("tmp.bmp", "wb");
 scale_image(new, image_write, w, h);
 fclose(image_write);
 fclose(new);
 new = fopen("tmp.bmp", "rb");
 sBmpHeader new_header = read_header(new);
 fwrite(&cover_header, sizeof(sBmpHeader), 1, output);
 // forgot in mid
 y+=new_header.height;
 // forgot in mid
 // y = cover_header.width - y;
 for (int32_t i = 0; i < abs(cover_header.height); i++)
 {
 for (int32_t j = 0; j < cover_header.width; j++)
 {
 sBmpPixel24 pixel;
 if (i >= cover_header.height - y && i < cover_header.height - y + h && j >= x && j < x + w)
 {
 pixel = read_pixel(new, new_header, i - (cover_header.height - y), j - x, 0);
 }
 else
 {
 pixel = read_pixel(cover, cover_header, i, j, 0);
 }
 fwrite(&pixel, sizeof(sBmpPixel24), 1, output);
 }
 write_edge_pixel(cover_header.width, output);
 }
 fclose(cover);
 fclose(new);
 fclose(output);
 remove("tmp.bmp");

 return 0;
}

第四題 Colorful Fantastic Render System []

這題是最簡單的，只要先設一個 $256 \times 256$ 的 array 來存顏色，設定顏色跟方向循環用的 array，存現在位置，再把每一個指令射程 function 來處理就好，然後中括號的循環就是用遞迴來處理，就是從 ‘[’ 讀到 ‘]’ 然後跑兩次就好。

得分：23 / 25 我忘了把顏色填入陣列了，兩分顏色處理就沒了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203


#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include "mybmp.h"

#define WIDTH 256
#define HEIGHT 256
int32_t di[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int32_t dj[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int32_t ri = 0, rj = 0;
int32_t now_x = 127, now_y = 127;
int32_t color_now = 0;
sBmpPixel24 color_draw[8];
sBmpPixel24 picture[256][256];

int8_t F_command()
{
 now_x += di[ri];
 now_y += dj[rj];
 if (now_x < 0 || now_x >= WIDTH || now_y < 0 || now_y >= HEIGHT)
 {
 return -1;
 }
 picture[now_x][now_y] = color_draw[color_now];
 return 0;
}
int8_t R_command()
{
 ri = (ri + 1) % 8;
 rj = (rj + 1) % 8;
 return 0;
}

int8_t C_command()
{
 color_now = (color_now + 1) % 8;
 return 0;
}

int8_t loop_command(int32_t *code_n, char *code)
{
 (*code_n)++;
 int32_t temp = *code_n;
 while (code[*code_n] != ']')
 {
 if (code[*code_n] == '[')
 {
 loop_command(code_n, code);
 }
 else if (code[*code_n] == 'F')
 {
 if (F_command() == -1)
 {
 break;
 }
 }
 else if (code[*code_n] == 'R')
 {
 R_command();
 }
 else if (code[*code_n] == 'C')
 {
 C_command();
 }
 (*code_n)++;

 }

 *code_n = temp;

 while (code[*code_n] != ']')
 {
 if (code[*code_n] == '[')
 {
 loop_command(code_n, code);
 }
 else if (code[*code_n] == 'F')
 {
 if (F_command() == -1)
 {
 break;
 }
 }
 else if (code[*code_n] == 'R')
 {
 R_command();
 }
 else if (code[*code_n] == 'C')
 {
 C_command();
 }
 (*code_n)++;
 }
 return 0;
}

int main()
{
 char file_name[5000];
 printf("Enter the output filename: ");
 fgets(file_name, 5000, stdin);
 file_name[strlen(file_name) - 1] = '\0';
 FILE *file = fopen(file_name, "wb");
 if (file == NULL)
 {
 printf("No file.\n");
 return -1;
 }
 printf("Enter the background color (R,G,B): ");
 sBmpPixel24 bg_color;
 scanf("(%hhd,%hhd,%hhd)", &bg_color.r, &bg_color.g, &bg_color.b);
 printf("Type code here: ");
 fgetc(stdin);
 char code[1000];
 fgets(code, 1000, stdin);
 code[strlen(code) - 1] = '\0';

 create_bmp24_bg(WIDTH, HEIGHT, bg_color, file);
 fclose(file);
 file = fopen(file_name, "rb");
 sBmpHeader header = read_header(file);
 // forget in midterm.
 for(int32_t i =0;i<256;i++)
 {
 for(int32_t j = 0;j<256;j++)
 {
 picture[i][j]=read_pixel(file,header,i,j,0);
 }
 }
 // forget in midterm
 file = fopen(file_name, "wb");

 {
 color_draw[0].r = 0xff;
 color_draw[0].g = 0xff;
 color_draw[0].b = 0xff;

 color_draw[1].r = 0;
 color_draw[1].g = 0;
 color_draw[1].b = 0;

 color_draw[2].r = 0x33;
 color_draw[2].g = 0x66;
 color_draw[2].b = 0xff;

 color_draw[3].r = 0x00;
 color_draw[3].g = 0xcc;
 color_draw[3].b = 0x00;

 color_draw[4].r = 0x00;
 color_draw[4].g = 0xcc;
 color_draw[4].b = 0xcc;

 color_draw[5].r = 0xcc;
 color_draw[5].g = 0x00;
 color_draw[5].b = 0x00;

 color_draw[6].r = 0xcc;
 color_draw[6].g = 0x00;
 color_draw[6].b = 0xcc;

 color_draw[7].r = 0xcc;
 color_draw[7].g = 0xcc;
 color_draw[7].b = 0x00;
 }
 int32_t code_n = 0;
 while (code[code_n] != '\0')
 {
 if (code[code_n] == '[')
 {
 loop_command(&code_n, code);
 }
 else if (code[code_n] == 'F')
 {
 if (F_command() == -1)
 {
 break;
 }
 }
 else if (code[code_n] == 'R')
 {
 R_command();
 }
 else if (code[code_n] == 'C')
 {
 C_command();
 }
 code_n++;
 }

 fwrite(&header, sizeof(sBmpHeader), 1, file);
 for (int i = 0; i < HEIGHT; i++)
 {
 for (int j = 0; j < WIDTH; j++)
 {
 fwrite(&picture[i][j], sizeof(sBmpPixel24), 1, file);
 }
 write_edge_pixel(WIDTH, file);
 }
 fclose(file);
 return 0;
}

結論

這次因為最後剩十幾分鐘來不及寫完第一題，不過如果有個一小時應該是寫得完第一題的，然後第四題是真的好玩，感謝老師調降難度。

Search

Mon, 01 Jan 0001 00:00:00 +0000

VPN	PFN	page table unit
0	1	1
1	5	1
2	4	1
3	2	1
4	3	2
5	9	2
6	8	2
7	7	2
8	10	3
9	11	3
10	6	3
11	15	3
12	12	4
13	14	4
14	13	4
15	16	4

VPN	PFN	page table unit
0	1	1
1	5	1
2	4	1
3	2	1
4	3	2
5	9	2
6	8	2
7	7	2
8	10	3
9	11	3
10	6	3
11	15	3
12	12	4
13	14	4
14	13	4
15	16	4

VPN	PFN	page table unit
0	1	1
1	5	1
2	4	1
3	2	1
4	3	2
5	9	2
6	8	2
7	7	2
8	10	3
9	11	3
10	6	3
11	15	3
12	12	4
13	14	4
14	13	4
15	16	4