⇰  HEAP SORT :- Heap sort is also a type of sorting technique, which can apply in binary tree sorting. Heap sort technique is comparison based sorting technique based on Heap data structure. This technique is similar to the selection sort . But first of all we need to know about Heap data structure. A Binary Heap is a Complete Binary Tree where items are stored in a special order such that  root node is compared with its children and arranged  accordingly. The heap is of two types:- Min heap ( value of root node is less than or equal to child) , Max heap ( value of root node is greater or equal to child). The heap can be represented by binary tree or array.   ⇰  ALGORITHM HEAP SORT :- Step1 :- Write root in the list. Step2 :- Write last element at the root. Step3 :- Heapify the tree. Step4 :- Repeat all three steps.   ⇰  IMPLEMENTATION OF HEAP SORT :- Let us take a heap:-   We...

In this post we learn the basic algorithms of frame allocation.There are basically two algorithms for frame allocation :-  1. Equal allocation.  2. Proportional alloccation.  1. Equal allocation :-    The easiest way to split m number of frames among n processes is to give everyone an equal share, m/n frames ( ignoring frames needed by the O/S for that moment). As, if there is 93 frames and 5 processes, each process will get 18 frames. The 3 leftover frames can be used as a free-frame buffer pool. This scheme is called equal allocation. DISADVANTAGE :-   In a system with processes varying sizes, it does not make such sense to give each processes equal frames.   Allocation of large number of frames to a small process will eventually lead to the wastage of large number of allocated unused frames. 2. Proportional alloccation.     Consider a system with 1KB frame. If a smalll student process of 10KB and an interactivedatabase of 127KB are the inl...

 In this post we will cover the topic :- allocation of frame. As we know an important aspects of operating system is virtual memory, which is implemented by using demand paging technique. Demand paging necessitates the development of a page replacement algorithm and a frame allocation algorithm. Frame allocation algorithms are used if you have multiple processes. It helps to decide how many frames are allocated to each process. Consider a single user system with 128 KB of memory composed of 1 KB in size. This system has 128 frames. The operating system may take 35 KB leaving 93 frames for the user processes.  Under pure demand paging all 93 frames would initially be put on free frame list. When a user process started execution, it would generate a sequence of page faults. The first 93 page faults would all get free frames from the free frame list. When the free frame list exhausts, a page replacement algorithm would be used to select one of the 93 in memory pages to be replace...

    ⇰  MERGE SORT :- Merge sort is also a type of sorting technique. It is mainly based on divide-and-conquer algorithm as quick and merge sort, which breaks down a list into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list.  Merge sort is a sorting technique based on divide and conquer technique. Its  worst-case time complexity is Ο(n log n).    It divides input list in two sub-lists, calls itself for the two sub-lists and then merges the two sorted sub-lists. Suppose we have two sub-lists. listA is a list with n element and listB with m element. The operator that combines the element of listA and listB into single result_list with R=n+m elements is called merging.     If the elements of listA and listB are in sorted order then we may get a result_list in sorted order. If listA and listB are not in sorted order then we have to make them...

As we know if we have to increase our degree of multiprogramming, we will over-allocate memory. For this we use demand paging technique.But if CPU demands a page which is not present in memory then page fault occurs. In this situation the command of CPU is taken by O/S and O/S replace the page with the demanded page. Then return command to the CPU then CPU will perform its execution on that demanded page. Therefore, we can say page replacement occur when CPU demands any page which is not in memory and the memory is full, then one page is to replace from memory by demanded page. And page fault happens when a running program accesses a memory page that is mapped into the virtual address space, but not loaded in physical memory . Page replacement takes the following approach. If no frame is free, we find one that is not currently being used and freee it. We can free a frame by writing its contents to swap space and changing the page table to indicate that the page is no longer in memory. ...

There are many different page-replacement algorithms. Every operating system probably has its own replacement scheme.  Let us watch various types of page replacement algorithms in this post. There are following types of page replacement algorithms :-   1. FIFO page replacement.   2. Optimal page replacement.   3. LRU page replacement. In general, we want the algorithm which have the lowest page-fault rate. We evaluate an algorithm by running it on a particular string of memory references and computing the number of page faults. The string of memory references is called a reference string. We can generate reference strings artificially by using a random-number generator.  We use the reference string as follows for a memory with three frames :-      7 0 1 2 0 3 4 2 3 0 3 2 0 1 7 0 1 1. FIFO page replacement :-    It is the simplest page replacement algorithm. Its full form is First-In-First-Out. A FIFO page replacement associates with...

We have discussed before various memory management strategies used in computer system. All these memory manage management strategies have the same goal:- to keep many processes in memory simultaneously to allow multiprogramming. Here we will read overall concept of Virtual Memory. Virtual Memory is a storage allocation scheme in which secondary memory can be considered as the part of main memory. The size of virtual storage is limited by the addressing scheme of the computer system and amount of secondary memory is available. Virtual memory is implemented using both hardware and software. It maps memory addresses, called virtual addresses into physical addresses in computer memory.    Virtual memory is a technique that allows the execution of process that are not completely loaded in memory. One major advantage of this scheme is that programs can be of larger than physical memory. This technique frees the programmers from the concerns of memory-storage limitations. Virtual mem...

  As we Know  when we load the entire program in physical memory at program execution time, Known as paging. And when we load pages of program only as they are neede, known as demand paging and commonly used in virtual memory system. With demand paging, virtual memory pages are loaded only when they are demanded during program execution. Pages that that are never accessed are thus never loaded into physical memory (RAM).     So, demand paging can significantly affect the performance of a computer system. To see how demand paging affect the performance of computer system, let's compute the 'effective access time' for a demand-paged memory. For most computer systems, the memory-access time is denoted by ma, ranged from 10 to 200 nanoseconds. As long as we have no page faults, the effective access time is equal to the memory access time. But if a page fault occurs, we must first read the relevant page from disk and then access the desired word. To complete the effective...

       ⇰  SYNCHRONIZATION :- Process Synchronization  is simply a way to coordinate processes that share something or use shared data. Synchronization occurs in an operating system among cooperating processes. Before starting the brief discuss we have to know types of processes.   There are two types of process according to sharing :- i>  Independent process. ii> Coordinate process. i>  Independent process :- Those process which do not share anything to other processes is called Independent process. Execution of one process will not affect other process. ii> Coordinate process :- Those process which share something with other processes as common variable, memory, code or resources(cpu, printer). So execution of a particular process can affect other process. And cooperative process is not properly synchronised, that can create problem as data inconsistancy.   While executing many cooperative processes, process s...

    ⇰   QUICK SORT :- Quick sort is one of the type of sorting technique. It  follows the di vide and conquer algorithm.  The Quick sort   treats an array as a list of elements. When sorting process begins, it selects the List's middle element as the list pivote. The algorithm then divides the list into two sub-lists, one with the elements that are less then the list pivote and other list with elements greater then or equal to list pivote.    The algorithm then recursively invokes or calls itself with both the list. Each time when the sorting algorithm is invoked, it further divides the elements into smaller sub-lists.  This algorithm is quite efficient for large-sized data.  In quick Sort generally middle element of list is considered as pivote, but we can  take pivot in different ways as follows:-     i > picking first element as pivot.  ii > picking last element as pivot iii > Pick a rand...