05. 练习题

进程与线程的区别：

应用场景：

进程适用于：

• 需要高安全性和隔离性的应用
• 需要独立内存空间的程序
• 系统服务程序
• 需要故障隔离的场景

线程适用于：

• 需要高并发性能的应用
• 共享大量数据的程序
• 需要快速响应的用户界面
• 计算密集型任务的分割

进程状态转换图：

就绪状态 ←→ 运行状态 ←→ 阻塞状态
    ↑           ↓           ↓
    └───────────┴───────────┘

状态转换条件：

1. 就绪 → 运行：

   • CPU 调度器选择该进程执行
   • 进程获得 CPU 时间片
   • 更高优先级进程让出 CPU

2. 运行 → 就绪：

   • 时间片用完
   • 被更高优先级进程抢占
   • 进程主动让出 CPU

3. 运行 → 阻塞：

   • 进程请求 I/O 操作
   • 等待某个事件或资源
   • 进程调用阻塞系统调用

4. 阻塞 → 就绪：

   • 等待的事件发生
   • 请求的资源可用
   • I/O 操作完成

实际例子：

• 用户程序等待键盘输入：运行 → 阻塞
• 磁盘 I/O 完成：阻塞 → 就绪
• 时间片用完：运行 → 就绪
• 调度器选择进程：就绪 → 运行

算法特点比较：

详细分析：

1. 先来先服务（FCFS）：

• 优点：实现简单，公平性好
• 缺点：平均等待时间长，对短进程不利，可能产生饥饿
• 适用场景：批处理系统，进程长度相近的系统

2. 短作业优先（SJF）：

• 优点：平均周转时间最短，系统吞吐量高
• 缺点：对长进程不公平，需要预知进程长度
• 适用场景：批处理系统，进程长度差异较大的系统

3. 时间片轮转（RR）：

• 优点：响应时间好，公平性好，适合交互式系统
• 缺点：上下文切换开销大，时间片选择影响性能
• 适用场景：分时系统，交互式系统

时间片选择的影响：

• 时间片太小：上下文切换频繁，系统开销大
• 时间片太大：退化为 FCFS，响应时间差
• 最佳时间片：10-100ms

信号量概念： 信号量是一个整型变量，除了初始化外，只能通过两个原子操作访问：

• P 操作（wait）：申请资源，信号量减 1
• V 操作（signal）：释放资源，信号量加 1

P/V 操作含义：

• P 操作：如果信号量大于 0，则减 1 并继续；如果为 0，则进程阻塞等待
• V 操作：信号量加 1，如果有进程在等待，则唤醒一个进程

生产者-消费者问题解决方案：

#define N 100
semaphore mutex = 1;    // 互斥信号量
semaphore empty = N;    // 空缓冲区数量
semaphore full = 0;     // 满缓冲区数量

// 生产者
void producer() {
    while (true) {
        item = produce_item();
        P(&empty);      // 等待空缓冲区
        P(&mutex);      // 进入临界区
        insert_item(item);
        V(&mutex);      // 退出临界区
        V(&full);       // 增加满缓冲区数量
    }
}

// 消费者
void consumer() {
    while (true) {
        P(&full);       // 等待满缓冲区
        P(&mutex);      // 进入临界区
        item = remove_item();
        V(&mutex);      // 退出临界区
        V(&empty);      // 增加空缓冲区数量
        consume_item(item);
    }
}

信号量类型：

1. 二元信号量：值为 0 或 1，用于互斥
2. 计数信号量：值可以为任意非负整数，用于同步

死锁的四个必要条件：

1. 互斥条件：资源不能被多个进程同时使用
2. 请求和保持条件：进程在等待其他资源时，不释放已占有的资源
3. 不可剥夺条件：资源不能被强制剥夺
4. 循环等待条件：存在进程等待链，形成循环

死锁避免方法：

1. 破坏互斥条件：

• 使用可共享的资源
• 使用虚拟化技术
• 使用资源池

2. 破坏请求和保持条件：

• 一次性分配所有资源
• 申请新资源前释放所有已占有资源

3. 破坏不可剥夺条件：

• 允许资源抢占
• 设置资源优先级
• 使用超时机制

4. 破坏循环等待条件：

• 资源有序分配
• 资源编号策略
• 资源层次结构

实际例子：

哲学家进餐问题的死锁情况：

所有哲学家同时拿起左边的筷子
然后等待右边的筷子
形成循环等待

解决方案：

// 使用资源有序分配
void philosopher(int i) {
    int left = i;
    int right = (i + 1) % 5;

    // 总是先申请编号小的筷子
    if (left < right) {
        acquire_chopstick(left);
        acquire_chopstick(right);
    } else {
        acquire_chopstick(right);
        acquire_chopstick(left);
    }

    eat();

    release_chopstick(left);
    release_chopstick(right);
}

银行家算法：

• 在分配资源前检查是否会导致不安全状态
• 只有在安全状态下才分配资源
• 需要预知进程的最大资源需求

读者-写者问题：

• 多个读者可以同时读取共享数据
• 写者必须独占访问
• 读者和写者不能同时访问

读者优先解决方案：

semaphore mutex = 1;    // 保护readcount
semaphore wrt = 1;      // 写者互斥
int readcount = 0;      // 读者数量

// 读者
void reader() {
    P(&mutex);          // 进入临界区
    readcount++;
    if (readcount == 1)
        P(&wrt);        // 第一个读者，阻止写者
    V(&mutex);          // 退出临界区

    read_data();        // 读取数据

    P(&mutex);          // 进入临界区
    readcount--;
    if (readcount == 0)
        V(&wrt);        // 最后一个读者，允许写者
    V(&mutex);          // 退出临界区
}

// 写者
void writer() {
    P(&wrt);            // 等待写者互斥锁
    write_data();       // 写入数据
    V(&wrt);            // 释放写者互斥锁
}

写者优先解决方案：

semaphore mutex = 1;    // 保护readcount
semaphore wrt = 1;      // 写者互斥
semaphore read = 1;     // 读者队列
int readcount = 0;      // 读者数量
int writecount = 0;     // 写者数量

// 读者
void reader() {
    P(&read);           // 等待读者队列
    P(&mutex);
    readcount++;
    if (readcount == 1)
        P(&wrt);        // 第一个读者，阻止写者
    V(&mutex);
    V(&read);           // 释放读者队列

    read_data();

    P(&mutex);
    readcount--;
    if (readcount == 0)
        V(&wrt);        // 最后一个读者，允许写者
    V(&mutex);
}

// 写者
void writer() {
    P(&mutex);
    writecount++;
    if (writecount == 1)
        P(&read);       // 第一个写者，阻止读者
    V(&mutex);

    P(&wrt);
    write_data();
    V(&wrt);

    P(&mutex);
    writecount--;
    if (writecount == 0)
        V(&read);       // 最后一个写者，允许读者
    V(&mutex);
}

两种方案的区别：

• 读者优先：读者可以连续进入，写者可能饥饿
• 写者优先：写者优先，读者可能饥饿

进程结构定义：

typedef struct {
    int pid;            // 进程ID
    char name[32];      // 进程名
    int priority;       // 优先级
    int arrival_time;   // 到达时间
    int burst_time;     // 执行时间
    int remaining_time; // 剩余时间
    int state;          // 进程状态
    int start_time;     // 开始时间
    int completion_time; // 完成时间
    int turnaround_time; // 周转时间
    int waiting_time;   // 等待时间
} Process;

// 进程状态
#define READY 0
#define RUNNING 1
#define BLOCKED 2
#define COMPLETED 3

优先级调度算法实现：

#define MAX_PROCESSES 100

Process processes[MAX_PROCESSES];
int process_count = 0;
int current_time = 0;

// 添加进程
void add_process(int pid, char* name, int priority, int arrival_time, int burst_time) {
    if (process_count < MAX_PROCESSES) {
        processes[process_count].pid = pid;
        strcpy(processes[process_count].name, name);
        processes[process_count].priority = priority;
        processes[process_count].arrival_time = arrival_time;
        processes[process_count].burst_time = burst_time;
        processes[process_count].remaining_time = burst_time;
        processes[process_count].state = READY;
        processes[process_count].start_time = -1;
        processes[process_count].completion_time = -1;
        processes[process_count].turnaround_time = -1;
        processes[process_count].waiting_time = -1;
        process_count++;
    }
}

// 找到最高优先级的就绪进程
int find_highest_priority_ready_process() {
    int highest_priority = -1;
    int selected_process = -1;

    for (int i = 0; i < process_count; i++) {
        if (processes[i].state == READY &&
            processes[i].arrival_time <= current_time &&
            processes[i].priority > highest_priority) {
            highest_priority = processes[i].priority;
            selected_process = i;
        }
    }

    return selected_process;
}

// 优先级调度主函数
void priority_scheduling() {
    int completed = 0;
    int current_process = -1;

    while (completed < process_count) {
        // 检查是否有新进程到达
        for (int i = 0; i < process_count; i++) {
            if (processes[i].arrival_time == current_time) {
                processes[i].state = READY;
            }
        }

        // 如果当前没有进程运行，选择新进程
        if (current_process == -1 || processes[current_process].state != RUNNING) {
            current_process = find_highest_priority_ready_process();
            if (current_process != -1) {
                processes[current_process].state = RUNNING;
                if (processes[current_process].start_time == -1) {
                    processes[current_process].start_time = current_time;
                }
            }
        }

        // 执行当前进程
        if (current_process != -1) {
            processes[current_process].remaining_time--;

            // 检查进程是否完成
            if (processes[current_process].remaining_time == 0) {
                processes[current_process].state = COMPLETED;
                processes[current_process].completion_time = current_time;
                processes[current_process].turnaround_time =
                    processes[current_process].completion_time -
                    processes[current_process].arrival_time;
                processes[current_process].waiting_time =
                    processes[current_process].turnaround_time -
                    processes[current_process].burst_time;
                completed++;
                current_process = -1;
            }
        }

        current_time++;
    }
}

// 打印调度结果
void print_scheduling_results() {
    printf("进程调度结果：\n");
    printf("PID\t名称\t优先级\t到达时间\t执行时间\t开始时间\t完成时间\t周转时间\t等待时间\n");

    for (int i = 0; i < process_count; i++) {
        printf("%d\t%s\t%d\t%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%d\n",
               processes[i].pid,
               processes[i].name,
               processes[i].priority,
               processes[i].arrival_time,
               processes[i].burst_time,
               processes[i].start_time,
               processes[i].completion_time,
               processes[i].turnaround_time,
               processes[i].waiting_time);
    }
}

使用示例：

int main() {
    // 添加测试进程
    add_process(1, "P1", 3, 0, 6);
    add_process(2, "P2", 1, 2, 4);
    add_process(3, "P3", 4, 4, 2);
    add_process(4, "P4", 2, 6, 8);

    // 执行调度
    priority_scheduling();

    // 打印结果
    print_scheduling_results();

    return 0;
}

资源分配图结构：

#define MAX_PROCESSES 10
#define MAX_RESOURCES 10

typedef struct {
    int process_id;
    int resource_id;
    int allocation;  // 分配数量
    int request;     // 请求数量
} Edge;

typedef struct {
    int process_count;
    int resource_count;
    Edge edges[MAX_PROCESSES * MAX_RESOURCES];
    int edge_count;
    int available[MAX_RESOURCES];
    int total[MAX_RESOURCES];
} ResourceAllocationGraph;

死锁检测算法实现：

// 初始化资源分配图
void init_graph(ResourceAllocationGraph* graph, int processes, int resources) {
    graph->process_count = processes;
    graph->resource_count = resources;
    graph->edge_count = 0;

    for (int i = 0; i < resources; i++) {
        graph->available[i] = 0;
        graph->total[i] = 0;
    }
}

// 添加资源分配边
void add_allocation_edge(ResourceAllocationGraph* graph, int process_id, int resource_id, int amount) {
    graph->edges[graph->edge_count].process_id = process_id;
    graph->edges[graph->edge_count].resource_id = resource_id;
    graph->edges[graph->edge_count].allocation = amount;
    graph->edges[graph->edge_count].request = 0;
    graph->edge_count++;
}

// 添加资源请求边
void add_request_edge(ResourceAllocationGraph* graph, int process_id, int resource_id, int amount) {
    graph->edges[graph->edge_count].process_id = process_id;
    graph->edges[graph->edge_count].resource_id = resource_id;
    graph->edges[graph->edge_count].allocation = 0;
    graph->edges[graph->edge_count].request = amount;
    graph->edge_count++;
}

// 检查进程是否可以完成
bool can_process_complete(ResourceAllocationGraph* graph, int process_id) {
    for (int i = 0; i < graph->edge_count; i++) {
        if (graph->edges[i].process_id == process_id &&
            graph->edges[i].request > 0) {
            // 检查是否有足够的可用资源
            if (graph->edges[i].request > graph->available[graph->edges[i].resource_id]) {
                return false;
            }
        }
    }
    return true;
}

// 释放进程占有的资源
void release_process_resources(ResourceAllocationGraph* graph, int process_id) {
    for (int i = 0; i < graph->edge_count; i++) {
        if (graph->edges[i].process_id == process_id &&
            graph->edges[i].allocation > 0) {
            graph->available[graph->edges[i].resource_id] += graph->edges[i].allocation;
            graph->edges[i].allocation = 0;
        }
    }
}

// 死锁检测算法
bool detect_deadlock(ResourceAllocationGraph* graph) {
    bool finish[MAX_PROCESSES];
    int work[MAX_RESOURCES];

    // 初始化
    for (int i = 0; i < graph->process_count; i++) {
        finish[i] = false;
    }
    for (int i = 0; i < graph->resource_count; i++) {
        work[i] = graph->available[i];
    }

    // 查找可以完成的进程
    bool found;
    do {
        found = false;
        for (int i = 0; i < graph->process_count; i++) {
            if (!finish[i] && can_process_complete(graph, i)) {
                // 释放进程资源
                for (int j = 0; j < graph->edge_count; j++) {
                    if (graph->edges[j].process_id == i &&
                        graph->edges[j].allocation > 0) {
                        work[graph->edges[j].resource_id] += graph->edges[j].allocation;
                    }
                }
                finish[i] = true;
                found = true;
            }
        }
    } while (found);

    // 检查是否所有进程都完成
    for (int i = 0; i < graph->process_count; i++) {
        if (!finish[i]) {
            return true; // 存在死锁
        }
    }

    return false; // 不存在死锁
}

// 打印资源分配图
void print_graph(ResourceAllocationGraph* graph) {
    printf("资源分配图：\n");
    printf("进程\t资源\t分配\t请求\n");

    for (int i = 0; i < graph->edge_count; i++) {
        printf("P%d\tR%d\t%d\t%d\n",
               graph->edges[i].process_id,
               graph->edges[i].resource_id,
               graph->edges[i].allocation,
               graph->edges[i].request);
    }

    printf("可用资源：");
    for (int i = 0; i < graph->resource_count; i++) {
        printf("R%d=%d ", i, graph->available[i]);
    }
    printf("\n");
}

使用示例：

int main() {
    ResourceAllocationGraph graph;

    // 初始化图
    init_graph(&graph, 3, 3);

    // 设置可用资源
    graph.available[0] = 1;
    graph.available[1] = 1;
    graph.available[2] = 0;

    // 添加资源分配和请求
    add_allocation_edge(&graph, 0, 0, 1);  // P0持有R0
    add_allocation_edge(&graph, 1, 1, 1);  // P1持有R1
    add_request_edge(&graph, 0, 1, 1);     // P0请求R1
    add_request_edge(&graph, 1, 0, 1);     // P1请求R0

    // 打印图
    print_graph(&graph);

    // 检测死锁
    if (detect_deadlock(&graph)) {
        printf("检测到死锁！\n");
    } else {
        printf("没有检测到死锁。\n");
    }

    return 0;
}