概念

进程是正在运行的程序，它包含代码和执行状态（栈堆寄存器等）。而程序仅仅是一些静态的代码。一个程序可以生成多个进程（如记事本进程）。进程是资源分配最小单元

Linux系统进程

Linux进程是采用进程树的方式。程序开始时创建一个零号进程，然后零号进程创建一号进程再由一号进程创建其他的进程。linux进程是一种树状结构，可以通过pstree命令查看进程树。

sys/types.h：储存了一些宏定义如pid_t
#include <sys/wait.h>

fork():创建当前进程的子进程，并且子进程和当前进程完全相同。

返回值：返回两个返回值，如果返回值是零，代表当前在子进程中。如果返回值>0,代表在父进程中并且返回值是子进程pid，如果返回值<0,代表出错。

注意： 这里复制子进程是采用copy on right的方式，即开始子进程与父进程完全相同，只有当子父进程之间有差异时才会额外开辟空间储存差异。

例：

#include<stdio.h>
int main()
{
    int pid = fork();
    if(pid < 0)
    {
        fprintf(stderr, "fork error\n");
        exit(-1);
    }
    else if(pid == 0)
    {
        printf("this is the child process\n");
    }
    printf("this is the parent process\n");
    return 0;
}

getpid(): 获得pid

exec家族， 用于在子进程中调用系统中有的函数

int execl(const char *path, const char *arg, ...)

int execv(const char *path, char *const argv[])

int execle(const char *path, const char *arg, ..., char *const envp[])

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

int execlp(const char *file, const char *arg, ...)

int execvp(const char *file, char *const argv[])

其中有p的代表会自动在系统路径中搜索，例如
execlp("ls", "ls", " -l", NULL)会执行ls -l指令，如果没有p，则需要/bin/ls

v代表传入一个数组，这个字符数组加起来就是命令，最后以NULL结尾

e代表绝对地址

int wait(int *status)： 会阻塞当前进程，直到找到了僵尸子进程（死了的子进程），之后就彻底杀死子进程并返回进程号，失败会返回-1。status可以设置成NULL，

pid_t waitpid(pid_t pid,int *status,int options): pid是子进程进程号，表示只等待这一个子进程，其他子进程终止仍处于阻塞状态。

options有：

  • WNOHANG(wait no hung)： 即使没有子进程退出，它也会立即返回
  • Returns information about a child process stopped by SIGTTIN,
    SIGTTOU, SIGSSTP, and SIGTSTOP signals.(返回子进程被某些信号而停止的信息）

进程的状态

进程的状态一般可以分为三大类：运行，就绪，阻塞。

运行状态是指正在cpu中执行指令的进程。

就绪 是指获得了除cpu意外所有资源，正在等待cpu的进程

阻塞 是指因为某些原因放弃争夺cpu的进程

进程的调度

批处理系统中的调度

批处理系统就是不具备交互性，单纯完成任务的系统。这种系统一般需要考虑提高cpu利用率（早期计算机使用批处理系统）。批处理系统中的任务一般相对固定，所以可以大致知道它所需要花费的时间。

周转时间

周转时间 = 作业完成时刻 - 作业到达时刻 = 运行时间 + 等待时间

带权周转时间

带权周转时间 = $\frac{周转时间}{完成时间}$

先来先服务

指的是先来的任务先进行服务，这种方式最大的问题是单位时间内可以执行的任务数量比较低。如果一个任务时间很短而前面有一个需要大量时间的任务，那么他将不得不花很长的时间去等待。

最短时间优先

指的是时间短的进程先来服务。但是这种方式可能让时间长的进程一直无法执行（如果中间一直插入时间短的进程的话）

高响应率优先

这种方法考虑了等待时间的影响，是对最短时间优先的改进。

通过比较响应率，响应率高的先执行。

这种方法考虑了时间的影响，在时间短的进程先运行的同时不会让长进程无限制的等待。

交互式系统中的调度

交互式系统就是现在微机所使用的系统，在系统中需要运行的进程一般有很多，因此需要不停的将进程调入调出来让使用者感觉上进程是并行执行的。因此需要规定一个时间片避免进程无限制的执行。时间片到了会强制将当前进程调出然后从进程池中调入一个新的进程。在windows系统中时间片是15ms，linux系统中时间片是10ms

轮转调度

轮转调度是使用一个队列，运行完的进程放到队列的尾部，然后从队列的首部拉入一个进程执行。这种方法最大的问题是没有考虑到一些进程需要紧急执行（如火灾报警程序）

优先级调度

如图，这是优先级调度的一种组织形式。数字低的是高优先级（windows或linux中），他会首先从高优先级查找，如果有待执行的程序就执行它。

在windows系统中，正常的优先级是80，低于80是高优先级，高于80是低优先级。如果高优先级较多，低优先级可能一直没有执行的机会。所以高优先级一般都是服务进程，在不需要服务的时候他们会阻塞，一旦有信号将他们唤醒他们便会优先执行。

有时还会对使用cpu时间长的程序进行惩罚。

Priority = base + nice + CPU_PENALTY
CPU_PENALTY = CPU_USAGE * R
CPU_USAGE = CPU_USAGE * D

CPU_USAGE 是CPU使用次数，每过1s（或其他时间）就会执行第三条指令防止CPU_USAGE一直增大。而CPU_PENALTY就是根据CPU_USAGE得来的。

nice是我们可以设置的优先级，在linux中有个nice命令可以在程序运行前设置优先级，范围是-20-19，非root用户只能变大不能变小。renice可以在运行时设置优先级

竞争条件和信号量

进程之间有两种关系，协同和竞争。而怎么防止两个进程同时使用一个东西或如何通知其他进程便是多进程中需要考虑的问题

引例

这个队列是等待使用打印机的队列，out是即将被答应的文件。

我们可以假设这种情况，进程a刚刚访问in发现它是7但是这时时间片到了。它被迫退出cpu。此时进程b进入cpu发现in是7并且将文件放在7处。之后再回到a，a会把他的文件放在7处然后in++。这时b的文件就被覆盖掉了

皮德森算法

我们可以考虑这种情况，a进程到了turn = process处停止，b进程一路往下到了while，发现a进程对他有兴趣而终止。

而如果a到了turn = process终止，b也到turn = process终止，那么此时因为turn被改变，所以while第一个条件不满足，进入临界区。

这种算法可以解决竞争条件，但是首先它是对两个进程来说的，多个进程不好扩展，另外每次都要写这两个函数非常麻烦。

TSL信号法

此方法使用了一条汇编指令TSL，这条指令执行了两个内容mov lock, %register;mov $1, %lock ；前面相当于读锁的内容，后面是更改锁的值

这条指令和上面例子的区别是这是原子指令，也就是说要么都不做，要么必须做完，时钟中断不会产生干扰。

PV操作

更为常用的方法是使用pv操作，p就使信号量-1，v就使信号量+1.

信号量可正可负

信号量可正可负代表有一个等待队列，信号量为负时代表有多少个进程正在等待。

**信号量只有1或0

P(Semaphore e)
{
    while(!s)
    s--;
}

V(Semaphore e)
{
    s++;
}

注意： pv操作是操作系统提供的，他也是原子操作。

例子

生产者消费者问题

有一个生产者和消费者并且有一个队列可以存放生产者生产的产品。

一个普通的办法是

#define N 100
int count = 0;

void producer(void)
{
    int item;
    while(TRUE)
    {
        item = produce_item();
        if(count == N)sleep();
        insert_item(item);
        count = count+1;
        if(count == 1)wakeup(consumer);
    }
}

void consumer(void)
{
    int item;
    while(TRUE)
    {
        if(count == 0)
        {
            sleep();
        }
        item = remove_item();
        count -= 1;
        if(count == N-1)wakeup(producer);
        consume_item(item);
    }
}

这种方法是有问题的。假如消费者先运行，发现count == 0，然后发生时钟中断，之后生产者生产一个物品并发送wakeup信号，但这个时候consumer并没有睡眠，所以这个信号是没有用的。之后consumer睡眠，然后生产者一直生产物品也进行睡眠。这就产生了死锁。

#define N 100
semophore mutex = 1;
semophore empty = N;
semophore full = 0;

void producer(void)
{
    int item;
    while(TRUE)
    {
        item = produce_item();
        P(empty);
        P(mutex);
        insert_item(item);
        V(mutex);
        V(full);
    }
}
另外一个类似

这里empty和full也可以变成一个信号量，但是P的逻辑需要更改。empty初始值是N，每次生产一个就会减一，当empty变成0也就是满的时候就会阻塞。

哲学家就餐问题

哲学家问题是五个哲学家五根筷子，有五盘面，每个哲学家从左边和右边各拿一个筷子就可以吃到面，问怎样才可以让所有哲学家都吃到面。

如果完全不加控制，可能会出现五个人同时拿起左边筷子又同时拿起右边筷子的情况，这样就会饿死。



这里使用了信号量mutex保证同一时间只有一个人试图拿筷子

读写问题

读写问题是同一时间可以有多个读的，但是同一时间最多有一个写的，如果有人在读那么写的就要等待


这是读者优先的策略，还有写者优先和公平竞争。

写者优先

写者优先指的是可以有多个写，一旦有人在写就阻塞读。

reader:

    p(read);
    p(readcntsign);
    if(readcnt == 0)
        p(file);
    readcnt++;
    v(readcntsign);
    v(read);
   
    do_something();
    p(readcntsign);
    readcnt--;
    if(readcnt == 0)
        v(file);
    v(readcntsign);
    
writer:

    p(writecntsign);
    if(writecntsign == 0)
        p(read);
    writecnt++;
    v(writecntsign);
    
    p(file);
    do_something();
    v(file);
    
    p(writecntsign);
    writecntsign--;
    if(writecnt == 0)
        v(read);
    v(writecntsign);

公平竞争

公平急诊就是两者优先级相同，谁先来谁先进行。

/* 读者队列初始值为0，其他资源初始值为1*/
int readCount = 0;
semaphore keySignal = 1;
semaphore readCountSignal = 1;
 
reader()
{
    while(true)
    {
      wait(keySignal);        //申请令牌
      wait(readCountSignal);  //申请计数器资源
      if(!readCount)          //为零则申请文件资源
         wait(fileSrc);
      readCount++;
      signal(readCountSignal); //释放计数器资源
      signal(keySignale);      //释放令牌
 
      ...
      perform read operation  //执行临界区代码
      ...
  
      wait(readCountSignal);  //申请计数器资源
      readCount--;
      if(!readCount)                //为零则释放文件资源
         signal(fileSrc);
    signal(readCountSignal); //释放读者计数器资源
    }
}
 
writer()
{
     while(true)
     {
        wait(keySignal);     //申请令牌
        wait(fileSrc);       //申请文件资源
 
        ...
        perform write operation //执行临界区代码
        ...
 
        signal(fileSrc);   //释放文件资源
        signal(keysignal); //释放令牌
     }
}

例如一个读者先来，然后来了一个写者。这时写者因为申请不到filesrc而被阻塞。这时再来一个读者，读者因为申请不到key而被阻塞。于是第一个读者执行完成之后释放file。然后写者执行，然后读者再执行。

进程间通讯

  • 给进程发信号，但是信号只有63种并且有些还不能使用所以这种方法一般不使用。
  • 使用进程间通讯的函数

这些是进程间通讯的信号量，和下面线程间通讯不同。

#include<sys/types.h>
#include<sys/ipc.h>
#include<sys/sem.h>
+int semget(key_t key, int nesms, int semflg);key是信号量键值，nesm是创建信号量数量， semflg如果是IPC_EXCL创建唯一一个信号量，如果键值已经存在，那么就会出错。而IPC_CRATE即使存在也不会出错.返回semid
+int semctl(int semid, int semnum, int cmd, union semun arg): 删除或调整信号量，具体使用看下面
+int semop(int semid, struct sembuf *sops, size_t nsops):nsop是操作信号量数目（一般是1），结构体结构看下面

union semun {
	int val;
	struct semid_ds *buf;
	unsigned short int *array;
	/*struct seminfo *__buf;*/
};
struct sembuf {
	short sem_num;
	short sem_op;
	short sem_flg;
};
static void sem_del(semaphore sem_id)
{
    union semun sem_union;
    if (semctl(sem_id, 0, IPC_RMID, sem_union) == -1)
        fprintf(stderr, "Failed to delete semaphore\n");
}
int sem_p(semaphore sem_id)
{
    struct sembuf sem_b;
    sem_b.sem_num = 0;
    sem_b.sem_op = -1; /* P() */
    sem_b.sem_flg = SEM_UNDO;//进程结束而信号量没释放时，会自动释放信号量
    if (semop(sem_id, &sem_b, 1) == -1) {
        fprintf(stderr, "semaphore_p failed\n");
        return(0);
    	}
    return(1);
}
int sem_v(semaphore sem_id)
{
    struct sembuf sem_b;
    sem_b.sem_num = 0;
    sem_b.sem_op = 1; /* V() */
    sem_b.sem_flg = SEM_UNDO;
    if (semop(sem_id, &sem_b, 1) == -1) {
        fprintf(stderr, "semaphore_v failed\n");
        return(0);
    	 }
   return(1);
}

线程

线程可以看成比较小的进程，有自己的状态（寄存器和参数等），也会有一些可以被多个线程共享的参数（全局变量）。线程使独立运行和独立调度最小单元。线程可以分为用户级线程和内核级线程和混合线程三种方式。

  • 用户级线程： 这种线程不需要内核参与调度。优点是切换快（和函数调用类似），可以在不支持内核级线程的操作系统中执行。但是有一个缺点就是有一个线程被阻塞，那么其余该进程线程也会被阻塞-在操作系统层面上只会看到一个进程。
  • 内核级线程，由内核参与线程的调度。优点是一个线程被阻塞，那么其他的线程不会被阻塞，缺点是线程间切换所需时间多（要清空高速缓存等）

现在操作系统一般使用内核级线程

linux线程编程 C语言

头文件<pthread.h>

线程创建
extern int pthread_create (pthread_t *__restrict __newthread,
			   const pthread_attr_t *__restrict __attr,
			   void *(*__start_routine) (void *),
			   void *__restrict __arg) 
第一个参数是指向这个线程的指针。第二个参数设置线程的属性，一般设置成NULL。第三个参数是这个线程运行时所运行的函数。第四个参数是运行时函数的参数。

#include<stdio.h>
#include<pthread.h>
void* test(void* args)
{
    printf("this is the arguments-%s", (char*)args);
}
int main()
{
    pthread_t p;
    pthread_create(&p, NULL, test, "arg1");
    pthread_join(p, NULL);
    return 0;
}
输出： this is the arguments-arg1

如果想传递多个参数可以将参数整合成一个结构体然后传递结构体
  • int pthread_join(pthread_t thread, void **retval);.它的作用是让主线程等待某个线程结束再执行。retval是线程结束后的返回值，可以设置成NULL。

需要使用pthread_join的原因是主线程结束这个程序就结束了，这时候其他线程不一定执行完成。

  • 线程信号量 头文件pthread.h

    • pthread_mutex_t lock_put;//信号量创建
    • pthread_mutex_lock(&lock_put);
    • pthread_mutex_unlock(&lock_put);

    • pthread_mutex_init(&lock_put, NULL);//初始化，后面一般是NULL,当然也可以是下列值

      • PTHREAD_MUTEX_TIMED_NP，这是缺省值，也就是普通锁。当一个线程加锁以后，其余请求锁的线程将形成一个等待队列，并在解锁后按优先级获得锁。这种锁策略保证了资源分配的公平性。

      • PTHREAD_MUTEX_RECURSIVE_NP，嵌套锁，允许同一个线程对同一个锁成功获得多次，并通过多次unlock解锁。如果是不同线程请求，则在加锁线程解锁时重新竞争。

      • PTHREAD_MUTEX_ERRORCHECK_NP，检错锁，如果同一个线程请求同一个锁，则返回EDEADLK，否则与PTHREAD_MUTEX_TIMED_NP类型动作相同。这样就保证当不允许多次加锁时不会出现最简单情况下的死锁。

      • PTHREAD_MUTEX_ADAPTIVE_NP，适应锁，动作最简单的锁类型，仅等待解锁后重新竞争。

  • 线程信号量2 头文件semaphore.h
    • int sem_init (sem_t *sem , int pshared, unsigned int value);初始化,pshared固定是0来表示线程间通讯
      • value - 信号量 sem 的初始值。
    • int sem_post(sem_t *sem); 加1
    • int sem_wait(sem_t *sem); 减1
    • int sem_destroy(sem_t *sem); 销毁
  • 屏障： 屏障是当不满足条件时阻塞线程，满足条件之后再一起释放
    • pthread_cond_t cond; 创建
    • int pthread_cond_init(pthread_cond_t *cond, pthread_condattr_t *cond_attr)： 初始化，但是Linux中cond_attr并没有实现，所以直接NULL
    • int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex) : 等待,注意 还必须要有一个互斥量，只有拿到了互斥量才可以执行等待，并且与此同时会释放mutex。
    • pthread_cond_signal(): 激活一个等待线程
    • pthread_cond_broadcast()：激活所有等待线程，要注意激活后是从等待位置开始而不是从broadcast位置开始。
for (i = 0; i < 20000; i++) 
{
    int t = bstate.round;
    assert (i == t);
    
    pthread_mutex_lock(&bstate.barrier_mutex);
    bstate.nthread++;
    if(bstate.nthread < nthread)//没都到就待着
    {
	    pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
    }
    else//到了就全部激活
    {
	    bstate.nthread = 0;
	    bstate.round++;
	    pthread_cond_broadcast(&bstate.barrier_cond);
    }
    pthread_mutex_unlock(&bstate.barrier_mutex);
    usleep(random() % 100);
}

死锁问题

死锁条件：

  • 互斥条件： 一个资源只可以被一个进程占有
  • 保持和等待条件： 一个进程因请求而进入阻塞时，对自身已获得的资源不放。
  • 无抢占条件（抢占就是在一定条件下可以抢夺这个资源，如CPU就是抢占条件）
  • 循环等待条件： 形成首尾相接的环。如下

如图，圆代表进程，方形代表资源，由方形指向圆代表这个进程有这个资源，由圆指向方形代表这个进程需要这个资源。如果形成环路就代表出现了死锁。

资源按需分配可以破坏循环等待条件。

死锁解决方法：

  • 忽略问题
  • 检测复原，例如隔多少分钟产生一个备份，一旦死锁就让某个进程回到这个备份，相应资源也会被释放
  • 杀死某个进程释放资源。例如Spooling 技术。假脱机技术。为临界资源增加一个等待队列，使其好像可以被共享使用，如打印机。 当死锁发生时，杀死运行时间较短的进程，损失较小，因为容易恢复。
  • 动态避免通过小心的资源分配

银行家算法

银行家算法是通过资源分配来避免（不是预防）死锁的。并且没有破坏死锁的任何一个条件

首先要知道总共有多少资源，已经分配了多少资源，总共还剩多少资源，还需要多少资源。

总共有(10, 5, 7)个资源可以使用

现在还有(3, 2, 2)资源可以使用

之后一旦有进程请求就先把资源给他。如果资源不够就不给，如果资源够就用剩下的资源进行安全状态检查。

安全状态检查就是看看现有资源可以分配给哪个进程，有就把资源给他然后回收这个进程资源（不用考虑其他进程还会申请资源）。然后用这些资源再进行分配，如果最后有进程分配不了则说明这个状态不安全。

  • 例如p4申请了(2, 1, 0)资源，先把资源给他，那么现在还有(1, 1, 2)资源可以使用，p4变成(2, 2, 1)先把资源给p3然后回收，那么p3完成，剩余资源变成（3, 2, 3)
  • 把资源给p1, 剩余资源变成(5, 3, 3)
  • 资源给p4，剩余资源变成（7， 4， 5）
  • 之后就一步一步分配