Transcript מצגת של PowerPoint

Defeating The Thrashing
The RAM is limited.
Sometimes, too many processes need
large memory allocations and the sum
of these allocations is larger than the
RAM.
Most Operating System schedulers are
versions of Round-Robin.
Each process will cause a page fault
when its turn comes.
8.1 Advanced Operating Systems
What Can Be Done?
When Linux sees too many page faults,
Linux will decide on “thrashing” state.
On thrashing state Linux will kill memory
consuming processes.
– Killing a process is a very aggressive
action and can cause unwelcome results.
Windows ignores the thrashing and the
system will continue to mark time.
8.2 Advanced Operating Systems
Can We Do Better?
Two level of scheduling like the old medium
scheduler used by some operating systems,
can improve the solutions.
The first level will schedule groups of
processes.
The second level will schedule the processes
within each group.
The memory allocation size of each group will
be almost equal to the RAM size.
8.3 Advanced Operating Systems
The Bin Packing Problem
Let Pi be a set of processes with
memory allocation Mi.
We need to group the processes such
that the sum of Mis in each group will
not be bigger than the available RAM.
Fewer groups will yield better
performance; hence we try to minimize
the number of groups.
This is exactly the Bin-Packing
Problem
8.4 Advanced Operating Systems
Using Bin-Packing
Opps... The Bin-Packing Problem is NPHard.
Obviously, the exponential algorithm must
not be used in the scheduler.
– The scheduler must be fast.
There are some polynomial
approximations solving this problem.
Which one is the best?
– The answer will be the “First-Fit”
approximation, but should be proved.
8.5 Advanced Operating Systems
“First Fit”
“First Fit” algorithm:
– Sort the items.
– Try to insert each item to an existing
bin.
– If there is no room for this item, open
a new bin.
“First Fit” will never take out an item
after it has been put in a bin.
8.6 Advanced Operating Systems
Group Time Slice
The group time slice should be long
enough in order to prevent thrashing.
Sometimes the groups are not equal.
– Indeed, a group contains even just one
process is possible.
Set the time slice duration according to
the group size.
8.7 Advanced Operating Systems
Shared Memory
Usually processes with shared memory
allocations have the same shared allocation
size; hence no need for a special action.
8
7
6
5
4
3
2
1
process nam e
8.8 Advanced Operating Systems
Be
nc
h8
Be
nc
h8
Se
nd
m
ai
l
se
nd
m
ai
l
Be
nc
h8
Ba
sh
Ba
sh
Ba
sh
0
Kd
ei
ni
t
Kd
ei
ni
t
Kd
ei
ni
t
Kd
ei
ni
t
Kd
ei
ni
t
Em
ac
s
Em
ac
s
Em
ac
s
Kbytes of shared memory
9
Interactive Processes
Interactive processes need fast response time.
Waiting for their group can be an irksome
delay.
The kernel puts the interactive processes in
every group; thus they will always be running.
However, in order to be fair, the time slice
duration of the interactive processes should be
diminished.
– The time slice of the interactive processes is divided
by the numbers of the bins.
8.9 Advanced Operating Systems
Real Time Processes
Real time processes are similar to
interactive processes. They cannot wait
for their group to be activated.
The solution is similar. The kernel puts
real time processes in every group.
The only difference is the time slice,
which is obviously must not be
diminished.
8.10 Advanced Operating Systems
Priority
It might happen that the highest priority
processes will be in one group, whereas
the lowest priority processes will be in a
second group.
The time slice is set according to the
processes’ average priority within each
group.
8.11 Advanced Operating Systems
No. of Swaps and Execution Time
Synthetic Benchmark
3000000
no. of swaps
2500000
2000000
1500000
1000000
500000
0
16
24
32
40
48
56
64
72
80
88
96
104
112
120
128
136
Proce s s e s ' total s ize
Strict Linux
20
Medium-Term Scheduler
Time (hours)
16
12
8
4
0
16
24
32
40
48
56
64
72
80
88
96
104 112 120 128 136
Proce s s e s ' total s ize
8.12 Advanced
Operating Systems
Medium-Term Scheduler
Strict Linux
(g
2c
ra
2+
p
er
lb
zi
p
+5
p
k
m
r
k
+v
p
rt
ex
er
lb
zi
p
+2
p
cc
+g
ft
y
g
+v
o
/3
0
/2
/1
0
r)
cf
)
+3
vp
+3
m
zi
p
ar
se
r
m
(g
ap
(g
2c
ra
2+
p
er
lb
zi
p
+5
p
b
ap
3
2.5
2
1.5
1
0.5
0
b
ap
3g
2
zi
p
zi
p
3g
3b
Time (hours)
k
/3
0
m
r
k
+v
p
rt
ex
er
lb
zi
p
+2
p
cc
+g
ft
y
g
+v
o
cf
)
/2
/1
0
r)
ap
+3
vp
+3
m
zi
p
ar
se
r
m
(g
3g
2
zi
p
zi
p
3g
3b
no. of swaps
No. of Swaps and Execution Time
SPEC
7000000
6000000
5000000
4000000
3000000
2000000
1000000
0
Linux Scheduler
Medium-Term
Scheduler
Test name
Linux Scheduler
Medium-Term
Scheduler
Test name
8.13 Advanced Operating Systems
pr
)/
2
gc
c+
gz
ip
+v
pr
2c
ra
fty
+2
pe
rlb
m
k
+v
or
te
x
m
k+
3m
c.
..
bz
ip
2+
pa
rs
er
(g
ap
+5
pe
rlb
(g
zi
p+
3v
3g
ap
/1
0
3g
zi
p
3b
zi
p2
Time (hours)
(g
zi
(g
p+
ap
3v
+5
pr
pe
)/
2
rlb
m
k+
3m
bz
cf
)/
ip
30
2+
pa
rs
e
r+
vo
rte
x
gc
c+
gz
ip
+v
2c
pr
ra
fty
+2
pe
rlb
m
k
3g
ap
/1
0
3g
zi
p
3b
zi
p2
no. of swaps
Time Slice Duration
8000000
6000000
4000000
1 second
2000000
2 seconds
0
2.5
2
1.5
1
0.5
0
Te s t nam e
1 second
2 seconds
Test nam e
8.14 Advanced Operating Systems
Selecting an Approximation
no. of swaps
1250000
1000000
750000
First Fit
500000
Best Fit
250000
0
16
32
48
64
80
96
112
128
144
160
20
40
60
80
100
120
140
160
180
200
Processes' total size
Time (hours)
12.5
10
7.5
First Fit
5
Best Fit
2.5
0
16
32
48
64
80
96
112
128
144
160
20
40
60
80
100
120
140
160
180
200
Processes' total size
8.15 Advanced Operating Systems
Conclusions
The medium-term scheduler drastically
reduces the thrashing overhead.
No decline in performance when there
is no thrashing.
Can easily installed on any Linux
machine.
The code is free and can be obtained
at:
http://www.cs.biu.ac.il/~reubenm/
8.16 Advanced Operating Systems