操作系统-学习

系统系统 进程状态转化

作业 进程控制(一)

(1)

某操作系统有如下状态变化图:

1

请说明发生1~4的状态变化的具体原因

① 进程由就绪状态运行状态是由于调度程序的调度引起的

② 进程由运行状态就绪状态是由于时间片用完引起的

③ 进程由运行状态阻塞状态是由于等待事件引起的如(等待I/O传输队列)

④ 进程由阻塞状态就绪状态是由于I/O完成或者等待的事件发生引起的

(2)

编写程序创建如下图所示的进程树。

2

在Linux下可以使用C语言中的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
36
37
38
39
40
41
42
43
#include<stdio.h>
#include<unistd.h>

int main() {
int pid,ppid;

int ret=fork();
if(ret>0) {
pid=getpid();
ppid=getppid();
printf("我是A进程,pid=%d , ppid=%d \n",pid,ppid);
sleep(3);
}
else if(ret==0){

int ret1=fork();
if(ret1>0) {
pid=getpid();
ppid=getppid();
printf("我是B进程,pid=%d , ppid=%d \n",pid,ppid);
sleep(3);
}
else if(ret1==0) {

int ret2=fork();
if(ret2>0) {
pid=getpid();
ppid=getppid();
printf("我是C进程,pid=%d , ppid=%d \n",pid,ppid);
sleep(3);
}
else {
pid=getpid();
ppid=getppid();
printf("我是D进程,pid=%d , ppid=%d \n",pid,ppid);
sleep(3);
}
}
}

return 0;
}

tips : 其中加入sleep是为了防止父进程提前直接结束 然后子节点就访问不到ppid

3

作业 进程控制(二)

(1)

​ 根据如下的前驱图写出可并发执行的程序:

4

答:

(2)

系统有三个进程Read,Write1,Write2共享一个整数缓冲器b,b中每次只能存放一个整数。Read进程每次启动输入设备输入一个整数到b。若b中是奇数,则由进程Write1将其取出打印;若b中是偶数,则由进程Write2将其取出打印。规定输入与打印整数的个数和次序完全一致。(用wait,signal原语实现)

答:

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
semaphore S=1, SO=SE=0;
buffer B;
void Read() {
int x;
while(1) {
从输入设备接受一个数;
x = 数;
wait(S);
B=X;
if (B%2 != 0)
then signal(SO);
else signal(SE);

}
}
void Write1() {
int y;
while(1) {
wait(SO);
y=B;
signal(S);
输出打印y;
}
}
void Write2() {
int z;
while(1) {
wait(SE);
z=B;
signal(S);
输出打印y;
}
}
void main() {
cobegin
Read();Write1();Write2();
coend
}

课上实训题目:

编制一段程序,实现进程的管道通信。使用系统调用pipe()建立一条管道线分别向通道写一句话:

child1 progress is sending message!

child2 progress is sending message!

而父进程则从管道中读出来自两个进程的信息,显示在屏幕上。

答:

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
#include<stdio.h>
#include<unistd.h>
#include<sys/types.h>
#include<sys/wait.h>

int main() {

int fd[2];
char buf[100], s[100];
pipe(fd);

int ret1=fork();
if(ret1 == 0) {
// son1 progress
lockf(fd[1], 1, 0);
sprintf(buf, "child1 process is sending message!");
write(fd[1], buf, 100);
sleep(5);
lockf(fd[1], 0, 0);
}
else if(ret1 > 0) {

int ret2=fork();
if(ret2 == 0) {
// son2 progress
lockf(fd[1], 1, 0);
sprintf(buf, "child2 process is sending message!");
write(fd[1], buf, 100);
sleep(5);
lockf(fd[1], 0, 0);

}
else if(ret2 > 0) {
// father progress
pos1:
wait(0);
if(read(fd[0], s, 100) == -1) {
goto pos1;
}
else {
printf("%s\n", s);
}

pos2:
wait(0);
if(read(fd[0], s, 100) == -1) {
goto pos2;
}
else {
printf("%s\n", s);
}
}
}

return 0;
}

运行截图

银行家调度算法

c++版本:

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
#include<bits/stdc++.h>
using namespace std;
#define MaxNum 100

int Available[MaxNum];
int Max[MaxNum][MaxNum];
int Allocation[MaxNum][MaxNum];
int Need[MaxNum][MaxNum];
int Work[MaxNum]={0};
int Request[MaxNum];
int SafeOrder[MaxNum];
int m,n,a;
char name[MaxNum];



void Input(){
int flag;
cout<<"------银行家算法------"<<endl;
cout<<"请输入可用的资源数量:";
cin>>n;
for(int i=0;i<n;i++) {
cout<<"请输入第"<<i+1<<"个资源的名称:";
cin>>name[i];
cout<<"请输入第"<<i+1<<"个资源的数量";
cin>>Available[i];
}

cout<<"请输入进程的数量:";
cin>>m;
cout<<endl;

for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
cout<<"请输入第"<<i+1<<"个进程的第"<<j+1<<"个资源的最大需求资源数 MAX"<<endl;
cin>>Max[i][j];
}
}

do{
flag=0;

for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
cout<<"请输入第"<<i+1<<"个进程的第"<<j+1<<"个资源的已分配资源数 Allocation"<<endl;
cin>>Allocation[i][j];
if(Allocation[i][j]>Max[i][j]) {
flag = 1;
}
Need[i][j] = Max[i][j] - Allocation[i][j];
}
}
if(flag) {
cout<<"申请的资源大于最大需求量,重新输入"<<endl;
}
}while(flag);

cout<<"系统目前可分配的资源:"<<endl;

for(int i=0;i<n;i++) {
cout<<name[i]<<" ";
}

cout<<endl;

for(int i=0;i<n;i++) {

for(int j=0;j<m;j++) {
Available[i] = Available[i] - Allocation[j][i];
}
cout<<Available[i]<<" ";

}

cout<<endl;
cout<<"****************************"<<endl;
cout<<" Max Allocation Need Available"<<endl;
cout<<"资源名称:";
for(int i=0;i<3;i++) {
for(int j=0;j<n;j++) {
cout<<name[j];
cout<<" ";
}
cout<<" ";
}

cout<<endl;
for(int i=0;i<m;i++) {
cout<<"P"<<i<<" ";
for(int j=0;j<n;j++) {
// cout<<Max[i][j]<<" ";
printf("%4d",Max[i][j]);
}
cout<<" ";
for(int j=0;j<n;j++) {
// cout<<Allocation[i][j]<<" ";
printf("%4d",Allocation[i][j]);
}
cout<<" ";
for(int j=0;j<n;j++) {
// cout<<Need[i][j]<<" ";
printf("%4d",Need[i][j]);
}
// cout<<" ";
cout<<endl;
}

}



void OutPut() {
cout<<"当前可分配的资源:"<<endl;
for(int i=0;i<n;i++) {
cout<<name[i]<<" ";
}
cout<<endl;

for(int i=0;i<n;i++) {
cout<<Available[i]<<" ";
}

cout<<endl;
cout<<" Work Need Allocation Finish"<<endl;
cout<<"资源名称:";
for(int i=0;i<3;i++) {
for(int j=0;j<n;j++) {
cout<<name[j]<<" ";
}
cout<<" ";
}
cout<<endl;
for(int i=0;i<m;i++) {
cout<<"P"<<i<<" ";
for(int j=0;j<n;j++) {
printf("%4d",Work[j]);
}
cout<<" ";
for(int j=0;j<n;j++) {
printf("%4d",Need[i][j]);
}
cout<<" ";
for(int j=0;j<n;j++) {
printf("%4d",Allocation[i][j]);
}
cout<<" ";
if(Request[i]==0) {
cout<<"false";
}else {
cout<<"true";
}
cout<<endl;



}

}

void Check(){
int q=0;
int apply;

// init
for(int i=0;i<n;i++) {
Request[i] = false;
}

for(int i=0;i<n;i++) {
Work[i]=Available[i];
}

for(int i=0;i<m;i++) {
apply=0;
for(int j=0;j<n;j++) {
if(Request[i]==false&&Need[i][j]<=Work[j]) {
apply++;
if(apply==n) {
for(int k=0;k<n;k++) {
Work[k]=Work[k]+Allocation[i][k];
Available[k] = Work[k];
}
Request[i]=true;
SafeOrder[q]=i;
OutPut();
i=-1;
q++;

}
}
}
}

for(int i=0;i<m;i++) {
if(Request[i]==false) {
cout<<"no safe!"<<endl;
return;
}
}

cout<<"system is safe!"<<endl;
cout<<"safe list:";
for(int i=0;i<m;i++) {
cout<<SafeOrder[i];
if(i<m-1) {
cout<<"->";
}
}
cout<<endl;
return;
}


int main() {
Input();
Check();


return 0;
}

Python版本:

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
class BankAlgorithm(object):
def __init__(self, resource, MAX, Allocation):
""""
:param resource: dict name:value
:param MAX: array(array())
:param Allocation: array(array())
"""
self.resource = resource
self.MAX = MAX
self.Allocation = Allocation

self.Need = []

def show_raw(self, resource, MAX, Allocation, Need):
print(resource)
print(" MAX Allocation Need")
tmp_str = " ".join(resource.keys())
print("资源名称 {} {} {}".format(tmp_str,tmp_str,tmp_str))
# print(MAX)
# print(Allocation)
for i in range(len(MAX)):
tmp_str = ""
for j in range(len(MAX[0])):
tmp_str = tmp_str + MAX[i][j] + " "


tmp_str2 = ""
for j in range(len(MAX[0])):
tmp_str2 = tmp_str2 + Allocation[i][j] + " "

tmp_str3 = ""
for j in range(len(MAX[0])):
tmp_str3 = tmp_str3 + str(Need[i][j]) + " "

print("P{} ".format(i+1) + tmp_str + " " + tmp_str2+ " " +tmp_str3)

def check(self, resource, MAX, Allocation, Need):
# 当前可分配
work = []

for i in range(len(MAX[0])):
# 资源
count = 0
for j in range(len(MAX)):
# 进程
count = count + int(Allocation[j][i])

work.append(int(list(resource.values())[i]) - count)

progess_staus = [0 for _ in range(len(MAX))]
SafeOrder = []


i = 0
while i < len(MAX):
# 进程
flag = 0
for j in range(len(MAX[0])):
# 资源
if progess_staus[i] == 0 and Need[i][j] <= work[j]:
flag = flag + 1
if flag == len(MAX[0]):
# print(Need[i][j])
# print(work[j])
for k in range(len(MAX[0])):
work[k] = work[k] + int(Allocation[i][k])

progess_staus[i] = 1
SafeOrder.append(i)
i=-1
i = i + 1

for staus in progess_staus:
if staus == 0:
print("不安全!")
return

print("系统是安全的")
for order in SafeOrder[:-1]:
print(order , end="->")
print(SafeOrder[-1], end="")


def init_Need(self):
for i in range(len(self.MAX)):
tmp = []
for j in range(len(MAX[0])):
tmp.append(int(MAX[i][j]) - int(Allocation[i][j]))
self.Need.append(tmp)
# print(self.Need)



def run(self):
self.init_Need()
# self.show_raw(self.resource, self.MAX, self.Allocation, self.Need)
self.check(self.resource, self.MAX, self.Allocation, self.Need)



if __name__ == '__main__':
resource = {}
resource_num = input("请输入可用资源数量:")
for i in range(int(resource_num)):
tmp_name = input("请输入第{}个资源的名称:".format(i+1))
resource[tmp_name] = input("请输入第{}个资源的数量:".format(i + 1))

process_num = input("请输入进程数量:")
MAX = []
Allocation = []
for i in range(int(process_num)):
tmp = []
for j in range(int(resource_num)):
tmp.append(input("请输入第{}个进程的第{}个资源的最大(MAX)需求资源数:".format(i+1, j+1)))
MAX.append(tmp)

for i in range(int(process_num)):
tmp = []
for j in range(int(resource_num)):
tmp.append(input("请输入第{}个进程的第{}个资源的已分配资源数(Allocation):".format(i+1, j+1)))
Allocation.append(tmp)

midi = BankAlgorithm(resource, MAX, Allocation)
midi.run()

输入样例:

(该样例为 银行家算法作业二 )

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
3
A
17
B
5
C
20
5
5
5
9
5
4
6
4
0
11
4
2
5
8
2
4
2
1
2
4
0
2
4
0
5
2
0
4
3
1
4

处理机调度算法(先进先出、最短优先级)

C++版本

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
#include<bits/stdc++.h>
using namespace std;
#define N 100

struct work {
char name[10];
float arrive_time;

float need_time;

float start_time;

float end_time;

float turnaround_time;
float turnaround_time_with_weight;
};


void output(struct work works2[N], int n) {
double sum_turnaround_time=0;
double sum_turnaround_time_with_weight=0;
printf("作业名\t\t到达时间\t\t服务时间\t\t开始时间\t\t结束时间\t\t周转时间\t\t带权周转时间:\n");
for (int i=0;i<n;i++) {
printf("%s\t\t%f\t\t%f\t\t%f\t\t%f\t\t%f\t\t%f", works2[i].name,works2[i].arrive_time,works2[i].need_time,works2[i].start_time,works2[i].end_time,works2[i].turnaround_time, works2[i].turnaround_time_with_weight);
printf("\n");
sum_turnaround_time = sum_turnaround_time+works2[i].turnaround_time;
sum_turnaround_time_with_weight = sum_turnaround_time_with_weight + works2[i].turnaround_time_with_weight;
}
printf("平均周转时间:%f \n", sum_turnaround_time/n);
printf("平均带权周转时间: %f \n", sum_turnaround_time_with_weight/n);
}


void fcfs(struct work works[N], int n) {
struct work works2[N];
memcpy(works2,works,sizeof(work)*N);



for (int i=0;i<n;i++) {
// todo sort 根据到达时间排序

if(i==0) {
works2[i].start_time = works2[i].arrive_time;

works2[i].end_time = works2[i].start_time + works2[i].need_time;

works2[i].turnaround_time = works2[i].end_time - works2[i].arrive_time;

works2[i].turnaround_time_with_weight = works2[i].turnaround_time / works2[i].need_time;
}
// 如果到达了 前一个害没结束 就得等待
else if(works2[i].start_time < works2[i-1].end_time) {

works2[i].start_time = works2[i-1].end_time;

works2[i].end_time = works2[i].start_time + works2[i].need_time;

works2[i].turnaround_time = works2[i].end_time - works2[i].arrive_time;

works2[i].turnaround_time_with_weight = works2[i].turnaround_time / works2[i].need_time;
} else {
// 如果 前一个结束了,这个进程过很久才达到
works2[i].start_time = works2[i].arrive_time;
works2[i].end_time = works2[i].start_time + works2[i].need_time;
works2[i].turnaround_time = works2[i].end_time - works2[i].arrive_time;
works2[i].turnaround_time_with_weight = works2[i].turnaround_time / works2[i].need_time;
}

}
output(works2, n);

}



void sjf(struct work works[N], int n) {

// 默认按到达时间排序的

struct work works2[N];
memcpy(works2,works,sizeof(work)*N);

bool flag[n] = {0};
int the_pre_work_id = 0;

works2[0].start_time = works2[0].arrive_time;

works2[0].end_time = works2[0].start_time + works2[0].need_time;

works2[0].turnaround_time = works2[0].end_time - works2[0].arrive_time;

works2[0].turnaround_time_with_weight = works2[0].turnaround_time / works2[0].need_time;
printf("作业顺序为:%s ",works2[0].name);
double now_end = works2[0].end_time;


flag[0] = 1;

int temp_the_minist_id;


while(1) {
double temp_the_minist_need_time=999999999;
bool queue[n] = {0};
for(int i=1;i<n;i++) {
if(works2[i].arrive_time <= now_end && flag[i] ==0) {
queue[i] = 1;
// ready
}
}

// find the minist one
for(int i=1;i<n;i++) {
if(queue[i] == 1) {
// printf("queue : %d", i);
if(temp_the_minist_need_time > works2[i].need_time) {
temp_the_minist_need_time = works2[i].need_time;
temp_the_minist_id = i;
}
}
}

// do this work
if(flag[temp_the_minist_id] ==1) {
// already do all and exit
break;
} else {
printf("%s ", works2[temp_the_minist_id].name);
works2[temp_the_minist_id].start_time = works2[the_pre_work_id].end_time;

works2[temp_the_minist_id].end_time = works2[temp_the_minist_id].start_time + works2[temp_the_minist_id].need_time;

works2[temp_the_minist_id].turnaround_time = works2[temp_the_minist_id].end_time - works2[temp_the_minist_id].arrive_time;

works2[temp_the_minist_id].turnaround_time_with_weight = works2[temp_the_minist_id].turnaround_time / works2[temp_the_minist_id].need_time;

the_pre_work_id = temp_the_minist_id;
flag[temp_the_minist_id] = 1;
now_end = works2[temp_the_minist_id].end_time;
}



}
printf("\n");
output(works2, n);
}


int main() {

int n;
cout<<"请输入进程个数:"<<endl;
cin>>n;

struct work works[N];

for (int i=0;i<n;i++) {
cout<<"请输入第"<<i+1<<"个进程的名称、到达时间、服务时间:"<<endl;
scanf("%s %f %f", works[i].name, &works[i].arrive_time, &works[i].need_time);
}

cout<<"作业名\t\t到达时间\t\t运行时间\t\t"<<endl;
for (int i=0;i<n;i++) {
printf("%s\t\t%f\t\t%f", works[i].name, works[i].arrive_time, works[i].need_time);
printf("\n");
}

cout<<"先来先服务(FCFS):"<<endl;
fcfs(works, n);


cout<<"短作业优先服务(SJF):"<<endl;
sjf(works, n);

return 0;
}

输入样例

1
2
3
4
5
6
5
A 0 3
B 2 6
C 4 4
D 6 5
E 8 2