编制生产者—消费者算法，模拟 1 个生产者、3 个消费者进行同步的操作

好的，我可以回答这个问题。生产者-消费者问题是一个经典的同步问题，可以使用信号量来实现。具体实现方式可以使用一个缓冲区来存储生产者生产的数据，当缓冲区满时，生产者需要等待，直到有消费者消费数据，缓冲区有空位时，生产者才能继续生产。同样，当缓冲区为空时，消费者需要等待，直到有生产者生产数据，缓冲区有数据时，消费者才能继续消费。在这个问题中，可以使用一个互斥锁来保证同时只有一个线程访问缓冲区，避免竞争条件的发生。

相关问题

（1） 设计进程同步算法，使用P/V（wait/signal）操作模拟解决进程中经典同步问题。假设有一个生产者和一个消费者，缓冲区可以存放产品，生产者不断生产产品并存入缓冲区，消费者不断从缓冲区中取出产品并消费，设计代码并运行实现结果。 （2） 编制时间片轮转调度算法，可自定义时间片的大小。 （3） 编制静态优先级调度算法，优先级高低可自定义

（1）生产者-消费者问题的P/V解决方案已经在上一个问题中提到了，这里再提供一份代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>

#define N 10 // 缓冲区大小
#define P 20 // 生产者需要生产的产品数量
#define C 20 // 消费者需要消费的产品数量

sem_t mutex; // 互斥信号量
sem_t empty; // 空闲信号量
sem_t full; // 满信号量

int buffer[N]; // 缓冲区
int in = 0; // 生产者写入位置
int out = 0; // 消费者读取位置

void *producer(void *arg) {
    for (int i = 0; i < P; i++) {
        int item = rand() % 100; // 生产一个产品
        sem_wait(&empty); // 等待空闲缓冲区
        sem_wait(&mutex); // 申请互斥访问缓冲区
        buffer[in] = item; // 将产品存入缓冲区
        in = (in + 1) % N; // 更新写入位置
        printf("producer produced item %d\n", item);
        sem_post(&mutex); // 释放互斥访问缓冲区
        sem_post(&full); // 通知有新的产品可供消费
    }
    return NULL;
}

void *consumer(void *arg) {
    for (int i = 0; i < C; i++) {
        sem_wait(&full); // 等待满缓冲区
        sem_wait(&mutex); // 申请互斥访问缓冲区
        int item = buffer[out]; // 从缓冲区取出产品
        out = (out + 1) % N; // 更新读取位置
        printf("consumer consumed item %d\n", item);
        sem_post(&mutex); // 释放互斥访问缓冲区
        sem_post(&empty); // 通知已释放一个空闲缓冲区
    }
    return NULL;
}

int main() {
    // 初始化信号量
    sem_init(&mutex, 0, 1);
    sem_init(&empty, 0, N);
    sem_init(&full, 0, 0);

    // 创建生产者和消费者线程
    pthread_t producer_thread, consumer_thread;
    pthread_create(&producer_thread, NULL, producer, NULL);
    pthread_create(&consumer_thread, NULL, consumer, NULL);

    // 等待线程结束
    pthread_join(producer_thread, NULL);
    pthread_join(consumer_thread, NULL);

    // 销毁信号量
    sem_destroy(&mutex);
    sem_destroy(&empty);
    sem_destroy(&full);

    return 0;
}

（2）时间片轮转调度算法的代码实现如下：

#include <stdio.h>
#include <stdlib.h>

#define MAX_PROCESS_NUM 10 // 最大进程数量
#define TIME_SLICE 2 // 时间片大小

int process_num = 0; // 进程数量
int current_time = 0; // 当前时间
int current_process = 0; // 当前进程
int remaining_time[MAX_PROCESS_NUM]; // 进程剩余执行时间
int arrival_time[MAX_PROCESS_NUM]; // 进程到达时间
int completion_time[MAX_PROCESS_NUM]; // 进程完成时间
int turnaround_time[MAX_PROCESS_NUM]; // 进程周转时间
int waiting_time[MAX_PROCESS_NUM]; // 进程等待时间

void input_process() {
    printf("请输入进程数量：");
    scanf("%d", &process_num);
    printf("请输入进程信息（到达时间 执行时间）：\n");
    for (int i = 0; i < process_num; i++) {
        scanf("%d %d", &arrival_time[i], &remaining_time[i]);
    }
}

void output_process() {
    printf("进程信息如下：\n");
    printf("进程编号 到达时间 执行时间 完成时间 周转时间 等待时间\n");
    for (int i = 0; i < process_num; i++) {
        printf("%d %11d %8d %10d %8d %8d\n", i, arrival_time[i], remaining_time[i], completion_time[i], turnaround_time[i], waiting_time[i]);
    }
}

void schedule_process() {
    printf("时间片大小为%d，进程轮转调度如下：\n", TIME_SLICE);
    while (1) {
        int flag = 1;
        for (int i = 0; i < process_num; i++) {
            if (remaining_time[i] > 0) {
                flag = 0;
                if (remaining_time[i] > TIME_SLICE) {
                    current_time += TIME_SLICE;
                    remaining_time[i] -= TIME_SLICE;
                } else {
                    current_time += remaining_time[i];
                    remaining_time[i] = 0;
                    completion_time[i] = current_time;
                    turnaround_time[i] = completion_time[i] - arrival_time[i];
                    waiting_time[i] = turnaround_time[i] - remaining_time[i];
                }
            }
        }
        if (flag) {
            break;
        }
    }
}

int main() {
    input_process();
    schedule_process();
    output_process();
    return 0;
}

（3）静态优先级调度算法的代码实现如下：

#include <stdio.h>
#include <stdlib.h>

#define MAX_PROCESS_NUM 10 // 最大进程数量

int process_num = 0; // 进程数量
int current_time = 0; // 当前时间
int current_process = 0; // 当前进程
int priority[MAX_PROCESS_NUM]; // 进程优先级
int remaining_time[MAX_PROCESS_NUM]; // 进程剩余执行时间
int arrival_time[MAX_PROCESS_NUM]; // 进程到达时间
int completion_time[MAX_PROCESS_NUM]; // 进程完成时间
int turnaround_time[MAX_PROCESS_NUM]; // 进程周转时间
int waiting_time[MAX_PROCESS_NUM]; // 进程等待时间

void input_process() {
    printf("请输入进程数量：");
    scanf("%d", &process_num);
    printf("请输入进程信息（到达时间 执行时间 优先级）：\n");
    for (int i = 0; i < process_num; i++) {
        scanf("%d %d %d", &arrival_time[i], &remaining_time[i], &priority[i]);
    }
}

void output_process() {
    printf("进程信息如下：\n");
    printf("进程编号 到达时间 执行时间 优先级 完成时间 周转时间 等待时间\n");
    for (int i = 0; i < process_num; i++) {
        printf("%d %11d %8d %6d %10d %8d %8d\n", i, arrival_time[i], remaining_time[i], priority[i], completion_time[i], turnaround_time[i], waiting_time[i]);
    }
}

void schedule_process() {
    printf("进程静态优先级调度如下：\n");
    while (1) {
        int next_process = -1;
        int max_priority = -1;
        for (int i = 0; i < process_num; i++) {
            if (arrival_time[i] <= current_time && remaining_time[i] > 0 && priority[i] > max_priority) {
                next_process = i;
                max_priority = priority[i];
            }
        }
        if (next_process == -1) {
            break;
        }
        current_process = next_process;
        current_time += remaining_time[current_process];
        remaining_time[current_process] = 0;
        completion_time[current_process] = current_time;
        turnaround_time[current_process] = completion_time[current_process] - arrival_time[current_process];
        waiting_time[current_process] = turnaround_time[current_process] - remaining_time[current_process];
    }
}

int main() {
    input_process();
    schedule_process();
    output_process();
    return 0;
}

写一个进程同步与调度的实验，实验内容为（1）设计进程同步算法，使用P/V（wait/signal）操作模拟解决进程中经典同步问题。假设有一个生产者和一个消费者，缓冲区可以存放产品，生产者不断生产产品并存入缓冲区，消费者不断从缓冲区中取出产品并消费，设计代码并运行实现结果。 （2）编制时间片轮转调度算法，可自定义时间片的大小。 （3）编制静态优先级调度算法，优先级高低可自定义。

实验一：进程同步

1. 设计进程同步算法

生产者和消费者问题是经典的同步问题，可以使用P/V（wait/signal）操作模拟解决。P操作相当于wait操作，如果资源不可用，则等待；V操作相当于signal操作，如果资源可用，则发送信号。

2. 算法实现

下面是一个使用P/V操作解决生产者和消费者问题的示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>

#define MAX_BUFFER_SIZE 10

int buffer[MAX_BUFFER_SIZE];
int count = 0;
sem_t empty; // 空闲缓冲区信号量
sem_t full; // 已用缓冲区信号量
pthread_mutex_t mutex; // 互斥锁

void *producer(void *arg)
{
    int i, item;
    for (i = 0; i < 100; i++) {
        item = rand() % 1000;
        sem_wait(&empty); // 等待空闲缓冲区
        pthread_mutex_lock(&mutex); // 加锁
        buffer[count++] = item;
        printf("Producer %d produce item %d, buffer size is %d\n", *((int *)arg), item, count);
        pthread_mutex_unlock(&mutex); // 解锁
        sem_post(&full); // 增加已用缓冲区
    }
    pthread_exit(NULL);
}

void *consumer(void *arg)
{
    int i, item;
    for (i = 0; i < 100; i++) {
        sem_wait(&full); // 等待已用缓冲区
        pthread_mutex_lock(&mutex); // 加锁
        item = buffer[--count];
        printf("Consumer %d consume item %d, buffer size is %d\n", *((int *)arg), item, count);
        pthread_mutex_unlock(&mutex); // 解锁
        sem_post(&empty); // 增加空闲缓冲区
    }
    pthread_exit(NULL);
}

int main()
{
    int i;
    pthread_t producer_thread, consumer_thread;
    int producer_id = 1, consumer_id = 1;
    sem_init(&empty, 0, MAX_BUFFER_SIZE);
    sem_init(&full, 0, 0);
    pthread_mutex_init(&mutex, NULL);
    for (i = 0; i < 2; i++) {
        pthread_create(&producer_thread, NULL, producer, &producer_id);
        pthread_create(&consumer_thread, NULL, consumer, &consumer_id);
        producer_id++;
        consumer_id++;
    }
    pthread_join(producer_thread, NULL);
    pthread_join(consumer_thread, NULL);
    sem_destroy(&empty);
    sem_destroy(&full);
    pthread_mutex_destroy(&mutex);
    return 0;
}

3. 实验结果

运行上述代码，可以看到生产者和消费者的交替输出，表示生产和消费过程已经成功同步。

实验二：时间片轮转调度算法

1. 算法实现

时间片轮转调度算法是一种简单的调度算法，它将所有进程按照到达时间排序，并按照轮转的方式分配时间片，每个进程最多执行一个时间片。

下面是一个使用时间片轮转调度算法的示例代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_PROCESS_NUM 5 // 进程数量
#define TIME_QUANTUM 2 // 时间片大小

typedef struct {
    int pid; // 进程ID
    int burst_time; // 执行时间
    int arrival_time; // 到达时间
    int remaining_time; // 剩余执行时间
} process_t;

process_t processes[MAX_PROCESS_NUM] = {
    {1, 10, 0, 0},
    {2, 5, 1, 0},
    {3, 2, 3, 0},
    {4, 6, 4, 0},
    {5, 4, 5, 0},
};

void schedule()
{
    int i, j;
    int finished[MAX_PROCESS_NUM] = {0}; // 标记进程是否完成
    int time = 0; // 当前时间
    int remaining_num = MAX_PROCESS_NUM; // 剩余进程数量
    while (remaining_num > 0) {
        for (i = 0; i < MAX_PROCESS_NUM; i++) {
            if (!finished[i] && processes[i].arrival_time <= time) { // 进程未完成且到达时间早于等于当前时间
                printf("Time %d: Process %d running, remaining time %d\n", time, processes[i].pid, processes[i].remaining_time);
                for (j = 0; j < TIME_QUANTUM && processes[i].remaining_time > 0; j++) { // 执行一个时间片
                    processes[i].remaining_time--;
                    time++;
                }
                if (processes[i].remaining_time == 0) { // 进程已完成
                    finished[i] = 1;
                    remaining_num--;
                    printf("Time %d: Process %d finished\n", time, processes[i].pid);
                } else { // 进程未完成，加入队列尾部
                    printf("Time %d: Process %d not finished, added to queue end\n", time, processes[i].pid);
                }
            }
        }
    }
}

int main()
{
    int i;
    for (i = 0; i < MAX_PROCESS_NUM; i++) { // 初始化剩余执行时间
        processes[i].remaining_time = processes[i].burst_time;
    }
    schedule();
    return 0;
}

2. 实验结果

运行上述代码，可以看到各个进程的执行情况，以及最终完成时间。

实验三：静态优先级调度算法

1. 算法实现

静态优先级调度算法是一种根据进程优先级来进行调度的算法。每个进程被赋予一个优先级，优先级高的进程先被执行。如果有多个进程的优先级相同，则按照到达时间排序。

下面是一个使用静态优先级调度算法的示例代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_PROCESS_NUM 5 // 进程数量

typedef struct {
    int pid; // 进程ID
    int burst_time; // 执行时间
    int arrival_time; // 到达时间
    int priority; // 优先级
} process_t;

process_t processes[MAX_PROCESS_NUM] = {
    {1, 10, 0, 2},
    {2, 5, 1, 1},
    {3, 2, 3, 3},
    {4, 6, 4, 4},
    {5, 4, 5, 5},
};

void schedule()
{
    int i, j;
    int finished[MAX_PROCESS_NUM] = {0}; // 标记进程是否完成
    int time = 0; // 当前时间
    int remaining_num = MAX_PROCESS_NUM; // 剩余进程数量
    while (remaining_num > 0) {
        int highest_priority = -1;
        int highest_priority_index = -1;
        for (i = 0; i < MAX_PROCESS_NUM; i++) { // 找到优先级最高的进程
            if (!finished[i] && processes[i].arrival_time <= time) { // 进程未完成且到达时间早于等于当前时间
                if (processes[i].priority > highest_priority) { // 找到优先级最高的进程
                    highest_priority = processes[i].priority;
                    highest_priority_index = i;
                }
            }
        }
        if (highest_priority_index == -1) { // 没有进程可执行，等待一段时间
            printf("Time %d: No process to run, waiting...\n", time);
            time++;
        } else { // 执行优先级最高的进程
            printf("Time %d: Process %d running, remaining time %d\n", time, processes[highest_priority_index].pid, processes[highest_priority_index].burst_time);
            processes[highest_priority_index].burst_time--;
            time++;
            if (processes[highest_priority_index].burst_time == 0) { // 进程已完成
                finished[highest_priority_index] = 1;
                remaining_num--;
                printf("Time %d: Process %d finished\n", time, processes[highest_priority_index].pid);
            }
        }
    }
}

int main()
{
    int i;
    schedule();
    return 0;
}

2. 实验结果

运行上述代码，可以看到各个进程的执行情况，以及最终完成时间。