# 操作系统实验指导（Linux 进程/线程/调度/存储/文件/设备/同步/通信）
## 实验一 进程与线程——Linux 进程与线程通信
### 1.1 实验目的
深刻理解线程和进程的概念，掌握线程与进程在组成成分上的差别，以及与其相适应的通信方式和应用目标。

Linux 系统的 fork() 保持了 UNIX 的经典语义，被创建进程具有独立于父进程的地址空间，二者之间的通信通常可以采用 pipe 机制。clone() 是 Linux 系统特有的系统调用，可以通过参数确定父子之间是否共享存储空间等资源，在地址空间等资源共享的情况下 clone() 实质上相当于创建了一个轻进程或线程，这是 clone() 的通常用法。实际在 Linux 系统中，fork() 以及用户级线程 pthread 都是基于 clone() 实现的。

### 1.2 实验内容
以 Linux 系统进程和线程机制为背景，掌握 fork() 和 clone() 系统调用的形式和功能，以及与其相适应的高级通信方式。由 fork() 派生的子进程之间通过 pipe 通信，由 clone() 创建的线程之间通过共享内存通信，对于后者需要考虑互斥问题。

以生产者-消费者问题为例，通过实验理解 fork() 和 clone() 两个系统调用的区别。程序要求能够创建 4 个进程或线程，其中包括两个生产者和两个消费者，生产者和消费者之间能够传递数据。

### 1.3 实验准备
1. **fork() 系统调用**
```cpp
pid = fork();
```
创建一个子进程，子进程是父进程的完整复制，正常返回值为非负整数。对于父进程返回值大于 0（子进程 pid），对于子进程返回 0，利用返回值差别执行不同逻辑。

2. **clone() 系统调用**
```cpp
int clone(int (*fn)(void *arg), void *stack, int flags, void *arg);
```
- fn：轻进程执行函数
- stack：轻进程使用栈
- flags：CLONE_VM/CLONE_FS/CLONE_FILES/CLONE_SIGHAND/CLONE_PID 组合
- arg：传递参数

3. **pipe() 系统调用**
```cpp
int pipe(int fd[2]);
```
创建管道，返回 fd[0]（读）、fd[1]（写），可被 fork() 子进程继承共享。

4. **信号量与互斥锁**
- sem_wait(&s)：P 操作；sem_post(&s)：V 操作
- pthread_mutex_lock(&mutex)：加锁；pthread_mutex_unlock(&mutex)：解锁

### 1.4 实验设计
1. 用 pipe() 创建管道，fork() 创建 2 生产者 + 2 消费者进程，管道通信。
2. 用 clone() 创建 4 个轻进程（线程），共享内存，互斥锁保护共享区。

### 1.5 参考代码
#### 基于 fork()
```cpp
#include "sys/types.h"
#include "sys/file.h"
#include "unistd.h"

char r_buf[4];
char w_buf[4];
int pipe_fd[2];
pid_t pid1, pid2, pid3, pid4;

int producer(int id);
int consumer(int id);

int main(int argc, char **argv) {
    if (pipe(pipe_fd) < 0) {
        printf("pipe create error \n");
        exit(-1);
    } else {
        printf("pipe is created successfully!\n");
        if ((pid1 = fork()) == 0) producer(1);
        if ((pid2 = fork()) == 0) producer(2);
        if ((pid3 = fork()) == 0) consumer(1);
        if ((pid4 = fork()) == 0) consumer(2);
    }
    close(pipe_fd[0]);
    close(pipe_fd[1]);
    int i, pid, status;
    for (i = 0; i < 4; i++)
        pid = wait(&status);
    exit(0);
}

int producer(int id) {
    printf("producer %d is running!\n", id);
    close(pipe_fd[0]);
    int i = 0;
    for (i = 1; i < 10; i++) {
        sleep(3);
        if (id == 1)
            strcpy(w_buf, "aaa\0");
        else
            strcpy(w_buf, "bbb\0");
        if (write(pipe_fd[1], w_buf, 4) == -1)
            printf("write to pipe error\n");
    }
    close(pipe_fd[1]);
    printf("producer %d is over!\n", id);
    exit(id);
}

int consumer(int id) {
    close(pipe_fd[1]);
    printf("consumer %d is running!\n", id);
    if (id == 1)
        strcpy(w_buf, "ccc\0");
    else
        strcpy(w_buf, "ddd\0");
    while (1) {
        sleep(1);
        strcpy(r_buf, "eee\0");
        if (read(pipe_fd[0], r_buf, 4) == 0)
            break;
        printf("consumer %d get %s, while the w_buf is %s\n", id, r_buf, w_buf);
    }
    close(pipe_fd[0]);
    printf("consumer %d is over!\n", id);
    exit(id);
}
```

#### 基于 clone()
```cpp
#include "sched.h"
#include "pthread.h"
#include "stdio.h"
#include "stdlib.h"
#include "semaphore.h"

int producer(void *args);
int consumer(void *args);

pthread_mutex_t mutex;
sem_t product;
sem_t warehouse;
char buffer[8][4];
int bp = 0;

int main(int argc, char ** argv) {
    pthread_mutex_init(&mutex, NULL);
    sem_init(&product, 0, 0);
    sem_init(&warehouse, 0, 8);
    int clone_flag, arg, retval;
    char *stack;
    clone_flag = CLONE_VM | CLONE_SIGHAND | CLONE_FS | CLONE_FILES;
    int i;
    for (i = 0; i < 2; i++) {
        arg = i;
        stack = (char *)malloc(4096);
        retval = clone((void *)producer, &(stack[4095]), clone_flag, (void *)&arg);
        stack = (char *)malloc(4096);
        sleep(1);
        retval = clone((void *)consumer, &(stack[4095]), clone_flag, (void *)&arg);
    }
    exit(1);
}

int producer(void *args) {
    int id = *((int *)args);
    int i;
    for (i = 0; i < 10; i++) {
        sleep(i + 1);
        sem_wait(&warehouse);
        pthread_mutex_lock(&mutex);
        if (id == 0)
            strcpy(buffer[bp], "aaa\0");
        else
            strcpy(buffer[bp], "bbb\0");
        bp++;
        printf("producer%d produce %s in %d\n", id, buffer[bp - 1], bp - 1);
        pthread_mutex_unlock(&mutex);
        sem_post(&product);
    }
    printf("producer%d is over!\n", id);
    return 0;
}

int consumer(void *args) {
    int id = *((int *)args);
    int i;
    for (i = 0; i < 10; i++) {
        sleep(10 - i);
        sem_wait(&product);
        pthread_mutex_lock(&mutex);
        bp--;
        printf("consumer%d get %s in %d\n", id, buffer[bp], bp);
        strcpy(buffer[bp], "zzz\0");
        pthread_mutex_unlock(&mutex);
        sem_post(&warehouse);
    }
    printf("consumer%d is over!\n", id);
    return 0;
}
```

### 1.6 实验结果
- fork() 进程独立地址空间，通过管道通信，数据互不影响。
- clone() 线程共享内存，需互斥与同步，数据一致。

### 1.7 思考问题
1. 用 shm/msg 实现生产者-消费者。
2. 对比 pipe、clone、shm、msg 优缺点与适用场景。

---

## 实验二 处理器调度——实时调度算法 EDF 和 RMS
### 2.1 实验目的
深入理解处理器调度算法，了解硬实时概念，掌握周期性任务调度算法 EDF（Earliest Deadline First）和 RMS（Rate Monotonic Scheduling）的可调度条件，并能在可调度情况下给出具体调度结果。

### 2.2 实验内容
在 Linux 环境采用用户级线程模拟 EDF 和 RMS。给定实时任务，判断可调度性，创建线程按算法调度，用字符绘制 Gantt 图。

### 2.3 实验准备
- EDF 可调度条件：∑(Ci/Ti) ≤ 1（可抢占）
- RMS 可调度条件：∑(Ci/Ti) ≤ n·(exp(ln2/n) − 1)（不可抢占）
- pthread_create 创建用户级线程

### 2.4 实验设计
用 task 结构体描述实时任务，实现 select_proc() 调度算法，主线程按算法唤醒线程，线程执行一个时间单位后交还控制权。

### 2.5 参考代码
```cpp
#include "math.h"
#include "sched.h"
#include "pthread.h"
#include "stdlib.h"
#include "semaphore.h"
#include "stdio.h"

typedef struct {
    char task_id;
    int call_num;
    int ci;
    int ti;
    int ci_left;
    int ti_left;
    int flag;
    int arg;
    pthread_t th;
} task;

void proc(int *args);
void *idle();
int select_proc();

int task_num = 0;
int idle_num = 0;
int alg;
int curr_proc = -1;
int demo_time = 100;
task *tasks;
pthread_mutex_t proc_wait[100];
pthread_mutex_t main_wait, idle_wait;
float sum = 0;
pthread_t idle_proc;

int main(int argc, char ** argv) {
    pthread_mutex_init(&main_wait, NULL);
    pthread_mutex_lock(&main_wait);
    pthread_mutex_init(&idle_wait, NULL);
    pthread_mutex_lock(&idle_wait);
    printf("Please input number of real time tasks:\n");
    scanf("%d", &task_num);
    tasks = (task *)malloc(task_num * sizeof(task));
    int i;
    for (i = 0; i < task_num; i++) {
        pthread_mutex_init(&proc_wait[i], NULL);
        pthread_mutex_lock(&proc_wait[i]);
    }
    for (i = 0; i < task_num; i++) {
        printf("Please input task id, followed by Ci and Ti:\n");
        getchar();
        scanf("%c,%d,%d,", &tasks[i].task_id, &tasks[i].ci, &tasks[i].ti);
        tasks[i].ci_left = tasks[i].ci;
        tasks[i].ti_left = tasks[i].ti;
        tasks[i].flag = 2;
        tasks[i].arg = i;
        tasks[i].call_num = 1;
        sum += (float)tasks[i].ci / (float)tasks[i].ti;
    }
    printf("Please input algorithm, 1 for EDF, 2 for RMS:");
    getchar();
    scanf("%d", &alg);
    printf("Please input demo time:");
    scanf("%d", &demo_time);
    double r = 1;
    if (alg == 2) {
        r = (double)task_num * (exp(log(2) / (double)task_num) - 1);
        printf("r is %lf\n", r);
    }
    if (sum > r) {
        printf("(sum = %lf > r = %lf), not schedulable!\n", sum, r);
        exit(2);
    }
    pthread_create(&idle_proc, NULL, (void *)idle, NULL);
    for (i = 0; i < task_num; i++)
        pthread_create(&tasks[i].th, NULL, (void *)proc, &tasks[i].arg);
    for (i = 0; i < demo_time; i++) {
        int j;
        if ((curr_proc = select_proc(alg)) != -1) {
            pthread_mutex_unlock(&proc_wait[curr_proc]);
            pthread_mutex_lock(&main_wait);
        } else {
            pthread_mutex_unlock(&idle_wait);
            pthread_mutex_lock(&main_wait);
        }
        for (j = 0; j < task_num; j++) {
            if (--tasks[j].ti_left == 0) {
                tasks[j].ti_left = tasks[j].ti;
                tasks[j].ci_left = tasks[j].ci;
                pthread_create(&tasks[j].th, NULL, (void *)proc, &tasks[j].arg);
                tasks[j].flag = 2;
            }
        }
        printf("\n");
        sleep(1);
    }
}

void proc(int * args) {
    while (tasks[*args].ci_left > 0) {
        pthread_mutex_lock(&proc_wait[*args]);
        if (idle_num != 0) {
            printf("idle(%d)", idle_num);
            idle_num = 0;
        }
        printf("%c%d", tasks[*args].task_id, tasks[*args].call_num);
        tasks[*args].ci_left--;
        if (tasks[*args].ci_left == 0) {
            printf("(%d)", tasks[*args].ci);
            tasks[*args].flag = 0;
            tasks[*args].call_num++;
        }
        pthread_mutex_unlock(&main_wait);
    }
}

void *idle() {
    while (1) {
        pthread_mutex_lock(&idle_wait);
        printf("->");
        idle_num++;
        pthread_mutex_unlock(&main_wait);
    }
}

int select_proc(int alg) {
    int j;
    int templ, temp2;
    templ = 10000;
    temp2 = -1;
    if ((alg == 2) && (curr_proc != -1) && (tasks[curr_proc].flag != 0))
        return curr_proc;
    for (j = 0; j < task_num; j++) {
        if (tasks[j].flag == 2) {
            switch (alg) {
                case 1:
                    if (templ > tasks[j].ti_left) {
                        templ = tasks[j].ti_left;
                        temp2 = j;
                    }
                    break;
                case 2:
                    if (templ > tasks[j].ti) {
                        templ = tasks[j].ti;
                        temp2 = j;
                    }
                    break;
            }
        }
    }
    return temp2;
}
```

### 2.6 实验结果
编译：`gcc -lpthread -lm test_scheduler.c -o scheduler.out`
- EDF：按截止时间优先调度
- RMS：按周期短优先，不可抢占

### 2.7 思考问题
1. 改进调度：仅需重调度时返回主线程，减少开销。
2. 统计线程切换次数。

---

## 实验三 存储管理——动态不等长存储资源分配算法
### 3.1 实验目的
理解动态异长存储分区资源管理，掌握所需数据结构和管理程序，了解各种存储分配算法的优点和缺点。

### 3.2 实验内容
1. 分析 UNIX 最先适应（FF）map 结构、malloc、mfree。
2. 实现最佳适应（BF）、最坏适应（WF）。

### 3.3 实验准备
掌握动态不等长存储管理、UNIX 存储资源管理。

### 3.4 实验设计
编写 BF、WF 分配与释放函数，初始化存储表，处理请求/释放并显示。

### 3.5 参考代码
```cpp
#include <stdio.h>
#include <stdlib.h>
#define MAPSIZE 100

struct map {
    int m_addr;
    int m_size;
};
struct map map[MAPSIZE];

int BF_malloc(struct map *mp, int size) {
    register int a, s;
    register struct map *bp, *bpp;
    for (bp = mp; bp->m_size; bp++) {
        if (bp->m_size >= size) {
            a = bp->m_addr;
            s = bp->m_size;
            for (bpp = bp; bpp->m_size; bpp++) {
                if (bpp->m_size >= size && bpp->m_size < s) {
                    a = bpp->m_addr;
                    s = bpp->m_size;
                    bp = bpp;
                }
            }
            bp->m_addr += size;
            if ((bp->m_size -= size) == 0) {
                do {
                    bp++;
                    (bp - 1)->m_addr = bp->m_addr;
                } while (((bp - 1)->m_size = bp->m_size));
            }
            return a;
        }
    }
    return -1;
}

int WF_malloc(struct map *mp, int size) {
    register int a, s;
    register struct map *bp, *bpp;
    for (bp = mp; bp->m_size; bp++) {
        if (bp->m_size >= size) {
            a = bp->m_addr;
            s = bp->m_size;
            for (bpp = bp; bpp->m_size; bpp++) {
                if (bpp->m_size > s) {
                    a = bpp->m_addr;
                    s = bpp->m_size;
                    bp = bpp;
                }
            }
            bp->m_addr += size;
            if ((bp->m_size -= size) == 0) {
                do {
                    bp++;
                    (bp - 1)->m_addr = bp->m_addr;
                } while (((bp - 1)->m_size = bp->m_size));
            }
            return a;
        }
    }
    return -1;
}

void mfree(struct map *mp, int aa, int size) {
    register struct map *bp;
    register int t, a;
    a = aa;
    for (bp = mp; bp->m_addr <= a && bp->m_size != 0; bp++);
    if (bp > mp && (bp - 1)->m_addr + (bp - 1)->m_size == a) {
        (bp - 1)->m_size += size;
        if (a + size == bp->m_addr) {
            (bp - 1)->m_size += bp->m_size;
            while (bp->m_size) {
                bp++;
                (bp - 1)->m_addr = bp->m_addr;
                (bp - 1)->m_size = bp->m_size;
            }
        }
    } else {
        if (a + size == bp->m_addr && bp->m_size) {
            bp->m_addr -= size;
            bp->m_size += size;
        } else if (size) {
            do {
                t = bp->m_addr;
                bp->m_addr = a;
                a = t;
                t = bp->m_size;
                bp->m_size = size;
                bp++;
            } while ((size = t));
        }
    }
}

void init() {
    struct map *bp;
    int addr, size;
    bp = map;
    printf("Please input starting addr and total size:");
    scanf("%d,%d", &addr, &size);
    bp->m_addr = addr;
    bp->m_size = size;
    (++bp)->m_size = 0;
}

void show_map() {
    system("clear");
    printf("\nCurrent memory map...\n");
    printf("Address\t\tSize\n");
    struct map *bp = map;
    while (bp->m_size != 0) {
        printf("<%d\t\t%d>\n", bp->m_addr, bp->m_size);
        bp++;
    }
    printf("\n");
}

int main() {
    int a, s, i;
    char c;
    init();
    printf("Please input, b for BF, w for WF:");
    scanf("%c", &c);
    do {
        show_map();
        printf("Please input, 1 for request, 2 for release, 0 for exit:");
        scanf("%d", &i);
        switch (i) {
            case 1:
                printf("Please input size:");
                scanf("%d", &s);
                if (c == 'b')
                    a = BF_malloc(map, s);
                else
                    a = WF_malloc(map, s);
                if (a == -1)
                    printf("request can not be satisfied\n");
                else
                    printf("alloc memory at address:%d,size:%d\n", a, s);
                break;
            case 2:
                printf("Please input addr and size:");
                scanf("%d,%d", &a, &s);
                mfree(map, a, s);
                break;
            case 0:
                exit(0);
        }
    } while (1);
}
```

### 3.6 实验结果
按输入分配/释放，实时显示空闲块。

### 3.7 思考问题
1. 按大小排序空闲块，优化分配速度，重写释放。
2. 设计伙伴堆（buddy heap）数据结构与算法。

---

## 实验四 文件系统——散列结构文件
### 4.1 实验目的
理解 Linux 文件系统内部技术，掌握文件系统调用，建立面向随机检索的散列结构文件。

### 4.2 实验内容
设计散列文件创建、打开、关闭、读、写、删除等函数，编写测试程序验证。

### 4.3 实验准备
散列算法、Linux 文件系统调用 creat/open/close/read/write/lseek。

### 4.4 实验设计
文件头保存散列信息，实现冲突处理，提供随机检索接口。

### 4.5 参考代码
#### HashFile.h
```cpp
#include <unistd.h>
#define COLLISIONFACTOR 0.5

struct HashFileHeader {
    int sig;
    int reclen;
    int total_rec_num;
    int current_rec_num;
};

struct CFTag {
    char collision;
    char free;
};

int hashfile_creat(const char *filename, mode_t mode, int reclen, int recnum);
int hashfile_open(const char *filename, int flags, mode_t mode);
int hashfile_close(int fd);
int hashfile_read(int fd, int keyoffset, int keylen, void *buf);
int hashfile_write(int fd, int keyoffset, int keylen, void *buf);
int hashfile_delrec(int fd, int keyoffset, int keylen, void *buf);
int hashfile_findrec(int fd, int keyoffset, int keylen, void *buf);
int hashfile_saverec(int fd, int keyoffset, int keylen, void *buf);
int hash(int keyoffset, int keylen, void *buf, int recnum);
int checkHashFileFull(int fd);
int readHashFileHeader(int fd, struct HashFileHeader *hfh);
```

#### HashFile.c
```cpp
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include "HashFile.h"

int hashfile_creat(const char *filename, mode_t mode, int reclen, int total_rec_num) {
    struct HashFileHeader hfh;
    int fd, rtn;
    char *buf;
    hfh.sig = 31415926;
    hfh.reclen = reclen;
    hfh.total_rec_num = total_rec_num;
    hfh.current_rec_num = 0;
    fd = creat(filename, mode);
    if (fd != -1) {
        rtn = write(fd, &hfh, sizeof(struct HashFileHeader));
        if (rtn != -1) {
            buf = (char *)malloc((reclen + sizeof(struct CFTag)) * total_rec_num);
            memset(buf, 0, (reclen + sizeof(struct CFTag)) * total_rec_num);
            rtn = write(fd, buf, (reclen + sizeof(struct CFTag)) * total_rec_num);
            free(buf);
        }
        close(fd);
        return rtn;
    }
    close(fd);
    return -1;
}

int hashfile_open(const char *filename, int flags, mode_t mode) {
    int fd = open(filename, flags, mode);
    struct HashFileHeader hfh;
    if (read(fd, &hfh, sizeof(struct HashFileHeader)) != -1) {
        lseek(fd, 0, SEEK_SET);
        if (hfh.sig == 31415926)
            return fd;
    }
    return -1;
}

int hashfile_close(int fd) {
    return close(fd);
}

int hashfile_read(int fd, int keyoffset, int keylen, void *buf) {
    struct HashFileHeader hfh;
    readHashFileHeader(fd, &hfh);
    int offset = hashfile_findrec(fd, keyoffset, keylen, buf);
    if (offset != -1) {
        lseek(fd, offset + sizeof(struct CFTag), SEEK_SET);
        return read(fd, buf, hfh.reclen);
    }
    return -1;
}

int hashfile_write(int fd, int keyoffset, int keylen, void *buf) {
    return hashfile_saverec(fd, keyoffset, keylen, buf);
}

int hashfile_delrec(int fd, int keyoffset, int keylen, void *buf) {
    int offset = hashfile_findrec(fd, keyoffset, keylen, buf);
    if (offset != -1) {
        struct CFTag tag;
        read(fd, &tag, sizeof(struct CFTag));
        tag.free = 0;
        lseek(fd, offset, SEEK_SET);
        write(fd, &tag, sizeof(struct CFTag));
        struct HashFileHeader hfh;
        readHashFileHeader(fd, &hfh);
        int addr = hash(keyoffset, keylen, buf, hfh.total_rec_num);
        offset = sizeof(struct HashFileHeader) + addr * (hfh.reclen + sizeof(struct CFTag));
        lseek(fd, offset, SEEK_SET);
        read(fd, &tag, sizeof(struct CFTag));
        tag.collision--;
        lseek(fd, offset, SEEK_SET);
        write(fd, &tag, sizeof(struct CFTag));
        hfh.current_rec_num--;
        lseek(fd, 0, SEEK_SET);
        write(fd, &hfh, sizeof(struct HashFileHeader));
        return 0;
    }
    return -1;
}

int hashfile_findrec(int fd, int keyoffset, int keylen, void *buf) {
    struct HashFileHeader hfh;
    readHashFileHeader(fd, &hfh);
    int addr = hash(keyoffset, keylen, buf, hfh.total_rec_num);
    int offset = sizeof(struct HashFileHeader) + addr * (hfh.reclen + sizeof(struct CFTag));
    lseek(fd, offset, SEEK_SET);
    struct CFTag tag;
    read(fd, &tag, sizeof(struct CFTag));
    char count = tag.collision;
    if (count == 0) return -1;
recfree:
    if (tag.free == 0) {
        offset += hfh.reclen + sizeof(struct CFTag);
        lseek(fd, offset, SEEK_SET);
        read(fd, &tag, sizeof(struct CFTag));
        goto recfree;
    }
    char *p = (char *)malloc(hfh.reclen);
    read(fd, p, hfh.reclen);
    char *p1 = (char *)buf + keyoffset;
    char *p2 = p + keyoffset;
    int j = 0;
    while (*p1 == *p2 && j < keylen) {
        p1++; p2++; j++;
    }
    if (j == keylen) {
        free(p);
        return offset;
    }
    free(p);
    offset += hfh.reclen + sizeof(struct CFTag);
    lseek(fd, offset, SEEK_SET);
    read(fd, &tag, sizeof(struct CFTag));
    goto recfree;
}

int hashfile_saverec(int fd, int keyoffset, int keylen, void *buf) {
    if (checkHashFileFull(fd)) return -1;
    struct HashFileHeader hfh;
    readHashFileHeader(fd, &hfh);
    int addr = hash(keyoffset, keylen, buf, hfh.total_rec_num);
    int offset = sizeof(struct HashFileHeader) + addr * (hfh.reclen + sizeof(struct CFTag));
    lseek(fd, offset, SEEK_SET);
    struct CFTag tag;
    read(fd, &tag, sizeof(struct CFTag));
    tag.collision++;
    lseek(fd, sizeof(struct CFTag) * (-1), SEEK_CUR);
    write(fd, &tag, sizeof(struct CFTag));
    while (tag.free != 0) {
        offset += hfh.reclen + sizeof(struct CFTag);
        if (offset >= lseek(fd, 0, SEEK_END))
            offset = sizeof(struct HashFileHeader);
        lseek(fd, offset, SEEK_SET);
        read(fd, &tag, sizeof(struct CFTag));
    }
    tag.free = 1;
    lseek(fd, sizeof(struct CFTag) * (-1), SEEK_CUR);
    write(fd, &tag, sizeof(struct CFTag));
    write(fd, buf, hfh.reclen);
    hfh.current_rec_num++;
    lseek(fd, 0, SEEK_SET);
    return write(fd, &hfh, sizeof(struct HashFileHeader));
}

int hash(int keyoffset, int keylen, void *buf, int total_rec_num) {
    int i = 0, addr = 0;
    char *p = (char *)buf + keyoffset;
    for (i = 0; i < keylen; i++) {
        addr += (int)(*p);
        p++;
    }
    return addr % (int)(total_rec_num * COLLISIONFACTOR);
}

int readHashFileHeader(int fd, struct HashFileHeader *hfh) {
    lseek(fd, 0, SEEK_SET);
    return read(fd, hfh, sizeof(struct HashFileHeader));
}

int checkHashFileFull(int fd) {
    struct HashFileHeader hfh;
    readHashFileHeader(fd, &hfh);
    return hfh.current_rec_num >= hfh.total_rec_num;
}
```

#### 测试程序
```cpp
#include "HashFile.h"
#define RECORDLEN 32
struct jtRecord {
    int key;
    char other[RECORDLEN - sizeof(int)];
};
#define KEYOFFSET 0
#define KEYLEN sizeof(int)
#define FILENAME "jing.hash"

void showHashFile() {
    int fd = open(FILENAME, O_RDWR);
    lseek(fd, sizeof(struct HashFileHeader), SEEK_SET);
    struct jtRecord jt;
    struct CFTag tag;
    while (1) {
        if (read(fd, &tag, sizeof(struct CFTag)) <= 0) break;
        printf("Tag is <%d,%d>\t", tag.collision, tag.free);
        if (read(fd, &jt, sizeof(struct jtRecord)) <= 0) break;
        printf("Record is {%d,%s}\n", jt.key, jt.other);
    }
    close(fd);
}

int main() {
    struct jtRecord rec[6] = {
        {1,"jing"},{2,"wang"},{3,"li"},{4,"zhang"},{5,"qing"},{6,"yuan"}
    };
    int fd = hashfile_creat(FILENAME, O_RDWR | O_CREAT, RECORDLEN, 6);
    fd = hashfile_open(FILENAME, O_RDWR, 0);
    for (int i = 0; i < 6; i++)
        hashfile_saverec(fd, KEYOFFSET, KEYLEN, &rec[i]);
    hashfile_close(fd);
    showHashFile();
    return 0;
}
```

### 4.6 实验结果
成功创建散列文件，支持增删查改。

### 4.7 思考问题
1. 实现 hashfile_update() 记录更新函数。
2. 内核级实现散列文件的方案与困难。

---

## 实验五 设备管理——Linux 设备驱动程序安装
### 5.1 实验目的
认识 Linux 设备种类与工作方式，理解设备驱动原理，掌握驱动编写规范，安装简单字符设备驱动。

### 5.2 实验内容
编写字符设备驱动模块，实现 open/close/read/write，动态注册/卸载，创建设备文件 /dev/mydev。

### 5.3 实验准备
- device_struct、file_operations 结构体
- register_chrdev/unregister_chrdev
- init_module/cleanup_module
- copy_to_user/copy_from_user

### 5.4 实验设计
编写驱动模块与测试程序，编译→加载→创建设备→测试→卸载。

### 5.5 参考代码
#### 设备驱动 mydev.c
```cpp
#ifndef __KERNEL__
#define __KERNEL__
#endif
#ifndef MODULE
#define MODULE
#endif
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/fs.h>
#include <linux/uaccess.h>

#define SUCCESS 0
#define DEVICE_NAME "kueng_char_dev"
#define BUF_LEN 50

static int Device_Open = 0;
static char Message[BUF_LEN];
static int Major;

static int mydev_open(struct inode *inode, struct file *file) {
    if (Device_Open) return -EBUSY;
    Device_Open = 1;
    return 0;
}

static int mydev_release(struct inode *inode, struct file *file) {
    Device_Open = 0;
    return 0;
}

static ssize_t mydev_read(struct file *file, char *buffer, size_t length, loff_t *f_pos) {
    return copy_to_user(buffer, Message, length);
}

static ssize_t mydev_write(struct file *file, const char *buffer, size_t length, loff_t *f_pos) {
    int len = BUF_LEN < length ? BUF_LEN : length;
    return copy_from_user(Message, buffer, len);
}

static struct file_operations fops = {
    .open = mydev_open,
    .release = mydev_release,
    .read = mydev_read,
    .write = mydev_write,
};

int init_module(void) {
    Major = register_chrdev(0, DEVICE_NAME, &fops);
    if (Major < 0) {
        printk("Register char device failed\n");
        return Major;
    }
    printk("Registered with major %d\n", Major);
    return 0;
}

void cleanup_module(void) {
    unregister_chrdev(Major, DEVICE_NAME);
}

MODULE_LICENSE("GPL");
MODULE_AUTHOR("KUENG");
```

#### 测试程序 test.c
```cpp
#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <string.h>

int main() {
    int testdev = open("/dev/mydev", O_RDWR);
    if (testdev == -1) {
        printf("can not open file\n");
        exit(0);
    }
    char buf[50] = "pear to dev!";
    write(testdev, buf, 50);
    printf("write: %s\n", buf);
    strcpy(buf, "apple to dev!");
    read(testdev, buf, 50);
    printf("read: %s\n", buf);
    close(testdev);
    return 0;
}
```

### 5.6 实验结果
加载模块→查看主设备号→mknod→运行测试→读写正常→卸载。

### 5.7 思考问题
1. 仿照 /dev/null 编写 sink 设备驱动。
2. 源码级编译驱动与模块方式对比。

---

## 实验六 同步机制——信号量集与哲学家就餐问题
### 6.1 实验目的
理解 Linux SystemV 信号量集同步机制，掌握 semget/semctl/semop，解决哲学家就餐死锁问题。

### 6.2 实验内容
创建 5 个信号量（叉子），哲学家同时申请左右叉子，避免死锁。

### 6.3 实验准备
- semget：创建信号量集
- semctl：设置初值
- semop：原子操作多个信号量

### 6.4 实验设计
semget 创建 5 信号量，semctl 置 1，fork 5 进程，semop 同时申请/释放两把叉子。

### 6.5 参考代码
```cpp
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>

union semun {
    int val;
    struct semid_ds *buf;
    unsigned short *array;
    struct seminfo *__buf;
} arg;

int semid;

void philosopher(int i) {
    struct sembuf sbuf[2];
    sbuf[0].sem_num = i;
    sbuf[0].sem_flg = SEM_UNDO;
    sbuf[1].sem_num = (i + 1) % 5;
    sbuf[1].sem_flg = SEM_UNDO;
    while (1) {
        printf("philosopher %d is thinking\n", i);
        sleep(2);
        printf("philosopher %d is hungry\n", i);
        sbuf[0].sem_op = -1;
        sbuf[1].sem_op = -1;
        semop(semid, sbuf, 2);
        printf("philosopher %d is eating\n", i);
        sleep(2);
        sbuf[0].sem_op = 1;
        sbuf[1].sem_op = 1;
        semop(semid, sbuf, 2);
    }
}

int main() {
    key_t key = ftok("fname", 1);
    semid = semget(key, 5, IPC_CREAT | 0666);
    arg.val = 1;
    for (int i = 0; i < 5; i++)
        semctl(semid, i, SETVAL, arg);
    for (int i = 0; i < 5; i++) {
        if (fork() == 0) {
            philosopher(i);
        }
    }
    while (wait(NULL) > 0);
    return 0;
}
```

### 6.6 实验结果
无相邻哲学家同时进食，无死锁。

### 6.7 思考问题
1. 用 clone/vfork 替代 fork。
2. 用信号量集解决吸烟者问题。

---

## 实验七 进程通信——消息方式
### 7.1 实验目的
理解 Linux 消息队列通信机制，掌握 msgget/msgsnd/msgrcv/msgctl。

### 7.2 实验内容
创建消息队列，P1/P2 发消息，P3 收 P1、P4 收 P2，大消息拆分传输。

### 7.3 实验准备
消息队列系统调用，按类型收发。

### 7.4 实验设计
msgget 创建队列，fork 4 进程，P1 拆分矩阵发送，P3 合并；P2 发短消息，P4 接收。

### 7.5 参考代码
```cpp
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/msg.h>

struct msgbuf {
    long mtype;
    char mtext[1024];
};

int main() {
    key_t key = ftok(IPC_PRIVATE, 1);
    int msgid = msgget(key, IPC_CREAT | 0666);
    if (fork() == 0) {
        char a[64][64];
        for (int i = 0; i < 64; i++)
            for (int j = 0; j < 64; j++)
                a[i][j] = i < 32 ? (j < 32 ? 'a' : 'b') : (j < 32 ? 'c' : 'd');
        struct msgbuf mgb;
        mgb.mtype = 1;
        int k = 0;
        for (int i = 0; i < 32; i++) for (int j = 0; j < 32; j++) mgb.mtext[k++] = a[i][j];
        msgsnd(msgid, &mgb, sizeof(mgb), 0);
        k = 0;
        for (int i = 0; i < 32; i++) for (int j = 32; j < 64; j++) mgb.mtext[k++] = a[i][j];
        msgsnd(msgid, &mgb, sizeof(mgb), 0);
        k = 0;
        for (int i = 32; i < 64; i++) for (int j = 0; j < 32; j++) mgb.mtext[k++] = a[i][j];
        msgsnd(msgid, &mgb, sizeof(mgb), 0);
        k = 0;
        for (int i = 32; i < 64; i++) for (int j = 32; j < 64; j++) mgb.mtext[k++] = a[i][j];
        msgsnd(msgid, &mgb, sizeof(mgb), 0);
        exit(1);
    }
    if (fork() == 0) {
        struct msgbuf mgb;
        mgb.mtype = 2;
        strcpy(mgb.mtext, "ijkl");
        msgsnd(msgid, &mgb, sizeof(mgb), 0);
        strcpy(mgb.mtext, "mnop");
        msgsnd(msgid, &mgb, sizeof(mgb), 0);
        exit(2);
    }
    if (fork() == 0) {
        char a[64][64];
        struct msgbuf mgb;
        msgrcv(msgid, &mgb, sizeof(mgb), 1, 0);
        int k = 0;
        for (int i = 0; i < 32; i++) for (int j = 0; j < 32; j++) a[i][j] = mgb.mtext[k++];
        msgrcv(msgid, &mgb, sizeof(mgb), 1, 0);
        k = 0;
        for (int i = 0; i < 32; i++) for (int j = 32; j < 64; j++) a[i][j] = mgb.mtext[k++];
        msgrcv(msgid, &mgb, sizeof(mgb), 1, 0);
        k = 0;
        for (int i = 32; i < 64; i++) for (int j = 0; j < 32; j++) a[i][j] = mgb.mtext[k++];
        msgrcv(msgid, &mgb, sizeof(mgb), 1, 0);
        k = 0;
        for (int i = 32; i < 64; i++) for (int j = 32; j < 64; j++) a[i][j] = mgb.mtext[k++];
        for (int i = 0; i < 64; i++) {
            for (int j = 0; j < 64; j++) printf("%c", a[i][j]);
            printf("\n");
        }
        exit(3);
    }
    if (fork() == 0) {
        struct msgbuf mgb;
        msgrcv(msgid, &mgb, sizeof(mgb), 2, 0);
        printf("p4 received %s\n", mgb.mtext);
        msgrcv(msgid, &mgb, sizeof(mgb), 2, 0);
        printf("p4 received %s\n", mgb.mtext);
        exit(4);
    }
    wait(NULL);
    msgctl(msgid, IPC_RMID, NULL);
    return 0;
}
```

### 7.6 实验结果
矩阵拆分传输成功合并，短消息按类型收发。

### 7.7 思考问题
1. 传输杨辉三角矩阵。
2. 测试系统消息最大长度与队列容量。

---

## 实验八 进程通信——共享内存
### 8.1 实验目的
理解共享内存通信，掌握 shmget/shmat/shmdt/shmctl，信号量同步。

### 8.2 实验内容
创建共享内存，fork 子进程写，父进程读入文件，信号量同步。

### 8.3 实验准备
共享内存系统调用，信号量同步。

### 8.4 实验设计
shmget 创建共享内存，shmat 附加，fork 子进程输入写入，父进程读入文件，信号量同步。

### 8.5 参考代码
```cpp
#include <stdio.h>
#include <unistd.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/sem.h>
#include <string.h>

#define BUFFERSIZE 200
#define SEMKEY 251
#define SHMKEY 231
#define SHMSIZE 1024
#define FILENAME "abc.txt"

union semun {
    int val;
    struct semid_ds *buf;
    unsigned short *array;
};

int main() {
    char buf[BUFFERSIZE];
    int sem_id = semget(SEMKEY, 1, IPC_CREAT | 0600);
    union semun sem_val;
    sem_val.val = 0;
    semctl(sem_id, 0, SETVAL, sem_val);
    int shm_id = shmget(SHMKEY, SHMSIZE, IPC_CREAT | 0600);
    char *shm_addr = (char *)shmat(shm_id, NULL, 0);
    memset(shm_addr, 0, SHMSIZE);
    char *cur = shm_addr;
    FILE *fp = fopen(FILENAME, "wb");
    if (fork() == 0) {
        int isend = 0;
        int line = 1;
        printf("\n#line%d$ ", line);
        while (!isend && fgets(buf, BUFFERSIZE, stdin) != NULL) {
            line++;
            printf("\n#line%d$ ", line);
            if (buf[0] == 'Q' && strlen(buf) <= 2) {
                isend = 1;
                printf("\nExit...\n");
            } else {
                memcpy(cur, buf, strlen(buf));
                cur += strlen(buf);
                struct sembuf sem_op = {0, 1, 0};
                semop(sem_id, &sem_op, 1);
            }
        }
        *cur = -1;
        shmdt(shm_addr);
        exit(0);
    } else {
        while (1) {
            struct sembuf sem_op = {0, -1, 0};
            semop(sem_id, &sem_op, 1);
            if (*cur == -1) break;
            int i;
            for (i = 0; *cur != '\n'; cur++, i++)
                buf[i] = *cur;
            cur++;
            buf[i] = '\n';
            buf[++i] = 0;
            fwrite(buf, strlen(buf), 1, fp);
        }
        fclose(fp);
        wait(NULL);
        shmdt(shm_addr);
        shmctl(shm_id, IPC_RMID, NULL);
    }
    return 0;
}
```

### 8.6 实验结果
子进程输入，父进程写入文件，共享内存高效传输。

### 8.7 思考问题
1. 循环使用共享内存缓冲区。
2. 改用 pthread 线程的修改点。

---

## 实验九 内存与文件——内存映射文件
### 9.1 实验目的
理解内存映射文件机制，掌握 mmap/munmap/msync，提高文件访问效率。

### 9.2 实验内容
将文本文件映射内存，小写转大写，反序写入目标文件。

### 9.3 实验准备
mmap 映射文件到进程地址空间，直接内存操作。

### 9.4 实验设计
打开源文件与目标文件，mmap 映射，修改内容，反序写入，munmap 解除映射。

### 9.5 参考代码
```cpp
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdio.h>
#include <ctype.h>

int main(int argc, char **argv) {
    int fd1 = open(argv[1], O_RDONLY);
    int fd2 = open(argv[2], O_RDWR | O_CREAT, 0666);
    int flength = lseek(fd1, 0, SEEK_END);
    write(fd1, "\0", 1);
    lseek(fd1, 0, SEEK_SET);
    char *mapped_mem = mmap(NULL, flength, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd1, 0);
    char *p = mapped_mem;
    for (int i = 0; i <= flength; i++) {
        if (*p >= 'a' && *p <= 'z')
            *p = toupper(*p);
        p++;
    }
    p = mapped_mem + flength;
    for (int i = flength; i >= 0; i--) {
        write(fd2, p, 1);
        p--;
    }
    printf("%s\n", mapped_mem);
    munmap(mapped_mem, flength + 1);
    close(fd1);
    close(fd2);
    return 0;
}
```

### 9.6 实验结果
源文件小写转大写，目标文件为反序结果。

### 9.7 思考问题
1. 用数组下标访问映射内存。
2. 内存映射文件优势场景。

---

## 实验十 文件通信——命名管道
### 10.1 实验目的
理解命名管道（FIFO）与匿名管道差异，掌握 mkfifo/open/read/write，实现无亲缘进程通信。

### 10.2 实验内容
设计双管道聊天程序，Peter 与 Jack 双向对话。

### 10.3 实验准备
命名管道可永久存在，支持无亲缘进程，阻塞/非阻塞读写。

### 10.4 实验设计
A 端创建 fa/fb，fork 子进程读 fb、父进程写 fa；B 端子进程读 fa、父进程写 fb。

### 10.5 参考代码
#### A 端（Peter）
```cpp
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>
#include <signal.h>

int main() {
    unlink("fa");
    unlink("fb");
    mkfifo("fa", 0666);
    mkfifo("fb", 0666);
    printf("I am Peter...\n");
    if (fork() == 0) {
        int fd2 = open("fb", O_RDONLY);
        char buf[100];
        while (1) {
            memset(buf, 0, 100);
            if (read(fd2, buf, 100) == 0) {
                kill(getppid(), 9);
                return 0;
            }
            printf("\rJack says:%s", buf);
            fflush(stdout);
        }
    } else {
        int fd1 = open("fa", O_WRONLY);
        char buf[100];
        while (1) {
            fgets(buf, sizeof(buf), stdin);
            write(fd1, buf, sizeof(buf));
        }
    }
    return 0;
}
```

#### B 端（Jack）
```cpp
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>
#include <signal.h>

int main() {
    printf("I am Jack...\n");
    if (fork() == 0) {
        int fd1 = open("fa", O_RDONLY);
        char buf[100];
        while (1) {
            memset(buf, 0, 100);
            if (read(fd1, buf, 100) == 0) {
                kill(getppid(), 9);
                return 0;
            }
            printf("\rPeter says:%s", buf);
            fflush(stdout);
        }
    } else {
        int fd2 = open("fb", O_WRONLY);
        char buf[100];
        while (1) {
            fgets(buf, sizeof(buf), stdin);
            write(fd2, buf, sizeof(buf));
        }
    }
    return 0;
}
```

### 10.6 实验结果
先运行 A 端，再运行 B 端，双向聊天。

### 10.7 思考问题
1. 单进程实现双向通信，匿名管道能否实现。
2. 三方聊天程序设计。