On a system with paging, a process cannot access memory that it does not own; why? How could the operating system allow access to other memory? Why should it or should it not?

An address on a paging system is a logical page number and an offset. The physical page is found by searching a table based on the logical page number to produce a physical page number. Because the operating system controls the contents of this table, it can limit a process to accessing only those physical pages allocated to the process. There is no way for a process to refer to a page it does not own because the page will not be in the page table. To allow such access, an operating system simply needs to allow entries for non-process memory to be added to the process’s page table. This is useful when two or more processes need to exchange data—they just read and write to the same physical addresses (which may be at varying logical addresses). This makes for very efficient interprocess communication.

Why are page sizes always powers of 2?

Recall that paging is implemented by breaking up an address into a page and offset number. It is most efficient to break the address into X page bits and Y offset bits, rather than perform arithmetic on 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.

What is the cause of thrashing? How does the system detect thrashing? Once it detects thrashing, what can the system do to eliminate this problem?

Thrashing is caused by under allocation of the minimum number of pages required by a process, forcing it to continuously page fault. The system can detect thrashing by evaluating the level of CPU utilization as compared to the level of multiprogramming. It can be eliminated by reducing the level of multiprogramming.

Under what circumstances 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 the free frame. Upon completion of I/O, the process table and page table are updated and the instruction is restarted.

Explain Segmentation with paging?

Segments can be of different lengths, so it is harder to find a place for a segment in memory than a page. With segmented virtual memory, we get the benefits of virtual memory but we still have to do dynamic storage allocation of physical memory. In order to avoid this, it is possible to combine segmentation and paging into a two-level virtual memory system. Each segment descriptor points to page table for that segment. This give some of the advantages of paging (easy placement) with some of the advantages of segments (logical division of the program).

Define Demand Paging, Page fault interrupt, and Trashing?

Demand Paging: Demand paging is the paging policy that a page is not read into memory until it is requested, that is, until there is a page fault on the page.

Page fault interrupt: A page fault interrupt occurs when a memory reference is made to a page that is not in memory.

The present bit in the page table entry will be found to be off by the virtual memory hardware and it will signal an interrupt.

           Trashing: The problem of many page faults occurring in a short time, called “page                 thrashing,”

What is fragmentation? Different types of fragmentation?

Fragmentation occurs in a dynamic memory allocation system when many of the free blocks are too small to satisfy any request.

External Fragmentation: External Fragmentation happens when a dynamic memory allocation algorithm allocates some memory and a small piece is left over that cannot be effectively used. If too much external fragmentation occurs, the amount of usable memory is drastically reduced.

Total memory space exists to satisfy a request, but it is not contiguous

Internal Fragmentation: Internal fragmentation is the space wasted inside of allocated memory blocks because of restriction on the allowed sizes of allocated blocks.

Allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used

Reduce external fragmentation by compaction

o   Shuffle memory contents to place all free memory together in one large block.

o   Compaction is possible only if relocation is dynamic, and is done at execution time.

 

What are the different Dynamic Storage-Allocation methods?

How to satisfy a request of size n from a list of free holes?

First-fit:  Allocate the first hole that is big enough.

Best-fit:  Allocate the smallest hole that is big enough; must search entire list, unless ordered by size. It produces the smallest leftover hole.

Worst-fit:  Allocate the largest hole; must also search entire list.  Produces the largest leftover hole.

First-fit and best-fit are better than worst-fit in terms of speed and storage utilization.

What are Dynamic Loading, Dynamic Linking and Overlays?

Dynamic Loading:

o   Routine is not loaded until it is called

o   Better memory-space utilization; unused routine is never loaded.

o   Useful when large amounts of code are needed to handle infrequently occurring cases.

o   No special support from the operating system is required implemented through program design.

Dynamic Linking:

Linking postponed until execution time.

o   Small piece of code, stub, used to locate the appropriate memory-resident library routine.

o   Stub replaces itself with the address of the routine, and executes the routine.

o   Operating system needed to check if routine is in processes’ memory address.

o   Dynamic linking is particularly useful for libraries.

Overlays:

·         Keep in memory only those instructions and data that are needed at any given time.

·         Needed when process is larger than amount of memory allocated to it.

Implemented by user, no special support needed from operating system, programming design of overlay structure is complex.

Binding of Instructions and Data to Memory?

Address binding of instructions and data to memory addresses can happen at three different stages

     Compile time:  If memory location known a priori, absolute code can be generated; must recompile code if starting   location changes.

     Load time:  Must generate relocatable code if memory location is not known at compile time.

     Execution time:  Binding delayed until run time if the process can be moved during its execution from one memory segment to another.  Need hardware support for address maps (e.g., base and limit registers). 

Difference between Logical and Physical Address Space?

·         The concept of a logical address space that is bound to a separate physical address space is central to proper memory management.

Logical address – generated by the CPU; also referred to as virtual address.

Physical address – address seen by the memory unit.

·         Logical and physical addresses are the same in compile-time and load-time address-binding schemes; logical (virtual) and physical addresses differ in execution-time address-binding scheme

Recovery from Deadlock?

Process Termination:

·         Abort all deadlocked processes.

·         Abort one process at a time until the deadlock cycle is eliminated.

·         In which order should we choose to abort?

   1) Priority of the process.

   2) How long process has computed, and how much longer to completion.

   3) Resources the process has used. 

   4) Resources process needs to complete.

   5) How many processes will need to be terminated? 

   6) Is process interactive or batch?

 Resource Preemption:

§  Selecting a victim – minimize cost.

§  Rollback – return to some safe state, restart process for that state.

§  Starvation – same process may always be picked as victim, include number of rollback in cost factor.

Deadlock Detection-Algorithm Usage?

·         When, and how often, to invoke depends on:

 How often a deadlock is likely to occur?

 How many processes will need to be rolled back?

·         If detection algorithm is invoked arbitrarily, there may be many cycles in the resource graph and so we would not be  able to tell which of the many deadlocked processes “caused” the deadlock.

What is a Safe State and its’ use in deadlock avoidance?

When a process requests an available resource, system must decide if immediate allocation leaves the system in a  safe state

v  System is in safe state if there exists a safe sequence of all processes.  

v  Sequence <P1, P2… Pn> is safe if for each Pi, the resources that Pi can still request can be satisfied by currently available resources + resources held by all the Pj, with j<I.

     If Pi resource needs are not immediately available, then Pi can wait until all Pj have finished.

     When Pj is finished, Pi can obtain needed resources, execute, return allocated resources, and terminate. 

     When Pi terminates, Pi+1 can obtain its needed resources, and so on. 

Deadlock Avoidance ⇒ ensure that a system will never enter an unsafe state.

What are the Methods for Handling Deadlocks?

v  Ensure that the system will never enter a deadlock state.

v  Allow the system to enter a deadlock state and then recover.

v  Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX.

Condition for deadlock occurrence?

Deadlock can arise if four conditions hold simultaneously.

Mutual exclusion:  only one process at a time can use a resource.

Hold and wait:  a process holding at least one resource is waiting to acquire

additional resources held by other processes.

No preemption:  a resource can be released only voluntarily by the process holding it, after that process has completed its task.

Circular wait:  there exists a set {P0, P1, …, P0} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by  Pn, and P0 is waiting for a resource that is held by P0. 

Different types of Real-Time Scheduling?

Hard real-time systems – required to complete a critical task within a guaranteed amount of time.

            Soft real-time computing – requires that critical processes receive priority over    less fortunate ones.

What is starvation and aging?

Starvation: Starvation is a resource management problem where a process does not get the resources it needs for a long time because the resources are being allocated to other processes.

            Aging: Aging is a technique to avoid starvation in a scheduling system. It works by adding an aging factor to the priority of each request. The aging         factor must increase the request’s priority as time passes and must ensure that     a request will eventually be the highest priority request (after it has waited long enough)

Compare Linux credit based algorithm with other scheduling algorithms?

For the conventional time –shared processes, Linux uses a prioritized, credit-based algorithm. Each process possesses a certain number of scheduling credits; when a new task must be chosen to run, the process with most credits is selected. Every time that a timer interrupt occurs, the currently running process loses one credit; when its credits reaches zero, it is suspended and another process is chosen.

If no runnable processes have any credits, then Linux performs a recrediting operation, adding credits to every process in the system (rather than just to the runnable ones), according to the following rule:

                                     Credits = credits/2 + priority

                        The above scheduling class is used for time-shared process and the in Linux for the real-time scheduling is simpler it uses scheduling classes: first come, first served (FCFS), and round-robin (RR) .In both cases, each process has a priority in addition to its scheduling class. In time-sharing scheduling, however, processes of different priorities can still compete with one another to some extent; in real-time scheduling, the scheduler always runs the process with the highest priority. Among processes of equal priority, it runs the process that has been waiting longest. The only difference between FCFS and RR scheduling is that FCFS processes continue to run until they either exit or block, whereas a round-robin process will be preempted after a while and will be moved to the end of the scheduling queue, so round-robin processes of equal priority will automatically time share among themselves.

                        Linux’s real-time scheduling is soft-real time rather than hard-real time. The scheduler offers strict guarantees about the relative priorities of real-time processes, but the kernel does not offer any guarantees about how quickly a real-time process will be scheduled once that process becomes runnable.

Thus the Linux uses different scheduling classes for time-shared and real-time processes.

 

Give a non-computer example of pre-emptive and non-pre-emptive scheduling.

         Consider   any system where people use some kind of resources and compete for them.

                        The non-computer examples for preemptive scheduling the traffic on the single lane road if there is emergency or there is an ambulance on the road the other vehicles give path to the vehicles that are in need. The example for preemptive scheduling is people standing in queue for tickets.