PART A: OBJECTIVES [20 MARKS]

1. Which of these is NOT part of the general methods of handling deadlock?

A. Make sure deadlock NEVER happens.
B. Ignore it totally.
C. Mutual exclusion.

j D. Let it happen and then recover from it.

2. A system has 5 printers on 3 different floors, 2 disk drives on the top floor and 1 cloud
storage facility. Which of these statements is TRUE?
A. Resource R = printers has 5 instances.
B. Resource R = printers has 3 instances.
C. Resource R = printers has 1 instance.
D. Resource R = printers has 6 instances.

3. Resource-Allocation Graph (RAG) consists of a set of vertices and edges. Which of these is
NOT part of the set in RAG?
A. Processes. C. Instances Edge.
B. Resources. D. Request Edge.

4. Which is the best definition of a safe state?

A. The system can allocate all resources requested by all processes while they are in a
cycle/circle without entering a deadlock state.
B. The system can allocate all resources requested by all processes without entering a
deadlock state.
C. The system can only allocate available resources requested by all high priority processes
without entering a deadlock state.
D. The system only allocates one resource at a time to prevent a deadlock state.

1
 5. Necessary conditions that must be hold simultaneously for deadlock to occur are listed below
EXCEPT:
A. mutual exclusion. C. preemption.
B. hold and wait. D. circular wait.

6. Total free memory space is enough to satisfy a request or to reside a process in it, but it is not
contiguous so it cannot be used. This description is referred as:

Gunned
A. internal fragmentation. C. swapping.
in tht
gnats B. external fragmentation.
freemoney
D. relocation.
Madden
7. The mapping of virtual to physical address is done by a hardware device called:
A. Relocation register. C. Cache memory.
B. Memory Management Unit (MMU). D. Virtual memory.

O
9. __________ has the least wasted space and the smallest partition fitting the requirements.
A. Worst-fit memory allocation C. Dynamic-fit memory allocation

o
B. First-fit memory allocation D. Best-fit memory allocation

10. The following statement is FALSE about advantages of virtual memory:

oA.B. Job size is restricted to the size of main memory.

Memory used more efficiently.
C. Allows an unlimited amount of multiprogramming.
D. Eliminates external fragmentation and minimizes internal fragmentation.

11. Virtual memory allows program execution even if not stored entirely in memory. However it
will increase ______________ .
A. processor hardware costs
B. overhead for handling paging interrupts
C. software complexity to prevent thrashing.
D. all the above

2
12. The following algorithm can be described as ______________ .

1 Set counter to 1
2 Do while counter <= number of blocks in memory
If job_size > memory_size(counter)
Then counter = counter + 1
Else
load job into memory_size(counter)
adjust free/busy memory lists
go to step 4
End do
3 Put job in waiting queue
4 Go fetch next job

A. first-fit memory allocation

B. best-fit memory allocation
C. least-fit memory allocation
D. worst-fit memory allocation

13. Below are the list of page replacement policies EXCEPT:

A. Least Frequently Used (LFU).
B. Most Frequently Used (MFU).
C. Last In First Out (LIFO).
D. Optimal Page Replacement (OPT).

14. Page fault means ________.

A. hit page
B. miss page
C. total pages
D. smaller page size

3
15. In virtual memory concept, if there is no free frame for page replacement, what is the action
taken?
A. Waiting until frame free.
B. Select a victim frame.
C. Continue the user process.
D. Process exit.

16. Access Control Matrix and Access Control Lists are techniques that may be used in
implementing the File Access Control in Operating Systems. Which of the statements below
are TRUE?
i. Access Control List requires less storage space than the Access Control Matrix.
ii. Unix operating system is using Access Control Lists Technique.
iii. As files or users of the system increases, the size of Access Control List also
increases due to the NULL entries.
iv. Access Control Matrix only practical for systems with a few files and users.

A. i and ii C. i and iii

B. ii and iv D. i , ii and iv

17. Which one of the disk allocation scheme is being referred by the following statements:
o Does not support direct access
o In the directory file, only address of first data storage and number of extend are
important.
o No external fragmentation
o As long as the first data storage block is found, the rest of the file may possibly be
recovered even though the directory file is corrupted.

A. Storage level storage allocation.

B. Directory level storage allocation.
C. Indexed storage allocation.
D. Contiguous storage allocation.

4
18. Given a storage disk with size of 225 bytes. With size of a block equals to 214 bytes, what is
the length of the bit map of the disk?
A. 211 bits. C. 225 bits.
B. 214 bits. D. 239 bits.

19. _________ is the time required to reach the desired sector by spinning the storage disk.
A. Seek Time C. Transfer Time
B. Rotational Latency D. Disk Capacity

20. In Unix system, a filename that begins with the root and follows a path down to the specified
file is known as ________.
A. relative filename C. root filename
B. absolute filename D. path filename

5
PART B: STRUCTURED [80 MARKS]

QUESTION 1 (20 MARKS)

a. You are given the following set of edges. Use it to answer the following questions.

Edge, E = {P0  R1, P1  R1, R1P2, P2R2, R2P1, R3P0}

i. Draw the Resource Allocation Graph. [3]

ii. Using the RAG in (i) for the scenarios given below, please explain the possibility of
deadlock happening (if deadlock happens). [4]

Scenario A

R1 has 2 instances, R2 has 2 instances,

R3 has 1 instance

Scenario B

R1 has 1 instance, R2 has 2 instances,

R3 has 2 instances

6
b. Consider the following system has three processes, P0, P1 and P2, and with three resource
types, A, B and C. At time t0, the resource allocation state of the system is as shown below:
Max Allocation Available

A B C A B C A B C
P0 4 2 3 2 1 1 2 1 2
P1 3 1 6 1 0 2
P2 6 3 3 3 2 2

i. Calculate the total number of resource for type A, B and C. Show your calculation. [2]

ii. What is the content of the Need matrix ? [2]

iii. Determine whether the system is in safe or unsafe state at t0. [5]

iv. If at t1, P2 request for (1,1,1), should the system satisfy the request of P2? Show your
works. [4]

7
 QUESTION 2 (22 MARKS)

a. In an operating system, assume memory is allocated as specified in Figure 1.

10K 10K 20K 30K 10K 5K 30K 20K 10K 15K 20K 20K

Address: 0K 10K 20K … … … … 199K

Hole Used

Figure 1: Variable partition memory allocation.

i. Show how the following set of jobs {J1 - 20KB, J2 - 10KB, J3 - 5KB} (in that order)
are allocated inside the main memory using first-fit allocation. At what starting address
will each job be allocated? [3]

ii. Show how the following set of jobs {J1 - 20KB, J2 - 10KB, J3 - 5KB} (in that order)
are allocated inside the main memory using best-fit allocation. At what starting address
will each job be allocated? [3]

b. Given new jobs Job 6 until Job 10 in Figure 2 and main memory using relocatable
dynamic partition in Figure 3. Consider Job 1 until 5 end at t10.

Jobs Size 80K Job 1

6 40K
25K Job 2
7 40K
25K Job 3
8 20K

9 25K Job 4
40K
10 10K

5K Job 5
Figure 2: Job description

Figure 3: Memory partition

8
 i. Redraw and label each job that will be allocated into the memory after t10. Shades all
unused partition clearly. [4]
ii. Calculate the total fragmentation of the memory for case (i). [2]
iii. If another Job 11 with size 35K arrives, can this job be allocated into the memory?
Suggest your solution. [1]

c. What are the TWO major differences between paging and segmentation? [2]

d. Given a paging system with 224 bytes of physical memory; 210 pages of logical address
space and page size of 512 bytes.

i. What is the total size of the logical address space. [1]

ii. What is the frame size of the physical memory. [1]
iii. How many frames of the physical memory. [1]
iv. How many number of entry in the page table. [1]
v. Calculate the offset bits for a page of virtual memory. [1]
vi. Draw the frame offset of the physical memory address and page offset of logical
memory. [2]

9
QUESTION 3 (15 MARKS)

a. A page replacement algorithm should minimize the number of page faults. Consider the
following page reference string:

1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2

Assuming demand paging with FOUR page frames, how many page faults would occur for
the following replacement algorithms? Show all your works.
i. FIFO [3]
ii. OPT [4]
iii. Compare and discuss both algorithms in term of page faults occurred? Which do you
think is better? [2]

b. In paging, thrashing may occur.

i. What is the cause of thrashing? [2]
ii. How does the system detect thrashing? [2]
iii. Once it detects thrashing, what can the system do to eliminate this problem? [2]

10
QUESTION 4 (23 MARKS)

a. Indicate whether statements below are TRUE or FALSE statements, according to the Unix
files access control as shown in Figure 4.

-r-xr--r-x Ali Ali 2.6K Feb 16 2011 Untitled

-rw-r-xr-- Abu Student 436B Aug 28 2011 README
drwxr-xr-x Ali Student 197B Aug 28 2011 Notes

Figure 4: Unix file access control

i. Only Untitled and README are files. [1]

ii. Notes is a folder that is shared among users of the system. [1]
iii. Owner of the README file is Student. [1]
iv. Untitled file is editable by Ali. [1]
v. README is only editable by Abu. [1]

b. Assuming Figure 5 shows a storage map of a disk with capacity of 400KB. The disk has 20
storage blocks and size of a storage block is 20KB. Two files will be stored in the storage
disk that are File1 and File2. Size of File1 is 58KB, while the size of File2 is 36KB.
Assuming the operating system is using Indexed Storage Allocation. Each storage block
can only store 3 storage block addresses.

i. Fill in the Index Block Number column in Directory File, and update the Storage Map
accordingly for File1. Consider Index block for File 1 is block 3. [2]
ii. Fill in the Index Block Number column in Directory File, and update the Storage Map
accordingly for File2. Consider Index block for File 2 is block 18. [2]

11
 1 2 3 4 Filename File Size Index Block
(KB) Number

File1 58
5 6 7 8
File2 36

9 10 11 12 Directory File

13 14 15 16

17 18 19 20

Figure 5: Storage Map

c. Figure 6 shows a bit map for free space management for a hypothetical Operating System
whereby bit 0 indicates that the block is used and bit 1 indicates that the block is free.

Block No 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Bit Map 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0

Figure 6: Storage Map

Suppose that the size of a block is 15KB.

i. List the block numbers that are allocated to a file named [Link]. The size of the
[Link] is 64KB. [3]
ii. Is there any block that suffers from fragmentation in storing the [Link]?
If your answer is a YES, state the block number that contains the fragmentation. [2]

12
d. On a disk with 900 tracks: numbered 0 to 899. The disk queue in FIFO order contains
requests on the following tracks:

142, 778, 292, 575, 205, 376

Starting from the current head location 545, sketch figure to illustrate the head movement
(track traveled) to serve all the requests based on

i. SSTF seek strategy. [3]

ii. C-LOOK seek strategy. The head movement direction is outer to inner. [3]

iii. According to the above scenario (i) and (ii), which seek strategy is better between SSTF
and C-LOOK? Briefly justify your answer. [3]

13