写在前面的话：

本课程一共有四个实验，最后一个选做，由于时间原因，我只写了三个，并且每个都参考了老师所给的参考代码，建议还是要自己先试一试，构思一下，然后和参考代码作对比。至于实验环境的配置请自己搜索，我这里不再赘述。

前置知识部分，有的我借助了chatgpt进行生成，也许有不对的，欢迎指出，可以以邮件的形式发送给我。

实验环境： centos 7

实验一 ：进程与线程——Linux 进程与线程通讯

实验内容

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

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

前置知识

fork()

函数定义

1
2
3
4
#include <unistd.h>
pid_t fork(void);
//创建进程成功：在父进程中返回子进程的PID，在子进程中返回0
//创建失败返回-1

作用：通过系统调用创建一个与原来进程几乎完全相同的进程，也就是两个进程可以做完全相同的事情。

  • 一个进程调用fork函数之后，系统会先给新的进程分配资源，如存储数据、代码空间，然后将原来进程的所有值都复制给新的进程中，相当于克隆了一个自己。

  • 子进程是父进程的几乎完全拷贝，包括代码段、数据段、堆和栈等。

  • 虽然子进程和父进程的地址空间相同，但它们是独立的；修改子进程的内存不会影响父进程，反之亦然。

  • 使用 fork 创建子进程之后，父进程和子进程会并发运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<unistd.h>
#include<stdio.h>
int main()
{
 int tag=1;
 pid_t pid;
 printf("tag is %d now\n",tag);
 pid=fork();
 if(pid==-1) printf("there is error!\n");
 else if(pid==0)
{
     printf("i am father\n");
     printf("我是父亲,my pid is %d，我将修改tag，由%d变为%d\n",getpid(),tag,tag+1);
     tag++;
     printf("father:%d\n",tag);

}
 else
 {
     printf("i am son\n");
     printf("我是儿子，my pid is%d,my father's pid is %d,我将修改tag，由%d变为%d\n",getpid(),getppid(),tag,tag-10);
     tag-=10;
     printf("son:%d\n",tag);
 }
 return 0;
}
//输出：
//tag is 1 now
//i am son
//我是儿子，my pid is56935,my father's pid is 2467,我将修改tag，由1变为-9
//son:-9
//i am father
//我是父亲,my pid is 56936，我将修改tag，由1变为2
//father:2

由上述输出可以见得：

  • 父进程和子进程虽然共用地址空间，但是互相不影响
  • 子进程会从fork处开始运行

clone()

函数定义

1
int clone (int ( *fn ) (void  *arg) ,void *stack ,int flag ,void  *arg);
  • fn: 指向新进程将要执行的函数的指针。
  • stack: 为新进程分配的栈空间的指针。新进程将从该栈开始执行。
  • flag: 用于指定新进程的行为和资源共享方式的标志位。不同的标志位允许控制是否共享虚拟内存、文件描述符、信号处理等资源。
  • arg: 传递给新进程的参数

常用flag：

  • CLONE_VM: 新进程与父进程共享同一个内存空间。这意味着对内存的任何修改在两个进程中都是可见的。这通常用于创建线程，因为线程通常需要访问相同的内存。
  • CLONE_FS: 新进程与父进程共享文件系统信息。父进程和子进程将共享文件系统相关的信息，包括当前工作目录和根目录。这意味着对 chdir 或 chroot 的调用将对两个进程同时生效。
  • CLONE_FILES: 新进程与父进程共享文件描述符表。父进程和子进程将共享文件描述符表。关闭一个进程中的文件描述符将使该文件描述符在另一个进程中也不可用。
  • CLONE_SIGHAND: 新进程与父进程共享信号处理器。父进程和子进程将共享信号处理函数。这意味着信号处理函数的设置对两个进程都是有效的，信号处理的变化会互相影响。
  • CLONE_THREAD: 新进程与父进程属于同一个线程组。新进程将与父进程在同一个线程组（同一个进程的不同线程）中，这意味着它们作为一个单元协同工作，共享相同的线程组 ID (TGID)。

作用：

和fork一样也是用于创建当前进程的一个新进程（也可以创建线程），但更佳灵活，可以更精细地控制新进程的行为和父进程的资源共享方式,关键就在flag的组合

pipe()

函数定义

1
2
#include <unistd.h>
int pipe(int pipefd[2]);//创建管道

参数

  • pipefd：这是一个包含两个整数的数组。pipefd[0] 是用于读取的文件描述符，pipefd[1] 是用于写入的文件描述符。

返回值

  • 成功时返回 0。
  • 失败时返回 -1，并设置 errno 以指示错误。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//chatgpt生成

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
int main() {
    int pipefd[2];
    pid_t cpid;
    char buf;

    // 创建管道
    if (pipe(pipefd) == -1) {
        perror("pipe");
        exit(EXIT_FAILURE);
    }

    // 创建子进程
    cpid = fork();
    if (cpid == -1) {
        perror("fork");
        exit(EXIT_FAILURE);
    }

    if (cpid == 0) {    // 子进程
        close(pipefd[1]);  // 关闭写端

        // 从管道读取数据并输出到标准输出
        while (read(pipefd[0], &buf, 1) > 0) {
            write(STDOUT_FILENO, &buf, 1);
        }

        close(pipefd[0]);
        _exit(EXIT_SUCCESS);

    } else {            // 父进程
        close(pipefd[0]);  // 关闭读端

        // 向管道写入数据
        write(pipefd[1], "Hello from parent\n", 18);
        
        close(pipefd[1]);  // 关闭写端
        wait(NULL);        // 等待子进程结束
        exit(EXIT_SUCCESS);
    }
}

管道是单向的

作用：实现父进程与子进程之间的简单通信

sem_wait()

P操作

1
2
#include <semaphore.h>
int sem_wait(sem_t *sem);

参数

  • sem：指向信号量对象的指针。

返回值

  • 成功时返回 0。
  • 失败时返回 -1，并设置 errno 以指示错误。

功能

  • 如果信号量的值大于0，sem_wait 将信号量的值减1并立即返回。
  • 如果信号量的值为0，sem_wait 将阻塞，直到信号量的值大于0。

**sem_post() **

V操作

1
2
#include <semaphore.h>
int sem_post(sem_t *sem);

参数

  • sem：指向信号量对象的指针。

返回值

  • 成功时返回 0。
  • 失败时返回 -1，并设置 errno 以指示错误。

功能

  • 将信号量的值增加1。如果有其他进程或线程在等待这个信号量，sem_post 会唤醒其中一个等待者。

sem_init()

初始化信号量

1
2
#include <semaphore.h>
int sem_init(sem_t *sem, int pshared, unsigned int value);

参数

  1. sem：指向信号量对象的指针。

  2. pshared

    ：指定信号量是否在进程间共享。

    • 0：信号量用于进程内的线程同步。
    • 非零值：信号量在进程间共享。

  3. value：信号量的初始值。通常表示资源的初始数量。

返回值

  • 0：成功。
  • -1：失败，并设置 errno 以指示错误。

pthread_mutex_lock()

用于实现互斥锁。互斥锁是一种用于线程间同步的机制，它可以确保在任何时候只有一个线程能够访问共享资源，从而防止竞态条件的发生。

函数定义

1
2
#include <pthread.h>
int pthread_mutex_lock(pthread_mutex_t *mutex);

参数

  • mutex：一个指向互斥锁对象的指针，用于对其进行加锁操作。

返回值

  • 若成功，返回0。
  • 若失败，返回一个非零的错误码，表示出现了错误。

作用

  • pthread_mutex_lock() 用于尝试对指定的互斥锁进行加锁操作。
  • 如果互斥锁已经被其他线程锁定，调用线程将会被阻塞，直到该互斥锁可用为止。
  • 如果当前线程已经持有了该互斥锁，再次调用 pthread_mutex_lock() 会导致死锁

pthread_mutex_unlock()

用于释放互斥锁的函数之一

函数定义

1
2
#include <pthread.h>
int pthread_mutex_unlock(pthread_mutex_t *mutex);

参数

  • mutex：一个指向互斥锁对象的指针，用于对其进行解锁操作。

返回值

  • 若成功，返回0。
  • 若失败，返回一个非零的错误码，表示出现了错误。

作用

  • pthread_mutex_unlock() 用于释放指定的互斥锁。
  • 当一个线程拥有互斥锁时，调用 pthread_mutex_unlock() 可以将该互斥锁释放，以允许其他线程访问受保护的临界区。

确保每次 pthread_mutex_unlock() 都是由之前成功调用的 pthread_mutex_lock() 进行匹配，避免出现死锁等问题。

pthread_mutex_init

用于初始化互斥锁的函数。在使用互斥锁之前，需要通过该函数对互斥锁进行初始化。

函数定义

1
2
#include <pthread.h>
int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr);

参数

  • mutex：指向要初始化的互斥锁对象的指针。
  • attr：指向包含互斥锁属性的指针，通常设置为 NULL，表示使用默认属性。

返回值

  • 若成功，返回0。
  • 若失败，返回一个非零的错误码，表示出现了错误。

生产者消费者问题

生产者消费者问题（英语：Producer-consumer problem），也称有限缓冲问题（Bounded-buffer problem），是一个多进程同步问题的经典案例。该问题描述了共享固定大小缓冲区的两个进程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。

要解决该问题，就必须让生产者在缓冲区满时休眠（要么干脆就放弃数据），等到下次消费者消耗缓冲区中的数据的时候，生产者才能被唤醒，开始往缓冲区添加数据。同样，也可以让消费者在缓冲区空时进入休眠，等到生产者往缓冲区添加数据之后，再唤醒消费者。通常采用进程间通信的方法解决该问题，常用的方法有信号灯法[1]等。如果解决方法不够完善，则容易出现死锁的情况。出现死锁时，两个线程都会陷入休眠，等待对方唤醒自己。该问题也能被推广到多个生产者和消费者的情形。

----维基百科

代码1

使用了pipe函数 frok函数实现生产者消费者问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <semaphore.h>
#include <string.h>


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

char r_buf[4],w_buf[4];
int pipfd[2];
pid_t pid_p1,pid_p2,pid_c1,pid_c2;

int main()
{
	
	if(pipe(pipfd)==-1)
	{
		printf("管道创建失败！\n");
		return 0;
	}
	else
	{
		printf("管道创建成功！\n");
		
	
		if(pid_p1=fork()==0)// 子进程
			producer(1);
		if(pid_p2=fork()==0)//子进程
			producer(2);
		if(pid_c1=fork()==0)//子进程
			consumer(1);
		 if(pid_c2=fork()==0)//子进程
			consumer(2);
	} 
	
	close(pipfd[0]),close(pipfd[1]);
	int status,pid,i;
	for(i=1;i<=4;i++)//等待子进程结束
		pid=wait(&status); 
	return 0;
}
int producer(int id)
{
	int i;
	printf("生产者 %d ing ing\n",id) ;
	close(pipfd[0]);//关闭读
	for( i=1;i<=5;i++)
	{
		printf("producer %d 's %dth\n",id,i);
		if(id==1)//生产者1号
			{
				strcpy(w_buf,"p1\0");
			}
		else
			{
				strcpy(w_buf,"p2\0");
			}
		if(write(pipfd[1],w_buf,4)==-1)
			printf("生产者写入管道失败!\n");
		else
			printf("producer %d write %s\n",id,w_buf);
	}
	close(pipfd[1]);//关闭写 
	printf("生产者 %d 结束！\n",id);
	exit(id);
}
int consumer(int id)
{
	printf("消费者 %d inging...\n",id);
	close(pipfd[1]);

	while(1)
	{
		sleep(1);
		if(read(pipfd[0],r_buf,4)==0)
		 break;//读完了
		printf("消费者 %d 得到了 %s\n",id,r_buf) ;
	}
	close(pipfd[0]);
	printf("消费者%d 结束了\n",id);
	exit(id);
}

输出1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
管道创建成功！
消费者 2 inging...
生产者 1 ing ing
producer 1 's 1th
producer 1 write p1
producer 1 's 2th
producer 1 write p1
producer 1 's 3th
producer 1 write p1
producer 1 's 4th
producer 1 write p1
producer 1 's 5th
producer 1 write p1
生产者 1 结束！
生产者 2 ing ing
producer 2 's 1th
producer 2 write p2
producer 2 's 2th
producer 2 write p2
producer 2 's 3th
producer 2 write p2
producer 2 's 4th
producer 2 write p2
producer 2 's 5th
producer 2 write p2
生产者 2 结束！
消费者 1 inging...
消费者 2 得到了 p1
消费者 1 得到了 p1
消费者 2 得到了 p1
消费者 1 得到了 p1
消费者 2 得到了 p1
消费者 1 得到了 p2
消费者 2 得到了 p2
消费者 1 得到了 p2
消费者 2 得到了 p2
消费者 1 得到了 p2
消费者2 结束了
消费者1 结束了

代码2

使用clone函数通过信号量和互斥锁实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#define _GNU_SOURCE
#include <sched.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
#include <string.h>
#include <sys/wait.h>
#include <errno.h>

int  producer(void* args);
int  consumer(void* args);
pid_t pid_p[2],pid_c[2];//p1,p2,c1,c2
pthread_mutex_t mutex;
sem_t products,empty;
char buf[8][4];
int buf_size=8,top=-1;
int main()
{
	 pthread_mutex_init(&mutex,NULL);
	 sem_init(&products,0,0);
	 sem_init(&empty,0,8);
	 
	 int i=0,flag=CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND| SIGCHLD;
    //一定要加上SIGCHLD

	 for( i=0;i<=1;i++)
	{
		int*id=malloc(sizeof (int));
		 *(id)=i+1;
		char* stack = (char*)malloc(4096);
		pid_p[i] = clone(producer, stack + 4095, flag, id);
        	if (pid_p[i] == -1) 
		{
           		printf("Failed to create producer process!\n");
            	exit(1);
       		 }
        	printf("producer %d is created!\n", *id);
	}
	
	for ( i=0;i<=1;i++)
	{
		int*id=malloc(sizeof (int)); *(id)=i+1;
		char* stack= (char*)malloc(4096);
		pid_c[i]=clone(consumer,stack+4095,flag,id);
		if (pid_p[i] == -1) 
		{
           		printf("Failed to create consumer process!\n");
            	exit(1);
       		 }
		printf("consumer %d is created!\n",*id);
	}
	

	int status=0,pid;
    //一定要写这个 否则父进程会先于子进程结束
	for(i=1;i<=4;i++)
		pid=wait(&status);
    //销毁锁和信号量
	pthread_mutex_destroy(&mutex);
	sem_destroy(&products);
	sem_destroy(&empty);
	return 0;
 
}

int producer(void* args)
{
	int i=0,id=0;
	printf("producer %d is running!\n",id=*((int*)args));
	
	for( i=1;i<=10;i++)
	{
		
	  sleep(i);
	  sem_wait(&empty);
	  pthread_mutex_lock(&mutex);
	  top=top+1;
	  if(id==1)
	    strcpy(buf[top],"p1\0");
	  else
	     strcpy(buf[top],"p2\0");
	  
	  

	  printf("producer %d put %s into buf[%d]\n",id,buf[top],top);

	  pthread_mutex_unlock(&mutex);
	  sem_post(&products);
	 
	}
	printf("producer %d is deaded\n",id);
	return 0;
}
int consumer(void* args)
{
	int i=0,id=*((int*)args);
	printf("consumer %d is running!\n",id);
	for( i=1;i<=10;i++)
	{
	sleep(10-i);
	
	sem_wait(&products);
	pthread_mutex_lock(&mutex);

	printf("consumer %d gets %s from buf[%d]\n",id,buf[top],top);
	top--;
	
	pthread_mutex_unlock(&mutex);
	sem_post(&empty);

	}
	printf("consumer %d is deaded\n",id);
	return 0;
}

为什么需要 SIGCHLD

  • 通知机制：SIGCHLD 信号用于通知父进程其子进程已经终止。这允许父进程通过 wait 或 waitpid 函数来获取子进程的终止状态，并进行相应的处理。
  • 避免僵尸进程：当子进程终止时，如果父进程没有使用 wait 或 waitpid 获取子进程的终止状态，子进程会变成僵尸进程。SIGCHLD 信号可以触发父进程调用这些函数，从而防止僵尸进程的产生。

为什么要在主函数最后写wait

1. 避免僵尸进程

  • 当一个子进程终止时，它不会立即被完全清除。子进程的终止状态（如退出代码等）仍然保留在系统中，直到父进程调用 wait 或 waitpid 函数来获取这个状态。
  • 如果父进程没有调用 wait 或 waitpid，这些终止的子进程会变成僵尸进程，占用系统资源。通过调用 wait 或 waitpid，父进程可以清理这些子进程，释放相关的资源。

2. 同步父子进程

  • 使用 wait 或 waitpid 可以确保父进程在继续执行之前等待子进程完成。这对于确保所有子进程执行完毕并且所有资源都被正确释放是必要的。
  • 这也可以防止父进程在所有子进程完成之前退出，从而保证所有任务都能正确执行完毕。

3. 获取子进程的退出状态

  • wait 或 waitpid 可以让父进程获取子进程的退出状态，这对于调试、日志记录或者根据子进程的执行结果采取相应的措施非常重要。

输出2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
producer 1 is created!
producer 2 is created!
consumer 1 is created!
consumer 2 is created!
consumer 2 is running!
producer 1 is running!
producer 2 is running!
consumer 1 is running!
producer 1 put p1 into buf[0]
producer 2 put p2 into buf[1]
producer 1 put p1 into buf[2]
producer 2 put p2 into buf[3]
producer 1 put p1 into buf[4]
producer 2 put p2 into buf[5]
consumer 2 gets p2 from buf[5]
consumer 1 gets p1 from buf[4]
producer 1 put p1 into buf[4]
producer 2 put p2 into buf[5]
producer 1 put p1 into buf[6]
producer 2 put p2 into buf[7]
consumer 2 gets p2 from buf[7]
consumer 1 gets p1 from buf[6]
producer 1 put p1 into buf[6]
producer 2 put p2 into buf[7]
consumer 2 gets p2 from buf[7]
consumer 1 gets p1 from buf[6]
producer 1 put p1 into buf[6]
producer 2 put p2 into buf[7]
consumer 2 gets p2 from buf[7]
consumer 1 gets p1 from buf[6]
consumer 2 gets p2 from buf[5]
consumer 1 gets p1 from buf[4]
producer 1 put p1 into buf[4]
producer 2 put p2 into buf[5]
consumer 2 gets p2 from buf[5]
consumer 1 gets p1 from buf[4]
consumer 2 gets p2 from buf[3]
consumer 1 gets p1 from buf[2]
consumer 2 gets p2 from buf[1]
consumer 1 gets p1 from buf[0]
producer 1 put p1 into buf[0]
producer 2 put p2 into buf[1]
consumer 1 gets p2 from buf[1]
consumer 1 gets p1 from buf[0]
consumer 1 is deaded
producer 1 put p1 into buf[0]
producer 1 is deaded
producer 2 put p2 into buf[1]
producer 2 is deaded
consumer 2 gets p2 from buf[1]
consumer 2 gets p1 from buf[0]
consumer 2 is deaded

拓展

shm

msg

实验二：处理机调度——实时调度算法EDF和RMS

实验内容

在Linux环境中采用用户级线程模拟实现EDF和RMS两种实时调度算法。给定一组实时任务，按照EDF算法和RMS算法分别判断是否可调度，在可调度的情况下，创建一组用户级线程，分别代表各个实时任务，并按算法确定的调度次序安排各个线程运行，运行时在终端上画出其Gantt图。为避免图形绘制冲淡算法，Gantt图可用字符表示。

前置知识

EDF算法

EDF算法（Earliest Deadline First）是一种实时任务调度算法，它的核心思想是优先调度最紧迫的任务，即 将截止时间最早的任务优先分配处理器时间片。EDF算法适用于实时系统，其中任务有明确的截止时间，并且必须在截止时间之前完成。

调度规则

  • 系统在每个时刻会检查所有已到达但未完成的任务，并选择截止期限最早的任务进行执行。
  • 如果新的任务到达且其截止期限早于当前正在执行的任务，系统会进行任务切换，将新的任务置于当前任务之前执行。

特点

  1. 最优性：
    • EDF算法在理想条件下（如任务可抢占、无上下文切换开销、系统负载不超过100%）是最优的单处理器实时调度算法。这意味着，如果有一种方法能按时完成所有任务，EDF就能做到这一点。
  2. 动态优先级：
    • 任务的优先级是动态的，随着时间的推移和新任务的到来而变化。
  3. 简单性：
    • 实现相对简单，只需维护一个任务列表，并在任务到达或完成时更新列表排序。
  4. 可抢先性调度算法

优点

  • 高效性：在可抢占的环境中，EDF能够高效地利用处理器资源，最大限度地减少任务的等待时间。
  • 灵活性：适用于不同类型的任务，包括周期性任务和单次任务。

缺点

  • 开销问题：频繁的任务切换和排序操作可能带来一定的开销，尤其是在任务数量较多时。
  • 负载限制：在系统负载接近或超过100%时，EDF可能会无法确保所有任务都能按时完成，这时需要其他机制来处理超载情况。

例子

假设有三个任务，它们的执行时间和截止期限如下：

  • 任务A：执行时间为2，截止期限为4
  • 任务B：执行时间为1，截止期限为3
  • 任务C：执行时间为2，截止期限为5

任务按照以下顺序到达：A、B、C

  1. 系统开始执行任务A，因为此时只有任务A在队列中。
  2. 任务B到达，截止期限比任务A早，因此系统切换到任务B。
  3. 任务B完成后系统继续执行任务A。
  4. 任务C到达，但任务A仍然是最早截止的任务，因此系统继续执行任务A。
  5. 任务A完成后系统执行任务C。

通过上述例子可以看出，EDF算法始终选择最紧急的任务来执行，从而尽量保证所有任务都能按时完成。

总的来说，Earliest Deadline First算法是实时系统中非常重要的一种调度策略，广泛应用于需要高实时性和确定性的领域。

调度条件

∑(CiTi)≤1\sum(\frac{C_{i}}{T_{i}})\leq1

Ci是任务i需要的工作时间，Ti是任务i的周期， 该条件表明任务系统的总CPU利用率不超过100%。

RMS算法

Rate Monotonic Scheduling (RMS) 是一种用于实时系统的优先级调度算法，主要用于调度周期性任务。它是一种固定优先级（static priority）的调度算法，每个任务的优先级在系统运行期间保持不变。

调度规则

  • 任务的优先级是根据其周期来确定的：周期越短，优先级越高。

特点

  1. 固定优先级：
    • 任务的优先级在整个系统运行期间保持不变，这与动态优先级调度算法（如EDF）不同。
  2. 周期性任务优化：
    • RMS专门针对周期性任务进行优化，确保周期性任务能够在其周期内按时完成。
  3. 理论基础：
    • RMS有严格的数学证明支持，证明了在某些条件下，RMS是最优的固定优先级调度算法。
  4. 不可抢先性调度算法。

优点

  • 简单性：由于优先级是固定的，实现起来相对简单。
  • 可预测性：固定优先级使得任务调度行为易于预测和分析。
  • 理论保证：对于周期性任务，RMS具有良好的理论基础和最优性保证。

缺点

  • 利用率限制：RMS在任务的总CPU利用率达到一定限度时，可能无法保证所有任务都能按时完成。具体来说，对于 nnn 个任务的系统，最大CPU利用率上限为 Umax=n(21/n−1)U_{max} = n(2^{1/n} - 1)Umax=n(21/n−1)。当任务数增加时，这个上限趋近于 ln⁡(2)≈0.693\ln(2) \approx 0.693ln(2)≈0.693 或者 69.3%。
  • 不适合非周期性任务：RMS主要针对周期性任务，非周期性任务可能无法得到有效调度。

例子

假设有三个任务，它们的执行时间和周期如下：

  • 任务A：执行时间 CA=1C_A = 1CA=1，周期 PA=4P_A = 4PA=4
  • 任务B：执行时间 CB=1C_B = 1CB=1，周期 PB=5P_B = 5PB=5
  • 任务C：执行时间 CC=2C_C = 2CC=2，周期 PC=8P_C = 8PC=8

根据RMS规则，任务的优先级顺序为：A > B > C（周期越短，优先级越高）。

调度过程：

  1. 从时间0开始，任务A、B、C均到达。由于A优先级最高，执行任务A。
  2. 时间1，任务A完成，执行任务B（下一个优先级最高的任务）。
  3. 时间2，任务B完成，执行任务C。
  4. 时间4，任务A的下一个周期到来，打断任务C，执行任务A。
  5. 时间5，继续执行任务C。
  6. 时间8，任务A和B的下一个周期同时到来，首先执行任务A，然后执行任务B，任务C被打断。

通过上述例子可以看出，RMS算法总是优先执行周期最短的任务，确保高优先级任务按时完成。

调度条件

∑(CiTi)≤n(21n−1)\sum(\frac{C_{i}}{T_{i}})\leq n(2^{\frac{1}{n}}-1)

这里 n 是任务的数量。这个条件表明任务系统的总CPU利用率的上限随着任务数量的增加而变化，并且随着任务数量的增加，这个上限趋近 69.3%。

RMS与EDF对比

  • 优先级类型：RMS使用固定优先级，EDF使用动态优先级。
  • 适用任务：RMS适用于周期性任务，EDF适用于周期性和非周期性任务。
  • CPU利用率：EDF在理想条件下可以实现100%的CPU利用率，而RMS的利用率上限为69.3%（对于较多任务）。

pthread_create()

pthread_create 是 POSIX 线程库 (pthread) 中的一个函数，用于创建一个新的线程。这个函数是多线程编程的基础之一，允许程序在并发执行中创建和管理多个线程。

函数定义

1
int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void *), void *arg);

参数详解

  1. pthread_t *thread:
    • 这是一个指向 pthread_t 类型变量的指针。这个变量将保存新创建线程的 ID（线程句柄），用于后续对该线程的操作（如等待线程结束、取消线程等）。
  2. const pthread_attr_t *attr:
    • 这是一个指向线程属性对象的指针，用于设置新线程的属性。如果传递 NULL，则使用默认属性。
    • 线程属性可以包括堆栈大小、调度策略、优先级等。属性对象通过 pthread_attr_init、pthread_attr_set* 和 pthread_attr_destroy 函数进行管理。
  3. void *(*start_routine)(void *):
    • 这是一个函数指针，指向新线程的起始例程（函数）。新线程开始时将执行这个函数。
    • 这个函数必须符合特定的签名，即接收一个 void * 类型的参数并返回一个 void * 类型的值。
  4. void *arg:
    • 这是传递给 start_routine 函数的参数。可以传递任意类型的数据，但必须通过 void * 进行类型转换。
    • 如果不需要传递参数，可以传递 NULL。

返回值

  • 成功时，pthread_create 返回 0。
  • 失败时，返回一个非零的错误代码，表示失败原因，如 EAGAIN（资源临时不可用）、EINVAL（无效的属性设置）或 EPERM（无权限设置指定的属性）。

特点

  • 共享地址空间：线程之间共享相同的地址空间（全局变量、堆等）。
  • 轻量级：线程的创建和销毁比进程开销小。
  • 并发执行：多个线程可以并发执行，提高性能。
  • 同步机制：需要使用同步机制（如互斥锁、条件变量）来防止共享资源竞争。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <sched.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
 

typedef struct 
{
  char task_id;//任务id
  int call_num;//发生次数
  int c_left;//剩余工作时间
  int t_left;//剩余周期时间
  int c;// 工作时间
  int t; //周期
  int flag;//状态 1活跃 2不活跃
  int arg;//参数
  pthread_t th;//对应线程
} task;

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

int task_num=0,idle_num=0;
int choice;//1 is EDF 2 is RMS
int curr_proc=-1;
int demo_time=100;
task* tasks;
pthread_mutex_t proc_wait[100];//每个任务对应一个等待互斥锁
pthread_mutex_t main_wait,idle_wait;//main  闲逛进程

float sum=0;

pthread_t idle_proc;
int main()
{
    //初始化互斥锁
    pthread_mutex_init(&main_wait,NULL);
    pthread_mutex_lock(&main_wait);
    pthread_mutex_init(&idle_wait,NULL);
    pthread_mutex_lock(&idle_wait);
    
    //读入任务
    
    printf("有多少任务：\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("输入任务id C和T\n");
	    getchar();//一定要写
        scanf("%c %d %d",&tasks[i].task_id,&tasks[i].c,&tasks[i].t);
        tasks[i].c_left=tasks[i].c;
        tasks[i].t_left=tasks[i].t;
        tasks[i].flag=2;
        tasks[i].arg=i;
        tasks[i].call_num=1;
        sum+=(float)tasks[i].c/(float)tasks[i].t;
    }
    //选择调度 判断是否满足条件
    
    printf("用什么调度1.EDF 2.RMS\n");
    scanf("%d",&choice);
    printf("想要运行多长时间\n");
    scanf("%d",&demo_time);
    double r=1;//EDF 为1
    if(choice==2)
    {
        r=((double)task_num)*(exp(log(2)/(double)task_num)-1);
        printf("r = %f\n",r);
    }
    if(sum>r)
    {
        printf("不满足条件，不能调度\n");
        exit(2);
    }
    // 创建闲逛进程
    pthread_create(&idle_proc,NULL,(void*)idle,NULL);
    // 创建实时任务线程
    for(i=0;i<task_num;i++) 
        pthread_create(&tasks[i].th,NULL,proc,(void*)&tasks[i].arg);
        
    //运行
    for(i=0;i<demo_time;i++)
    {
        int j;
        //选择线程
        if((curr_proc=select_proc(choice))!=-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++)//执行完一个时间片 更新剩余周期时间
        {
            tasks[j].t_left--;
            if(tasks[j].t_left==0)//周期到了 又来了一个
            {
                tasks[j].t_left=tasks[j].t;
	            tasks[j].c_left=tasks[j].c;
	            pthread_create(&tasks[j].th,NULL,(void*)proc,&tasks[j].arg);
                tasks[j].flag=2;
            }
        }
    }
    printf("\n");
    sleep(10);
    
}
void* proc(void* a)
{
   int* args=(int*)a;
    while(tasks[*args].c_left>0)
    {
        pthread_mutex_lock(&proc_wait[*args]);
        if(idle_num!=0)
        {
            printf("idle:%d\n",idle_num);
            idle_num=0;
        }
        printf("%c is running,已被调用%d 次\n",tasks[*args].task_id,tasks[*args].call_num);
        tasks[*args].c_left--;//剩余执行减一
        
        if(tasks[*args].c_left==0)//执行完了
        {
            printf("task %c over(it's work time is%d)\n",tasks[*args].task_id,tasks[*args].c);
            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 choice)
{
    if(choice==2&&curr_proc!=-1&&tasks[curr_proc].flag!=0)
    {
        return curr_proc;// RMS算法的优先级不会发生改变
    }
    int j,tmp1=1000,index=-1;
    for(j=0;j<task_num;j++)
    {
        if(tasks[j].flag==2)//当前任务活跃
        {
            if(choice==1)//EDF
            {
                if(tmp1>tasks[j].c_left) 
                    {
                        tmp1=tasks[j].c_left;
                        index=j;
                    }
            }
            else//RMS
            {
                if(tmp1>tasks[j].t)
                {
                    tmp1=tasks[j].t;
                    index=j;
                }
            }
        }
    }
    return index;
}

tips：
编译的时候要加上-pthread -lm选项

实验三：存储管理——动态不等长存储资源分配算法

实验内容

•分析UNIX最先适应(FF)存储分配算法，即map数据结构、存储分配函数malloc()和存储释放函数mfree()，找出与算法有关的成分。

• 修改上述与算法有关的成分，使其分别体现BF分配原则和WF分配原则。

前置知识

最先适应存储分配算法

工作原理：

  1. 维护空闲内存块：操作系统维护一个空闲内存块的链表（或其他数据结构）（ 按地址由低到高排列），这些内存块表示可用的内存空间。
  2. 按顺序查找：当有进程需要分配内存时，从链表的开始位置按顺序查找，寻找第一个能够满足该进程所需大小的空闲内存块。
  3. 分配内存：找到合适的内存块后，将这块内存分配给进程。如果空闲内存块大于所需大小，则将该块分割成两部分，一部分分配给进程，另一部分继续作为空闲内存块保留在链表中。
  4. 更新链表：分配完成后，更新空闲内存块链表。

优点：

  • 简单易实现：最先适应算法实现简单，遍历链表寻找合适的空闲块即可。
  • 较低的开销：由于从头开始查找第一个符合要求的块，通常能快速找到适合的内存块。

缺点：

  • 外部碎片化：长期运行后，系统会出现大量的小而零散的空闲块，导致无法有效利用内存。
  • 非最佳选择：最先适应算法可能不会总是选择最优的内存块，例如选择一个较大的块来满足小需求，从而留下更多的内存碎片。

最佳分配算法

工作原理

  1. 维护空闲块列表：操作系统维护一个空闲内存块的链表（或其他数据结构）（按照容量递增的次序排列）。
  2. 查找合适的块：当有内存分配请求时，遍历整个空闲块列表，找到能满足请求的最小块。
  3. 分割和分配：如果找到的空闲块比请求的大小大，进行分割；否则直接分配整个块。
  4. 更新空闲块列表：分配后更新空闲块列表，确保空闲块的管理和跟踪。

优点

  • 减少碎片：由于选择最小的能满足请求的块，最佳分配算法往往能减少内存碎片。
  • 高效利用内存：优化内存块的利用率，提高内存分配的效率。

缺点

  • 时间复杂度高：每次分配内存时都需要遍历整个空闲块列表，时间复杂度较高。
  • 维护复杂：需要频繁维护和更新空闲块列表，管理复杂度较高。

最坏分配算法

工作原理

  1. 维护空闲块列表：操作系统维护一个空闲内存块的链表或其他数据结构（按照容量由高到低排列）。
  2. 查找最大的块：当有内存分配请求时，遍历整个空闲块列表，找到最大的空闲块。
  3. 分割和分配：如果找到的空闲块比请求的大小大，进行分割；否则直接分配整个块。
  4. 更新空闲块列表：分配后更新空闲块列表，确保空闲块的管理和跟踪。

优点

  • 减少外部碎片：最坏分配算法通过分割最大的块来避免产生许多小块，从而减少外部碎片的数量。
  • 简单实现：该算法易于实现，因为只需找到最大的块进行分配。

缺点

  • 时间复杂度高：每次分配内存时都需要遍历整个空闲块列表以找到最大的块，时间复杂度较高。
  • 可能导致大的块被频繁分割：这可能导致大块内存变得稀缺，对于需要大块内存的请求来说可能会变得困难。

malloc()

malloc函数用于在堆上动态分配指定大小的内存块，并返回指向该内存块的指针。

原型

1
void *malloc(size_t size);

参数

  • size: 要分配的内存块的大小（以字节为单位）。

返回值

  • 成功时：返回指向分配内存块的指针。
  • 失败时：返回NULL，表示内存分配失败（例如内存不足）。

free()

free函数用于释放之前由malloc、calloc或realloc函数分配的内存块，避免内存泄漏。

原型

1
void free(void *ptr);

参数

  • ptr: 指向要释放的内存块的指针。如果ptr为NULL，则free函数什么也不做。

返回值

  • 无返回值。

*register

在C语言中，register关键字用于提示编译器将变量尽量存储在处理器的寄存器中，而不是在内存中。这样可以提高变量的访问速度，因为寄存器比内存访问速度快得多。需要注意的是，这只是一个建议，最终是否将变量存储在寄存器中取决于编译器。

语法

1
register int counter;

示例

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
int main() {
    register int i;
    int sum = 0;

    for (i = 0; i < 1000000; i++) {
        sum += i;
    }

    printf("Sum: %d\n", sum);
    return 0;
}

tips

  1. 仅用于自动变量：register关键字只能用于自动变量（局部变量）和函数参数。全局变量和静态变量不能使用register关键字。

  2. 限制数量：由于寄存器数量有限，不可能所有的register变量都被存储在寄存器中。编译器会根据寄存器的使用情况决定是否将变量存储在寄存器中。

  3. 无法获取地址

    由于寄存器可能不在内存中，因此不能对register变量使用取地址运算符（&），即不能获取register变量的地址。

    1
    2
    register int counter;
    int *ptr = &counter;  // 错误：无法获取register变量的地址

  4. 现代编译器优化：现代编译器已经具备非常先进的优化技术，能够自动选择哪些变量应该放在寄存器中。因此，在大多数情况下，不需要显式使用register关键字。编译器通常会比手动指定做得更好。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
#include<stdio.h>
#include<stdlib.h>
#define MAPSIZE 100

struct MAP//存储资源表项
{
	int addr;//起始地址
	int map_size; //
};
struct MAP map[MAPSIZE];//
int num=0;
char alg;

void init();
int BF_distru(int apply_size);
int WF_distru(int apply_size);
void mfree(int addr,int rsize);
void show();

int main()
{
	init();
	printf("b is BF,w is WF:\n");
	getchar();
	scanf("%c",&alg);
	while(1)
	{
		printf("1代表申请，2代表释放，0代表退出：\n");
		int option;
		scanf("%d",&option);
		if(option==0) exit(0);
		else if(option==1)
		{
			printf("你想申请多大的空间：\n");
			int apply_size,res;
			scanf("%d",&apply_size);
			if(alg=='b') res=BF_distru(apply_size);
			else res=WF_distru(apply_size);
			if(res==-1) printf("空间不足，申请失败!\n");
			else printf("申请成功，起始地址为%d 大小为%d \n",res,apply_size);
		}
		else
		{
			printf("你想释放空间的起始地址和大小：\n");
			int addr,rsize;
			scanf("%d%d",&addr,&rsize);
			mfree(addr,rsize);
		}
		show();
			
	}
}
void init()
{
	int addr,_size,i=0;
	printf("starting address and total size: \n");
	scanf("%d%d",&addr,&_size);
	map[0].addr=addr;
	map[0].map_size=_size;
	map[1].map_size=0;
	num=1;
}

int BF_distru(int apply_size)//找最小空闲分配，更新表，按容量递增排序
{
	int i=0,addr=-1;
	for(i=0;i<num;i++)
	{
		if(map[i].map_size>=apply_size)
			{
				addr=map[i].addr;
				map[i].addr+=apply_size;
				map[i].map_size-=apply_size;
				if(map[i].map_size==0)
				{
					num--;
					int j=i+1;
					for(i=i+1;j<num;j++) map[j-1]=map[j];
				}
				else
				{	
					int j=i-1;
					for(j=i-1;j>=0;j--)
					{
						if(map[j].map_size>map[i].map_size) 
						{
							struct MAP tmp;
							tmp=map[j]; map[j]=map[i];map[i]=tmp;
						}
					}
				}
				return addr;
			}
	}
	return addr;

}
int WF_distru(int apply_size)
{
	int i=0,addr=-1; 
	if(map[0].map_size<apply_size) return -1;
	for( i=0;i<num;i++)
	{
		if(map[i].map_size>=apply_size)
		{
				addr=map[i].addr;
				map[i].addr+=apply_size;
				map[i].map_size-=apply_size;
				if(map[i].map_size==0)
				{
					num--;
					int j=i+1;
					for(i=i+1;j<num;j++) map[j-1]=map[j];
				}
				else
				{	
					int j=i+1;
					for(j=i+1;j<num;j++)
					{
						if(map[j].map_size>map[i].map_size) 
						{
							struct MAP tmp;
							tmp=map[j]; map[j]=map[i];map[i]=tmp;
						}
					}
				}
				return addr;
		}
	}
	return addr;
}
void mfree(int addr,int rsize)
{
	int i=0,flag=0;
	for(i=0;i<num;i++)
	{
		if(map[i].addr+map[i].map_size==addr)//upper
		{
			map[i].map_size+=rsize;
			flag=1;
		}
		if(map[i].addr-rsize==addr)//lower
		{
			map[i].map_size+=rsize;
			map[i].addr=addr;	
			flag=1;
		}
		if(flag)
		{
			int j=0;
			for(j;j<num;j++)
			{
				if(j!=i)
				{
					if(map[j].addr+map[j].map_size==map[i].addr) 
					{
						map[j].map_size+=map[i].map_size;
						int k=i+1;
						for(k;k<num;k++) map[k-1]=map[k];
						num--;
						i=j;
						break;
					}
					if(map[i].addr+map[i].map_size==map[j].addr)
					{
						map[i].map_size+=map[j].map_size;
						int k=j+1;
						for(k;k<num;k++) map[k-1]=map[k];
						num--;
					}
				}

			}
			if(alg=='b')//BF
			{
				int j=i+1;
				for(j;j<num;j++)
				{
					if(map[j].map_size<map[i].map_size)
					{
						struct MAP tmp;
						tmp=map[j]; map[j]=map[i];map[i]=tmp;
						i=j;
					}
				}
			}
			else
			{
				int j=i-1;
				for(j;j>=0;j--)
				{
					if(map[j].map_size<map[i].map_size)
					{
						struct MAP tmp;
						tmp=map[j]; map[j]=map[i];map[i]=tmp;
						j=i;
					}
				}
			}
			return;
		}
	}
	num++;
	map[num-1].addr=addr;
	map[num-1].map_size=rsize;
	if(alg=='b')
	{
		int j=0;
		for(j;j<num;j++)
		{
			if(map[j].map_size>rsize) break;
		}
		if(j!=num)
		{
			int k=num-1;
			for(k;k>=j+1;k--) map[k]=map[k-1];
			map[j].addr=addr;
			map[j].map_size=rsize;
		}
	}
	else
	{
		int j=0;
		for(j;j<num;j++)
		{
			if(map[j].map_size<rsize) break;
		}
		if(j!=num)
		{
			int k=num-1;
			for(k;k>=j+1;k--) map[k]=map[k-1];
			map[j].addr=addr;
			map[j].map_size=rsize;
		}
	}
	return;
}

void show()
{
	int i=0;
	for(i=0;i<num;i++)
	{
		printf("<%d , %d>\n",map[i].addr,map[i].map_size);
	}
	return;
}