Paper presentation: OPERATING SYSTEM -1

OPERATING SYSTEM

1. What are the advantages of spooling?

· The spooling operation uses a disk as a very large buffer.

· Spooling is however capable of overlapping I/O operation for one job with processor operations for another job.

2. What are the advantages and disadvantages of batch system?

Advantages of batch system:

· Move much of the work of the operator to the computer

· Increased performance since it was possible for job to start as soon as the previous job finished.

Disadvantages of batch system:

· Turn around time can be large from user standpoint.

· Difficult to debug program.

· A job could enter an infinite loop.

· A job could corrupt the monitor, thus affecting pending jobs.

· Due to lack of protection scheme, one batch job can affect pending jobs.

3. What are the features of multi-processor systems?

1. If one processor fails, then another processor should retrieve the interrupted process state so that execution of the process can continue.

2. The processors should support efficient context switching operation.

3. Multiprocessor system supports large physical address space & large virtual address space.

4. The IPC mechanism should be provided and implemented in hardware as it becomes efficient and easy.

4. What are the difficulties in distributed OS?

1. There are no current commercially successful examples.

2. Protocol overhead can dominate computation costs.

3. Hard to build well.

4. Probably impossible to build at the scale of the internet.

5. Explain the characteristics of suspended process?

· Suspended process is not immediately available for execution.

· The process may or may not be waiting on an event.

· For preventing the execution, process is suspended by OS, parent process, process itself and an agent.

· Process may not be removed from the suspended state until the agent orders the removal.

6. What are the reasons for process suspension?

Swapping
Timing
Interactive user request
Parent process request

Swapping: OS needs to release required main memory to bring in a process that is ready to execute.

Timing: Process may be suspended while waiting for the next time interval.

Interactive user request: Process may be suspended for debugging purpose by user.

Parent process request: To modify the suspended process or to coordinate the activity of various descendants.

7. Explain whether following transitions between process states are possible or not. If possible, give the example?

1. Running - Ready 2.Running – Waiting

3. Waiting – Running 4.Running – Terminated

Ans:

For changing the state from running to ready is possible. For example, when a process time quantum expires.
Running – Waiting is also possible. When a process issues an I/O request.
Waiting – Running is not possible. From waiting state, the process goes to the ready state then running.
Running – Termination is possible, when a process terminates itself.

8. What are the drawbacks of semaphore?

· They are essentially shared global variables.

· Access to semaphores can come from anywhere in a program.

· There is no control or guarantee of proper usage.

· There is no linguistic connection between the semaphore and the data to which the semaphore controls access.

· They serve two purposes, mutual exclusion and scheduling constraints.

9. What are the drawbacks of monitors?

Major weakness of monitors is the absence of concurrency if a monitor encapsulates the resources, since only one process can be active within a monitor at a time.
There is the possibility of deadlocks in the case of nested monitors calls.
Monitor concept is its lack of implementation most commonly used programming languages.
Monitors cannot easily be added if they are not natively supported by the language.

10. What are the drawbacks of software solutions?

Complicated to program.
Busy waiting is possible.
It would be more efficient to block processes that are waiting.
Makes difficult assumptions about the memory system.

11. What are the advantages of test & set instruction?

It is simple and easy to verify.
It is applicable to any number of processes.
It can be used to support multiple critical section.

12. What are the disadvantages of test & set instruction?

Busy waiting is possible.
Starvation is also possible.
There may be deadlock.

13. Compare the long term, middle term and short term schedulers?

Sr.no	Long term scheduler	Short term scheduler	Medium term scheduler
1.	It is job scheduler.	It is CPU scheduler.	It is swapping.
2.	Speed is less than short term scheduler.	Speed is very fast.	Speed is in between both.
3.	It controls the degree of multiprogramming	Less control over degree of multiprogramming	Reduce the degree of multiprogramming
4.	Absent or minimal in time sharing system.	Minimal in time sharing system.	Time sharing system use medium term scheduler.
5.	It selects processes from pool and loads them into memory for execution.	It select from among the processes that are ready to execute.	Process can be reintroduced into memory and its execution can be continued.
6.	Process state is (New to Ready)	Process state is (Ready to Running)	----
7.	Select a good process, mix of I/O bound and CPU bound.	Select a new process for a CPU quite frequently.	----

14. Explain the comparison between FCFS and Round Robin (RR) method?

Sr.no.	FCFS	Round Robin
1.	FCFS decision made is non preemptive.	RR decision made is preemptive.
2.	It has minimum overhead.	It has low overhead.
3.	Response time may be high.	Provides good response time for short processes.
4.	It is troublesome for time sharing system.	It is mainly designed for time sharing system.
5.	The workload is simply processed in the order of arrival.	It is similar like FCFS but uses time quantum.
6.	No starvation in FCFS.	NO starvation in RR.

15. Consider following process, with the CPU burst time given in milliseconds.

Process	Burst time	Priority
P1	10	3
P2	1	1
P3	2	3
P4	1	4
P5	5	2

Processes are arrived in p1, p2, p3, p4, p5 order of all at time 0.

1. Draw Gantt charts to show execution using FCFS, SJF, nonpreemptive priority (small priority number implies higher priority) and RR (quantum = 1) scheduling.

2. Also calculate turn around time for each scheduling algorithms.

3. What is the waiting time of each process for each one of the above scheduling algorithm?

Ans:

1) Gantt chart

a) FCFS

b) SJF

Nonpreemptive priority

d) RR (quantum = 1)

2) Turn around time = burst time + waiting time

a) for FCFS

= (10+11+13+14+19)/5

= 67/5

= 13.4

b) for SJF

= (1+2+4+9+19) / 5

=35 / 5

c) for nonpreemptive priority

= (1+6+16+18+19) / 5

= 60 / 5

=12

d) for RR

= (19+2+7+4+14) / 5

= 46 / 5

= 9.2

3) waiting time

a) for FCFS

Process	Waiting time
P1	0
P2	10
P3	11
P4	13
P5	14

b) for SJF

Process	Waiting time
P1	9
P2	0
P3	2
P4	1
P5	4

c) for nonpreemptive priority

Process	Waiting time
P1	6
P2	0
P3	16
P4	18
P5	1

d) For RR method

Process	Waiting time
P1	9
P2	1
P3	5
P4	3
P5	9

16. For the following example calculate average turnaround time and average waiting time for the following algorithms.

1. FCFS

2. Preemptive SJF

3. Round robin (1 time unit)

Process	Arrival time	Burst time
P1	0	8
P2	1	4
P3	2	9
P4	3	5

Ans: 1. for FCFS

a) Gantt chart:

b) waiting time:

Process	Waiting time
P1	0
P2	7
P3	10
P4	18

c) Average waiting time = (0+7+10+18) / 4

= 35 / 4 = 8.75

d) Turn around time: burst time + waiting time

Process	Turn around time
P1	8+0=8
P2	4+7=11
P3	9+10=19
P4	5+18=23

e) average turn around time = (8+11+19+23) /4

=61/4 = 15.25

2. for preemptive SJF

a) Gantt chart:

b) Waiting time:

Process	Waiting time
P1	9
P2	0
P3	15
P4	2

c) Average waiting time = (9+0+15+2)/4

= 26/4 = 6.5

d) Turn around time:

Process	Turn around time
P1	8+9=17
P2	4+0=4
P3	9+15=24
P4	5+2=7

e) Average turnaround time = (17+4+24+7)/4

=52/4 =13

3) Round Robin (1 unit time)

a)Gantt chart:

b) Waiting time:

Process	Waiting time
P1	16
P2	9
P3	15
P4	11

c) Average waiting time = (16+9+15+11) / 4

= 51/4 = 12.75

d)turnaround time:

Process	Turnaround time
P1	8+16=24
P2	4+9=13
P3	9+15=24
P4	5+11=16

e) Average turnaround time = (24+13+24+16) / 4

= 77/4 = 19.25

17. For the process listed below, draw a Gantt chart using priority scheduling. A larger priority number has higher priority.

a) Preemptive

b) Nonpreemptive

Process	Arrival time	Burst time	Priority
P1	0.0	6	4
P2	3.0	5	2
P3	3.0	3	6
P4	6.0	5	3

Ans a) preemptive priority:

Gantt chart

b) Nonpreemptive priority:

Gantt chart:

18. What are the disadvantages of deadlock avoidance?
1. The maximum resource requirement for each process must be stated in advance.

2. There must be a fixed number of resources to allocate and a fixed number of processes.

3. The processes under consideration must be independent.

19. State the weakness of banker’s algorithm?

1. It requires that there be a fixed number of resources to allocate.

2. The algorithm requires that users state their maximum needs (request) in advance.

3. Number of users must remain fixed.

4. The algorithm requires that the bankers grant all requests with in a finite time.

5. Algorithm requires that process returns all resource within a finite time.

20. What are the advantages & disadvantages of deadlock prevention?

ADVANTAGES:

1 no preemption necessary

2. Works well for processes that perform a single burst of activity.

3. Needs no run-time computation.

4. feasible to enforce via compile time check.

Disadvantages:

1. Inefficient.

2. delays process initiation

3. subject to cyclic restart

4. disallows incremental resource request

21. Explain the comparison of scheduling algorithm?

Algorithm	Policy type	Used in	Advantages	Disadvantages
FCFS	Non preemptive	Batch	1.easy to implement 2.Minimum overhead	1.unpredicable turnaround time 2.average waiting is more
RR	Preemptive	Interactive	1.provides fair CPU allocation 2.provides reasonable response times to interactive users	1.requires selection of good time slice.
Priority	Non preemptive	Batch	1.ensures fast completion of important jobs	1.indefinite postponement of some jobs 2.faces starvation problem
SJF	Non preemptive	Batch	1.minimizes average waiting time 2.SJF algorithm is optimal	1.indefinite postponement of some jobs 2.cannot be implemented at the level of short term scheduling 3.difficulty is knowing the length of the next CPU request
Multilevel queues	preemptive or non preemptive	Batch/interactive	1.fexible 2.gives fair treatment to CPU bound jobs	1.overhead incurred by monitoring of queues

22. What are advantages and disadvantages of deadlock detection?

Advantages:

1. never delays process initiation

2. Facilitates online handling.

Disadvantages:

Inherent preemption losses.

23. what are the advantages and disadvantages of deadlock avoidance?

Advantages:

no preemption necessary

Disadvantages:

1. Future resource requirements must be known

Processes can be blocked for long periods.

24. Give the process resource usage and availability, draw the resource allocation graph?

Process	Current allocation	Outstanding request	Available resource
Process	R1	R2	R3	R1	R2	R3	R1	R2	R3
P1	2	0	0	1	1	0	0	0	0
P2	3	1	0	0	0	0
P3	1	3	0	0	0	1
P4	0	1	1	0	1	0

Ans: Resource-allocation graph:

25. Explain logical verses physical address space?

Logical address is generated by CPU. Physical address is the address of main memory and it is loaded into the memory address register.

· Compile-time and load-time address-binding methods generate same logical address and physical addresses.

· Execution-time address-binding scheme results in different logical and physical addresses.

· Generally logical address is referred as a virtual address.

· Logical address space-set of all logical addresses generated by program is a logical address space.

· Physical address space is a set of all physical addresses corresponding to these logical addresses.

· Memory management unit mapping at run-time from virtual to physical addresses is done by a hardware device. This hardware device is MMU.

· Relocation register is also called base register.

· Value of the relocation register is added to every address generated by a user process at the time it is sent to memory.

· User program never sees the real physical addresses.

26. Explain the advantages and disadvantages of contiguous memory allocation?

Advantages:

simple to implement
does not require expertise to understand and use such a system

Disadvantages:

memory is not fully utilized
poor utilization of processors
user’s process (job) being limited to the size of available main memory

27. Write the advantages and disadvantages of paging?

Advantages:

paging eliminates fragmentation
support higher degree of multiprogramming
paging increases memory and processor utilization
Compaction overhead required for the re locatable partition scheme is also eliminated.

Disadvantages:

page address mapping hardware usually increases the cost of the computer
memory must be used to store the various tables like page table, memory map table etc
some memory will still be unused if the number of available block is not sufficient for the address spaces of the jobs to be run

28.given memory partitions of 100K, 500K, 200K, 300K and 600K (in order) how would each of the first fit, best fit and worst fit algorithms place processes of 212K, 417K, 112K and 426K (in order) ? which algorithm makes the most efficient use of memory.

Ans:

first fit:

2.worst fit:

3.best fit:

29. Write the advantages and disadvantages of paging?

Advantages:

segmentation eliminates fragmentation
it provides virtual memory
allows dynamic segment growth
segmentation assists dynamic linking
segmentation is visible

Disadvantages:

maximum size of a segment is limited by the size of main memory
difficulty to manage variable size segments on secondary storage

30. Explain advantages and disadvantages of segmentation with paging?

Advantages

Combine all advantages of paging and segmentation.

Disadvantages:

it increases hardware cost
it increases processor overhead
Dangers of thrashing

31. Write the difference between segmentation and paging?

Sr.no	Segmentation	Paging
1.	Program is divided into variable size segments.	Program is divided into fixed size page.
2.	User (or compiler) is responsible for dividing the program into segments.	Division into pages is performed by the operating system.
3.	Segmentation is slower than paging.	Paging is faster than segmentation.
4.	Segmentation is visible to the user.	Paging is invisible to the user.
5.	Segmentation eliminates internal fragmentation	Paging suffers from internal fragmentation
6.	Segmentation suffers from external fragmentation	There is no external fragmentation
7.	Processor uses page number, offset to calculate absolute address	Processor uses segment number, offset to calculate absolute address
8.	OS maintain a list of free holes in main memory	OS must maintain a free frame list.

32. Explain the advantages and disadvantages of demand paging?

Advantages:

large virtual memory
more efficient use of memory
Unconstrained multiprogramming. There is no limit on degree of multiprogramming.

Disadvantages:

Number of tables and amount of processor over head for handling page interrupts are greater than in the case of the simple paged management technique.
Due to the lack of an explicit constraint on jobs address space size.

33. Consider the following snapshot of a system

processes	Allocation				Max				Available
processes	A	B	C	D	A	B	C	D	A B C D
P0	0	0	1	2	0	0	1	2	1 5 2 0
P1	1	0	0	0	1	7	5	0
P2	1	3	5	4	2	3	5	6
P3	0	6	3	2	0	6	5	2
P4	0	0	1	4	0	6	5	6

Answer the following questions using the banker’s algorithm.

a). what is the content of the matrix need?

b) is the system is a safe state?

c) if the request from process p1 arrives for (0,4,2,0) can the request be granted immediately?

Ans:

a) Content of the needed matrix is

Process	A	B	C	D
P0	0	0	0	0
P1	0	7	5	0
P2	1	0	0	2
P3	0	0	2	0
P4	0	6	4	2

b) System is in safe state because resources available (1,5,2,0),

c) Request from process p1 can be granted immediately. Request is (0,4,2,0) and available resource is (1,5,2,0).

34. Paging system consists of physical memory 2²⁴bytes, pages of logical address space is 256. Page size of 210 bytes, how many bits are in a logical address?

Ans:

Logical address space = 256 = 2⁸

Page size = 2¹⁰ bytes

So, total logical address space =2⁸ * 2¹⁰ = 2¹⁸ bytes

For 2¹⁸ byte address space – 18 bit address is required

35. Explain the comparison of demand paging with segmentation?

Sr.no	Segmentation	Demand paging
1	Segments may of different size	Pages are of same size.
2.	Segments can be shared.	Pages can not be shared.
3.	It allows dynamic growth of segments.	Page size is fixed.
4.	Segment map table indicates the address of each segment in memory.	Page map table keeps track of pages in memory.
5.	Segments are allocated to the program while compilation.	Pages are loaded in memory on demand.
6.	Provides virtual memory.	Also provides virtual memory.

36. On a system using simple segmentation, compute the physical address for each of the logical addresses, logical address is given in the following segment table. If the address generates a segment fault, indicates so.

Segment	Base	Length
0	330	124
1	876	211
2	111	99
3	498	302

a) 0, 99 b) 2, 78 c) 1,265 d) 3,222 e) 0,111

Ans: a) 0, 99

Offset = 99

Segment length = 124

Segment = 0

· Offset 99 is less than segment length 124.

· Starting location of segment 0 is start from 330.

· Physical address = offset + segment base

= 99 + 330 = 429

b) 2, 78

Segment = 2

Offset = 78

Segment length = 99

· Offset 78 is less than segment length 99.

· Starting location of segment 2 is 111.

· Physical address = offset + segment base

= 111 + 78 = 189

c) 1,265

Segment = 1

Offset = 265

Segment length = 211

· Offset 265 is greater than segment length 211.

· This address results in a segment fault.

d) 3, 222

Segment = 3

Offset = 222

Segment length = 302

· Offset 222 is less than segment length 302.

· Starting location of segment 3 is 498.

· Physical address = offset + segment base

= 498 + 222 = 720

e) 0,111

Segment = 0

Offset = 111

Segment length = 124

· Offset 111 is less than segment length 124.

· Starting location of segment 0 is 330.

· Physical address = offset + segment base

= 330 + 111 = 441

37. System using a paging and segmentation, the virtual address space consists of up to 8 segments where each segment can be up to 2²⁹ byte long. The hardware pages each segment into 256 bytes pages. How many bits in the virtual address specify the

1) Segment number?

2) Page number ?

3) Offset within page?

4) Entire virtual address?

Ans: 1) segment number: virtual address space consists up to 8 segments. So 8 = 2³

Since 3 bits are needed to specify segment number.

2) Page number: Hardware pages each segment into 256 byte pages. So

256 = 2⁸ byte page

Size of segment is 229 bytes.

Since 2²⁹ / 2⁸ = 2^29-8= 2²¹ = 21 pages

Since 21 bits are required to specify the page number.

3) Offset within the page: for 28 byte page, 8 bits are needed.

4) Entire virtual address:

= segment number + page number + offset

= 3 + 21 + 8 = 32.

38) Explain the advantages and disadvantages of tree structured directory?

Advantages:

1. It allows users to create their own subdirectory.

2. User can access the files of other users.

3. It allows users to define their own search paths.

Disadvantages:

1. Special system calls are required to create & delete directories.

2. It prohibits the sharing of files and directories.

3. Path to the file is longer than the two level directories.

39) Explain the characteristics, advantages, and disadvantages of contiguous file allocation?

Characteristics:

It supports variable size portions.
Pre-allocation is required.
It requires only single entry for a file.
Allocation frequency is only once.

Advantages:

It supports variable size portion.
Easy to retrieve single block.
Accessing a file is easy.
It provides good performance.

Disadvantages:

It suffers from external fragmentation.
Pre-allocation is required.

40) Explain the characteristics, advantages, and disadvantages of linked allocation?

Characteristics:

1. It supports fixed size portions.

2. Pre-allocation is possible.

3. File allocation table size is one entry for a file.
4. Allocation frequency is low to high.

Advantages:

There is no external fragmentation.
It is never necessary to compact disk space.
Pre-allocation is not required.

Disadvantages:

Files are accessed only sequentially.
Space required for pointers.
Reliability is not good.
Can not support direct access.

41) Explain the advantages, and disadvantages of indexed allocation?

Advantages:

It supports sequential and direct access.
No external fragmentation.
Faster than other two methods.
It supports fixed and variable size blocks.

Disadvantages:

Indexed allocation does suffer wasted space.
Pointer overhead is generally greater.

42) Explain the comparison between contiguous & linked file allocation method?

Parameter	Contiguous	Linked
1. pre-allocation	Necessary	Possible
2.fixed or variable size portion	Variable	Fixed blocks
3.FAT size	One entry	One entry
4. time to allocate	Medium	Long
5. allocation frequency	Once	Low or high
6. fragmentation	Suffer from external fragmentation	Does not suffer from external fragmentation.
7. file access	Randomly	Sequentially

43) The operating system contains 3 resources, the number of instance of each resource type are 7,7,10. The current resource allocation state is as shown below.

Process	Current allocation			Maximum need
Process	R1	R2	R3	R1	R2	R3
P1	2	2	3	3	6	8
P2	2	0	3	4	3	3
P3	1	2	4	3	4	4

1. is the current allocation in a safe state?

2. can the request made by process p1 (1 1 0) be granted?

Ans: 1) first find the available resource in the system.

Available: = Number of instance - sum of allocation

Process	Current allocation
Process	R1	R2	R3
P1	2	2	3
P2	2	0	3
P3	1	2	4
	5	4	10

Available = (7 7 10) – (5 4 10)

Available resource = (2 3 0)

Content of need matrix is

Process	Need
Process	R1	R2	R3
P1	1	4	5
P2	2	3	0
P3	2	2	0

Safe sequence < p3, p2, p1>

The system is in safe state.

2) process p1 request (1 1 0), this request is less than need. Need for process p1 is (1 4 5). Available resource is ( 2, 3, 0) and request is (1 1 0).

Request < available

( 1 1 0) < (2 3 0)

Process	Need
Process	R1	R2	R3
P1	0	3	5
P2	2	3	0
P3	2	2	0

after allocating (1 1 0) to process p1 the need becomes as follows.

And available resources is (1 2 0).

Need of any process is never satisfied after granting the process p1 request (1 1 0). So the system will be blocked. Therefore request of process p1 (1 1 0) is cannot be granted.

44) consider the following snapshot

Process	Allocation		Max		Available
Process	R1	R2	R1	R2	R1	R2
P1	1	2	4	2	1	1
P2	0	1	1	2
P3	1	0	1	3
P4	2	0	3	2

Whether the system is safe state or unsafe?

Ans: first calculated need

Need = max – allocation

Process	Need
Process	R1	R2
P1	3	0
P2	1	1
P3	0	3
P4	1	2

System is in safe state with safe sequence < p2, p4, p1, p3>

System will complete its operation in this sequence.

45) Consider the snapshot.

Process	Allocation		Max		Available
Process	R1	R2	R1	R2	R1	R2
P1	7	2	9	5	2	1
P2	1	3	2	6
P3	1	1	2	2
P4	3	0	5	0

1) Calculate content of need matrix.

2) System is safe or unsafe.

Ans: 1) need = max – allocation

Process	Need
Process	R1	R2
P1	2	3
P2	1	3
P3	1	1
P4	2	0

2) System is unsafe state. Resources are not available for processes p1 and p2 to complete their operation.

46. What is meant by “Hard real systems and soft real systems?

Hard real systems guarantee that critical tasks complete on time. In soft real system a critical task get priority over tasks and remains that priority until it complete.

47. What are the main differences between operating systems for mainframe computers and personal computers?

Generally, operating systems for batch systems have simpler requirements than personal computers. Batch systems do not have to be concerned with interacting with a user as much as personal computer. As a result, an operating system for a PC must be concerned with response time for an interactive user. Batch systems do not have such requirements. A pure batch system also may have not to handle time sharing, whereas an operating system must switch rapidly between different jobs.

48. What is the main advantage of the layered approach to system design? What are the disadvantages of using the layered approach?

As in all cases of modular design, designing an operating system in a modular way has several advantages. The system is easier to debug and modify because changes affect only limited sections of the system rather than touching all sections of the operating system. Information is kept only where it is needed and is accessible only within a defined restricted area, so any bugs affecting that data must be limited to a specific module or layer.

49. What are the three main purposes of an operating system?

1) To provide an environment for a computer user to execute programs on computer hardware in a convenient and efficient manner.

2) To allocate the separate resources of the computer as needed to solve this problem given. The allocation process should be as fair and efficient as possible.

3) As a control program it serves 2 major functions:

I. Supervision of the execution of user programs to prevent errors and improper use of the computer

II. Management of the operation and control of I/O devices.

50. What is the main advantage of multiprogramming?

Multiprogramming makes efficient use of the CPU by overlapping the demands for the CPU and I/O devices from various users. It attempts to increase CPU utilization by always having something for the CPU to execute.

51. Why are distributed systems desirable?

Distributed systems can provide resources, sharing, computation speeding, increased reliability, and the ability to communicate with remote sites.

52. What is the main difficulty that a programmer must overcome in writing an operating system for a real-time environment?

The main difficulty is keeping the operating system within the fixed time constraints of a real-time system. If the system does not complete a task in a certain time frame, it may cause a breakdown of the entire system it is running. Therefore when writing an operating system in a real-time system, the writer must be sure that his scheduling schemes don’t allow response time to exceed the time constraint.

53. List the advantages of Interprocess messages?

1. Processes need not define a complex protocol for communication.

2. Process does not need to guess the size of shared data area required for Interprocess communication.

3. The OS takes responsibility to block the process executing a receiver when no message exist for it.

4. The process may exist in different computer systems.

54. List the features of process scheduling in multiprogramming scheduler?

Features:

1) A single list of process control blocks is maintained in the system.

2) Process control blocks in the list are organized in the order of reducing priorities.

3) The process control blocks of newly created process is entered in the list in accordance with its priority.

4) The process control block is removed from the list when it terminates.

5) The scheduler scans the process control block list and schedules the first ready process.

55. Explain the features of process scheduling in time sharing system?

Features:

1) Process priority does not depend on the nature of the processes.

2) Processes are scheduled in the round robin manner.

3) A running process is pre-empted when its time slice elapses.

4) Processes may be swapped out of memory.

56. What information is saved and restored during a context switch?

Context switch requires saving the state of the old process and loading the saved state for the new process. Process state minimally includes current contents of registers, program counter, stack pointer, file descriptors, etc.

57. List the features of independent process?

A process is independent if it cannot affect or be affected by other processes executing in the system. This type of processes has following features:

· Its state is not shared in any way be any other process.

· Its execution is deterministic, i.e. the results of execution depend only on the input values.

· Its execution is reproducible i.e. the results of execution will always be the same for the same input.

· Its execution can be stopped and restarted without any negative effect.

58. List the characteristics of cooperating process?

Cooperating processes can affect or be affected by other processes executing in the system. They are characterized by:

· Their states are shared by other processes

· Its execution is not deterministic, i.e. the results of execution depend on relative execution sequence and can not be predicted in advance

· Its execution is irreproducible, i.e. the results of execution are not always the same for the same input.

59. What advantage is there in having different time-quantum sizes on different levels of a multilevel queuing system?

Processes that need more frequent servicing, for instance, interactive processes such as editors, can be in queuing with a small time quantum. Processes switch no need for frequent servicing can be in queue with a larger quantum, requiring fewer context switches to complete the processing, and thus making more efficient use of the computer.

60. Explain the difference in degree to which the following scheduling algorithm discriminate in favour of short processes?

1. FCFS

2. RR

3. Multilevel feedback queue.

FCFS: discriminates against short jobs since any short jobs arriving after long jobs will have a longer waiting time.

RR: treats all jobs equally so that short jobs will be able to leave the system faster since they will finish first.

MFQ: work similar to the RR algorithm – they discriminate favourably toward short job.

61. A CPU scheduling algorithm determines an order for the execution of its scheduled processes. Given n processes to be scheduled on one processor, how many possible different schedules are there? Give a formula in terms of n?

n! (n factorial = n * n -1* n – 2……….*2*1).

62. Define the difference between preemptive and non preemptive scheduling?

Preemptive scheduling allows a process to be interrupted in the middle of its execution, taking the CPU away and allocating it to another process. Nonpreemptive scheduling ensures that a process relinquishes control of the CPU only when it finishes with its current CPU burst.

63. What is the difference between a preemptive scheduler and a time-sliced one?

For a preemptive scheduler, process with highest priority runs first.

Unless there is a process with a higher priority is waiting, the current process runs until completion. Time slice is CPU based. It divides CPU time into equal time slots and each process gets one time slot to run.

64. Is a nonpreemptive scheduling algorithm a good choice for an interactive system?

No. once the process gains control of the CPU it returns control until it blocks or it terminates. A process could execute for an extended period of time doing unaccepted response time.

65. What is a Gantt chart?

A two dimensional chart that plots the activity of a unit on the Y-axis versus the time on the X-axis. The chart quickly represents how the activities of the units are serialized.

66. What is starvation problem in CPU scheduling?

A phenomenon in many resources allocation strategies in which some set of processes are perpetually ignored because of their priority is not as high as that of other processes.

67. Can the OS detect process starvation? If so, how? If not, what can it do to avoid it?

No; the best the OS can do is verify that a process has been blocked for a very long time – which need not denote starvation. However, it is also the one thing that the OS can do to prevent starvation: have an aging policy that eventually gives very high priority to jobs that have been blocked a long time, so that jobs that need fewer resources and might otherwise pass head will be denied the resources they need until the OS has accumulated enough free resources to fulfilled the request of the high-priority job.

68. What is a spin – lock?

When a process is in its critical section, any other process that tries to enter its critical section must loop continuously in the entry code of critical section until the first one gets out.

69. What is an alternative to spin locking?

Put the process in a wait queue, so it doesn’t waste CPU cycles and allow it to sleep until the block is released.

70. What is a race condition?

A condition in which the behaviour of two or more processes depends on the relative rate at which each process execute its programs. A race condition can cause a pair of processes to violate a critical section or deadlock.

71. Define a condition variable?

A structure that may appear within a monitor, global to all procedure within the monitor that can have its value manipulates by the wait, signal and queue operation.

72. List three examples of deadlocks that are not related to a computer system environment?

· Two cars crossing a single-lane bridge from opposite directions.

· A person going down a ladder while another person is climbing up the ladder.

· Two trains traveling towards each other on the same track.

· Two carpenters who must pound nails. There is a single hammer and a single bucket of nails. Deadlock occurs if one carpenter has the hammer and the other carpenter has the nails.

73. Distinguish between internal and external fragmentation?

Internal fragmentation is the area in a region or a page that is not used by the process it is allocated to. The space is wasted until the process terminates. External fragmentation occurs when there is enough free space to satisfy a request for memory, but none of the free holes between processes in memory is large enough to satisfy the request.

74. Name the difference between logical and physical addresses?

A logical address does not refer to an actual existing address ; rather, it refers to an abstract address in an abstract address space. Contrast this with physical address that refers to an actual physical address in memory. A logical address is generated by the CPU and is transferred into a physical address by the memory management unit (MMU). Therefore, physical addresses are generated by the MMU.

75. Why page size always power of 2?

Recalling that paging is implemented by breaking up an address into a page and offset number. It is most efficient to break the address to calculate the page number and offset. Because each bit position represents a power of 2, splitting an address between bits results in a page size that is a power of 2.

76. Consider a logical address space of eight 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?

Ans:

a) Logical address: 13 bits.

b) Physical address: 15 bits.

77. Under what circumstance do page faults occur? Describe the actions taken by the operating system when a page fault occurs?

A page fault occurs when an access to a page that has not been brought into main memory takes place. The operating system verifies the memory access, aborting the program if it is invalid. If it is valid, a free frame is located and I/O is requested to read the needed page into a free frame. Upon completion of I/O, the process table and page table are updated and the instruction is restarted.

78. Assume that you have a page-reference string for a process with m frames (initially all empty). The page-reference string has length p; n distinct page numbers occur in it. Answer these questions for any page replacement algorithm:

a) What is a lower bound on the number of page fault?

b) What is an upper bound on the number of page faults?

Ans:

a) n

b) p

79. An operating system supports a paged virtual memory, using a central processor with a cycle time of 1 microsecond. It costs an additional 1 microsecond to access a page other than the current one. Pages have 1000 words, and the paging device is a drum that rotates at 3000 revolutions per minute and transfers 1 million words per second. The following statistical measurements were obtained from the system.

· 1 percent of all instructions executed accessed another page other than the current page.

· Of the instructions that accessed another page, 80 percent accessed a page already in memory.

· When a new page was required, the replaced page was modified 50 percent of the time.

Calculate the effective instruction time on this system, assuming that the system is running one process only and that the processor is idle during drum transfers.

Ans:

Effective access time = 0.99 * (1sec + 0.008 * (2sec) +0.002 * (10000sec + 1000 sec) + 0.001 * (10000sec + 1000sec))

= (0.99+0.016+22.0+11.0) sec

= 34 sec

80. Consider a system that supports the strategies of contiguous, linked, and indexed allocation. What criteria should be used in deciding which strategy is best utilized for a particular file?

· Contiguous: if file is usually accessed sequentially, if file is relatively small.

· Linked: if file is large and usually accessed sequentially.

· Indexed: if file is large and usually accessed randomly.

81. Explain the purpose of the “OPEN” and “CLOSE” operation UNIX?

1) The OPEN operation informs the system that the named file is about to become active.

2) The CLOSE operation informs the system that the named file is no longer in active use by the user who issued the close operation.

82. Consider a system that supports 5000 users. Suppose that you want to allow 4990 of these users to be able to access one file.

a) How would you specify this protection scheme in UNIX?

b) Could you suggest another protection scheme that can be used more effectively for this purpose?

Ans:

a) there are two methods for achieving this:

· Create an access control list with the names of all 4990 users.

· Put these 4990 users in one group and set the group access accordingly. This scheme cannot always be implemented since user groups are restricted by the system.

b) The universal access to files applies to all users unless their name appears in the access-control list with different access permission.

With this scheme you simply put the names of the remaining ten users in the access control list but with no access privileges allowed.

Paper presentation

Search This Blog

Tuesday 22 February 2011

OPERATING SYSTEM -1

No comments:

baby