Operating Systems

UNIT – 3
Chapters 1, 2, and 3

1. Explain single and two level directory structures. (5)  To delete a file, the operating system confines its
search to the local UFD; thus, it cannot
1. Single-Level Directory: accidentally delete another user's file that has the
 The simplest directory structure is the single-level same name.
directory.
2. Explain the different attributes of a file. (5/6)
 All files are contained in the same directory,
which is easy to support and understand.
A file’s attributes vary from one operating system to
 A single-level directory has significant
another but typically consist of these:
limitations, when the number of files increases or
 Name. The symbolic file name is the only
when the system has more than one user.
information kept in human readable form.
 Since all files are in the same directory, they must
 Identifier. This unique tag, usually a number,
have unique names.
identifies the file within the file system; it is the
non-human-readable name for the file.
 Type. This information is needed for systems that
support different types of files.
 Location. This information is a pointer to a device
2. Two-Level Directory: and to the location of the file on that device.
 In the two-level directory structure, each user has  Size. The current size of the file (in bytes, words,
its own User File Directory (UFD). or blocks) and possibly the maximum allowed
 Each UFD has a similar structure, but lists only size are included in this attribute.
the files of a single user.  Protection. Access-control information
 When a user job starts or a user logs in, the determines who can do reading, writing,
system's Master File Directory (MFD) is executing, and so on.
searched.  Time, date, and user identification. This
 The MFD is indexed by user name or account information may be kept for creation, last
number, and each entry points to the UFD for that modification, and last use. These data can be
user. useful for protection, security, and usage
 When a user refers to a particular file, only his monitoring.
own UFD is searched.
3. What do you mean by a fault and a hit with respect
 Different users may have files with the same to page replacement? (2)
name, as long as all the file names within each
UFD are unique.  When a page references an invalid page, then it is
 To create a file for a user, the operating system called Page Fault. It means that page is not in
searches only that user's UFD to ascertain whether main memory.
another file of that name exists.  When a page references a valid page, then it is
called Page Hit. It means that page is present in
main memory.

4. Define fault ratio and hit ratio. (2)

 The percentage of times that the page number of
interest is not found in the main memory is called
the fault ratio.

Prepared by: Afzal, Lecturer, Department of Computer Science, FMKMC College, Madikeri. Page 1
Contact: [email protected], [email protected].
Operating Systems
 The percentage of times that the page number of  Initially, all memory is available for user
interest is found in the main memory is called the processes and is considered one large block of
hit ratio. available memory, a hole.
 As processes enter the system, they are put into an
5. Write a note on tree structured directory. input queue. The operating system takes into
 A tree structure is a more powerful and flexible account the memory requirements of each process
approach to organize files and directories in a and the amount of available memory space in
hierarchy. determining which processes are allocated
 There is a master directory (root), which has under memory.
it a number of user directories.  When a process is allocated space, it is loaded into
 Each of these user directories may have sub memory, and it can then compete for CPU time.
directories and files as entries. When a process terminates, it releases its memory,
 This is true at any level: That is, at any level, a which the operating system may then fill with
directory may consist of entries for subdirectories another process from the input queue.
and/or entries for files.
7. Define logical and physical address spaces. (2)
 The set of all logical addresses generated by the
CPU is called as a logical address space.
 The set of all physical addresses corresponding
to the logical addresses is called as a physical
address space.

8. Name two differences between logical and physical

addresses. (2)
 A logical address does not refer to an actual
existing address; rather, it refers to an abstract
address in an abstract address space. A physical
address refers to an actual physical address in
memory.
6. Differentiate fixed and variable length partition
 A logical address is generated by the CPU and is
schemes with an example. (5/6)
translated into a physical address by the memory
Fixed-sized partition Scheme: management unit(MMU). Therefore, physical
 One of the simplest methods for allocating addresses are generated by the MMU.
memory is to divide memory into several fixed-
sized partitions. 9. Explain the different file operations.
 Each partition may contain exactly one process.  Creating a file.
Thus, the degree of multiprogramming is bound  Two steps are necessary to create a file.
by the number of partitions.  First, space in the file system must be found
 In this multiple partition method, when a for the file.
partition is free, a process is selected from the  Second, an entry for the new file must be
input queue and is loaded into the free partition. made in the directory.
When the process terminates, the partition  Writing a file.
becomes available for another process.  To write a file, a system call specifying both
the name of the file and the information to be
Variable-partition scheme:
written to the file is made.
 In the variable-partition scheme, the operating
 The system must keep a write pointer to the
system keeps a table indicating which parts of
location in the file where the next write is to
memory are available and which are occupied.
take place.

Prepared by: Afzal, Lecturer, Department of Computer Science, FMKMC College, Madikeri. Page 2
Contact: [email protected], [email protected].
Operating Systems
 The write pointer must be updated whenever
a write occurs.
 Reading a file.
 To read from a file, a system call that specifies
the name of the file and where (in memory)
the next block of the file should be read is
made.
 The system needs to keep a read pointer to the
location in the file where the next read is to
take place. Once the read has taken place, the
read pointer is updated.
 Repositioning within a file.
 The directory is searched for the appropriate
entry, and the current-file-position pointer is
repositioned to a given value.
 This file operation is also known as a file seek.
 Deleting a file.
 To delete a file, the directory is searched for
the named file. 11. Explain the concept of paging with diagrams. (5/6)
 Having found the associated directory entry,  Paging permits the physical address space of a
all file space is released, so that it can be
process to be non-contiguous.
reused by other files, and the directory entry
 Paging avoids external fragmentation.
is erased.
 Physical Memory is divided into a number of
 Truncating a file.
fixed-sized blocks called frames (f).
 The user may want to erase the contents of a
 Logical Memory is divided into a number of
file but keep its attributes.
fixed-sized blocks called pages (p).
 Rather than forcing the user to delete the file
 When a process is to be executed, its pages are
and then recreate it, this function allows all
loaded into any available memory frames.
attributes to remain unchanged—except for
file length—but lets the file be reset to length
zero and its file space released.
 open () operation
 Informs the system that the named file is
about to become active.
 close () operation
 Informs the system that the named file is no
longer in active use by the user who issued the
close operation.
 Append operation
 To append new information to the end of an
existing file. Scheme
 Rename operation  Every address generated by the CPU is divided
 To rename an existing file. into two parts: a page number (p) and a page
offset (d).

10. Explain the different file types with examples.

The different file types with their common extensions  Where p is an index into the page table and d is
and descriptions is listed below. the displacement within the page.

Prepared by: Afzal, Lecturer, Department of Computer Science, FMKMC College, Madikeri. Page 3
Contact: [email protected], [email protected].
Operating Systems
 The page table contains the base address of each  Indexing into the page table, it can be found that
page in physical memory. page 0 is in frame 5. Thus, logical address 0 maps
 This base address is combined with the page offset to physical address 20. Logical address 3 (page 0,
to define the physical memory address that is sent to offset 3) maps to physical address 23.
the memory unit.  Similarly, according to the page table, page 1 is
 The paging model of memory is shown below. mapped to frame 6. Thus, logical address 4 maps
to physical address 24. Logical address 13 maps
to physical address 9.

12. Explain the concept of segmentation with diagrams.

 Segmentation is a memory-management scheme
that supports this programmer view of memory.

 The size of a page depends on the computer

architecture.  A logical address space is a collection of
Example segments.
 Consider the memory shown below.  Each segment has a name and a length. The
addresses specify both the segment name and the
offset within the segment.
<segment-number, offset>
 When a program is compiled, the compiler
automatically constructs segments. For example,
a C compiler might create separate segments as,
1. The code
2. Global variables
3. The stacks used by each thread
4. The standard C library

Segmentation Hardware

 The size of each page is 4 bytes and the size of the

main memory is 32 bytes (8 frames).
 Logical address 0 is page 0, offset 0; Logical
address 1 is page 0, offset 1; Logical address 2 is
page 0, offset 2; Logical address 3 is page 0, offset
3; Logical address 4 is page 1, offset 0; and so on.

Prepared by: Afzal, Lecturer, Department of Computer Science, FMKMC College, Madikeri. Page 4
Contact: [email protected], [email protected].
Operating Systems
 The segment table is an array of base–limit 13. Consider the following page reference string:
register pairs. 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6.
 Each entry in the segment table has a segment How many page faults would occur for the following
base and a segment limit. The segment base replacement algorithms, assuming one, two, three, four,
contains the starting physical address where the five, six, and seven frames? Remember that all frames
segment resides in memory, and the segment limit are initially empty, so your first unique pages will cost
specifies the length of the segment. one fault each.
 The segment number is used as an index to the  LRU replacement
segment table.  FIFO replacement
 The offset d of the logical address must be  Optimal replacement
between 0 and the segment limit. If it is not, we Number of frames LRU FIFO Optimal
trap to the operating system. 1 20 20 20
 When an offset is legal, it is added to the segment 2 18 18 15
base to produce the address in physical memory 3 15 16 11
of the desired byte. 4 10 14 08
5 08 10 07
Example 6 07 10 07
 We have five segments numbered from 0 through 7 07 07 07
4.
 The segments are stored in physical memory as 14. Consider the following page reference string:
shown. 7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0, 1.
 The segment table has a separate entry for each Assuming demand paging with three frames, how many
segment, giving the beginning address of the page faults would occur for the following replacement
segment in physical memory and the length of that algorithms?
segment.  LRU replacement
 Segment 2 is 400 bytes long and begins at location  FIFO replacement
4300. Thus, a reference to byte 53 of segment 2 is  Optimal replacement
mapped onto location 4353. Assignment
 A reference to segment 3, byte 852, is mapped to
15. How many page faults occur for optimal page
4052.
replacement algorithm for the following reference
 A reference to byte 1222 of segment 0 would
string with four page frames?
result in a trap to the operating system, as this
1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2.
segment is only 1,000 bytes long.
Assignment

16. Consider the following page reference string:

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
How many page faults would occur for the following
replacement algorithms, assuming one, two, three, four,
five, six, and seven frames? Remember that all frames
are initially empty, so your first unique pages will cost
one fault each.
 LRU replacement
 FIFO replacement
 Optimal replacement
Assignment

Prepared by: Afzal, Lecturer, Department of Computer Science, FMKMC College, Madikeri. Page 5
Contact: [email protected], [email protected].