基础知识_操作系统

o |======
  |======
  |------

一个进程可以类比成一个车间，多进程就是多个车间。
每个线程相当于车间内的一条生产，多线程就是一个车间内有多条生产线。

不同车间之间需要运送货物，可以人工搬运、传送带、货车等，
相当于进程间管道、消息队列、共享内存等IPC通信。

每个车间内有需要加工的材料，不同生产线都可以使用这些材料，
相当于线程间可以共享进程的一些资源，比如堆区数据、文件描述符等，
于是产生了资源争用，需要一些同步互斥的手段。

这个工厂内只有一个工人，就相当于CPU，他可以选择去不同的生产线去工作，
在不同的生产线之间切换，就相当于cpu的时间片轮转。

工人每次只能在一条生产线工作，代表对于内核来说，只有线程的概念，而没有进程的概念。

工人在不同生产线之间切换是相对容易的，不同车间之间的切换是比较麻烦的。

一个车间发生了事故，另一个车间一般还能继续工作。
而一条生产线发生事故，其他生产线可能就会受影响。

功能总结：
进程创建的核心实现在于copy_process()方法过程，而copy_process() 的主要实现在于copy_xxx()方法，根据不同的flags来决策采用何种拷贝方式。
执行dup_task_struct()，拷贝当前进程task_struct
检查进程数是否超过系统所允许的上限(默认32678)
执行sched_fork()，设置调度器相关信息，设置task进程状态为TASK_RUNNING，并分配CPU资源
执行copy_xxx()，拷贝进程的相关资源信息
	copy_semundo: 当设置CLONE_SYSVSEM，则父子进程间共享SEM_UNDO状态
	copy_files: 当设置CLONE_FILES，则只增加文件引用计数，不创建新的files_struct
	copy_fs: 当设置CLONE_FS，且没有执行exec, 则设置用户数加1
	copy_sighand: 当设置CLONE_SIGHAND, 则增加sighand->count计数
	copy_signal: 拷贝进程信号
	copy_mm：当设置CLONE_VM，则增加mm_users计数
	copy_namespaces：一般情况，不需要创建新用户空间
	copy_io： 当设置CLONE_IO，则父子进程间共享io context，增加nr_tasks计数
	copy_thread_tls：设置子进程的寄存器等信息，从父进程拷贝thread_struct的sp0，sp,io_bitmap_ptr等成员变量值
执行copy_thread_tls(), 拷贝子进程的内核栈信息
执行alloc_pid()，为新进程分配新pid

链接：https://www.jianshu.com/p/d811fb1017d3

就绪←→运行
  ↖  ↙
   阻塞

新建→就绪←→运行→终止
	  ↖  ↙
	   阻塞

老张爱喝茶，废话不说，煮开水。
出场人物：老张，水壶两把（普通水壶，简称水壶；会响的水壶，简称响水壶）。
1.老张把水壶放到火上，立等水开（同步阻塞）,老张觉得自己有点傻。
2.老张把水壶放到火上，去客厅看电视，时不时去厨房看看水开没有。（同步非阻塞）老张还是觉得自己有点傻，于是变高端了，买了把会响笛的那种水壶。水开之后，能大声发出嘀~~~~的噪音。
3.老张把响水壶放到火上，立等水开。（异步阻塞）老张觉得这样傻等意义不大.
4.老张把响水壶放到火上，去客厅看电视，水壶响之前不再去看它了，响了再去拿壶。（异步非阻塞）老张觉得自己聪明了。

所谓同步异步，只是对于水壶而言。普通水壶，同步；响水壶，异步。
	虽然都能干活，但响水壶可以在自己完工之后，提示老张水开了。这是普通水壶所不能及的。
	同步只能让调用者去轮询自己（情况2中），造成老张效率的低下。
所谓阻塞非阻塞，仅仅对于老张而言。立等的老张，阻塞；看电视的老张，非阻塞。
	情况1和情况3中老张就是阻塞的，媳妇喊他都不知道。
虽然3中响水壶是异步的，可对于立等的老张没有太大的意义。
所以一般异步是配合非阻塞使用的，这样才能发挥异步的效用。
来源：https://www.zhihu.com/question/19732473/answer/23434554

xxx

访问页	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
一号页	7	7	7	2		2		2			2			2				7	 	 
二号页		0	0	0		0		4			0			0				0	 	 
三号页			1	1		3		3			3			1				1	 	 
缺页否	√	√	√	√		√		√			√			√				√	 	 

缺页9次，置换6次。

访问页	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
一号页	7	7	7	2		2	2	4	4	4	0			0	0			7	7	7
二号页		0	0	0		3	3	3	2	2	2			1	1			1	0	0
三号页			1	1		1	0	0	0	3	3			3	2			2	2	1
缺页否	√	√	√	√		√	√	√	√	√	√			√	√			√	√	√

缺页15次，置换12次

访问页	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
一号页	7	7	7	2		2		4	4	4	0			1		1		1		
二号页		0	0	0		0		0	0	3	3			3		0		0       
三号页			1	1		3		3	2	2	2			2		2		7       
缺页否	√	√	√	√		√		√	√	√	√			√		√		√

缺页12次，置换9次

static int __=[](){std::ios::sync_with_stdio(false);return 0;}();
class LRUCache {
public:
    LRUCache(int capacity) {
        pageNumber=capacity;
    }
    //如果访问页在内存中，返回其value并更新该key。如果访问页不在，返回-1。
    int get(int key) {
        auto it=pageToCache.find(key);
        if(it==pageToCache.end()){
            return -1;
        }
        pair<int,int> tmp=*(it->second);
        cache.erase(it->second);
        cache.push_front(tmp);
        pageToCache[key]=cache.begin();
        return tmp.second;
    }
    //如果要设置的页不在内存，则插入该页，并判断是否超出限制。如果该页在内存，则更新该页。
    void put(int key, int value) {
        auto it=pageToCache.find(key);
        pair<int,int> tmp(key,value);
        if(it!=pageToCache.end()){
            (*(it->second)).second=value;
            cache.erase(it->second);
            cache.push_front(tmp);
            pageToCache[key]=cache.begin();
        }else{
            cache.push_front(tmp);
            pageToCache[key]=cache.begin();
            if(cache.size()>pageNumber){
                pageToCache.erase(cache.back().first);
                cache.pop_back();
            }
        }
    }
private:
    list<pair<int,int>> cache;
    unordered_map<int,list<pair<int,int>>::iterator> pageToCache;
    int pageNumber;
};

struct Node{
    int key;
    int val;
    int freq;
    Node(int k,int v,int f):key(k),val(v),freq(f){}
};

class LFUCache {
public:
    LFUCache(int _capacity):minfreq(0),capacity(_capacity) {}
    
    int get(int key) {
        if(capacity==0) return -1;
        auto it=cache.find(key);
        if(it==cache.end()) return -1;
        int val=it->second->val,freq=it->second->freq;
        freq_page[freq].erase(it->second);
        if(minfreq==freq && freq_page[freq].size()==0) minfreq++;
        freq_page[freq+1].push_front(Node(key,val,freq+1));
        cache[key]=freq_page[freq+1].begin();
        return val;
    }
    
    void put(int key, int value) {
        //如果容量为0，则退出
        if(capacity==0) return ;
        auto it=cache.find(key);
        //如果hash表中没有该key，需要添加当前key value
        if(it==cache.end()){
            //如果当前容量满了，需要先删除访问频率最小的那页，再添加新页
            if(cache.size()==capacity){
                int lastkey=freq_page[minfreq].back().key;
                freq_page[minfreq].pop_back();
                if(freq_page[minfreq].size()==0) minfreq++;
                cache.erase(lastkey);
            }
            //添加新的一页
            freq_page[1].push_front(Node(key,value,1));
            minfreq=1;
            cache[key]=freq_page[1].begin();
        }else{  //如果hash表中有该key，则更新其value，跟get()操作相似
            int freq=it->second->freq;
            freq_page[freq].erase(it->second);
            if(minfreq==freq && freq_page[minfreq].size()==0) minfreq++;
            freq_page[freq+1].push_front(Node(key,value,freq+1));
            cache[key]=freq_page[freq+1].begin();
        }
    }
private:
    int minfreq;
    int capacity;
    unordered_map<int,list<Node>::iterator> cache;
    unordered_map<int,list<Node>> freq_page;
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

int in=0,out=0;
item buffer[n];
semaphore mutex=1,empty=n,full=0;

void producer(){
    do{
        producer an item nextp;
        ...
        P(empty); //使empty减1；
        P(mutex); //同步互斥一块出现时同步在前。(如果先获得锁，接着在P操作阻塞了。消费者就会在获取锁的时候也阻塞)
        buffer[in]=nextp;
        in=(in+1)%n;
        V(mutex); //mutex+1；
        V(full);
    }while(true)
}

void consumer(){
    do{
        P(full);
        P(mutex);
        nextc=buffer[out];
        out=(out+1)%n;
        V(mutex);
        V(empty);
        consummer the item in mutex;
        ...
    }while(true);
}
//注意两个程序中的加锁操作(P操作)不能颠倒，否则可能引起进程死锁，解锁顺序无所谓。

#define N 5
semaphore chopstick[5];	//对应5根筷子的信号量，初值为1.

void philosopher(int i){	//i是哲学家编号，0-4
	while(true){
		think();	//思考
		P(chopstick[i]);	//取左手边筷子
		P(chopstick[(i+1)%N]);	//取右手边筷子
		eat();	//吃饭
		V(chopstick[i]);	//放下左手边筷子
		V(chopstick[(i+1)%N]);	//放下右手边筷子
	}
}

#define N 5
semaphore chopstick[5];	//对应5根筷子的信号量，初值为1.
semaphore mutex;	//*互斥信号量，初值为1

void philosopher(int i){	//i是哲学家编号，0-4
	while(true){
		think();	//思考
		P(mutex);	//*进入临界区，加锁
		P(chopstick[i]);	//取左手边筷子
		P(chopstick[(i+1)%N]);	//取右手边筷子
		eat();	//吃饭
		V(chopstick[i]);	//放下左手边筷子
		V(chopstick[(i+1)%N]);	//放下右手边筷子
		V(mutex);	//*退出临界区解锁
	}
}

#define N 5
semaphore chopstick[5];	//对应5根筷子的信号量，初值为1.

void philosopher(int i){	//i是哲学家编号，0-4
	while(true){
		think();	//思考
		
		if(i%2==0){
			P(chopstick[i]);	//取左手边筷子
			P(chopstick[(i+1)%N]);	//取右手边筷子
		}else{
			P(chopstick[(i+1)%N]);	//取右手边筷子
			P(chopstick[i]);	//取左手边筷子
		}
		
		eat();	//吃饭
		V(chopstick[i]);	//放下左手边筷子
		V(chopstick[(i+1)%N]);	//放下右手边筷子
	}
}

#define N 5
#define LEFT (i+N-1)%N
#define RIGHT (i+1)%N

#define THINKING 0	//思考状态
#define HUNGRY 1	//饥饿状态
#define EATING 2	//进餐状态

int state[N];	//记录5根筷子的状态
semaphore mutex;	//访问state需要的互斥锁，初值为1

semaphore s[5];		//每个哲学家一个信号量，初值为0.(可以将哲学家左右两根筷子看做一个整体)

void test(int i){//尝试让i号哲学家拿起两根筷子
	if(state[i]==HUNGRY && state[LEFT]!=EATING && state[RIGHT]!=EATING){
		state[i]=EATING;	//条件符合，设置为进餐状态
		V(s[i]);	//表示i号哲学家的两根筷子都能拿了
	}
}

void take_chopstick(int i){	//取筷子
	P(mutex);
	state[i]=HUNGRY;	//修改自己为饥饿状态
	test(i);	//尝试取筷子
	V(mutex);
	P(s[i]);	//没有筷子则阻塞，有筷子就获取筷子进餐。
}

void put_chopstick(int i){	//放下筷子
	P(mutex);
	state[i]=THINKING;	//设置自己为思考状态
	test(LEFT);		//通知左边的人尝试进餐
	test(RIGHT);	//通知右边的人尝试进餐
	V(mutex);	
}

void philosopher(int i){
	while(true){
		think();	//思考
		take_chopstick(i);	//取两根筷子
		eat();	//进餐
		put_chopstick(i);	//放下两根筷子
	}
}

读-读	允许，同一时刻可以有多个读操作
读-写 	互斥，同一时刻只能有一个主体去写。
		一个读者或写者在读操作，另一个写者就不能去写。
		一个写者在写，其他读者和写者就不能去读。
写-写	互斥，同一时刻只能一个写者在写。