操作系统

写在开篇

随着被字节和腾讯血虐，秋招告一段落了，接下来会好好总结，恢复更新博客。

概述

基本特征

1. 并发
   并发是指宏观上在一段时间内能同时运行多个程序，操作系统通过引入进程和线程，使得程序能够并发运行
   而并行则指同一时刻能运行多个指令，并行需要硬件支持，如多流水线、多核处理器或者分布式计算系统

2. 共享

   • 互斥共享
     互斥共享的资源称为临界资源，例如打印机等，在同一时刻只允许一个进程访问，需要用同步机制来实现互斥访问
   • 同时共享

3. 虚拟

   • 时（时间）分复用技术

     多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占用处理器，每次只执行一小个时间片并快速切换

   • 空（空间）分复用技术

     虚拟内存

4. 异步

   异步指进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进

基本功能

1. 进程管理
2. 内存管理
3. 文件管理
4. 设备管理

系统调用

• 内核态
• 用户态

Linux 的系统调用主要有以下这些：

Task	Commands
进程控制	fork()、exit()、wait()
进程通信	pipe()、shmget()、mmap()
文件操作	open()、read()、write()
设备操作	ioctl()、read()、write()
信息维护	getpid()、alarm()、sleep()
安全	chmod()、umask()、chown()

中断

1. 外中断
   由 CPU 执行指令以外的事件引起，如 I/O 完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。
2. 异常
   由 CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等。
3. 陷入
   在用户程序中使用系统调用。

进程管理

进程和线程

• 概念
  QQ 和浏览器是两个进程，浏览器进程里面有很多线程，例如 HTTP 请求线程、事件响应线程、渲染线程等等，线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时，浏览器还可以响应用户的其它事件。
• 区别
  1. 拥有的资源
     进程是资源分配的基本单位，但线程不拥有资源
  2. 系统开销
     创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备，所付出的开销远大于创建或撤销线程时的开销
     在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。
  3. 通信
     线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC

进程状态的切换

• 就绪状态（ready）：等待被调度
• 运行状态（running）
• 阻塞状态（waiting）：等待资源

有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。

阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

进程同步

临界区

对临界资源进行访问的那段代码称为临界区。

为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。

// entry section
// critical section;
// exit section

同步与互斥

• 同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后执行关系
• 互斥：多个进程在同一时刻只有一个进程能进入临界区

信号量

1. 特点
   信号量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作

• down : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0
• up ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作

2. 原型
   如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。

   typedef int semaphore;
   semaphore mutex = 1;
   void P1() {
       down(&mutex);
       // 临界区
       up(&mutex);
   }
   
   void P2() {
       down(&mutex);
       // 临界区
       up(&mutex);
   }

3. 例子

   #define N 100
   typedef int semaphore;
   semaphore mutex = 1;
   semaphore empty = N;
   semaphore full = 0;
   
   void producer() {
       while(TRUE) {
           int item = produce_item();
           down(&empty);
           down(&mutex);
           insert_item(item);
           up(&mutex);
           up(&full);
       }
   }
   
   void consumer() {
       while(TRUE) {
           down(&full);
           down(&mutex);
           int item = remove_item();
           consume_item(item);
           up(&mutex);
           up(&empty);
       }
   }

管程

使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。

进程调度

不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

批处理系统

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

1. 先来先服务（fcfs）
2. 短作业优先
3. 最短剩余时间优先

交互式系统

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

1. 时间片轮转
   将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。
2. 优先级调度
   为每个进程分配一个优先级，按优先级进行调度。为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。
3. 多级反馈队列
   一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。
   多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。
   每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。
   可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

   

   caozuoxitong03

实时系统

实时系统要求一个请求在一个确定时间内得到响应。

分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

进程间通信

管道

1. 特点

• 它是半双工的（即数据只能在一个方向上流动），具有固定的读端和写端。
• 只能在父子进程或者兄弟进程中使用
• 它可以看成是一种特殊的文件，对于它的读写也可以使用普通的read、write 等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中。

2. 原型

   #include <unistd.h>
   int pipe(int fd[2]);

管道是通过调用 pipe 函数创建的，当一个管道建立时，它会创建两个文件描述符：fd[0] 用于读，fd[1] 用于写。

3. 例子
   单个进程中的管道几乎没有任何用处。所以，通常调用 pipe 的进程接着调用 fork，这样就创建了父进程与子进程之间的 IPC 通道。

caozuoxitong01

若要数据流从父进程流向子进程，则关闭父进程的读端（fd[0]）与子进程的写端（fd[1]）；反之，则可以使数据流从子进程流向父进程。

#include<stdio.h>
#include<unistd.h>

int main()
{
    int fd[2];  // 两个文件描述符
    pid_t pid;
    char buff[20];

    if(pipe(fd) < 0)  // 创建管道
        printf("Create Pipe Error!\n");

    if((pid = fork()) < 0)  // 创建子进程
        printf("Fork Error!\n");
    else if(pid > 0)  // 父进程
    {
        close(fd[0]); // 关闭读端
        write(fd[1], "hello world\n", 12);
    }
    else
    {
        close(fd[1]); // 关闭写端
        read(fd[0], buff, 20);
        printf("%s", buff);
    }

    return 0;
}

FIFO

也称为命名管道，去除了管道只能在父子进程中使用的限制。

1. 特点

• FIFO可以在无关的进程之间交换数据，与无名管道不同
• FIFO有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中

2. 原型

   #include <sys/stat.h>
   // 返回值：成功返回0，出错返回-1
   int mkfifo(const char *pathname, mode_t mode);

其中的 mode 参数与open函数中的 mode 相同。一旦创建了一个 FIFO，就可以用一般的文件I/O函数操作它。

3. 例子
   FIFO的通信方式类似于在进程中使用文件来传输数据，只不过FIFO类型文件同时具有管道的特性。在数据读出时，FIFO管道中同时清除数据，并且“先进先出”。

write_fifo.c

#include<stdio.h>
#include<stdlib.h>   // exit
#include<fcntl.h>    // O_WRONLY
#include<sys/stat.h>
#include<time.h>     // time

int main()
{
    int fd;
    int n, i;
    char buf[1024];
    time_t tp;

    printf("I am %d process.\n", getpid()); // 说明进程ID

    if((fd = open("fifo1", O_WRONLY)) < 0) // 以写打开一个FIFO
    {
        perror("Open FIFO Failed");
        exit(1);
    }

    for(i=0; i<10; ++i)
    {
        time(&tp);  // 取系统当前时间
        n=sprintf(buf,"Process %d's time is %s",getpid(),ctime(&tp));
        printf("Send message: %s", buf); // 打印
        if(write(fd, buf, n+1) < 0)  // 写入到FIFO中
        {
            perror("Write FIFO Failed");
            close(fd);
            exit(1);
        }
        sleep(1);  // 休眠1秒
    }

    close(fd);  // 关闭FIFO文件
    return 0;
}

read_fifo.c

#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
#include<fcntl.h>
#include<sys/stat.h>

int main()
{
    int fd;
    int len;
    char buf[1024];

    if(mkfifo("fifo1", 0666) < 0 && errno!=EEXIST) // 创建FIFO管道
        perror("Create FIFO Failed");

    if((fd = open("fifo1", O_RDONLY)) < 0)  // 以读打开FIFO
    {
        perror("Open FIFO Failed");
        exit(1);
    }

    while((len = read(fd, buf, 1024)) > 0) // 读取FIFO管道
        printf("Read message: %s", buf);

    close(fd);  // 关闭FIFO文件
    return 0;
}

在两个终端里用 gcc 分别编译运行上面两个文件，可以看到输出结果如下：

[cheesezh@localhost]$ ./write_fifo
I am 5954 process.
Send message: Process 5954's time is Mon Apr 20 12:37:28 2015
Send message: Process 5954's time is Mon Apr 20 12:37:29 2015
Send message: Process 5954's time is Mon Apr 20 12:37:30 2015
Send message: Process 5954's time is Mon Apr 20 12:37:31 2015
Send message: Process 5954's time is Mon Apr 20 12:37:32 2015
Send message: Process 5954's time is Mon Apr 20 12:37:33 2015
Send message: Process 5954's time is Mon Apr 20 12:37:34 2015
Send message: Process 5954's time is Mon Apr 20 12:37:35 2015
Send message: Process 5954's time is Mon Apr 20 12:37:36 2015
Send message: Process 5954's time is Mon Apr 20 12:37:37 2015

[cheesezh@localhost]$ ./read_fifo
Read message: Process 5954's time is Mon Apr 20 12:37:28 2015
Read message: Process 5954's time is Mon Apr 20 12:37:29 2015
Read message: Process 5954's time is Mon Apr 20 12:37:30 2015
Read message: Process 5954's time is Mon Apr 20 12:37:31 2015
Read message: Process 5954's time is Mon Apr 20 12:37:32 2015
Read message: Process 5954's time is Mon Apr 20 12:37:33 2015
Read message: Process 5954's time is Mon Apr 20 12:37:34 2015
Read message: Process 5954's time is Mon Apr 20 12:37:35 2015
Read message: Process 5954's time is Mon Apr 20 12:37:36 2015
Read message: Process 5954's time is Mon Apr 20 12:37:37 2015

上述例子可以扩展成 客户进程—服务器进程 通信的实例，write_fifo的作用类似于客户端，可以打开多个客户端向一个服务器发送请求信息，read_fifo类似于服务器，它适时监控着FIFO的读端，当有数据时，读出并进行处理，但是有一个关键的问题是，每一个客户端必须预先知道服务器提供的FIFO接口，下图显示了这种安排：

caozuoxitong02

消息队列

消息队列，是消息的链接表，存放在内核中。一个消息队列由一个标识符（即队列ID）来标识。

1. 特点

• 消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级
• 消息队列独立于发送与接收进程，进程终止时，消息队列及其内容并不会被删除
• 消息队列可以实现消息的随机查询，消息不一定要以先进先出的次序读取,也可以按消息的类型读取

2. 原型

   #include <sys/msg.h>
   // 创建或打开消息队列：成功返回队列ID，失败返回-1
   int msgget(key_t key, int flag);
   // 添加消息：成功返回0，失败返回-1
   int msgsnd(int msqid, const void *ptr, size_t size, int flag);
   // 读取消息：成功返回消息数据的长度，失败返回-1
   int msgrcv(int msqid, void *ptr, size_t size, long type,int flag);
   // 控制消息队列：成功返回0，失败返回-1
   int msgctl(int msqid, int cmd, struct msqid_ds *buf);

函数msgrcv在读取消息队列时，type参数有下面几种情况：

• type == 0，返回队列中的第一个消息
• type > 0，返回队列中消息类型为 type 的第一个消息
• type < 0，返回队列中消息类型值小于或等于 type 绝对值的消息，如果有多个，则取类型值最小的消息

可以看出，type值非 0 时用于以非先进先出次序读消息。也可以把 type 看做优先级的权值。

3. 例子
   下面写了一个简单的使用消息队列进行IPC的例子，服务端程序一直在等待特定类型的消息，当收到该类型的消息以后，发送另一种特定类型的消息作为反馈，客户端读取该反馈并打印出来。

msg_server.c

#include <stdio.h>
#include <stdlib.h>
#include <sys/msg.h>

// 用于创建一个唯一的key
#define MSG_FILE "/etc/passwd"

// 消息结构
struct msg_form {
    long mtype;
    char mtext[256];
};

int main()
{
    int msqid;
    key_t key;
    struct msg_form msg;

    // 获取key值
    if((key = ftok(MSG_FILE,'z')) < 0)
    {
        perror("ftok error");
        exit(1);
    }

    // 打印key值
    printf("Message Queue - Server key is: %d.\n", key);

    // 创建消息队列
    if ((msqid = msgget(key, IPC_CREAT|0777)) == -1)
    {
        perror("msgget error");
        exit(1);
    }

    // 打印消息队列ID及进程ID
    printf("My msqid is: %d.\n", msqid);
    printf("My pid is: %d.\n", getpid());

    // 循环读取消息
    for(;;)
    {
        msgrcv(msqid, &msg, 256, 888, 0);// 返回类型为888的第一个消息
        printf("Server: receive msg.mtext is: %s.\n", msg.mtext);
        printf("Server: receive msg.mtype is: %d.\n", msg.mtype);

        msg.mtype = 999; // 客户端接收的消息类型
        sprintf(msg.mtext, "hello, I'm server %d", getpid());
        msgsnd(msqid, &msg, sizeof(msg.mtext), 0);
    }
    return 0;
}

msg_client.c

#include <stdio.h>
#include <stdlib.h>
#include <sys/msg.h>

// 用于创建一个唯一的key
#define MSG_FILE "/etc/passwd"

// 消息结构
struct msg_form {
    long mtype;
    char mtext[256];
};

int main()
{
    int msqid;
    key_t key;
    struct msg_form msg;

    // 获取key值
    if ((key = ftok(MSG_FILE, 'z')) < 0)
    {
        perror("ftok error");
        exit(1);
    }

    // 打印key值
    printf("Message Queue - Client key is: %d.\n", key);

    // 打开消息队列
    if ((msqid = msgget(key, IPC_CREAT|0777)) == -1)
    {
        perror("msgget error");
        exit(1);
    }

    // 打印消息队列ID及进程ID
    printf("My msqid is: %d.\n", msqid);
    printf("My pid is: %d.\n", getpid());

    // 添加消息，类型为888
    msg.mtype = 888;
    sprintf(msg.mtext, "hello, I'm client %d", getpid());
    msgsnd(msqid, &msg, sizeof(msg.mtext), 0);

    // 读取类型为777的消息
    msgrcv(msqid, &msg, 256, 999, 0);
    printf("Client: receive msg.mtext is: %s.\n", msg.mtext);
    printf("Client: receive msg.mtype is: %d.\n", msg.mtype);
    return 0;
}

信号量

信号量（semaphore）与已经介绍过的 IPC 结构不同，它是一个计数器。信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。

1. 特点

• 信号量用于进程间同步，若要在进程间传递数据需要结合共享内存
• 信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作
• 每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数
• 支持信号量组

2. 原型

   #include <sys/sem.h>
   // 创建或获取一个信号量组：若成功返回信号量集ID，失败返回-1
   int semget(key_t key, int num_sems, int sem_flags);
   // 对信号量组进行操作，改变信号量的值：成功返回0，失败返回-1
   int semop(int semid, struct sembuf semoparray[], size_t numops);
   // 控制信号量的相关信息
   int semctl(int semid, int sem_num, int cmd, ...);

当semget创建新的信号量集合时，必须指定集合中信号量的个数（即num_sems），通常为1； 如果是引用一个现有的集合，则将num_sems指定为 0 。

在semop函数中，sembuf结构的定义如下：

struct sembuf
{
    short sem_num; // 信号量组中对应的序号，0～sem_nums-1
    short sem_op;  // 信号量值在一次操作中的改变量
    short sem_flg; // IPC_NOWAIT, SEM_UNDO
}

其中 sem_op 是一次操作中的信号量的改变量：

• 若sem_op > 0，表示进程释放相应的资源数，将 sem_op 的值加到信号量的值上。如果有进程正在休眠等待此信号量，则换行它们
• 若sem_op < 0，请求 sem_op 的绝对值的资源
• 若sem_op == 0，进程阻塞直到信号量的相应值为0

3. 例子

   #include<stdio.h>
   #include<stdlib.h>
   #include<sys/sem.h>
   
   // 联合体，用于semctl初始化
   union semun
   {
       int              val; /*for SETVAL*/
       struct semid_ds *buf;
       unsigned short  *array;
   };
   
   // 初始化信号量
   int init_sem(int sem_id, int value)
   {
       union semun tmp;
       tmp.val = value;
       if(semctl(sem_id, 0, SETVAL, tmp) == -1)
       {
           perror("Init Semaphore Error");
           return -1;
       }
       return 0;
   }
   
   // P操作:
   //    若信号量值为1，获取资源并将信号量值-1
   //    若信号量值为0，进程挂起等待
   int sem_p(int sem_id)
   {
       struct sembuf sbuf;
       sbuf.sem_num = 0; /*序号*/
       sbuf.sem_op = -1; /*P操作*/
       sbuf.sem_flg = SEM_UNDO;
   
       if(semop(sem_id, &sbuf, 1) == -1)
       {
           perror("P operation Error");
           return -1;
       }
       return 0;
   }
   
   // V操作：
   //    释放资源并将信号量值+1
   //    如果有进程正在挂起等待，则唤醒它们
   int sem_v(int sem_id)
   {
       struct sembuf sbuf;
       sbuf.sem_num = 0; /*序号*/
       sbuf.sem_op = 1;  /*V操作*/
       sbuf.sem_flg = SEM_UNDO;
   
       if(semop(sem_id, &sbuf, 1) == -1)
       {
           perror("V operation Error");
           return -1;
       }
       return 0;
   }
   
   // 删除信号量集
   int del_sem(int sem_id)
   {
       union semun tmp;
       if(semctl(sem_id, 0, IPC_RMID, tmp) == -1)
       {
           perror("Delete Semaphore Error");
           return -1;
       }
       return 0;
   }
   
   
   int main()
   {
       int sem_id;  // 信号量集ID
       key_t key;
       pid_t pid;
   
       // 获取key值
       if((key = ftok(".", 'z')) < 0)
       {
           perror("ftok error");
           exit(1);
       }
   
       // 创建信号量集，其中只有一个信号量
       if((sem_id = semget(key, 1, IPC_CREAT|0666)) == -1)
       {
           perror("semget error");
           exit(1);
       }
   
       // 初始化：初值设为0资源被占用
       init_sem(sem_id, 0);
   
       if((pid = fork()) == -1)
           perror("Fork Error");
       else if(pid == 0) /*子进程*/
       {
           sleep(2);
           printf("Process child: pid=%d\n", getpid());
           sem_v(sem_id);  /*释放资源*/
       }
       else  /*父进程*/
       {
           sem_p(sem_id);   /*等待资源*/
           printf("Process father: pid=%d\n", getpid());
           sem_v(sem_id);   /*释放资源*/
           del_sem(sem_id); /*删除信号量集*/
       }
       return 0;
   }

上面的例子如果不加信号量，则父进程会先执行完毕。这里加了信号量让父进程等待子进程执行完以后再执行。

共享存储

共享内存（Shared Memory），指两个或多个进程共享一个给定的存储区。

1. 特点

• 共享内存是最快的一种 IPC，因为进程是直接对内存进行存取
• 因为多个进程可以同时操作，所以需要进行同步
• 信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问

2. 原型

   #include <sys/shm.h>
   // 创建或获取一个共享内存：成功返回共享内存ID，失败返回-1
   int shmget(key_t key, size_t size, int flag);
   // 连接共享内存到当前进程的地址空间：成功返回指向共享内存的指针，失败返回-1
   void *shmat(int shm_id, const void *addr, int flag);
   // 断开与共享内存的连接：成功返回0，失败返回-1
   int shmdt(void *addr);
   // 控制共享内存的相关信息：成功返回0，失败返回-1
   int shmctl(int shm_id, int cmd, struct shmid_ds *buf);

当用shmget函数创建一段共享内存时，必须指定其 size；而如果引用一个已存在的共享内存，则将 size 指定为0 。

当一段共享内存被创建以后，它并不能被任何进程访问。必须使用shmat函数连接该共享内存到当前进程的地址空间，连接成功后把共享内存区对象映射到调用进程的地址空间，随后可像本地空间一样访问。

shmdt函数是用来断开shmat建立的连接的。注意，这并不是从系统中删除该共享内存，只是当前进程不能再访问该共享内存而已。

shmctl函数可以对共享内存执行多种操作，根据参数 cmd 执行相应的操作。常用的是IPC_RMID（从系统中删除该共享内存）。

3. 例子
   下面这个例子，使用了【共享内存+信号量+消息队列】的组合来实现服务器进程与客户进程间的通信。

• 共享内存用来传递数据
• 信号量用来同步
• 消息队列用来在客户端修改了共享内存后 通知服务器读取

server.c

#include<stdio.h>
#include<stdlib.h>
#include<sys/shm.h>  // shared memory
#include<sys/sem.h>  // semaphore
#include<sys/msg.h>  // message queue
#include<string.h>   // memcpy

// 消息队列结构
struct msg_form {
    long mtype;
    char mtext;
};

// 联合体，用于semctl初始化
union semun
{
    int              val; /*for SETVAL*/
    struct semid_ds *buf;
    unsigned short  *array;
};

// 初始化信号量
int init_sem(int sem_id, int value)
{
    union semun tmp;
    tmp.val = value;
    if(semctl(sem_id, 0, SETVAL, tmp) == -1)
    {
        perror("Init Semaphore Error");
        return -1;
    }
    return 0;
}

// P操作:
//  若信号量值为1，获取资源并将信号量值-1
//  若信号量值为0，进程挂起等待
int sem_p(int sem_id)
{
    struct sembuf sbuf;
    sbuf.sem_num = 0; /*序号*/
    sbuf.sem_op = -1; /*P操作*/
    sbuf.sem_flg = SEM_UNDO;

    if(semop(sem_id, &sbuf, 1) == -1)
    {
        perror("P operation Error");
        return -1;
    }
    return 0;
}

// V操作：
//  释放资源并将信号量值+1
//  如果有进程正在挂起等待，则唤醒它们
int sem_v(int sem_id)
{
    struct sembuf sbuf;
    sbuf.sem_num = 0; /*序号*/
    sbuf.sem_op = 1;  /*V操作*/
    sbuf.sem_flg = SEM_UNDO;

    if(semop(sem_id, &sbuf, 1) == -1)
    {
        perror("V operation Error");
        return -1;
    }
    return 0;
}

// 删除信号量集
int del_sem(int sem_id)
{
    union semun tmp;
    if(semctl(sem_id, 0, IPC_RMID, tmp) == -1)
    {
        perror("Delete Semaphore Error");
        return -1;
    }
    return 0;
}

// 创建一个信号量集
int creat_sem(key_t key)
{
    int sem_id;
    if((sem_id = semget(key, 1, IPC_CREAT|0666)) == -1)
    {
        perror("semget error");
        exit(-1);
    }
    init_sem(sem_id, 1);  /*初值设为1资源未占用*/
    return sem_id;
}


int main()
{
    key_t key;
    int shmid, semid, msqid;
    char *shm;
    char data[] = "this is server";
    struct shmid_ds buf1;  /*用于删除共享内存*/
    struct msqid_ds buf2;  /*用于删除消息队列*/
    struct msg_form msg;  /*消息队列用于通知对方更新了共享内存*/

    // 获取key值
    if((key = ftok(".", 'z')) < 0)
    {
        perror("ftok error");
        exit(1);
    }

    // 创建共享内存
    if((shmid = shmget(key, 1024, IPC_CREAT|0666)) == -1)
    {
        perror("Create Shared Memory Error");
        exit(1);
    }

    // 连接共享内存
    shm = (char*)shmat(shmid, 0, 0);
    if((int)shm == -1)
    {
        perror("Attach Shared Memory Error");
        exit(1);
    }


    // 创建消息队列
    if ((msqid = msgget(key, IPC_CREAT|0777)) == -1)
    {
        perror("msgget error");
        exit(1);
    }

    // 创建信号量
    semid = creat_sem(key);

    // 读数据
    while(1)
    {
        msgrcv(msqid, &msg, 1, 888, 0); /*读取类型为888的消息*/
        if(msg.mtext == 'q')  /*quit - 跳出循环*/
            break;
        if(msg.mtext == 'r')  /*read - 读共享内存*/
        {
            sem_p(semid);
            printf("%s\n",shm);
            sem_v(semid);
        }
    }

    // 断开连接
    shmdt(shm);

    /*删除共享内存、消息队列、信号量*/
    shmctl(shmid, IPC_RMID, &buf1);
    msgctl(msqid, IPC_RMID, &buf2);
    del_sem(semid);
    return 0;
}

client.c

#include<stdio.h>
#include<stdlib.h>
#include<sys/shm.h>  // shared memory
#include<sys/sem.h>  // semaphore
#include<sys/msg.h>  // message queue
#include<string.h>   // memcpy

// 消息队列结构
struct msg_form {
    long mtype;
    char mtext;
};

// 联合体，用于semctl初始化
union semun
{
    int              val; /*for SETVAL*/
    struct semid_ds *buf;
    unsigned short  *array;
};

// P操作:
//  若信号量值为1，获取资源并将信号量值-1
//  若信号量值为0，进程挂起等待
int sem_p(int sem_id)
{
    struct sembuf sbuf;
    sbuf.sem_num = 0; /*序号*/
    sbuf.sem_op = -1; /*P操作*/
    sbuf.sem_flg = SEM_UNDO;

    if(semop(sem_id, &sbuf, 1) == -1)
    {
        perror("P operation Error");
        return -1;
    }
    return 0;
}

// V操作：
//  释放资源并将信号量值+1
//  如果有进程正在挂起等待，则唤醒它们
int sem_v(int sem_id)
{
    struct sembuf sbuf;
    sbuf.sem_num = 0; /*序号*/
    sbuf.sem_op = 1;  /*V操作*/
    sbuf.sem_flg = SEM_UNDO;

    if(semop(sem_id, &sbuf, 1) == -1)
    {
        perror("V operation Error");
        return -1;
    }
    return 0;
}


int main()
{
    key_t key;
    int shmid, semid, msqid;
    char *shm;
    struct msg_form msg;
    int flag = 1; /*while循环条件*/

    // 获取key值
    if((key = ftok(".", 'z')) < 0)
    {
        perror("ftok error");
        exit(1);
    }

    // 获取共享内存
    if((shmid = shmget(key, 1024, 0)) == -1)
    {
        perror("shmget error");
        exit(1);
    }

    // 连接共享内存
    shm = (char*)shmat(shmid, 0, 0);
    if((int)shm == -1)
    {
        perror("Attach Shared Memory Error");
        exit(1);
    }

    // 创建消息队列
    if ((msqid = msgget(key, 0)) == -1)
    {
        perror("msgget error");
        exit(1);
    }

    // 获取信号量
    if((semid = semget(key, 0, 0)) == -1)
    {
        perror("semget error");
        exit(1);
    }

    // 写数据
    printf("***************************************\n");
    printf("*                 IPC                 *\n");
    printf("*    Input r to send data to server.  *\n");
    printf("*    Input q to quit.                 *\n");
    printf("***************************************\n");

    while(flag)
    {
        char c;
        printf("Please input command: ");
        scanf("%c", &c);
        switch(c)
        {
            case 'r':
                printf("Data to send: ");
                sem_p(semid);  /*访问资源*/
                scanf("%s", shm);
                sem_v(semid);  /*释放资源*/
                /*清空标准输入缓冲区*/
                while((c=getchar())!='\n' && c!=EOF);
                msg.mtype = 888;
                msg.mtext = 'r';  /*发送消息通知服务器读数据*/
                msgsnd(msqid, &msg, sizeof(msg.mtext), 0);
                break;
            case 'q':
                msg.mtype = 888;
                msg.mtext = 'q';
                msgsnd(msqid, &msg, sizeof(msg.mtext), 0);
                flag = 0;
                break;
            default:
                printf("Wrong input!\n");
                /*清空标准输入缓冲区*/
                while((c=getchar())!='\n' && c!=EOF);
        }
    }

    // 断开连接
    shmdt(shm);

    return 0;
}

小结

1. 管道：速度慢，容量有限，只有父子进程能通讯
2. FIFO：任何进程间都能通讯，但速度慢
3. 消息队列：容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题
4. 信号量：不能传递复杂消息，只能用来同步
5. 共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题

死锁

必要条件

• 互斥：每个资源要么已经分配给了一个进程，要么就是可用的
• 占有和等待：已经得到了某个资源的进程可以再请求新的资源
• 不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放
• 环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源

处理方法

鸵鸟策略

把头埋在沙子里，假装根本没发生问题，因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能，当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略，大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

死锁检测与死锁恢复

不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。

1. 死锁检测，类似银行家算法
2. 死锁恢复

死锁预防

在程序运行之前预防发生死锁，即破坏死锁的四个比要条件。

死锁避免

在程序运行时避免发生死锁。

检查状态是否是安全的：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。

安全状态的检测：银行家算法。

内存管理

虚拟内存

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。

从上面的描述中可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。

caozuoxitong04

分页系统地址映射

内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。

一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。

下图的页表存放着 16 个页，这 16 个页需要用 4 个比特位来进行索引定位。例如对于虚拟地址（0010 000000000100），前 4 位是存储页面号 2，读取表项内容为（110 1），页表项最后一位表示是否存在于内存中，1 表示存在。后 12 位存储偏移量。这个页对应的页框的地址为 （110 000000000100）。

caozuoxitong05

页面置换算法

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。

页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。

最佳

所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。

最近最久未使用（LRU）

虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。

为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。

因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。

例子：

4，7，0，7，1，0，1，2，1，2，6

caozuoxitong06

先进先出(FIFO)

选择换出的页面是最先进入的页面，导致缺页率升高。

引用：

• https://github.com/CyC2018/CS-Notes/blob/master/notes/%E8%AE%A1%E7%AE%97%E6%9C%BA%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%20-%20%E7%9B%AE%E5%BD%95.md
• https://www.cnblogs.com/zgq0/p/8780893.html