System Software And Operating System Important Descriptive Questions 3
Q.21. Discuss two main approaches to identify and reuse free memory area in a heap. (6) Ans:
Two popular techniques to identify free memory areas as a result of allocation and de-
allocations in a heap are:
1. Reference count: the system associates a reference count with each memory area to indicate the number of its active users. This number is incremented when a user accesses that area and decrements when user stops using that. The area is free if the reference counts drops to zero. This scheme is very simple to implement however incurs incremental overheads.
2. Garbage collection: In this technique two passes are made over the memory to identify unused areas. In the first pass it traverses all pointers pointing to allocated areas and marks the memory areas that are in use. The second pass finds all unmarked areas and declares them to be free. The garbage collection overheads are not incremental. They are incurred every time the system runs out of free memory to allocate to fresh requests.
Two main approaches to reuse free memory area in a heap are:
First-fit: Allocate the first hole that is big enough. Searching can start either at the beginning of the set of holes or where the previous first-fit search ended. Searching is stopped as soon as a free hole is found that is large enough
Best-fit: Allocate the smallest hole that is big enough; Entire list is searched, unless
ordered by size. This strategy produces the smallest leftover hole.
25
DC14 System Software and Operating System
Q.22. List the steps needed to perform page replacement. Explain the different page replacement policies. Also list out the main requirements, which should be satisfied by a page replacement policy. (8)
Ans:
The steps needed to perform page replacement are:
1.Determine which page is to be removed from the memory.
2.Perform a page-out operation.
3.Perform a page-in operation.
Different page replacement algorithms are briefly described below:
1. First-in, first-out
The first-in, first-out (FIFO) page replacement algorithm is a low-overhead algorithm. Here the operating system keeps track of all the pages in memory in a queue, with the most recent arrival at the back, and the earliest arrival in front. When a page needs to be replaced, the page at the front of the queue (the oldest page) is selected.
Advantage: FIFO is cheap and intuitive.
Disadvantage: 1. Performs poorly in practical application.
2. Suffers from Belady’s anomaly.
2. Not recently used
The not recently used (NRU) page replacement algorithm works on the following principle: when a page is referenced, a referenced bit is set for that page, marking it as referenced. Similarly, when a page is modified (written to), a modified bit is set. At a certain fixed time interval, the clock interrupt triggers and clears the referenced bit of all the pages, so only pages referenced within the current clock interval are marked with a referenced bit. When a page needs to be replaced, the operating system divides the pages into four classes:
• Class 0: not referenced, not modified
• Class 1: not referenced, modified
• Class 2: referenced, not modified
• Class 3: referenced, modified.
The NRU algorithm picks a random page from the lowest category for removal.
3. Optimal page replacement algorithm
The optimal page replacement algorithm (also known as OPT )is an algorithm that works as follows: when a page needs to be swapped in, the operating system swaps out the page whose next use will occur farthest in the future. For example, a page that is not going to be used for the next 6 seconds will be swapped out over a page that is going to be used within the next 0.4 seconds.
Disadvantage: This algorithm cannot be implemented in the general purpose
operating system because it is impossible to compute reliably how long it will be before a page is going to be used.
The main requirements, which should be satisfied by a page replacement policy, are:
1. Non-interference with the program’s locality of reference: The page replacement
policy must not remove a page that may be referenced in the immediate future.
2. The page fault rate must not increase with an increase in the memory allocation for a program.
Q.23. What is an I/O buffer? What is the advantage of buffering? Is buffering always effective? Justify your answer with help of an example. (8)
26
DC14 System Software and Operating System
Ans:
One kind of I/O requirement arises from devices that have a very high character density such as tapes and disks. With these characteristics, it is not possible to regulate communication with devices on a character-by-character basis. The information transfer, therefore, is regulated in blocks of information. Additionally, sometimes this may require some kind of format control to structure the information to suit the device and/or data characteristics. For instance, a disk drive differs from a line printer or an image scanner. For each of these devices, the format and structure of information is different. It should be observed that the rate at which a device may provide data and the rates at which an end application may consume it might be considerably different. In spite of these differences, the OS should provide uniform and easy to use I/O mechanisms. Usually, this is done by providing a I/O buffer. The OS manages this buffer so as to be able to comply with the requirements of both the producer and consumer of data. Basically, the buffers absorb mismatch in the data transfer rates of processor or memory on one side and device on the other.
Q.24. Discuss the different techniques with which a file can be shared among different users. (8)
Ans:
Some popular techniques with which a file can be shared among different users are:
1. Sequential sharing: In this sharing technique, a file can be shared by only one program at a time, that is, file accesses by P1 and P2 are spaced out over time. A
lock field can be used to implement this. Setting and resetting of the lock at file open and close ensures that only one program can use the file at any time.
2. Concurrent sharing: Here a number of programs may share a file concurrently. When this is the case, it is essential to avoid mutual interference between them. There are three categories of concurrent sharing:
a. Immutable files: If a file is shared in immutable mode, none of the sharing programs can modify it. This mode has the advantage that sharing programs are independent of one another.
b. Single image immutable files: Here the changes made by one program are immediately visible to other programs. The Unix file system uses this file- sharing mode.
c. Multiple image mutable files: Here many programs can concurrently update the shared file. Each updating program creates a new version of the file, which is different from the version created by concurrent programs. This sharing mode can only be used in applications where concurrent updates and the existence of multiple versions are meaningful.
Q.25. Differentiate between protection and security. Explain the techniques used for protection of user files. (8)
Ans:
Operating system consists of a collection of objects, hardware or software. Each object has a unique name and can be accessed through a well-defined set of operations. Protection problem - ensure that each object is accessed correctly and only by those processes that are allowed to do so.
Security must consider external environment of the system, and protect it from:
27
DC14 System Software and Operating System
•Unauthorized access.
•malicious modification or destruction
•Accidental introduction of inconsistency.
It is easier to protect against accidental than malicious misuse.
Protection of user files means that file owner/creator should be able to control:
what can be done and by whom. Various categories of access to files are:
•Read
•Write
•Execute
•Append
•Delete
•List
Q.26. What is parsing? Explain any three parsing techniques. (8) Ans
Parsing is the process of analyzing a text, made of a sequence of tokens, to
determine its grammatical structure with respect to a given formal grammer. Parsing is also known as syntactic analysis and parser is used for analyzing a text. The task of the parser is essentially to determine if and how the input can be derived from the start symbol of the grammar.
Following are three parsing techniques:
Top-down parsing - Top-down parsing can be viewed as an attempt to find left-most derivations of an input-stream by searching for parse trees using a top-down expansion of the given formal grammar rules. Tokens are consumed from left to right. Inclusive choice is used to accommodate ambiguity by expanding all alternative right- hand-sides of grammar rules.
Bottom-up parsing - A parser can start with the input and attempt to rewrite it to the
start symbol. Intuitively, the parser attempts to locate the most basic elements, then the elements containing these, and so on. LR parsers are examples of bottom-up parsers. Another term used for this type of parser is Shift-Reduce parsing.
Recursive descent parsing- It is a top down parsing without backtracking. This parsing technique uses a set of recursive procedures to perform parsing. Salient advantages of recursive descent parsing are its simplicity and generality. It can be implemented in any language supporting recursive procedures.
Q.27. Draw the state diagram of a process from its creation to termination, including all transitions, and briefly elaborate every state and every transition. (8)
Ans:
As a process executes, it changes state
• new: The process is being created.
• running: Instructions are being executed.
• waiting: The process is waiting for some event to occur.
• ready: The process is waiting to be assigned to a processor.
• terminated: The process has finished execution.
28
DC14 System Software and Operating System
Q.28. Consider the following system snapshot using data structures in the Banker’s algorithm, with resources A, B, C, and D, and process P0 to P4:
Max Allocation Need Available
P0 A
6 B
0 C
1 D
2 A
4 B
0 C
0 D
1 A B C D A B C D
P1 1 7 5 0 1 1 0 0
P2 2 3 5 6 1 2 5 4
P3 1 6 5 3 0 6 3 3
P4 1 6 5 6 0 2 1 2
3 2 1 1
Using Banker’s algorithm, answer the following questions.
(a) How many resources of type A, B, C, and D are there? (2) (b) What are the contents of the Need matrix? (3) (c) Is the system in a safe state? Why (4) (d) If a request from process P4 arrives for additional resources of (1,2,0,0,), can the Banker’s algorithm grant the request immediately? Show the new system state and other criteria. (7)
Ans:
(a) A-9; B-13;C-10;D-11
(b) Need[i, j]=Max[i,j]-Allocation[i,j] so content of Need matrix is
A B C D
P0 2 0 1 1
P1 0 6 5 0
P2 1 1 0 2
P3 1 0 2 0
P4 1 4 4 4
(c) The system is in a safe state as the processes can be finished in the sequence P0, P2, P4, P1 and P3.
(d) If a request from process P4 arrives for additional resources of (1,2,0,0,), and if this request is granted, the new system state would be tabulated as
follows.
29
DC14 System Software and Operating System
Max Allocation Need Available
A B C D A B C D A B C D A B C D
P0 6 0 1 2 4 0 0 1 2 0 1 1
P1 1 7 5 0 1 1 0 0 0 6 5 0
P2 2 3 5 6 1 2 5 4 1 1 0 2
P3 1 6 5 3 0 6 3 3 1 0 2 0
P4 1 6 5 6 1 4 1 2 0 2 4 4
2
0
1
1
After PO completes P3 can be allocated. 1020 from released 6012 and available
2011(Total 80 23) and is a safe sequence.
Q.29. Define the following
(i) Process;
(ii) Process Control Block; (PCB) (iii) Multi programming;
(iv)Time sharing. (8)
Ans:
(i) Process: Process is a program in execution; process execution must progress in sequential fashion. A process includes:
• program counter
• stack
• data section
(ii) Process Control Block (PCB): Information associated with each process is stored in Process control Block.
Process state Program counter CPU registers
CPU scheduling information Memory-management information Accounting information
I/O status information
(iii) Multiprogramming: A multiprogramming operating system is system that allows more than one active user program (or part of user program) to be stored in main memory simultaneously. Multi programmed operating systems are fairly sophisticated. All the jobs that enter the system are kept in the job pool. This pool consists of all processes residing on mass storage awaiting allocation of main memory. If several jobs are ready to be brought into memory, and there is not enough room for all of them, then the system must choose among them. A time-sharing system is a multiprogramming system.
(iv) Time Sharing: Sharing of a computing resource among many users by means of multiprogramming and multi-tasking is known as timesharing. By allowing a large number of users to interact concurrently with a single computer, time-sharing dramatically lowered the cost of providing computing capability, made it possible for individuals and organizations to use a computer without owning one, and promoted the interactive use of computers and the development of new interactive applications.
Q.30. Why are Translation Look-aside Buffers (TLBs) important? In a simple paging system, what information is stored in a typical TLB table entry? (8)
30
DC14 System Software and Operating System
Ans:
The implementation of page-table is done in the following way:
• Page table is kept in main memory.
• Page-table base register (PTBR) points to the page table.
• Page-table length register (PRLR) indicates size of the page table.
• In this scheme every data/instruction access requires two memory accesses. One for the page table and one for the data/instruction.
The two-memory access problem can be solved by the use of a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs). A set of associative registers is built of high-speed memory where each register consists of two parts: a key and a value. When the associative registers are presented with an item, it is compared with all keys simultaneously. If the item is found, the corresponding value field is the output.
A typical TLB table entry consists of page# and frame#, when a logical address is generated by the CPU, its page number is presented to a set of associative registers that contain page number along with their corresponding frame numbers. If the page number is found in the associative registers, its frame number is available and is used to access memory. If the page number is not in the associated registers, a memory reference to the page table must be made. When the frame number is obtained, it can be used to access memory and the page number along with its frame number is added to the associated registers.
Q.21. Discuss two main approaches to identify and reuse free memory area in a heap. (6) Ans:
Two popular techniques to identify free memory areas as a result of allocation and de-
allocations in a heap are:
1. Reference count: the system associates a reference count with each memory area to indicate the number of its active users. This number is incremented when a user accesses that area and decrements when user stops using that. The area is free if the reference counts drops to zero. This scheme is very simple to implement however incurs incremental overheads.
2. Garbage collection: In this technique two passes are made over the memory to identify unused areas. In the first pass it traverses all pointers pointing to allocated areas and marks the memory areas that are in use. The second pass finds all unmarked areas and declares them to be free. The garbage collection overheads are not incremental. They are incurred every time the system runs out of free memory to allocate to fresh requests.
Two main approaches to reuse free memory area in a heap are:
First-fit: Allocate the first hole that is big enough. Searching can start either at the beginning of the set of holes or where the previous first-fit search ended. Searching is stopped as soon as a free hole is found that is large enough
Best-fit: Allocate the smallest hole that is big enough; Entire list is searched, unless
ordered by size. This strategy produces the smallest leftover hole.
25
DC14 System Software and Operating System
Q.22. List the steps needed to perform page replacement. Explain the different page replacement policies. Also list out the main requirements, which should be satisfied by a page replacement policy. (8)
Ans:
The steps needed to perform page replacement are:
1.Determine which page is to be removed from the memory.
2.Perform a page-out operation.
3.Perform a page-in operation.
Different page replacement algorithms are briefly described below:
1. First-in, first-out
The first-in, first-out (FIFO) page replacement algorithm is a low-overhead algorithm. Here the operating system keeps track of all the pages in memory in a queue, with the most recent arrival at the back, and the earliest arrival in front. When a page needs to be replaced, the page at the front of the queue (the oldest page) is selected.
Advantage: FIFO is cheap and intuitive.
Disadvantage: 1. Performs poorly in practical application.
2. Suffers from Belady’s anomaly.
2. Not recently used
The not recently used (NRU) page replacement algorithm works on the following principle: when a page is referenced, a referenced bit is set for that page, marking it as referenced. Similarly, when a page is modified (written to), a modified bit is set. At a certain fixed time interval, the clock interrupt triggers and clears the referenced bit of all the pages, so only pages referenced within the current clock interval are marked with a referenced bit. When a page needs to be replaced, the operating system divides the pages into four classes:
• Class 0: not referenced, not modified
• Class 1: not referenced, modified
• Class 2: referenced, not modified
• Class 3: referenced, modified.
The NRU algorithm picks a random page from the lowest category for removal.
3. Optimal page replacement algorithm
The optimal page replacement algorithm (also known as OPT )is an algorithm that works as follows: when a page needs to be swapped in, the operating system swaps out the page whose next use will occur farthest in the future. For example, a page that is not going to be used for the next 6 seconds will be swapped out over a page that is going to be used within the next 0.4 seconds.
Disadvantage: This algorithm cannot be implemented in the general purpose
operating system because it is impossible to compute reliably how long it will be before a page is going to be used.
The main requirements, which should be satisfied by a page replacement policy, are:
1. Non-interference with the program’s locality of reference: The page replacement
policy must not remove a page that may be referenced in the immediate future.
2. The page fault rate must not increase with an increase in the memory allocation for a program.
Q.23. What is an I/O buffer? What is the advantage of buffering? Is buffering always effective? Justify your answer with help of an example. (8)
26
DC14 System Software and Operating System
Ans:
One kind of I/O requirement arises from devices that have a very high character density such as tapes and disks. With these characteristics, it is not possible to regulate communication with devices on a character-by-character basis. The information transfer, therefore, is regulated in blocks of information. Additionally, sometimes this may require some kind of format control to structure the information to suit the device and/or data characteristics. For instance, a disk drive differs from a line printer or an image scanner. For each of these devices, the format and structure of information is different. It should be observed that the rate at which a device may provide data and the rates at which an end application may consume it might be considerably different. In spite of these differences, the OS should provide uniform and easy to use I/O mechanisms. Usually, this is done by providing a I/O buffer. The OS manages this buffer so as to be able to comply with the requirements of both the producer and consumer of data. Basically, the buffers absorb mismatch in the data transfer rates of processor or memory on one side and device on the other.
Q.24. Discuss the different techniques with which a file can be shared among different users. (8)
Ans:
Some popular techniques with which a file can be shared among different users are:
1. Sequential sharing: In this sharing technique, a file can be shared by only one program at a time, that is, file accesses by P1 and P2 are spaced out over time. A
lock field can be used to implement this. Setting and resetting of the lock at file open and close ensures that only one program can use the file at any time.
2. Concurrent sharing: Here a number of programs may share a file concurrently. When this is the case, it is essential to avoid mutual interference between them. There are three categories of concurrent sharing:
a. Immutable files: If a file is shared in immutable mode, none of the sharing programs can modify it. This mode has the advantage that sharing programs are independent of one another.
b. Single image immutable files: Here the changes made by one program are immediately visible to other programs. The Unix file system uses this file- sharing mode.
c. Multiple image mutable files: Here many programs can concurrently update the shared file. Each updating program creates a new version of the file, which is different from the version created by concurrent programs. This sharing mode can only be used in applications where concurrent updates and the existence of multiple versions are meaningful.
Q.25. Differentiate between protection and security. Explain the techniques used for protection of user files. (8)
Ans:
Operating system consists of a collection of objects, hardware or software. Each object has a unique name and can be accessed through a well-defined set of operations. Protection problem - ensure that each object is accessed correctly and only by those processes that are allowed to do so.
Security must consider external environment of the system, and protect it from:
27
DC14 System Software and Operating System
•Unauthorized access.
•malicious modification or destruction
•Accidental introduction of inconsistency.
It is easier to protect against accidental than malicious misuse.
Protection of user files means that file owner/creator should be able to control:
what can be done and by whom. Various categories of access to files are:
•Read
•Write
•Execute
•Append
•Delete
•List
Q.26. What is parsing? Explain any three parsing techniques. (8) Ans
Parsing is the process of analyzing a text, made of a sequence of tokens, to
determine its grammatical structure with respect to a given formal grammer. Parsing is also known as syntactic analysis and parser is used for analyzing a text. The task of the parser is essentially to determine if and how the input can be derived from the start symbol of the grammar.
Following are three parsing techniques:
Top-down parsing - Top-down parsing can be viewed as an attempt to find left-most derivations of an input-stream by searching for parse trees using a top-down expansion of the given formal grammar rules. Tokens are consumed from left to right. Inclusive choice is used to accommodate ambiguity by expanding all alternative right- hand-sides of grammar rules.
Bottom-up parsing - A parser can start with the input and attempt to rewrite it to the
start symbol. Intuitively, the parser attempts to locate the most basic elements, then the elements containing these, and so on. LR parsers are examples of bottom-up parsers. Another term used for this type of parser is Shift-Reduce parsing.
Recursive descent parsing- It is a top down parsing without backtracking. This parsing technique uses a set of recursive procedures to perform parsing. Salient advantages of recursive descent parsing are its simplicity and generality. It can be implemented in any language supporting recursive procedures.
Q.27. Draw the state diagram of a process from its creation to termination, including all transitions, and briefly elaborate every state and every transition. (8)
Ans:
As a process executes, it changes state
• new: The process is being created.
• running: Instructions are being executed.
• waiting: The process is waiting for some event to occur.
• ready: The process is waiting to be assigned to a processor.
• terminated: The process has finished execution.
28
DC14 System Software and Operating System
Q.28. Consider the following system snapshot using data structures in the Banker’s algorithm, with resources A, B, C, and D, and process P0 to P4:
Max Allocation Need Available
P0 A
6 B
0 C
1 D
2 A
4 B
0 C
0 D
1 A B C D A B C D
P1 1 7 5 0 1 1 0 0
P2 2 3 5 6 1 2 5 4
P3 1 6 5 3 0 6 3 3
P4 1 6 5 6 0 2 1 2
3 2 1 1
Using Banker’s algorithm, answer the following questions.
(a) How many resources of type A, B, C, and D are there? (2) (b) What are the contents of the Need matrix? (3) (c) Is the system in a safe state? Why (4) (d) If a request from process P4 arrives for additional resources of (1,2,0,0,), can the Banker’s algorithm grant the request immediately? Show the new system state and other criteria. (7)
Ans:
(a) A-9; B-13;C-10;D-11
(b) Need[i, j]=Max[i,j]-Allocation[i,j] so content of Need matrix is
A B C D
P0 2 0 1 1
P1 0 6 5 0
P2 1 1 0 2
P3 1 0 2 0
P4 1 4 4 4
(c) The system is in a safe state as the processes can be finished in the sequence P0, P2, P4, P1 and P3.
(d) If a request from process P4 arrives for additional resources of (1,2,0,0,), and if this request is granted, the new system state would be tabulated as
follows.
29
DC14 System Software and Operating System
Max Allocation Need Available
A B C D A B C D A B C D A B C D
P0 6 0 1 2 4 0 0 1 2 0 1 1
P1 1 7 5 0 1 1 0 0 0 6 5 0
P2 2 3 5 6 1 2 5 4 1 1 0 2
P3 1 6 5 3 0 6 3 3 1 0 2 0
P4 1 6 5 6 1 4 1 2 0 2 4 4
2
0
1
1
After PO completes P3 can be allocated. 1020 from released 6012 and available
2011(Total 80 23) and
Q.29. Define the following
(i) Process;
(ii) Process Control Block; (PCB) (iii) Multi programming;
(iv)Time sharing. (8)
Ans:
(i) Process: Process is a program in execution; process execution must progress in sequential fashion. A process includes:
• program counter
• stack
• data section
(ii) Process Control Block (PCB): Information associated with each process is stored in Process control Block.
Process state Program counter CPU registers
CPU scheduling information Memory-management information Accounting information
I/O status information
(iii) Multiprogramming: A multiprogramming operating system is system that allows more than one active user program (or part of user program) to be stored in main memory simultaneously. Multi programmed operating systems are fairly sophisticated. All the jobs that enter the system are kept in the job pool. This pool consists of all processes residing on mass storage awaiting allocation of main memory. If several jobs are ready to be brought into memory, and there is not enough room for all of them, then the system must choose among them. A time-sharing system is a multiprogramming system.
(iv) Time Sharing: Sharing of a computing resource among many users by means of multiprogramming and multi-tasking is known as timesharing. By allowing a large number of users to interact concurrently with a single computer, time-sharing dramatically lowered the cost of providing computing capability, made it possible for individuals and organizations to use a computer without owning one, and promoted the interactive use of computers and the development of new interactive applications.
Q.30. Why are Translation Look-aside Buffers (TLBs) important? In a simple paging system, what information is stored in a typical TLB table entry? (8)
30
DC14 System Software and Operating System
Ans:
The implementation of page-table is done in the following way:
• Page table is kept in main memory.
• Page-table base register (PTBR) points to the page table.
• Page-table length register (PRLR) indicates size of the page table.
• In this scheme every data/instruction access requires two memory accesses. One for the page table and one for the data/instruction.
The two-memory access problem can be solved by the use of a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs). A set of associative registers is built of high-speed memory where each register consists of two parts: a key and a value. When the associative registers are presented with an item, it is compared with all keys simultaneously. If the item is found, the corresponding value field is the output.
A typical TLB table entry consists of page# and frame#, when a logical address is generated by the CPU, its page number is presented to a set of associative registers that contain page number along with their corresponding frame numbers. If the page number is found in the associative registers, its frame number is available and is used to access memory. If the page number is not in the associated registers, a memory reference to the page table must be made. When the frame number is obtained, it can be used to access memory and the page number along with its frame number is added to the associated registers.
No comments:
Post a Comment