Doubts and Queries

If you have any doubts or queries or you want to understand any topic related with OS please comment below. Will solve all ur queries. 

Disk Scheduling

FCFS Scheduling

The simplest disk scheduling algorithm is First Come First Serve Scheduling algorithm.

<diagram>

SSTF Scheduling

SSTF stands for Shortest Seek Time First algorithm. The SSTF selects the request that have smallest seek time from the current head position. The algorithm have better performace over FCFS scheduling algorithm

<diagram>

SCAN Scheduling

In SCAN algorithm, disk arm starts moving from one end of the disk to other end. While moving, it services along the way. On reaching other end, direction of head movement is reversed and while coming back, it again services the request in the path. This algorithm is also known as elevator algorithm.

<diagram>

C-SCAN Scheduling

C-SCAN stands for Circular SCAN Scheduling. In this scheduling algorithm like SCAN algorithm, head moves from one end to other and services the request  along the way. But on reaching the other end, the head immediately returns to the beginning of the disk without service request while coming back.

 <diagram>

Linux Directory Structure

In a hierarchical inverted tree like structure, the Linux provides following directories under the /directory to store a specific type of file.

1. / – Root

    Every single file and directory starts from the root directory.    

    Only root user has write privilege under this directory.

     /root is root user’s home directory.

2. /home – Home Directories

    Contains all the HOME directories of users.

    Home directories for all users store particular user personal files.

    For example: /home/teachers, /home/students, /home/mhcollege

3. /bin – User Binaries

    Contains many utilities as binary executables.

    The utilities are common linux commands you need to use in single-user modes

    Commands used by all the users of the system are located here.

    For example: ps, ls, ping, grep, cp.

4. /dev – Device Files

    Contains device files.

    These include terminal devices, USB, or any device attached to the system.

    For example: /dev/tty1, /dev/usbmon0

5. /etc – Configuration Files

    Contains configuration files required by all programs.

    Stores system related data which users and the system need to refer.

    This also contains startup and shutdown shell scripts used to start/stop individual programs.

    For example: passwd, /etc/resolv.conf, /etc/logrotate.conf

6. /lib – System Libraries

    Contains library files for the compilers installed in the system 

    Library filenames are either ld* or lib*.so.*

    For example: ld-2.11.1.so, libncurses.so.5.7

7. /sbin – System Binaries

     Just like /bin, /sbin also contains binary executables.     

     But, the linux commands located under this directory are used by system aministrator, for system            maintenance purpose.

      For example: iptables, reboot, fdisk, ifconfig, swapon

8. /boot – Boot Loader Files

    Contains boot loader related files.

    Kernel initrd, vmlinux, grub files are located under /boot

    For example: initrd.img-2.6.32-24-generic, vmlinuz-2.6.32-24-generic

9. /usr – User Programs

    Contains operating system files which are not involved in the boot process. 

    /usr/bin contains binary files for user programs. For example: at, awk, cc, less, scp

    /usr/sbin contains binary files for system administrators. For example: useradd, userdel

    /usr/lib contains libraries for /usr/bin and /usr/sbin

    /usr/local contains users programs that you install from source. 

10. /var – Variable Files

    var stands for variable files.

    Content of the files that are expected to grow can be found under this directory.

     Includes system log files (/var/log); packages and database files (/var/lib); emails (/var/mail); print         queues (/var/spool); lock files (/var/lock); temp files needed across reboots (/var/tmp);

11. /tmp – Temporary Files

    Contains temporary files created by system and users.

    Files under this directory are deleted when system is rebooted.

12. /media – Removable Media Devices

    Temporary mount directory for removable devices.

    For examples, /media/cdrom for CD-ROM; 

                           /media/floppy for floppy drives; 

                           /media/cdrecorder for CD writer

vi Editor

The vi editor is visual editor used for creating and editing text files containing data, document or programs. 

It is like Notepad we use in Windows.

It display content of files on the screen and allows user to add, insert, delete or change text. 

Some of the other editors for Linux are

ed (line editor)

emacs(edit macros editor)

red (restricted line editor) etc.

Starting vi editor

SYNTAX: vi filename <Enter>

EXAMPLE: [root@localhost student]# vi msg.txt

- - - - - - - - - - “msg.txt” [New File]

             To end insertion or append mode, Press <Esc> and type vi editors command.

Commands of vi editor

The vi editor works in two mode insert mode and append mode. After starting vi editor, Press I to add text. The other commands are

:wq<Enter>                         save all changes and quit

:w<Enter>                         save file

:e<filename><Enter>    open specified file

yy or y                     marks current line as line to be copied

p                              paste marked text after current cursor position

P                            paste marked text before current cursor position 

Functions of vi editor

1. Vi editor allow user to create a file and write data to it.

2. It allow user to open existing file, modify content and save changes in file.

3. It allows user to copy and paste text from one position in a file to another.’

4. It allow searching for a particular expression or word.

5. Large amount of data can also be handled using vi editor.

The History of Linux

1991: Linus Torvalds announced Linux

Linux Torvalds, a student of Helsinki University, Finland, introduced linux in 1991. He worked on the Linux project and write the source code for the Linux kernel. He made Linux available on the Internet. Many programmers added to the code, changed it and built in support for all kinds of hardware. Linux 0.02 was introduced in 1991.

On 25 August 1991 sent a mail to a newsgroup on Usenet. He talked about developing a free operating system.

1992: Linux became Open Source

Linux was not always Open Source. The first few licenses of Linux forbid commercial redistribution. It was with version 0.12 in February’92 that Linux Kernel was released under GPL.

1993: Slackware Linux released

The oldest currently (as of 2018) existing Linux distribution, Slackware version 1.0 was released for the first time on 17th July 1993. Later in the same year, the Debian project is established. Today it is the largest community distribution.

1994: Someone registered Linux trademark and it was not Linus Torvalds

Torvalds and hundreds of developers from across the world worked on it and in March 1994, version 1.0 of Linux kernel was released.

Linux trademark was registered in 1994 by a William R. Della Croce, Jr.

1995: First Linux Expo

First Linux specific tradeshow and conference series was launched by people at North Carolina State University. This became one of the most attended annual Linux show for next several years.

Linux is also ported to the DEC Alpha and to the Sun SPARC.

1996: Tux gets to be the symbol of Linux

Linus Torvalds recommended a penguin as the mascot of Linux. Tux was created by Larry Ewing in 1996. Tux has been unchanged for last 19 years.

Version 2.0 of the Linux kernel is released. The kernel can now serve several processors at the same time using symmetric multiprocessing (SMP), and thereby becomes a serious alternative for many companies.

1997: GNOME Project is born

GNOME is one of the most successful open source projects. It has been crucial to the spread of desktop Linux. It has given us a number of programs that we use today on desktop Linux.

1998: KDE 1.0 released. Many major companies such as IBM, Compaq and Oracle announce their support for Linux.

2000: Dell announces that it is now the No. 2 provider of Linux-based systems worldwide and the first major manufacturer to offer Linux across its full product line.

2002: Red Hat Enterprise Linux released

The first commercial Linux for Business IT was released in the year 2002. RHEL is one of the few Linux distributions that changed Linux forever.

2003: Attempt to install backdoor in Linux kernel

An attempt was made to insert a backdoor in the Linux kernel source. Disguised as an innocuous error checking routine, the backdoor was designed to obtain root privileges under specific conditions. Linux Kernel maintainers caught it before it could made to mainline Linux kernel.

2004: Ubuntu 4.10 released

On 20th October 2004, Ubuntu 4.10 was released. This new Linux distribution marketed itself as Linux for human being.

2005: Linus Torvalds created Git

In 2005, BitKeeper decided to not provide the free version to the community anymore. This forced Linus Torvalds to work on his own version control system and thus Git was born.

2006: Oracle releases its own distribution of Red Hat Enterprise Linux. Novell and Microsoft announce cooperation for a better interoperability and mutual patent protection.

2007: Linux powered netbook arrived

In a time when Windows came pre-installed on majority of personal computers, Asus launched Eee PC, a lower end, lightweight netbook series. It came preinstalled with a custom version of Linux called Xandros. Dell also started distributing laptops with Ubuntu pre-installed on them.

2008: Android version 1.0 released

With the release of Android, a mobile operating system based on Linux Kernel, Linux took the first step in the world of mobile OS. While desktop Linux might not have been that big a sucess, with Android, Linux is dominating the world of mobile OS.

2009: Google announced Chrome OS

Google announces its own  desktop operating system Chrome OS, based on Linux kernel. Later on, Google also started releasing Chromebooks, dedicated devices to run Chrome OS. Chromebooks have grown in popularity in recent years and last year it outsold MacBooks in the US.

Red Hat's market capitalization equals Sun's, interpreted as a symbolic moment for the "Linux-based economy".

2010: Red Hat became first billion dollar open source company

Red Hat Linux became the first billion dollar open source company in 2010. The success of Red Hat breaks the myth that open source companies cannot make money.

2011: Version 3.0 of the Linux kernel is released.

2012: The aggregate Linux server market revenue exceeds that of the rest of the Unix market.[60]

2013: Ubuntu Phone announced

2014: Ubuntu claims 22,000,000 users.

Microsoft’s new CEO Satya Nadella shocked the tech world with his “Microsoft loves Linux” remark. As we see later that this was just the beginning of Microsoft’s grand design to rule cloud world. However, this actually brought a shift in Microsoft policies and for the first time Microsoft started open sourcing its products and bringing it to Linux.

2015: Version 4.0 of the Linux kernel is released

Microsoft has its own version of Linux. A of software meant for network switches that required Linux.

2019: Version 5.0 of the Linux kernel is released.

Source: Wikipedia, Timeline of Linux

Page Replacement Algorithm

When a process executes and the desired page is not in memory, page fault occurs. After locating desired page in memory, OS finds free frame. BUT OS finds that there are no free frames. The OS at this point have multiple options

1.       Terminate the user process

2.       Swap out the process and freeing all its frames

3.       Page Replacement

When no frame is free, process of finding a page that is not currently being used and free it is known as page replacement. The page replacement causes the following sequences of steps to occur

1.       Find the location of the desired page on the disk

2.       Find a free frame

a.       If frame is free, use it

b.      If there is no free frame, use page replacement algorithm to find a page that is not currently being used to select victim frame

c.       Write victim frame back to disk

d.      Update page and frame table

3.       Issue a disk read operation to a free frame

4.       After completing disk read, update page table to show desired page is in the memory now.

5.       Restart the user process

FIFO Page Replacement Algorithm

The simplest page replacement algorithm is First In First Out (FIFO) algorithm. The algorithm associates with each page the time it was brought into the memory.  It replaces that has been in memory for the longest period of time( brought in memory first).  A queue is used to implement FIFO algorithm. A new page is inserted at the rear end whereas page is replaced from the front end of the queue.

The algorithm is easy to understand and program. But performance is not good.

Optimal Page Replacement Algorithm

Optimal Page Replacement algorithm replaces the page that will not be used for the longest period of time.

This algorithm gives lowest possible page fault rate for a fixed number of frames. This algorithm on the other hand is difficult to implement because it requires future knowledge of reference string.

LRU Page Replacement Algorithm

LRU Page replacement algorithm replaces the page that has not been used for the longest period of time. The algorithm associates with each page the time of the page last use.

LRU can be viewed as Optimal Page replacement algorithm in backward  direction and therefore doesnot require future knowledge of reference string.

The algorithm can be implemented in two ways

Keep stack of page numbers. When page is referred, it is popped 

Demand Paging

Consider a menu driven program that has 50 options. Depending upon user choice one option will execute. But to execute a program it must be loaded into the memory.

One way is to load the complete program in physical memory at program execution time. This makes inefficient use of memory because out of 50 options available, code under one option will be executed.

Alternatively, we can load pages only when they are needed. This is known as demand paging and used in virtual memory management.

Demand Paging is an efficient memory management technique in which page is loaded only when demanded during program execution. Pages that are never accessed, never loaded into the memory. 

This technique has following advantages

i.                     No limitation on size of physical memory available.

ii.                   Each program takes less memory as a result more programs run at same time which in turn increases CPU utilization and throughput.

iii.                  Less number of swapping occurs therefore program runs faster

In demand paging, each process resides in secondary memory(disk). When a process execute instead of loading entire process in physical memory, the page that is needed will only be swapped. As compared to swappere who swaps all the pages of process in memory, we use a lazy swapper that swap only those pages that are need. In addition, since each process is a collection of pages therefore we call it a pager not swapper. Pager guess which page will be used and therefore instead of swapping whole process, pager brings only those pages in memory that is needed.

To distinguish between the pages that are in memory or on the disk, page table uses valid invalid bit scheme is used. If the page is legal and in memory, then the bit is set to valid. The bit is set to invalid, if the page is in the disk or page doesn’t belong to logical address space of the process.

When a process executes and access only pages that are in memory (known as memory resident pages), execution occurs normally. BUT when a process requires a page that was not in memory (bit is invalid), page fault occurs. The following steps is required to handle page fault

1.       Trap sent to the operating system

2.       If page reference was legal and determine the location of the page on the disk to brought the page into the memory.

3.       Find a free frame.

4.       Issue a disk read operation to a free frame

5.       After completing disk read, update page table to show desired page is in the memory now.

6.       Restart the instructions that were interrupted by the trap.

Virtual memory

Virtual memory is a storage allocation scheme in which secondary memory can be treated as a part of main memory.

Virtual memory gives an illusion of having large memory when in reality only smaller system’s RAM (physical memory) is available.

Virtual Memory is implemented using Demand Paging.

Paging

Paging is a memory management scheme that permits physical address space of a process to be non contiguous. 

In paging, physical memory is partitioned into fixed size blocks called FRAMES and logical memory is partitioned into block of same size called PAGES. The size of page is equal to frame size. Every CPU generated address is now divided into two parts 

i. Page Number (p): Used as an index into page table. 

ii. Offset

In paging, it is not necessary for a free frame to be contiguous. It can be allocated to a process that needs it. Thus there is no external fragmentation and there is no need for compaction.

Page table contain address of each page in physical memory. That is page table contain frame number in which page is available.  The base address plus page offset gives physical memory address. 

To provide memory protection, page table consists of additional bit known as valid or invalid bit. The bit is set to valid if page is in logical address space and is valid. It is set to invalid if page is not in the logical address space. Valid and Invalid bit is set by OS for each page. 

When a process arrives, its size in pages is examined. Each page of process needs one frame. Process of n pages requires that n frames are available. If frame is available, first page is loaded into one of the available frame and entry of frame number is made in the page table. The next page is now loaded and entry is made in page table. The process is repeated for all the pages of the process. 

<diagram>

In addition to page table, OS maintains a frame table. Frame table has one entry for each frame indicating whether it is free or allocated. If frame is allocated, frame table stores process name and its page number. 

Structure of Page Table

Some the methods to structuring the page table is as follows

1. Hierarchical Paging: In a 32 bit logical address space and page size of 4 KB (212), page table consist of 232/212 entries. The page table becomes very large. One solution is to divide the page table into smaller pieces. When we divide page table in two parts it is called two-level paging algorithm.  The table is also known as forward mapped page table because address obtained by moving for outer page to inner page.

In a 32 bit logical address space and page size 4KB (212), 12 bits consist off set. The remaining 20 bits page number is divided into two parts:  p1=10 bits for page number and p2=10 bits for offset. P1 is index number of outer page table and p2 is displacement of outer page table.

<diagram1>

2. Hashed Page Tables: In hashed page tables the hash value is the page number. Each entry in a hash table contains a linked list of elements that hash to same location. Each element consist of three parts

i. Logical page number

ii. Value of mapped page frame

iii. A pointer to next element of linked list

The logical page number is compared with the field 1 of first element in the linked list. If there is a match, the corresponding frame number present in field 2 is used to form the desired physical address. If no match, next entries are searched. 

Hashed Page Table

3. Inverted Page tables: An inverted page table has one entry for each frame of memory.  Each entry consist of logical address of the page and the information of a process to which the page belongs; i.e. process id. It means there is only one page table is in the system.  

Here, logical address consist of three parts

i. Process Id

ii. Page Number 

iii. Offset

The inverted page table is sorted by physical address but searching is done on logical address. When memory reference occurs, page table is searched for a match. If match is found at position x, then the physical address is (x,offset). If no match is found, an illegal address is accessed. 

Fragmentation

Fragmentation is a phenomenon in which storage space is used inefficiently. Fragmentation occurs when main memory is available but space is not sufficient to load any other process.  Due to swapping and dynamic memory allocation, user process swap in and swap out of the main memory. As a result there are free space but we cannot load new process because available size is smaller than size of the process.

Types of Fragmentation:

Internal Fragmentation occurs when memory allocated to a process is slightly larger than the actual memory requirement of the process. The difference is known as internal fragmentation. Internal fragmentation is actually unused memory internal to a process partition.

Example: Suppose, four process arrives and P1 requires 35 KB, P2 requires 70 KB, nd P4 requires 28 KB. The new process P5 requires 54KB. Memory requirement of process P5 is not fulfilled because internal fragmentation occurs in this case.

REASON: Total Free Memory = 50 + 2 + 5= 57 KB. But we cannot allocate to process P5 because free memory is within allocated process memory area.

2   External Fragmentation occurs when there is a sufficient area within main memory to satisfy current process memory requirement. BUT memory cannot be allocated because available memory is not contiguous.

Example: Suppose a new process arrives and needs 100 KB. In this case, external fragmentation occurs and memory is not allocated to new process.

REASON: The total free memory available is 30+20+60+10=120KB. But we cannot allocate memory to new process because available free memory is not contiguous.

 

The solution for external fragmentation is compaction and non contiguous memory allocation

Compaction is a process to shuffle memory content so that all free memory forms one large block. Practically this is not possible every time.

Another way to solve external fragmentation is allowing logical address space to be non contiguous. The two methods used are Paging and Segmentation.