IMPORTANT NOTE:
Paging arithmetic laws:
Page size = frame size
Logical address space (/size) = 2m (where m is the the number of bit in the logical
address)
Physical address space (/size) = 2x (where x is the number of bits in physical address)
Logical address space (/size) = number of pages × page size
Physical address space (/size) = number of frames × frame size
Page size= frame size= 2n (where n is the the number of bit in the logical address)
number of pages= 2m-n
number of entries (records)in page table = number of pages
Number of Entries = Process Size / Page Size
Internal Fragmentation Size = Page Size - (Process Size mod Page Size)
Number of Pages = Total Address Space / Page Size
How to convert from logical address to physical address in paging?
Physical address = base address + offset = (number of frame *
frame size) + offset
How to convert from logical address to physical address in segmentation?
If (offset < limit ) then
Physical address = base address + offset
Else
Address error
__________________________________________________
_________________________________
Exercises On Memory Management in an operating system
1) Explain the difference between internal and external fragmentation.
2) Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in order),
how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 212 KB,
CSC/ICT Department COMPUTER SCIENCE ADVANCED LEVEL GBHS DSCHANG
417 KB, 112 KB, and 426 KB (in order)?Which algorithm makes the most efficient use of
memory?
3) Consider a logical address space of 64 pages of 1024 words each, mapped onto a physical
memory of 32 frames. a. How many bits are there in the logical address? b. How many bits are
there in the physical address?
4) Consider a logical address space of 32 pages of 1024 words per page, mapped onto a physical
memory of 16 frames. a. How many bits are required in the logical address? b. How many bits
are required in the physical address?
5) Consider the following segment table
Segment Base Length
0 219 600
1 2300 14
2 90 100
3 1327 580
4 1952 96
What are the physical addresses for the following logical addresses?
a) 0, 430
b) 1, 10
c) 2, 500
d) 3, 400
e) 4, 112
6) Consider a process of size 72,776 bytes and page size of 2048 bytes
a) How many entries are in the page table?
b) What is the internal fragmentation size?
7) Determine the number of registers needed for the page table with a 16-bit address and an 8KB
page size. You may follow the step below for your answer:
- Convert Page Size to Binary:
- Calculate the Number of Pages
- Determine the Number of Registers
CSC/ICT Department COMPUTER SCIENCE ADVANCED LEVEL GBHS DSCHANG
8) Consider a system where the memory adopts the paged segmentation method. The page size is
400 B and the segment size is maximum 1200 B. A process, of size 5600 B, needs to execute
on the system. This process contains 2000 B as the main program, 1100 B as libraries, 1500 B
as functions and 1000 B as data.
a) Say how this process will be partitioned in order to be loaded in the memory (i.e.
division into segments and pages).
b) Was there any internal fragmentation? How many bytes?
Question 9 and 10 use the following state of the memory
Operating System
Process 1
Empty 60 Blocks
Process 2
Process 3
Empty 52 blocks
Empty 100 blocks
9) Distinguish between fixed partitions and dynamic partitions.
10) If the partitions are fixed and a new job arrives requiring 52 blocks of main memory, show
memory after using each of the following partition selection approaches: First fit, Best fit,
Worst fit.
11) If the partitions are dynamic and a new job arrives requiring 52 blocks of main memory, show
memory after using each of the following partition selection approaches: First fit, Best fit,
Worst fit.
12) If a logical address in a paged memory management system is <2, 133>, what do the values
mean?
13) Assuming a 1-KB page size, what are the page numbers and offsets for the following address
references (provided as decimal numbers):
A. 3085 B. 42095 C. 215201 D. 650000 E. 200000
CSC/ICT Department COMPUTER SCIENCE ADVANCED LEVEL GBHS DSCHANG
Exercises On Process management in an operating system
1) List three examples of deadlocks that are not related to a computer system environment.
2) Consider the following set of processes, with the length of the CPU burst time given in
milliseconds:
Process Burst time Priority
P1 2 2
P2 1 1
P3 8 4
P4 4 2
P5 5 3
The processes are assumed to have arrived in the order P1. P2, P3, P4, P5 all at time 0.
a) Draw four Gantt charts that illustrate the execution of these processes using the
following scheduling algorithms: FCFS, SJF, non-preemptive priority (a larger priority
number implies a higher priority), and RR (quantum = 2).
b) What is the turnaround time of each process for each of the scheduling algorithms in part
a?
c) What is the waiting time of each process for each of these scheduling algorithms?
d) Which of the algorithms results in the minimum average waiting time (over all
processes)
3) The following processes are being scheduled using a preemptive, round robin scheduling
algorithm.
Processes Priority Burst Arrival
P1 40 20 0
P2 30 25 25
P3 30 25 30
P4 35 15 60
P5 5 10 100
P6 10 10 105
CSC/ICT Department COMPUTER SCIENCE ADVANCED LEVEL GBHS DSCHANG
Each process is assigned a numerical priority, with a higher number indicating a higher relative
priority. In addition to the processes listed above,he system also has an idle task (which
consumes no CPU resources and is identified as Pidle). This task has priority 0 and is scheduled
whenever the system has no other available processes to run. The length of a time quantum is
10 units. If a process is preempted by a higher-priority process, the preempted process is
placed at the end of the queue.
a) Show the scheduling order of the processes using a Gantt chart.
b) What is the turnaround time for each process?
c) What is the waiting time for each process?
d) What is the CPU utilization rate
4) Many CPU-scheduling algorithms are parameterized. For example, the RR algorithm requires a
parameter to indicate the time slice. Multilevel feedback queues require parameters to dene the
number of queues, the scheduling algorithms for each queue, the criteria used to move
processes between queues, and so on.
5) These algorithms are thus really sets of algorithms (for example, the set of RR algorithms for all
time slices, and so on). One set of algorithms may include another (for example, the FCFS
algorithm is the RR algorithm with an innite time quantum). What (if any) relation holds
between the following pairs of algorithm sets?
a) Priority and SJF
b) Multilevel feedback queues and FCFS
c) Priority and FCFS
d) RR and
6) Consider seven processes P1, P2, …, P7 with arrival times and CPU burst times as follows:
Process P1 P2 P3 P4 P5 P6 P7
Arrival 2-ε 4-ε 5-ε 7-ε 9-ε 15-ε 16-ε
CPU burst 3 2 1 4 2 6 8
Here “2-ε” indicates that P1 has arrived just before time unit 2, and similarly for the others.
Assume that, when joining the Ready Queue, (new or existing) processes always get appended at
the end of the queue.
CSC/ICT Department COMPUTER SCIENCE ADVANCED LEVEL GBHS DSCHANG
a) Draw a chart that illustrates the execution of these processes using the FCFS algorithm.
CSC/ICT Department COMPUTER SCIENCE ADVANCED LEVEL GBHS DSCHANG
