操作系统

操作系统 实验

01 进程管理

fork

创建子进程

1
2
pid_t pidA;
while((pidA=fork())==-1);

fork调用的一个奇妙之处就是它仅仅被调用一次，却能够返回两次，它可能有三种不同的返回值：

在父进程中，fork返回新创建子进程的进程ID；

  1. 在子进程中，fork返回0；
  2. 如果出现错误，fork返回一个负值；
1
2
3
pid_t fork(void)；//pid_t为int类型，进行了重载
pid_t getpid();// 获取当前进程的 pid 值。
pid_t getppid(); //获取当前进程的父进程 pid 值。

创建两子进程

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
#include<stdio.h>
#include<stdlib.h>
#include <unistd.h>
#include<sys/wait.h>
#include<sys/types.h>
#include<string.h>
#include<iostream>
#include<string>
int main(int argc,std::string str)
{
    pid_t pid1,pid2;
    while ((pid1=fork())==-1);
    if(pid1==0) //子进程1
    {

    }
    else
    {
        while ((pid2=fork())==-1);
        if(pid2==0)//子进程2
        {
        
        }
        else 
        {
        }
    }
    
    return 0;
}

vfork

fork vfork
子进程拷贝父进程的地址空间，子进程是父进程的一个复 子进程共享父进程的地址空间（准确来说，在调用 exec（进程替换） 或 exit（退出进程） 之前与父进程数据是共享的）
父子进程的执行次序不确定 保证子进程先运行,在它调用 exec（进程替换） 或 exit（退出进程）之后父进程才可能被调度运行。

需要搭配 exec 或者 _exit() 使用

可以用来统计一共有多少进程

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
#include<stdio.h>
#include<stdlib.h>
#include <unistd.h>
#include<sys/wait.h>
#include<sys/types.h>
#include<string.h>
int main(){
	signal(SIGCHLD,SIG_IGN);
	int num = 0; 
	pid_t pid1,pid2,pid3,pid4,pid5;
	while((pid1 = vfork()) == -1);
	if(pid1 == 0)
	{
		while((pid2=vfork())==-1);
		if(pid2 == 0)
		{
			wait(0);
			num++;
			printf("Dpid is %d , Dppid is %d\n",getpid(),getppid());
			_exit(0);
		}
		else
		{
			wait(0);
			num++;
			printf("Bpid is %d , Bppid is %d\n",getpid(),getppid());
			_exit(0);
		}
	}
	else
	{
		while((pid3=vfork())==-1);
		if(pid3 == 0)
		{
			while((pid4=vfork())==-1);
			if(pid4 == 0)
			{
				wait(0);
				num++;
				printf("Fpid is %d , Fppid is %d\n",getpid(),getppid());
				_exit(0); 
			}
			else
			{
				while((pid5=vfork())==-1);
				if(pid5 == 0)
				{
					wait(0);
					num++;
					printf("Epid is %d , Eppid is %d\n",getpid(),getppid());
					_exit(0);
				}
				else
				{
					wait(0);
					num++;
					printf("Cpid is %d , Cppid is %d\n",getpid(),getppid());
					_exit(0);
				}	
			}			
		}
		else
		{
			wait(0);
			printf("Apid is %d , Appid is %d\n",getpid(),getppid());
			printf("childnum is %d\n",num);			
		}
	}
}

execl

1
int execl(const char *path, const char *arg, ...);

execl()用来执行参数path字符串所代表的文件路径，接下来的参数代表执行该文件的参数argv[0],argv[1]…

最后一个参数必须是空指针NULL作为结束。

返回值：成功则不返回，执行失败则返回－1，失败原因在errno中。

pipe

进程创建管道，得到两个件描述符指向管道的两端

父进程fork出子进程，子进程也有两个文件描述符指向同管道。

父进程关闭fd[0],子进程关闭fd[1]，即子进程关闭管道读端,父进程关闭管道写端（因为管道只支持单向通信）。子进程可以往管道中写,父进程可以从管道中读,管道是由环形队列实现的,数据从写端流入从读端流出,这样就实现了进程间通信。

image-20230316200446335

管道创建

1
2
int fd[2];
int ret=pipe(fd);

失败返回-1

成功返回0

waitpid

1
pid_t waitpid(pid_t pid,int *status,int options)

pid>0时，只等待进程ID等于pid的子进程，不管其它已经有多少子进程运行结束退出了，只要指定的子进程还没有结束，waitpid就会一直等下去。
pid=-1时，等待任何一个子进程退出，没有任何限制，此时waitpid和wait的作用一模一样。
pid=0时，等待同一个进程组中的任何子进程，如果子进程已经加入了别的进程组，waitpid不会对它做任何理睬。
pid<-1时，等待一个指定进程组中的任何子进程，这个进程组的ID等于pid的绝对值。

创建进程并使用管道

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
#include<stdio.h>
#include<stdlib.h>
#include <unistd.h>
#include<sys/wait.h>
#include<sys/types.h>
#include<string.h>
#include<iostream>
#include<string>
#include<string.h>
const int MAXBUFFSIZE=1000;
int main()
{
    int fd[2];
    int ret=pipe(fd);
    char write_buff[1000];
    scanf("%s",write_buff);
    if(ret==-1)
    {
        std::cout<<"无法使用管道\n";
    }
    pid_t pid1,pid2;
    while ((pid1=fork())==-1);
    if(pid1==0)
    {            
        close(fd[0]);
        int len=strlen(write_buff);
        write(fd[1],write_buff,len+1);
        _exit(0);
    }
    else
    {
        while ((pid2=fork())==-1);
        if(pid2==0)
        {
            waitpid(pid1,NULL,WNOHANG);
            close(fd[1]);
            char read_buff[MAXBUFFSIZE];
            int len = read(fd[0], read_buff, MAXBUFFSIZE);

            execl("./output/encode",read_buff,NULL);
            _exit(0);
        }
        _exit(0);
    }
    
    return 0;
}

ps:

这边 值得注意的是

write 函数需要 的 size_t 参数 要+1

read 函数 的 size_t 参数 直接用数组的长度即可

02 进程调度

PCB

PCB：process ctrl block（进程控制块）在操作系统代码当中是一个结构体：struct task_struct{…}

如进程状态、进程ID、优先级、程序计数器、寄存器值、内存管理信息、打开文件列表等。PCB是操作系统对进程的抽象，它记录了进程在系统中的运行状态，是操作系统进行进程调度和管理的重要数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*本次实验模拟实现操作系统中进程调度算法,模拟进程在不同时刻到达的情况*/
#define PNUM  5 //进程的数量
#define TIMER 10 //定时器,最长CPU区间时间
#define SLICE 2//轮转算法的时间片
 int timenow=0;     //当前时刻
typedef struct node{
   int pid;   //进程号
   int priority;//进程优先级,1~3,数字越小优先级越高
   int arrival; //到达时间
   int burst;  //CPU区间时间
   int rest;  //剩余时间
   char state;//进程状态,'N'新建,'R'运行,'W'等待CPU(就绪),'T'终止
   struct node *next;
}PCB;
int gantt[TIMER*PNUM]={0}; //用一个gantt数组记录调度过程,每个时刻调度的进程号 

PCB *job;//所有作业的序列,带头节点(为简化编程)
PCB *ready=NULL; //进程就绪队列,不带头节点
PCB *tail=NULL;  //记录就绪队列的尾节点
PCB *run=NULL;//正在运行中的进程,不带头结点
PCB *finish=NULL;//已经结束的程序,不带头结点
PCB* temp=NULL;

SJF(最短作业优先，非抢占)

短作业优先调度算法

优点：考虑到作业的服务时间情况，降低了周转时间等相应时间；
缺点：有可能短进程一致插队，导致长进程处于长期饥饿状态；

FCFS(先来先服务)

FCFS 策略可以通过 FIFO 队列容易地实现。当一个进程进入就绪队列时，它的 PCB 会被链接到队列尾部。当 CPU 空闲时，它会分配给位于队列头部的进程，并且这个运行进程从队列中移去。FCFS 调度代码编写简单并且理解容易。

FCFS 策略的缺点是，平均等待时间往往很长。假设有如下一组进程，它们在时间 0 到达，CPU 执行长度按 ms 计：

image-20230321191906644

RR

时间片轮转（RR）调度算法是专门为分时系统设计的。它类似于 FCFS调度，但是增加了抢占以切换进程。

该算法中，将一个较小时间单元定义为时间量或时间片。时间片的大小通常为 10~100ms。就绪队列作为循环队列。CPU 调度程序循环整个就绪队列，为每个进程分配不超过一个时间片的 CPU。

为了实现 RR 调度，我们再次将就绪队列视为进程的 FIFO 队列。新进程添加到就绪队列的尾部。CPU 调度程序从就绪队列中选择第一个进程，将定时器设置在一个时间片后中断，最后分派这个进程。

初始化 以及 更新队列 显示队列

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
void InitialJob()
{   
    int i=0;
    PCB *p,*tail;
    job=(PCB *)malloc(sizeof(PCB));//生成头节点,其它域无意义
    job->next=NULL;
    tail=job;
    
 for(i=0;i<PNUM;i++)
 { p=(PCB *)malloc(sizeof(PCB));//生成新节点(新进程)
   p->pid=i+1;
   p->priority=rand()%3+1;//随机生成优先级:1~3
   p->arrival=rand()%TIMER;//随机生成到达时刻0-9,(预计到达就绪队列的时间) 
   p->burst=rand()%TIMER+1;//随机生成CPU区间时间:1~10;(估计运行时间)
   p->rest=p->burst;
   p->state='N';//初始化进程的状态为'新建'
   p->next=NULL; 
   tail->next=p; 
   tail=p;  //带头结点
  }
}
void DisplayPCB(PCB *pcb) //显示队列
{
  struct node *p=pcb;
  if(pcb==NULL) {printf("XXXXXX\n");return;}
  printf("进程号 优先级 到达时刻 区间时间 剩余时间 进程状态\n");
  do{
    printf("P%-3d\t",p->pid);
    printf("%3d\t",p->priority);
    printf("%3d\t",p->arrival);
    printf("%3d\t",p->burst);
	printf("%3d\t",p->rest);
	printf("%3c\t",p->state);
    printf("\n");
    p=p->next;
  }while(p!=NULL);   
}

void DisplayGantt() //显示甘特数组
{
  int i=0;
  for(i=0;i<timenow;i++)
  {
   if(gantt[i]==0) printf("空闲,");
   else
     printf("P%d,",gantt[i]);
  }
  printf("\n");
}

/*注:关于周转时间,等待时间与响应时间的概念释疑:
  在课程教材<操作系统概念第7版>中(P141),上述三个时间是从进程到达的时间开始的.
  在辅助教材<现代操作系统第4版>中(P89),上述三个时间时从进程提交的时刻(0时刻)开始的.
  国内普遍接受前一种理解,本程序以课程教材中的解释为准来计算时间.
*/
void DisplayTime() //显示周转时间t,等待时间w和响应时间r
{
    int t=0,w=0,r=0;
    float t_avg=0,w_avg=0,r_avg=0; 
    int i,j;
    PCB *p; //用p遍历finish队列,查找进程Pi的到达时间,调用该函数时所有进程都已放入finish队列
    if(finish==NULL) {return;}
    printf("进程号    周转时间    等待时间    响应时间\n");
    for(i=1;i<=PNUM;i++)
     { p=finish;
       while(p->pid!=i) p=p->next;
       j=0;
       while(gantt[j]!=i) j++; //遍历甘特数组,求进程Pi的响应时间
        r=j;  //响应时刻
        t=j+1;        
       for(j=r+1;j<timenow;j++) //继续遍历,求周转时间
       { if(i==gantt[j]) t=j+1;}//结束时刻
       r=r-p->arrival;  //响应时间=响应时刻-到达时刻
       t=t-p->arrival; //周转时间=结束时刻-到达时刻
       w=t-p->burst; //等待时间=周转时间-运行时间
       r_avg+=(float)r/PNUM; //平均响应时间
       w_avg+=(float)w/PNUM;  //平均等待时间
       t_avg+=(float)t/PNUM;   //平均周转时间
       
       printf("P%d       %4d       %4d       %4d\n",i,t,w,r);
     }
     printf("平均周转时间:%.2f,平均等待时间%.2f,平均响应时间%.2f\n",t_avg,w_avg,r_avg);
}
void ReadyQueue(char * algo,int t) //根据作业队列构造就绪队列,algo:算法,t:当前时刻
{   
   struct node *jpre,*jcur,*rpre,* rcur; 
   int j,r,a=0;         
   if(strcmp(algo,"FCFS")==0||strcmp(algo,"RR")==0)//FCFS和RR的就绪队列的构造方式相同
      a=0;
   else if(strcmp(algo,"SJF")==0)  //非抢占SJF
      a=1;
   else if(strcmp(algo,"SRTF")==0)  //抢占式SJF,最短剩余时间优先
      a=2;
   else if(strcmp(algo,"Priority")==0||strcmp(algo,"NonPriority")==0)//抢占和非抢占优先级 
      a=3;
   else {printf("ReadyQueue()函数调用参数错误!\n");exit(0);}
   if(job->next==NULL) {printf("作业队列为空!\n");return;}  
   jpre=job;
   jcur=job->next;
   while(jcur!=NULL) //遍历作业序列中选择已到达进程,将其从作业队列移入就绪队列,直到作业队列为空 	  
   {  
      if(jcur->arrival<=t) //如果当前时刻进程已经到达,则将其插入到就绪队列的合适位置
      {
         printf("P%d到达.\n",jcur->pid);
	      jpre->next=jcur->next;  //将jcur从作业队列移除
         jcur->state='W';//将进程状态设置为就绪
 	      if(ready==NULL) //就绪队列为空
         {jcur->next=NULL;ready=jcur;tail=ready;}
         else  //就绪队列不为空,遍历就绪队列,将jcur插入到合适位置
         {	 rpre=ready;
             rcur=ready;
              switch (a){ //遍历就绪队列查找插入点
                case 0:    //FCFS,RR.根据到达时间arrival查找合适插入点
                        while((rcur!=NULL)&&(jcur->arrival>=rcur->arrival)) 
                             {rpre=rcur;rcur=rcur->next;}
						break;
                case 1: //SJF,根据区间时间burst查找合适插入点 
                         while((rcur!=NULL)&&(jcur->burst>=rcur->burst))
                               {rpre=rcur;rcur=rcur->next;}
						 break;
                case 2:  //STRF,根据剩余时间rest查找合适插入点
						   while((rcur!=NULL)&&(jcur->rest>=rcur->rest))
                               {rpre=rcur;rcur=rcur->next;}
						   break;
                case 3:  //Priority, Non-Priority,根据优先级查找合适插入点
						while((rcur!=NULL)&&(jcur->priority>=rcur->priority)) 
                             {rpre=rcur;rcur=rcur->next;}
                       
                        break;
                default: break;
              }
             if(rcur==NULL)// 插入点在就绪队列尾部
             { 
               jcur->next=NULL;
               rpre->next=jcur;
               tail=jcur;
			    }
			    else if(rcur==ready) //插入点在头部
             {
                jcur->next=rcur;
                ready=jcur; 
             }
             else //插入到rpre和rcur之间
             {   
                jcur->next=rcur;
                rpre->next=jcur;  
             }
         }
         jcur=jpre->next;  //下一个作业
       }else   //当前作业未达到
       {jpre=jcur;jcur=jcur->next;} //下一个作业
     }
      printf("\n作业队列:\n");
      DisplayPCB(job->next); 
}

03 进程同步

问题背景

同时访问共享数据可能造成数据的不一致。

维持数据的一致性需要有保证协作进程有序执行的机制

多线程竞争

生产者进程中count++ 按如下顺序执行：

1
2
3
register1 = count
register1 = register1 + 1
count = register1

同时，消费者者进程中count–按如下顺序执行：

1
2
3
register2 = count
register2 = register2 - 1
count = register2

多个进程并发访问和操作同一组数据，且执行结果与访问顺序有关。

临界区

临界区：并发进程中可能改变共同变量、更新同一个表、写同一个文件的代码段。

进入区（上锁）、临界区、退出区（开锁）、剩余区

解决临界区问题必须满足如下三项要求：

1.互斥 ：进程Pi在临界区内执行，其他进程不得进入临界区

2.前进：如果没有进程在临界区执行，那么允许不在剩余区的进程计入临界区

3.有限等待：从一个进程作出进入临界区的请求，直到该请求被允许为止，其他进程允许进入其临界区的次数有上限。

总结：

忙则等待；空则让进；等则有限；等则让权

Peterson 算法

适用于两个进程在临界区和剩余区间交替执行

信号量

1
2
#include <semaphore.h>
int sem_init(sem_t *sem, int pshared, unsigned int value); //通常 pshared 为 0.表示线程间
1
2
3
4
int sem_destroy(sem_t * sem);//注销信号量
int sem_post(sem_t * sem); //相当于解锁
int sem_wait(sem_t * sem);     //相当于加锁
int sem_trywait(sem_t * sem);   //不阻塞

example_1

image-20230404195434037

设置两个信号量 s1 s2

第一个程序等待 s1 释放 s2

第二个程序 等待 s2 释放 s1

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
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<string.h>
#include<pthread.h>
#include<semaphore.h>
sem_t s1,s2; //信号量结构
void *thread_t1()
{
  while(1){
     
   sem_wait(&s1);
   printf("X");
   usleep(1000);
   printf("x");
   sem_post(&s2);
    
  }
}

void *thread_t2() 
{
   while(1){
   sem_wait(&s2);   
   printf("O");
   usleep(1000);
   printf("o");
   sem_post(&s1);
   }	
}

void main()
{
   int res;
   pthread_t a_thread;
   sem_init(&s1,0,1);
   sem_init(&s2,0,0);
   res=pthread_create(&a_thread,NULL,thread_t1,NULL);
   if(res!=0){perror("Thread creation failure!\n");}
   res=pthread_create(&a_thread,NULL,thread_t2,NULL);
   if(res!=0){perror("Thread creation failure!\n");}

   sleep(2);
    printf("\n");

}

pthread_create 创建线程

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

**pthread_t *thread**：传递一个 pthread_t 类型的指针变量，也可以直接传递某个 pthread_t 类型变量的地址。pthread_t 是一种用于表示线程的数据类型，每一个 pthread_t 类型的变量都可以表示一个线程。

**const pthread_attr_t *attr**：用于手动设置新建线程的属性，例如线程的调用策略、线程所能使用的栈内存的大小等。大部分场景中，我们都不需要手动修改线程的属性，将 attr 参数赋值为 NULL，pthread_create() 函数会采用系统默认的属性值创建线程。

pthread_attr_t 类型以结构体的形式定义在<pthread.h>头文件中，此类型的变量专门表示线程的属性。

**void *(*start_routine) (void *)：以函数指针的方式指明新建线程需要执行的函数，该函数的参数最多有 1 个（可以省略不写），形参和返回值的类型都必须为 void 类型。void 类型又称空指针类型，表明指针所指数据的类型是未知的。使用此类型指针时，我们通常需要先对其进行强制类型转换，然后才能正常访问指针指向的数据。

**void *arg**：指定传递给 start_routine 函数的实参，当不需要传递任何数据时，将 arg 赋值为 NULL 即可。

如果成功创建线程，pthread_create() 函数返回数字 0，反之返回非零值。各个非零值都对应着不同的宏，指明创建失败的原因，常见的宏有以下几种：

EAGAIN：系统资源不足，无法提供创建线程所需的资源。

EINVAL：传递给 pthread_create() 函数的 attr 参数无效。

EPERM：传递给 pthread_create() 函数的 attr 参数中，某些属性的设置为非法操作，程序没有相关的设置权限

#Linux
操作系统
http://example.com/2023/03/15/cao-zuo-xi-tong/
作者
CynicCat
发布于
2023年3月15日
许可协议