Process🕸

process = code + data section + pc + registers + stack + heap

是资源组织分配的一个unit

new                                            done
 │                                              /\
 │                                               │ 
 └───────> ready ──────────────> running ────────┘ 
             /\                      │ 
             └─────────waiting <─────┘

PCB

存放在kernel mode的栈中

state
meta data

struct task_struct {
/* these are hardcoded - don't touch */
	long state;	/* -1 unrunnable, 0 runnable, >0 stopped */
	long counter;
	long priority;
	long signal;
	struct sigaction sigaction[32];
	long blocked;	/* bitmap of masked signals */
/* various fields */
	int exit_code;
	unsigned long end_code,end_data,brk,start_stack;
	long pid,father,pgrp,session,leader;
	unsigned short uid,euid,suid;
	unsigned short gid,egid,sgid;
	long alarm;
	long utime,stime,cutime,cstime,start_time;
	unsigned short used_math;
/* file system info */
	int tty;		/* -1 if no tty, so it must be signed */
	unsigned short umask;
	struct m_inode * pwd;
	struct m_inode * root;
	unsigned long close_on_exec;
	struct file * filp[NR_OPEN];
/* ldt for this task 0 - zero 1 - cs 2 - ds&ss */
	struct desc_struct ldt[3];
/* tss for this task */
	struct tss_struct tss;
};

Context Switch

该部分的实现，需要用到task_struct的结构

在user mode和kernel mode产生上下文交换，或者说在user mode使用syscall()时，相关的reg会存在ptregs中，在kernel mode的stack上

Inter- Process Communication

Google浏览器启动三种不同的进程:

Browser
Render
Plug-in

IPC的模型：

Message passing

较为整洁，但实现较为繁琐

send和recv

在分布式系统中是关键
Shared memory

安全性有很大问题

没有通用的解决方案，起始的ID无法share
Signal
Pipe

使用shared memory实现

f[0] 是读入端，f[1]是写入端

文件描述符同样使用这种方式，只不过为管道命名了

fork产生的子进程会继承父进程对应的文件描述符。利用这个特性，父进程先pipe创建管道之后，子进程也会得到同一个管道的读写文件描述符。从而实现了父子两个进程使用一个管道可以完成半双工通信。此时，父进程可以通过fd[1]给子进程发消息，子进程通过fd[0]读。子进程也可以通过fd[1]给父进程发消息，父进程用fd[0]读
Socket

Thread

线程是运行以及调度的基本单元，而进程是分配资源的基本单元

fork()和exec()
中断信号处理
线程终止目标线程
线程本地存储
调度

一个线程是一个执行的单元

thread:

id
stack
pc
regs set

需要share的内容：

code section
data section
heap
files and signals

**************-----*****************
code            data           files
registers                      stack

               thread
*******single-threaded process******

**************-----*****************
code            data           files
registers    registers         registers
stack        stack             stack
thread       thread            thread
*******single-threaded process******

Detailed figure:
****************************---------****************************
  globale variable              shared address space
****************************---------****************************
  thread                thread                 thread
  pc                    pc                     pc
  stack                 stack                  stack
****************************---------****************************
method f              shared code           method g
****************************---------****************************
                        \    /
                         \  / 
                          \/
                        process

thread的概念是在1967年提出的，在Linux中是red hat实现的，而microsoft不开源，同样的是apple

优势：

轻量级，开销较小，不需要清理cache
上下文切换开销较小
资源共享
响应性很好

client --request--> server --new thread--> thread
                   |    /\
                   |____|

NGINX是一个web引擎

缺点：

一个线程会影响整个进程
存储会限制thread的数量

user thread和kernel thread

在chrome中，既是mutiple process又是mutiple threads

当一个thread调用fork时，只会产生一个，单线程的进程，而不会复制进程中的所有线程

引入thread后，发送的signal变成了thread接收，不同的thread会处理不同的signal

一般thread的终止一般是异步的

Windows thread

提供Windows API，可以实现one-to-one mapping, kernel-level

```c /* *the primary structures of a thread include: */ struct ETHREAD; struct KTHREAD; struct TEB;
Linux thread

在引入thread的概念后，pcb -> tcb，所以一个process中，含有许多的task_struct

所以process中的第一个thread的task_struct，作为process的task_struct:pid = tid[0]

pcb == tcb[0]

可以使用clone()函数，指定不同的flag，来规定共享部分的尺度

thread的栈是以页对齐的

同样的thread，在user mode和kernel mode中都有布局，都有其task_struct，在调用system call时，会跳转到kernel mode中，使用相应的栈，并执行相应的代码

user mode下的stack的大小作为虚拟地址可以任意涨，而kernel mode下的stack只有4k大小

所以一个thread只有一个task_struct，这也说明了，Linux下的thread满足的是1:1的mapping

Synchronization

Race Condition:

int counter = 0;
void worker(){    
    for (int i = 0;i < 1000000; i++ ){
        counter++;
    }
}

int main(){
    pthread_create(....1);
    pthread_create(....2);
    printf("%d\n",counter);
    return 0;
}

                               ld a1, mem()
   counter = counter + 1 ===>  addi $0x1,%eax
                               sd a1, mem()
                               
     os         thread_1              thread_2           
 ─────────────────────────────────────────────────────
                  ld 
                  addi 
   interrupt 
    switch
                                       ld
                                       addi
                                       sd
   interrupt 
   switch 
                  sd

在汇编层面，很容易出现这样竞态现象

Critical Section

类似写、更新存储的操作，中间是严格不能有其它指令的，也就是互斥

单核：关闭中断以独占cpu
多核：用锁，来避免竞态

实现Critical Section的要求：

Mutual Exclusion

互斥访问：在同一时刻，最多只有一个线程可以执行临界区
Progress

空闲让进：当没有线程在执行临界区代码时，必须在申请进入临界区的线程中选择一个线程，允许其执行临界区代码
Bounded waiting

当一个进程申请进入临界区后，必须在有限的时间内获得许可并进入临界区

Peterson’s Solution

flag[0] = FALSE;
flag[1] = FALSE;
//P0:
do{
    flag[0] = TRUE;
    turn = 1;
    while(flag[1] && turn);
    //critical section
    flag[0] = FALSE;
    //remainder section
}while (1);

//P1:
do{
    flag[1] = TRUE;
    turn = 1;
    while(flag[0] && turn);
    //critical section
    flag[1] = FALSE;
    //remainder section
}while (1);

乱序执行和分支预测为cpu的发展提供了很大的进步

该方法只适用于两个进程的互斥，并不实用，如果出现instruction reorder时，就会对其产生影响

Hardware Support

Memory barriers

使其他处理器立即看到存储变化的指令，现在使用的使meakly ordered

```c //ensure t1 output 100: //t1: while (!flag); memory_barrier(); printf(“%d”,x);

//t2 x = 100; mamory_barrier(); flag = true;

Hardware Instructions

原语指令(atomically)

test and set

bool test_set(bool *target){
    bool rv = *target;
    *target = TRUE;
    return rv;
}

使用该指令来加锁:

//shared
bool lock = FALSE;
    
do{
    while(test_set(&lock));
    //critical section
    lock = FALSE;
    //remainder section
}while (TRUE);

满足bounded waiting的版本：

```c //shared bool lock = FALSE;

do{ waiting[i] = true;

while(waiting[i] && test_set(&lock));
    
waiting[i] = false;
//critical section
j = (i + 1)%n;
while((j != i) && !waiting[j])
    j = (j + 1) %n;
if (j == 1) 
    lock = false;
else waiting[j] = false;
    
//remainder section }while (TRUE);

compare and swap

int compare_and_wsap(int *value, int expected, int new_value){
    int temp = *value;
    if (*value == expected)
        *value = new_value;
    return temp;
}

使用该指令来加锁：

while(true){
    while(compare_and_swap(&lock,0,1) != 0);
    //critical section
    lock = 0;
    //remainder section
}

在x86中:cmpchg

在ARM64中:LDREX, STREX

Atomic variables

void increment(atomic_int*v){
    int temp;
      
    do{
        temp = *v;
    }while(temp != (compare_and_swap(v,temp, temp + 1)));
      
}

最后给一个锁的总称:mutex locks

while(true){
    acquire();//acquire lock;
    //critical section;
    release();//release  lock;
    //remainder section;
}

Deadlocks

两个或者多个进程，同时独立地等待事件的执行，造成其中一个程序的等待

Priority inversion

Priority inheritance

死锁的四种情况：

资源互斥
一个进程持有至少一个资源，等待取来另一个进程持有的资源
无竞态
循环等待

解决死锁：

Prevention
- mutual exclusion
  
  不申请共享资源
  
  只持有非共享的资源
- hold and wait
  
  当申请资源时，不能持有任何资源
  
  没有拿到资源时，要释放掉所有的资源
- no preemption
  
  当进程未申请到需要的资源时：
  - 释放掉当前所有的资源
  - 将需要的资源添加到等待队列里
  - 当获得所有等待的资源后，进程重启
- circuit wait
  
  从特定的顺序来申请资源
Avoidance

先计算是否会发生死锁，而不是在开始执行后才判断

会先计算出一个安全序列：safe state

Banker's Algorithms
Deadlock dectection and recovery

dectection:

resource-allocation graph -> wait-for graph

recovery:

关闭占用资源的进程

All the kernel comes from the bootlin.com

Process🕸

Contents

Process🕸

PCB

Context Switch

Inter- Process Communication

Thread

Synchronization

Deadlocks