简解操作系统
第一部分：进程与线程管理
1. 进程状态转换
-
文字解释：进程在其生命周期中会经历多个状态：新建、就绪、运行、阻塞、终止。
-
就绪 → 运行：被调度器选中，获得CPU。
-
运行 → 就绪：时间片用完或被更高优先级进程抢占。
-
运行 → 阻塞：等待某种事件（如I/O完成、信号量）。
-
阻塞 → 就绪：等待的事件已发生。
-
-
代码描述：在Linux中，可以通过
ps命令查看进程状态（R=运行/就绪，S=可中断睡眠，D=不可中断睡眠，Z=僵尸）。
bash
# 查看进程状态 ps aux | grep "process_name" # 状态列显示: R, S, D, Z, T 等
2. 进程调度算法
-
文字解释：
-
FCFS（先来先服务）：简单但可能造成“护航效应”。
-
SJF（短作业优先）：最优平均等待时间，但难以预知作业长度。
-
时间片轮转：公平，每个进程获得固定时间片，适合分时系统。
-
多级反馈队列：综合优先级和时间片，是实际系统常用的算法。
-
-
代码描述：模拟简单的时间片轮转。
c
// 伪代码: 时间片轮转调度
#include <stdio.h>
#include <unistd.h>
int main() {
int time_quantum = 10; // 时间片10ms
while (1) {
// 从就绪队列取出下一个进程
Process* p = ready_queue.dequeue();
if (p == NULL) break;
// 运行该进程，最多运行 time_quantum
int used = p->run(time_quantum);
if (p->remaining_time > 0) {
ready_queue.enqueue(p); // 仍未完成，放回队列末尾
} else {
p->terminate();
}
}
return 0;
}
3. 进程间通信（IPC）
-
文字解释：
-
管道（Pipe）：父子进程间单向通信，字节流。
-
消息队列：数据块传输，有边界，支持多对多。
-
共享内存：最快的IPC，但需要同步（如信号量）。
-
信号：异步通知机制，如
SIGKILL、SIGSTOP。
-
-
代码描述：使用共享内存和信号量实现生产者-消费者（简化版）。
c
// 生产者-消费者 (使用POSIX信号量和共享内存)
#include <semaphore.h>
#include <sys/mman.h>
#include <fcntl.h>
struct shared {
int buffer[10];
int in, out;
sem_t empty, full, mutex;
};
int main() {
// 创建共享内存
int shm_fd = shm_open("/myshm", O_CREAT | O_RDWR, 0666);
ftruncate(shm_fd, sizeof(struct shared));
struct shared* sp = mmap(NULL, sizeof(*sp), PROT_READ | PROT_WRITE, MAP_SHARED, shm_fd, 0);
// 初始化信号量
sem_init(&sp->empty, 1, 10); // 空槽位=10
sem_init(&sp->full, 1, 0); // 满槽位=0
sem_init(&sp->mutex, 1, 1);
// 生产者生产一个物品
sem_wait(&sp->empty);
sem_wait(&sp->mutex);
// 放入buffer[in]
sp->buffer[sp->in] = produce_item();
sp->in = (sp->in + 1) % 10;
sem_post(&sp->mutex);
sem_post(&sp->full);
}
第二部分：内存管理
1. 分页与分段
-
文字解释：
-
分页：将物理内存划分为固定大小的帧，逻辑内存划分为同样大小的页。通过页表映射逻辑地址到物理地址。优点是无外部碎片，但可能有内部碎片。
-
分段：按照程序逻辑结构（代码段、数据段、栈段）划分，每个段有独立的基址和限长。优点是有利于保护和共享，但会产生外部碎片。
-
-
代码描述：模拟简单的地址转换（页号 + 偏移 → 物理地址）。
c
// 模拟页式地址转换
#define PAGE_SIZE 4096
int page_table[64]; // 页号 -> 帧号
int translate_address(int logical_address) {
int page_num = logical_address / PAGE_SIZE;
int offset = logical_address % PAGE_SIZE;
if (page_num >= 64 || page_table[page_num] == -1) {
return -1; // 缺页错误
}
return page_table[page_num] * PAGE_SIZE + offset;
}
2. 页面置换算法
-
文字解释：当物理内存不足时，需将某些页换出到磁盘。
-
FIFO（先进先出）：简单但会出现Belady异常（增加帧数反而缺页增多）。
-
LRU（最近最少使用）：性能好，但需要硬件支持。
-
Clock（二次机会）：近似LRU，使用引用位，操作系统实际常用。
-
-
代码描述：模拟FIFO页面置换，计算缺页次数。
python
def fifo_page_replacement(pages, frame_count):
frames = []
page_faults = 0
for page in pages:
if page not in frames:
if len(frames) < frame_count:
frames.append(page)
else:
frames.pop(0) # 移除最早进来的
frames.append(page)
page_faults += 1
return page_faults
# 测试
pages = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3]
print(fifo_page_replacement(pages, 3)) # 输出 9
第三部分：文件系统
1. 文件分配方式
-
文字解释：
-
连续分配：文件块在磁盘上连续存储，读写快，但会产生外部碎片，且文件增长困难。
-
链接分配：每个块包含指向下一个块的指针，无外部碎片，但随机访问慢，且指针占用空间。
-
索引分配：每个文件有一个索引块，记录所有数据块地址。支持随机访问，但索引块大小需权衡。
-
-
代码描述：模拟简单的索引分配，读取文件的第N个块。
c
// 模拟索引分配的文件读取
#define MAX_BLOCKS 100
int index_block[MAX_BLOCKS]; // 存储数据块号，-1表示未分配
int read_block(int file_index, int block_num) {
if (block_num >= MAX_BLOCKS) return -1;
int data_block = index_block[block_num];
if (data_block == -1) return -1;
// 从磁盘读取 data_block 块
return disk_read(data_block);
}
2. 目录实现
-
文字解释：
-
线性列表：简单，但查找速度O(n)。
-
哈希表：查找速度快，但管理复杂（冲突处理）。
-
树形结构（如Linux的ext4使用B树），支持快速查找和扩展。
-
-
代码描述：模拟简单的线性目录查找（简化版）。
c
struct dir_entry {
char name[256];
int inode_number;
};
struct dir_entry directory[100];
int dir_size = 0;
int lookup(char* filename) {
for (int i = 0; i < dir_size; i++) {
if (strcmp(directory[i].name, filename) == 0) {
return directory[i].inode_number;
}
}
return -1; // 文件不存在
}
第四部分：并发与同步
1. 临界区问题与互斥
-
文字解释：多个进程/线程访问共享资源时，需保证同一时刻只有一个执行单元进入临界区。满足条件：互斥、前进、有限等待。
-
代码描述：使用
pthread_mutex_t实现互斥锁（Linux C）。
c
#include <pthread.h>
#include <stdio.h>
pthread_mutex_t lock;
int shared_counter = 0;
void* increment(void* arg) {
for (int i = 0; i < 100000; i++) {
pthread_mutex_lock(&lock);
shared_counter++; // 临界区
pthread_mutex_unlock(&lock);
}
return NULL;
}
int main() {
pthread_t t1, t2;
pthread_mutex_init(&lock, NULL);
pthread_create(&t1, NULL, increment, NULL);
pthread_create(&t2, NULL, increment, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
printf("Final counter: %d\n", shared_counter); // 应为200000
pthread_mutex_destroy(&lock);
return 0;
}
2. 死锁的四个必要条件与预防
-
文字解释：
-
互斥：资源不能被多个进程同时使用。
-
占有并等待：进程持有资源并等待其他资源。
-
非抢占：资源只能由持有者主动释放。
-
循环等待：存在进程等待环路。
-
-
预防策略：
-
破坏“占有并等待”：要求进程一次性申请所有资源。
-
破坏“循环等待”：对资源进行排序，强制按顺序申请。
-
-
代码描述：银行家算法（避免死锁）的简化判断——检查资源分配是否安全。
c
// 银行家算法安全性检查（伪代码）
bool is_safe(int available[], int max[][], int allocation[][]) {
int finish[processes] = {0};
int work[] = available;
while (1) {
bool found = false;
for each process i {
if (!finish[i] && max[i] - allocation[i] <= work) {
work += allocation[i];
finish[i] = 1;
found = true;
}
}
if (!found) break;
}
return all(finish == 1);
}
第五部分：一个综合实验：实现一个迷你Shell
这个例子结合了进程管理（fork/exec）、信号处理和文件描述符。
c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <sys/wait.h>
#define MAX_CMD 256
int main() {
char cmd[MAX_CMD];
while (1) {
printf("mysh> ");
fgets(cmd, sizeof(cmd), stdin);
cmd[strcspn(cmd, "\n")] = '\0'; // 去掉换行
if (strcmp(cmd, "exit") == 0) break;
pid_t pid = fork();
if (pid == 0) {
// 子进程: 解析命令并执行
char* args[10];
char* token = strtok(cmd, " ");
int i = 0;
while (token != NULL && i < 9) {
args[i++] = token;
token = strtok(NULL, " ");
}
args[i] = NULL;
execvp(args[0], args);
perror("execvp failed");
exit(1);
} else if (pid > 0) {
wait(NULL); // 等待子进程结束
} else {
perror("fork failed");
}
}
return 0;
}
openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构
更多推荐
11
0- 0
已为社区贡献1条内容
所有评论(0)