COSC 423 Operating Systems Final
Exam Study Guide
7.11: Consider the deadlock situation that can occur in the dining philosophers
problem when the philosophers obtain the chopsticks one at a time. Discuss
how each of the four necessary conditions for deadlock hold in this setting.
Discuss how deadlocks could be avoided by eliminating any one of the four
necessary conditions. - ANSWER Mutual exclusion holds because each
chopstick can only be used by one person at a time. Hold and wait is in action
because each philosopher is holding a chopstick (resource), and then waiting
for another one to pick up. Since no philosopher can force another one to put
down their chopsticks, there is no pre-emption. All of the philosophers are
waiting for a resource held by another philosopher at the table which indicates
circular wait.
If mutual exclusion wasn't in effect and they could share chopsticks, all of the
philosophers could share the single chopstick between them and eat.
If the philosophers didn't behave in a hold and wait pattern, any/all philosophers
wouldn't pick up a chopstick and wait indefinitely. They'd put it down until they
could acquire both at the same time.
If the philosophers could force another one next to them to put their chopstick
down, then pre-emption would prevent the deadlock situation too.
If all of the philosophers waiting for chopsticks weren't all at the same table,
there wouldn't be circular wait and deadlock wouldn't be occurring.
7.18: Consider a system consisting of m resources of the same type being
shared by n processes. A process can request or release only one resource at a
time. Prove that the system is deadlock free if the following two conditions
holds:
-The maximum need of each process is between one resource and m resources
-The sum of all maximum needs is less than m+n
One way to complete the proof is to show how these conditions preclude one of
the four necessary conditions. - ANSWER Assuming:
A=Sum of all needs
B=Sum of all allocations
C=Sum of all max need
, Let's say that our system is not deadlock free right now. If the system is in
deadlock then sum of all allocations should be equal to the total number of
resources i.e. B = m
Now the statement (b) says that sum of all maximum needs is less than
m+ n i.e. A + B = C < m + n.
As from above deduction B = m so, A + m < m + n
or A < n, which means that there is one process for which need it zero as the
number of processes it greater than need and a process can request and
release only one resource at a time. So, there are n-1 processes sharing m
resources currently. But no process will wait permanently, hence there is a
contradiction and there is no deadlock
8.3 "Why are page sizes always powers of 2?" - ANSWER Paging breaks up an
address into a page and offset number. It is more efficient to break the address
into X page bits and Y offset bits, rather than perform arithmetic on the address
to calculate the page number and offset.Each bit position represents a power of
2 in binary, splitting an address between bits results in a page size that is a
power of 2.
8.4 "Consider a logical address space of 64 pages of 1,024 words each, mapped
onto a physical memory of 32 frames.
(a) How many bits are there in a logical address? - ANSWER A 1024-word page
requires 10 bits because 1024 = 210. Since the logical address space consists of
8 = 23 pages, the logical addresses must be
10+3 = 13 bits
(b) How many bits are there in a physical address?" - ANSWER Since there are
32 = 25 physical pages, physical addresses are 5 + 10 = 15 bits long.
8.9 Explain the difference between internal and external fragmentation. -
ANSWER Internal fragmentation is the area occupied by a process but cannot
be used by the process. This space is unusable by the system until the process
releases the space. External fragmentation exists when total free memory is
enough for the new process but it's not contiguous and can't satisfy the request.
Storage is fragmented into small holes.
8.11 Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600
KB (in that order), how would the first-fit, best fit, and worst fit algorithms place
processes of 212 KB, 417 KB, 112 KB, and 426 KB (in that order)? Which
algorithm makes the most efficient use of memory?
a) First-fit - ANSWER The first-fit algorithm selects the first free partition that is
large enough to accommodate the request.
First-fit would allocate as follows:
Exam Study Guide
7.11: Consider the deadlock situation that can occur in the dining philosophers
problem when the philosophers obtain the chopsticks one at a time. Discuss
how each of the four necessary conditions for deadlock hold in this setting.
Discuss how deadlocks could be avoided by eliminating any one of the four
necessary conditions. - ANSWER Mutual exclusion holds because each
chopstick can only be used by one person at a time. Hold and wait is in action
because each philosopher is holding a chopstick (resource), and then waiting
for another one to pick up. Since no philosopher can force another one to put
down their chopsticks, there is no pre-emption. All of the philosophers are
waiting for a resource held by another philosopher at the table which indicates
circular wait.
If mutual exclusion wasn't in effect and they could share chopsticks, all of the
philosophers could share the single chopstick between them and eat.
If the philosophers didn't behave in a hold and wait pattern, any/all philosophers
wouldn't pick up a chopstick and wait indefinitely. They'd put it down until they
could acquire both at the same time.
If the philosophers could force another one next to them to put their chopstick
down, then pre-emption would prevent the deadlock situation too.
If all of the philosophers waiting for chopsticks weren't all at the same table,
there wouldn't be circular wait and deadlock wouldn't be occurring.
7.18: Consider a system consisting of m resources of the same type being
shared by n processes. A process can request or release only one resource at a
time. Prove that the system is deadlock free if the following two conditions
holds:
-The maximum need of each process is between one resource and m resources
-The sum of all maximum needs is less than m+n
One way to complete the proof is to show how these conditions preclude one of
the four necessary conditions. - ANSWER Assuming:
A=Sum of all needs
B=Sum of all allocations
C=Sum of all max need
, Let's say that our system is not deadlock free right now. If the system is in
deadlock then sum of all allocations should be equal to the total number of
resources i.e. B = m
Now the statement (b) says that sum of all maximum needs is less than
m+ n i.e. A + B = C < m + n.
As from above deduction B = m so, A + m < m + n
or A < n, which means that there is one process for which need it zero as the
number of processes it greater than need and a process can request and
release only one resource at a time. So, there are n-1 processes sharing m
resources currently. But no process will wait permanently, hence there is a
contradiction and there is no deadlock
8.3 "Why are page sizes always powers of 2?" - ANSWER Paging breaks up an
address into a page and offset number. It is more efficient to break the address
into X page bits and Y offset bits, rather than perform arithmetic on the address
to calculate the page number and offset.Each bit position represents a power of
2 in binary, splitting an address between bits results in a page size that is a
power of 2.
8.4 "Consider a logical address space of 64 pages of 1,024 words each, mapped
onto a physical memory of 32 frames.
(a) How many bits are there in a logical address? - ANSWER A 1024-word page
requires 10 bits because 1024 = 210. Since the logical address space consists of
8 = 23 pages, the logical addresses must be
10+3 = 13 bits
(b) How many bits are there in a physical address?" - ANSWER Since there are
32 = 25 physical pages, physical addresses are 5 + 10 = 15 bits long.
8.9 Explain the difference between internal and external fragmentation. -
ANSWER Internal fragmentation is the area occupied by a process but cannot
be used by the process. This space is unusable by the system until the process
releases the space. External fragmentation exists when total free memory is
enough for the new process but it's not contiguous and can't satisfy the request.
Storage is fragmented into small holes.
8.11 Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600
KB (in that order), how would the first-fit, best fit, and worst fit algorithms place
processes of 212 KB, 417 KB, 112 KB, and 426 KB (in that order)? Which
algorithm makes the most efficient use of memory?
a) First-fit - ANSWER The first-fit algorithm selects the first free partition that is
large enough to accommodate the request.
First-fit would allocate as follows:
