Popular sorting algorithms

Link: http://en.wikipedia.org/wiki/Sorting_algorithm

Bubble sort

Bubble sort is a simple sorting algorithm. The algorithm starts at the beginning of the data set. It compares the first two elements, and if the first is greater than the second, it swaps them. It continues doing this for each pair of adjacent elements to the end of the data set. It then starts again with the first two elements, repeating until no swaps have occurred on the last pass. This algorithm's average and worst case performance is O(n²), so it is rarely used to sort large, unordered, data sets. Bubble sort can be used to sort a small number of items (where its asymptotic inefficiency is not a high penalty). Bubble sort can also be used efficiently on a list of any length that is nearly sorted (that is, the elements are not significantly out of place). For example, if any number of elements are out of place by only one position (e.g. 0123546789 and 1032547698), bubble sort's exchange will get them in order on the first pass, the second pass will find all elements in order, so the sort will take only 2n time.

Selection sort

Main article: Selection sort

Selection sort is an in-place comparison sort. It has O(n²) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.

The algorithm finds the minimum value, swaps it with the value in the first position, and repeats these steps for the remainder of the list. It does no more than n swaps, and thus is useful where swapping is very expensive.

Insertion sort

Main article: Insertion sort

Insertion sort is a simple sorting algorithm that is relatively efficient for small lists and mostly sorted lists, and often is used as part of more sophisticated algorithms. It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list. In arrays, the new list and the remaining elements can share the array's space, but insertion is expensive, requiring shifting all following elements over by one. Shell sort (see below) is a variant of insertion sort that is more efficient for larger lists.

Shell sort

 Main article: Shell sort

Shell sort was invented by Donald Shell in 1959. It improves upon bubble sort and insertion sort by moving out of order elements more than one position at a time. One implementation can be described as arranging the data sequence in a two-dimensional array and then sorting the columns of the array using insertion sort.

 

Comb sort

Main article: Comb sort

Comb sort is a relatively simple sorting algorithm originally designed by Wlodzimierz Dobosiewicz in 1980. Later it was rediscovered and popularized by Stephen Lacey and Richard Box with a Byte Magazine article published in April 1991. Comb sort improves on bubble sort, and rivals algorithms like Quicksort. The basic idea is to eliminate turtles, or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously. (Rabbits, large values around the beginning of the list, do not pose a problem in bubble sort)

Merge sort

Main article: Merge sort

Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list. Of the algorithms described here, this is the first that scales well to very large lists, because its worst-case running time is O(n log n). Merge sort has seen a relatively recent surge in popularity for practical implementations, being used for the standard sort routine in the programming languages Perl,^[12] Python (as timsort^[13]), and Java (also uses timsort as of JDK7^[14]), among others. Merge sort has been used in Java at least since 2000 in JDK1.3.^[15][16]

Heapsort

Main article: Heapsort

Heapsort is a much more efficient version of selection sort. It also works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called a heap, a special type of binary tree. Once the data list has been made into a heap, the root node is guaranteed to be the largest (or smallest) element. When it is removed and placed at the end of the list, the heap is rearranged so the largest element remaining moves to the root. Using the heap, finding the next largest element takes O(log n) time, instead of O(n) for a linear scan as in simple selection sort. This allows Heapsort to run in O(n log n) time, and this is also the worst case complexity.

Quicksort

Main article: Quicksort

Quicksort is a divide and conquer algorithm which relies on a partition operation: to partition an array an element called a pivot is selected. All elements smaller than the pivot are moved before it and all greater elements are moved after it. This can be done efficiently in linear time and in-place. The lesser and greater sublists are then recursively sorted. Efficient implementations of quicksort (with in-place partitioning) are typically unstable sorts and somewhat complex, but are among the fastest sorting algorithms in practice. Together with its modest O(log n) space usage, quicksort is one of the most popular sorting algorithms and is available in many standard programming libraries. The most complex issue in quicksort is choosing a good pivot element; consistently poor choices of pivots can result in drastically slower O(n²) performance, if at each step the median is chosen as the pivot then the algorithm works in O(n log n). Finding the median however, is an O(n) operation on unsorted lists and therefore exacts its own penalty with sorting.

Counting sort

Main article: Counting sort

Counting sort is applicable when each input is known to belong to a particular set, S, of possibilities. The algorithm runs in O(|S| + n) time and O(|S|) memory where n is the length of the input. It works by creating an integer array of size |S| and using the ith bin to count the occurrences of the ith member of S in the input. Each input is then counted by incrementing the value of its corresponding bin. Afterward, the counting array is looped through to arrange all of the inputs in order. This sorting algorithm cannot often be used because S needs to be reasonably small for it to be efficient, but the algorithm is extremely fast and demonstrates great asymptotic behavior as n increases. It also can be modified to provide stable behavior.

Bucket sort

Main article: Bucket sort

Bucket sort is a divide and conquer sorting algorithm that generalizes Counting sort by partitioning an array into a finite number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. A variation of this method called the single buffered count sort is faster than quicksort.^{[citation needed]}

Due to the fact that bucket sort must use a limited number of buckets it is best suited to be used on data sets of a limited scope. Bucket sort would be unsuitable for data that have a lot of variation, such as social security numbers.

Radix sort

Main article: Radix sort

Radix sort is an algorithm that sorts numbers by processing individual digits. n numbers consisting of k digits each are sorted in O(n · k) time. Radix sort can process digits of each number either starting from the least significant digit (LSD) or starting from the most significant digit (MSD). The LSD algorithm first sorts the list by the least significant digit while preserving their relative order using a stable sort. Then it sorts them by the next digit, and so on from the least significant to the most significant, ending up with a sorted list. While the LSD radix sort requires the use of a stable sort, the MSD radix sort algorithm does not (unless stable sorting is desired). In-place MSD radix sort is not stable. It is common for the counting sort algorithm to be used internally by the radix sort. Hybrid sorting approach, such as using insertion sort for small bins improves performance of radix sort significantly.

Distribution sort

Distribution sort refers to any sorting algorithm where data are distributed from their input to multiple intermediate structures which are then gathered and placed on the output. For example, both bucket sort and flashsort are distribution based sorting algorithms.

Timsort

Main article: Timsort

Timsort finds runs in the data, creates runs with insertion sort if necessary, and then uses merge sort to create the final sorted list. It has the same complexity (O(nlogn)) in the average and worst cases, but with pre-sorted data it goes down to O(n).

Memory usage patterns and index sorting

When the size of the array to be sorted approaches or exceeds the available primary memory, so that (much slower) disk or swap space must be employed, the memory usage pattern of a sorting algorithm becomes important, and an algorithm that might have been fairly efficient when the array fit easily in RAM may become impractical. In this scenario, the total number of comparisons becomes (relatively) less important, and the number of times sections of memory must be copied or swapped to and from the disk can dominate the performance characteristics of an algorithm. Thus, the number of passes and the localization of comparisons can be more important than the raw number of comparisons, since comparisons of nearby elements to one another happen at system bus speed (or, with caching, even at CPU speed), which, compared to disk speed, is virtually instantaneous.

For example, the popular recursive quicksort algorithm provides quite reasonable performance with adequate RAM, but due to the recursive way that it copies portions of the array it becomes much less practical when the array does not fit in RAM, because it may cause a number of slow copy or move operations to and from disk. In that scenario, another algorithm may be preferable even if it requires more total comparisons.

One way to work around this problem, which works well when complex records (such as in a relational database) are being sorted by a relatively small key field, is to create an index into the array and then sort the index, rather than the entire array. (A sorted version of the entire array can then be produced with one pass, reading from the index, but often even that is unnecessary, as having the sorted index is adequate.) Because the index is much smaller than the entire array, it may fit easily in memory where the entire array would not, effectively eliminating the disk-swapping problem. This procedure is sometimes called "tag sort".^[17]

Another technique for overcoming the memory-size problem is to combine two algorithms in a way that takes advantages of the strength of each to improve overall performance. For instance, the array might be subdivided into chunks of a size that will fit easily in RAM (say, a few thousand elements), the chunks sorted using an efficient algorithm (such as quicksort or heapsort), and the results merged as per mergesort. This is less efficient than just doing mergesort in the first place, but it requires less physical RAM (to be practical) than a full quicksort on the whole array.

Techniques can also be combined. For sorting very large sets of data that vastly exceed system memory, even the index may need to be sorted using an algorithm or combination of algorithms designed to perform reasonably with virtual memory, i.e., to reduce the amount of swapping required.

Some other sorting algorithms also i.e. New friends sort algorithm, Relative split and concatenate sort etc

Unix Questions: Generic

unix interview questions:

1. How are devices represented in UNIX?
Ans: All devices are represented by files called special files that are located in/dev directory. Thus, device files and other files are named and accessed in the same way. A ‘regular file’ is just an ordinary data file in the disk. A ‘block special file’ represents a device with characteristics similar to a disk (data transfer in terms of blocks). A ‘character special file’ represents a device with characteristics similar to a keyboard (data transfer is by stream of bits in sequential order).

2. What is ‘inode’?
Ans: All UNIX files have its description stored in a structure called ‘inode’. The inode contains info about the file-size, its location, time of last access, time of last modification, permission and so on. Directories are also represented as files and have an associated inode. In addition to descriptions about the file, the inode contains pointers to the data blocks of the file. If the file is large, inode has indirect pointer to a block of pointers to additional data blocks (this further aggregates for larger files). A block is typically 8k.
Inode consists of the following fields:
File owner identifier
File type
File access permissions
File access times
Number of links
File size
Location of the file data

3. Brief about the directory representation in UNIX?
Ans: A Unix directory is a file containing a correspondence between filenames and inodes. A directory is a special file that the kernel maintains. Only kernel modifies directories, but processes can read directories. The contents of a directory are a list of filename and inode number pairs. When new directories are created, kernel makes two entries named ‘.’ (refers to the directory itself) and ‘..’ (refers to parent directory).
System call for creating directory is mkdir (pathname, mode).

4. What are the Unix system calls for I/O?
Ans: open(pathname,flag,mode) – open file
creat(pathname,mode) – create file
close(filedes) – close an open file
read(filedes,buffer,bytes) – read data from an open file
write(filedes,buffer,bytes) – write data to an open file
lseek(filedes,offset,from) – position an open file
dup(filedes) – duplicate an existing file descriptor
dup2(oldfd,newfd) – duplicate to a desired file descriptor
fcntl(filedes,cmd,arg) – change properties of an open file
ioctl(filedes,request,arg) – change the behaviour of an open file
The difference between fcntl anf ioctl is that the former is intended for any open file, while the latter is for device-specific operations.

5. How do you change File Access Permissions?
Ans: Every file has following attributes:
owner’s user ID ( 16 bit integer )
owner’s group ID ( 16 bit integer )
File access mode word
‘r w x -r w x- r w x’
(user permission-group permission-others permission)
r-read, w-write, x-execute
To change the access mode, we use chmod(filename,mode).
Example 1:
To change mode of myfile to ‘rw-rw-r–’ (ie. read, write permission for user – read,write permission for group – only read permission for others) we give the args as:
chmod(myfile,0664) .
Each operation is represented by discrete values
‘r’ is 4
‘w’ is 2
‘x’ is 1
Therefore, for ‘rw’ the value is 6(4+2).
Example 2:
To change mode of myfile to ‘rwxr–r–’ we give the args as:
chmod(myfile,0744).

6. What are links and symbolic links in UNIX file system?
Ans: A link is a second name (not a file) for a file. Links can be used to assign more than one name to a file, but cannot be used to assign a directory more than one name or link filenames on different computers.
Symbolic link ‘is’ a file that only contains the name of another file.Operation on the symbolic link is directed to the file pointed by the it.Both the limitations of links are eliminated in symbolic links.
Commands for linking files are:
Link ln filename1 filename2
Symbolic link ln -s filename1 filename2

7. What is a FIFO?
Ans: FIFO are otherwise called as ‘named pipes’. FIFO (first-in-first-out) is a special file which is said to be data transient. Once data is read from named pipe, it cannot be read again. Also, data can be read only in the order written. It is used in interprocess communication where a process writes to one end of the pipe (producer) and the other reads from the other end (consumer).

8. How do you create special files like named pipes and device files?
Ans: The system call mknod creates special files in the following sequence.
1. kernel assigns new inode,
2. sets the file type to indicate that the file is a pipe, directory or special file,
3. If it is a device file, it makes the other entries like major, minor device numbers.
For example:
If the device is a disk, major device number refers to the disk controller and minor device number is the disk.

9. Discuss the mount and unmount system calls ?
Ans : The privileged mount system call is used to attach a file system to a directory of another file system; the unmount system call detaches a file system. When you mount another file system on to your directory, you are essentially splicing one directory tree onto a branch in another directory tree. The first argument to mount call is the mount point, that is , a directory in the current file naming system. The second argument is the file system to mount to that point. When you insert a cdrom to your unix system’s drive, the file system in the cdrom automatically mounts to /dev/cdrom in your system.

10. How does the inode map to data block of a file?
Ans: Inode has 13 block addresses. The first 10 are direct block addresses of the first 10 data blocks in the file. The 11th address points to a one-level index block. The 12th address points to a two-level (double in-direction) index block. The 13th address points to a three-level(triple in-direction)index block. This provides a very large maximum file size with efficient access to large files, but also small files are accessed directly in one disk read.

11. What is a shell?
Ans: A shell is an interactive user interface to an operating system services that allows an user to enter commands as character strings or through a graphical user interface. The shell converts them to system calls to the OS or forks off a process to execute the command. System call results and other information from the OS are presented to the user through an interactive interface. Commonly used shells are sh,csh,ks etc.

12. Brief about the initial process sequence while the system boots up?
Ans: While booting, special process called the ‘swapper’ or ‘scheduler’ is created with Process-ID 0. The swapper manages memory allocation for processes and influences CPU allocation. The swapper inturn creates 3 children:
the process dispatcher, vhand and dbflush with IDs 1,2 and 3 respectively.
This is done by executing the file /etc/init. Process dispatcher gives birth to the shell. Unix keeps track of all the processes in an internal data structure called the Process Table (listing command is ps -el).

13. What are various IDs associated with a process?
Ans: Unix identifies each process with a unique integer called ProcessID. The process that executes the request for creation of a process is called the ‘parent process’ whose PID is ‘Parent Process ID’. Every process is associated with a particular user called the ‘owner’ who has privileges over the process. The identification for the user is ‘UserID’. Owner is the user who executes the process. Process also has ‘Effective User ID’ which determines the access privileges for accessing resources like files.
getpid() -process id
getppid() -parent process id
getuid() -user id
geteuid() -effective user id

14. Explain fork() system call?
Ans: The `fork()’ used to create a new process from an existing process. The new process is called the child process, and the existing process is called the parent. We can tell which is which by checking the return value from `fork()’. The parent gets the child’s pid returned to him, but the child gets 0 returned to him.

15. Predict the output of the following program code
main()
{
fork();
printf(“Hello World!”);
}
Ans: Hello World!Hello World!
Explanation:
The fork creates a child that is a duplicate of the parent process. The child begins from the fork().All the statements after the call to fork() will be executed twice.(once by the parent process and other by child). The statement before fork() is executed only by the parent process.



16. Predict the output of the following program code
main()
{
fork(); fork(); fork();
printf(“Hello World!”);
}
Ans: “Hello World” will be printed 8 times.
Explanation:
2^n times where n is the number of calls to fork()

17. List the system calls used for process management:
Ans: System calls Description
fork() To create a new process
exec() To execute a new program in a process
wait() To wait until a created process completes its execution
exit() To exit from a process execution
getpid() To get a process identifier of the current process
getppid() To get parent process identifier
nice() To bias the existing priority of a process
brk() To increase/decrease the data segment size of a process

18. How can you get/set an environment variable from a program?
Ans: Getting the value of an environment variable is done by using `getenv()’. Setting the value of an environment variable is done by using `putenv()’.

19. How can a parent and child process communicate?
Ans: A parent and child can communicate through any of the normal inter-process communication schemes (pipes, sockets, message queues, shared memory), but also have some special ways to communicate that take advantage of their relationship as a parent and child. One of the most obvious is that the parent can get the exit status of the child.

20. What is a zombie?
Ans: When a program forks and the child finishes before the parent, the kernel still keeps some of its information about the child in case the parent might need it – for example, the parent may need to check the child’s exit status. To be able to get this information, the parent calls `wait()’; In the interval between the child terminating and the parent calling `wait()’, the child is said to be a `zombie’ (If you do `ps’, the child will have a `Z’ in its status field to indicate this.)

21. What are the process states in Unix?
Ans: As a process executes it changes state according to its circumstances. Unix processes have the following states:
Running : The process is either running or it is ready to run .
Waiting : The process is waiting for an event or for a resource.
Stopped : The process has been stopped, usually by receiving a signal.
Zombie : The process is dead but have not been removed from the process table.

22. What Happens when you execute a program?
Ans: When you execute a program on your UNIX system, the system creates a special environment for that program. This environment contains everything needed for the system to run the program as if no other program were running on the system. Each process has process context, which is everything that is unique about the state of the program you are currently running. Every time you execute a program the UNIX system does a fork, which performs a series of operations to create a process context and then execute your program in that context. The steps include the following:
Allocate a slot in the process table, a list of currently running programs kept by UNIX.
Assign a unique process identifier (PID) to the process.
iCopy the context of the parent, the process that requested the spawning of the new process.
Return the new PID to the parent process. This enables the parent process to examine or control the process directly. After the fork is complete, UNIX runs your program.

23. What Happens when you execute a command?
Ans: When you enter ‘ls’ command to look at the contents of your current working directory, UNIX does a series of things to create an environment for ls and the run it: The shell has UNIX perform a fork. This creates a new process that the shell will use to run the ls program. The shell has UNIX perform an exec of the ls program. This replaces the shell program and data with the program and data for ls and then starts running that new program. The ls program is loaded into the new process context, replacing the text and data of the shell. The ls program performs its task, listing the contents of the current directory.

24. What is a Daemon?
Ans: A daemon is a process that detaches itself from the terminal and runs, disconnected, in the background, waiting for requests and responding to them. It can also be defined as the background process that does not belong to a terminal session. Many system functions are commonly performed by daemons, including the sendmail daemon, which handles mail, and the NNTP daemon, which handles USENET news. Many other daemons may exist. Some of the most common daemons are:
init: Takes over the basic running of the system when the kernel has finished the boot process.
inetd: Responsible for starting network services that do not have their own stand-alone daemons. For example, inetd usually takes care of incoming rlogin, telnet, and ftp connections.
cron: Responsible for running repetitive tasks on a regular schedule.

25. What is ‘ps’ command for?
Ans: The ps command prints the process status for some or all of the running processes. The information given are the process identification number (PID),the amount of time that the process has taken to execute so far etc.

26. How would you kill a process?
Ans: The kill command takes the PID as one argument; this identifies which process to terminate. The PID of a process can be got using ‘ps’ command.

27. What is an advantage of executing a process in background?
Ans: The most common reason to put a process in the background is to allow you to do something else interactively without waiting for the process to complete. At the end of the command you add the special background symbol, &. This symbol tells your shell to execute the given command in the background.
Example: cp *.* ../backup& (cp is for copy)

28. How do you execute one program from within another?
Ans: The system calls used for low-level process creation are execlp() and execvp(). The execlp call overlays the existing program with the new one , runs that and exits. The original program gets back control only when an error occurs. execlp(path,file_name,arguments..); //last argument must be NULL A variant of execlp called execvp is used when the number of arguments is not known in advance. execvp(path,argument_array); //argument array should be terminated by NULL

29. What is IPC? What are the various schemes available?
Ans: The term IPC (Inter-Process Communication) describes various ways by which different process running on some operating system communicate between each other. Various schemes available are as follows: Pipes:
One-way communication scheme through which different process can communicate. The problem is that the two processes should have a common ancestor (parent-child relationship). However this problem was fixed with the introduction of named-pipes (FIFO).
Message Queues :
Message queues can be used between related and unrelated processes running on a machine.
Shared Memory:
This is the fastest of all IPC schemes. The memory to be shared is mapped into the address space of the processes (that are sharing). The speed achieved is attributed to the fact that there is no kernel involvement. But this scheme needs synchronization.
Various forms of synchronization are mutexes, condition-variables, read-write locks, record-locks, and semaphores.

30. What is the difference between Swapping and Paging?
Ans: Swapping: Whole process is moved from the swap device to the main memory for execution. Process size must be less than or equal to the available main memory. It is easier to implementation and overhead to the system. Swapping systems does not handle the memory more flexibly as compared to the paging systems.
Paging:
Only the required memory pages are moved to main memory from the swap device for execution. Process size does not matter. Gives the concept of the virtual memory.
It provides greater flexibility in mapping the virtual address space into the physical memory of the machine. Allows more number of processes to fit in the main memory simultaneously. Allows the greater process size than the available physical memory. Demand paging systems handle the memory more flexibly.

31. What is major difference between the Historic Unix and the new BSD release of Unix System V in terms of Memory Management?
Ans: Historic Unix uses Swapping – entire process is transferred to the main memory from the swap device, whereas the Unix System V uses Demand Paging – only the part of the process is moved to the main memory. Historic Unix uses one Swap Device and Unix System V allow multiple Swap Devices.

32. What is the main goal of the Memory Management?
Ans: It decides which process should reside in the main memory, Manages the parts of the virtual address space of a process which is non-core resident, Monitors the available main memory and periodically write the processes into the swap device to provide more processes fit in the main memory simultaneously.

33. What is a Map?
Ans: A Map is an Array, which contains the addresses of the free space in the swap device that are allocatable resources, and the number of the resource units available there.
This allows First-Fit allocation of contiguous blocks of a resource. Initially the Map contains one entry – address (block offset from the starting of the swap area) and the total number of resources. Kernel treats each unit of Map as a group of disk blocks. On the allocation and freeing of the resources Kernel updates the Map for accurate information.

34. What scheme does the Kernel in Unix System V follow while choosing a swap device among the multiple swap devices?
Ans: Kernel follows Round Robin scheme choosing a swap device among the multiple swap devices in Unix System V.


35. What is a Region?
Ans: A Region is a continuous area of a process’s address space (such as text, data and stack). The kernel in a ‘Region Table’ that is local to the process maintains region. Regions are sharable among the process.

36. What are the events done by the Kernel after a process is being swapped out from the main memory?
Ans: When Kernel swaps the process out of the primary memory, it performs the following:
Kernel decrements the Reference Count of each region of the process. If the reference count becomes zero, swaps the region out of the main memory,Kernel allocates the space for the swapping process in the swap device,Kernel locks the other swapping process while the current swapping operation is going on,The Kernel saves the swap address of the region in the region table.

37. Is the Process before and after the swap are the same? Give reason.
Ans: Process before swapping is residing in the primary memory in its original form. The regions (text, data and stack) may not be occupied fully by the process, there may be few empty slots in any of the regions and while swapping Kernel do not bother about the empty slots while swapping the process out. After swapping the process resides in the swap (secondary memory) device. The regions swapped out will be present but only the occupied region slots but not the empty slots that were present before assigning. While swapping the process once again into the main memory, the Kernel referring to the Process Memory Map, it assigns the main memory accordingly taking care of the empty slots in the regions.

38. What do you mean by u-area (user area) or u-block?
Ans: This contains the private data that is manipulated only by the Kernel. This is local to the Process, i.e. each process is allocated a u-area.

39. What are the entities that are swapped out of the main memory while swapping the process out of the main memory?
Ans: All memory space occupied by the process, process’s u-area, and Kernel stack are swapped out, theoretically. Practically, if the process’s u-area contains the Address Translation Tables for the process then Kernel implementations do not swap the u-area.

40. What is Fork swap?
Ans: fork() is a system call to create a child process. When the parent process calls fork() system call, the child process is created and if there is short of memory then the child process is sent to the read-to-run state in the swap device, and return to the user state without swapping the parent process. When the memory will be available the child process will be swapped into the main memory.

41. What is Expansion swap?
Ans: At the time when any process requires more memory than it is currently allocated, the Kernel performs Expansion swap. To do this Kernel reserves enough space in the swap device. Then the address translation mapping is adjusted for the new virtual address space but the physical memory is not allocated. At last Kernel swaps the process into the assigned space in the swap device. Later when the Kernel swaps the process into the main memory this assigns memory according to the new address translation mapping.

42. How the Swapper works?
Ans: The swapper is the only process that swaps the processes. The Swapper operates only in the Kernel mode and it does not uses System calls instead it uses internal Kernel functions for swapping. It is the archetype of all kernel process.

43. What are the processes that are not bothered by the swapper? Give Reason.
Ans: Zombie process: They do not take any up physical memory.Processes locked in memories that are updating the region of the process.Kernel swaps only the sleeping processes rather than the ‘ready-to-run’ processes, as they have the higher probability of being scheduled than the Sleeping processes.

44. What are the requirements for a swapper to work?
Ans: The swapper works on the highest scheduling priority. Firstly it will look for any sleeping process, if not found then it will look for the ready-to-run process for swapping. But the major requirement for the swapper to work the ready-to-run process must be core-resident for at least 2 seconds before swapping out. And for swapping in the process must have been resided in the swap device for at least 2 seconds. If the requirement is not satisfied then the swapper will go into the wait state on that event and it is awaken once in a second by the Kernel.

45. What are the criteria for choosing a process for swapping into memory from the swap device?
Ans: The resident time of the processes in the swap device, the priority of the processes and the amount of time the processes had been swapped out.

46. What are the criteria for choosing a process for swapping out of the memory to the swap device?
Ans: The process’s memory resident time,Priority of the process and the nice value.

47. What do you mean by nice value?
Ans: Nice value is the value that controls {increments or decrements} the priority of the process. This value that is returned by the nice () system call. The equation for using nice value is: Priority = (“recent CPU usage”/constant) + (base- priority) + (nice value) Only the administrator can supply the nice value. The nice () system call works for the running process only. Nice value of one process cannot affect the nice value of the other process.

48. What are conditions on which deadlock can occur while swapping the processes?
Ans: All processes in the main memory are asleep.All ‘ready-to-run’ processes are swapped out.
There is no space in the swap device for the new incoming process that are swapped out of the main memory. There is no space in the main memory for the new incoming process.

49. What are conditions for a machine to support Demand Paging?
Ans: Memory architecture must based on Pages, The machine must support the ‘restartable’ instructions.

50. What is ‘the principle of locality’?
Ans: It’s the nature of the processes that they refer only to the small subset of the total data space of the process. i.e. the process frequently calls the same subroutines or executes the loop instructions.

51. What is the working set of a process?
Ans: The set of pages that are referred by the process in the last ‘n’, references, where ‘n’ is called the window of the working set of the process.

52. What is the window of the working set of a process?
Ans: The window of the working set of a process is the total number in which the process had referred the set of pages in the working set of the process.

53. What is called a page fault?
Ans: Page fault is referred to the situation when the process addresses a page in the working set of the process but the process fails to locate the page in the working set. And on a page fault the kernel updates the working set by reading the page from the secondary device.

54. What are data structures that are used for Demand Paging?
Ans: Kernel contains 4 data structures for Demand paging. They are, Page table entries, Disk block descriptors, Page frame data table (pfdata), Swap-use table.

55. What are the bits that support the demand paging?
Ans: Valid, Reference, Modify, Copy on write, Age. These bits are the part of the page table entry, which includes physical address of the page and protection bits.
Page address
Age
Copy on write
Modify
Reference
Valid
Protection

56. How the Kernel handles the fork() system call in traditional Unix and in the System V Unix, while swapping?
Ans: Kernel in traditional Unix, makes the duplicate copy of the parent’s address space and attaches it to the child’s process, while swapping. Kernel in System V Unix, manipulates the region tables, page table, and pfdata table entries, by incrementing the reference count of the region table of shared regions.

57. Difference between the fork() and vfork() system call?
Ans: During the fork() system call the Kernel makes a copy of the parent process’s address space and attaches it to the child process. But the vfork() system call do not makes any copy of the parent’s address space, so it is faster than the fork() system call. The child process as a result of the vfork() system call executes exec() system call. The child process from vfork() system call executes in the parent’s address space (this can overwrite the parent’s data and stack ) which suspends the parent process until the child process exits.

58. What is BSS(Block Started by Symbol)?
Ans: A data representation at the machine level, that has initial values when a program starts and tells about how much space the kernel allocates for the un-initialized data. Kernel initializes it to zero at run-time.

59. What is Page-Stealer process?
Ans: This is the Kernel process that makes rooms for the incoming pages, by swapping the memory pages that are not the part of the working set of a process. Page-Stealer is created by the Kernel at the system initialization and invokes it throughout the lifetime of the system. Kernel locks a region when a process faults on a page in the region, so that page stealer cannot steal the page, which is being faulted in.

60. Name two paging states for a page in memory?
Ans: The two paging states are:
The page is aging and is not yet eligible for swapping,
The page is eligible for swapping but not yet eligible for reassignment to other virtual address space.

61. What are the phases of swapping a page from the memory?
Ans: Page stealer finds the page eligible for swapping and places the page number in the list of pages to be swapped. Kernel copies the page to a swap device when necessary and clears the valid bit in the page table entry, decrements the pfdata reference count, and places the pfdata table entry at the end of the free list if its reference count is 0.

62. What is page fault? Its types?
Ans: Page fault refers to the situation of not having a page in the main memory when any process references it. There are two types of page fault :
Validity fault,
Protection fault.

63. In what way the Fault Handlers and the Interrupt handlers are different?
Ans: Fault handlers are also an interrupt handler with an exception that the interrupt handlers cannot sleep. Fault handlers sleep in the context of the process that caused the memory fault. The fault refers to the running process and no arbitrary processes are put to sleep.

64. What is validity fault?
Ans: If a process referring a page in the main memory whose valid bit is not set, it results in validity fault. The valid bit is not set for those pages:
that are outside the virtual address space of a process,
that are the part of the virtual address space of the process but no physical address is assigned to it.
65. What does the swapping system do if it identifies the illegal page for swapping?
Ans: If the disk block descriptor does not contain any record of the faulted page, then this causes the attempted memory reference is invalid and the kernel sends a “Segmentation violation” signal to the offending process. This happens when the swapping system identifies any invalid memory reference.

66. What are states that the page can be in, after causing a page fault?
Ans: On a swap device and not in memory, On the free page list in the main memory, In an executable file, Marked “demand zero”, Marked “demand fill”.

67. In what way the validity fault handler concludes?
Ans: It sets the valid bit of the page by clearing the modify bit. It recalculates the process priority.

68. At what mode the fault handler executes?
Ans: At the Kernel Mode.

69. What do you mean by the protection fault?
Ans: Protection fault refers to the process accessing the pages, which do not have the access permission. A process also incur the protection fault when it attempts to write a page whose copy on write bit was set during the fork() system call.

70. How the Kernel handles the copy on write bit of a page, when the bit is set?
Ans: In situations like, where the copy on write bit of a page is set and that page is shared by more than one process, the Kernel allocates new page and copies the content to the new page and the other processes retain their references to the old page. After copying the Kernel updates the page table entry with the new page number. Then Kernel decrements the reference count of the old pfdata table entry. In cases like, where the copy on write bit is set and no processes are sharing the page, the Kernel allows the physical page to be reused by the processes. By doing so, it clears the copy on write bit and disassociates the page from its disk copy (if one exists), because other process may share the disk copy. Then it removes the pfdata table entry from the page-queue as the new copy of the virtual page is not on the swap device. It decrements the swap-use count for the page and if count drops to 0, frees the swap space.

71. For which kind of fault the page is checked first?
Ans: The page is first checked for the validity fault, as soon as it is found that the page is invalid (valid bit is clear), the validity fault handler returns immediately, and the process incur the validity page fault. Kernel handles the validity fault and the process will incur the protection fault if any one is present.

72. In what way the protection fault handler concludes?
Ans: After finishing the execution of the fault handler, it sets the modify and protection bits and clears the copy on write bit. It recalculates the process-priority and checks for signals.

73. How the Kernel handles both the page stealer and the fault handler?
Ans: The page stealer and the fault handler thrash because of the shortage of the memory. If the sum of the working sets of all processes is greater that the physical memory then the fault handler will usually sleep because it cannot allocate pages for a process. This results in the reduction of the system throughput because Kernel spends too much time in overhead, rearranging the memory in the frantic pace.

74. Explain different types of Unix systems.
Ans: The most widely used are: 1. System V (AT&T) 2. AIX (IBM) 3. BSD (Berkeley) 4. Solaris (Sun) 5. Xenix ( A PC version of Unix)

75. Explain kernal and shell.
Ans: Kernal: It carries out basic operating system functions such as allocating memory, accessing files and handling communications. Shell:A shell provides the user interface to the kernal.There are 3 major shells : C-shell, Bourne shell , Korn shell


76. What is ex and vi ?
Ans: ex is Unix line editor and vi is the standard Unix screen editor.

77. Which are typical system directories below the root directory?
Ans: (1)/bin: contains many programs which will be executed by users (2)/etc : files used by administrator (3)/dev: hardware devices (4)/lib: system libraries (5)/usr: application software (6)/home: home directories for different systems.

78. Construct pipes to execute the following jobs?
Ans:
1. Output of who should be displayed on the screen with value of total number of users who have logged in displayed at the bottom of the list.
2. Output of ls should be displayed on the screen and from this output the lines containing the word ‘poem’ should be counted and the count should be stored in a file.
3. Contents of file1 and file2 should be displayed on the screen and this output should be appended in a file.
From output of ls the lines containing ‘poem’ should be displayed on the screen along with the count.
4. Name of cities should be accepted from the keyboard . This list should be combined with the list present in a file. This combined list should be sorted and the sorted list should be stored in a file ‘newcity’.
5. All files present in a directory dir1 should be deleted any error while deleting should be stored in a file ‘errorlog’.

79.Explain the following commands?
$ ls > file1
$ banner hi-fi > message
$ cat par.3 par.4 par.5 >> report
$ cat file1>file1
$ date ; who
$ date ; who > logfile
$ (date ; who) > logfile

80. What is the significance of the “tee” command?
Ans: It reads the standard input and sends it to the standard output while redirecting a copy of what it has read to the file specified by the user.

81. What does the command “ $who | sort –logfile > newfile” do?
Ans: The input from a pipe can be combined with the input from a file . The trick is to use the special symbol “-“ (a hyphen) for those commands that recognize the hyphen as std input.
In the above command the output from who becomes the std input to sort , meanwhile sort opens the file logfile, the contents of this file is sorted together with the output of who (rep by the hyphen) and the sorted output is redirected to the file newfile.

82. What does the command “$ls | wc –l > file1” do?
Ans: ls becomes the input to wc which counts the number of lines it receives as input and instead of displaying this count , the value is stored in file1.

83.Which of the following commands is not a filter man , (b) cat , (c) pg , (d) head
man A filter is a program which can receive a flow of data from std input, process (or filter) it and send the result to the std output.

84. How is the command “$cat file2 “ different from “$cat >file2 and >> redirection operators ?
Ans: is the output redirection operator when used it overwrites while >> operator appends into the file.

85. Explain the steps that a shell follows while processing a command.
Ans: After the command line is terminated by the key, the shell goes ahead with processing the command line in one or more passes. The sequence is well defined and assumes the following order.
Parsing: The shell first breaks up the command line into words, using spaces and the delimiters, unless quoted. All consecutive occurrences of a space or tab are replaced here with a single space.
Variable evaluation: All words preceded by a $ are valuated as variables, unless quoted or escaped.
Command substitution: Any command surrounded by back quotes is executed by the shell which then replaces the standard output of the command into the command line.
Wild-card interpretation: The shell finally scans the command line for wild-cards (the characters *, ?, [, ]).
Any word containing a wild-card is replaced by a sorted list of
filenames that match the pattern. The list of these filenames then forms the arguments to the command.
PATH evaluation: It finally looks for the PATH variable to determine the sequence of directories it has to search in order to hunt for the command.

86. What difference between cmp and diff commands?
Ans: cmp – Compares two files byte by byte and displays the first mismatch diff – tells the changes to be made to make the files identical

87. What is the use of ‘grep’ command?
Ans: ‘grep’ is a pattern search command. It searches for the pattern, specified in the command line with appropriate option, in a file(s).
Syntax : grep
Example : grep 99mx mcafile


88. What is the difference between cat and more command?
Ans: Cat displays file contents. If the file is large the contents scroll off the screen before we view it. So command ‘more’ is like a pager which displays the contents page by page.

89. Write a command to kill the last background job?
Ans: Kill $!

90. Which command is used to delete all files in the current directory and all its sub-directories?
Ans: rm -r *

91. Write a command to display a file’s contents in various formats?
Ans: $od -cbd file_name c – character, b – binary (octal), d-decimal, od=Octal Dump.

92. What will the following command do?
Ans: $ echo *
It is similar to ‘ls’ command and displays all the files in the current directory.

93. Is it possible to create new a file system in UNIX?
Ans: Yes, ‘mkfs’ is used to create a new file system.

94. Is it possible to restrict incoming message?
Ans: Yes, using the ‘mesg’ command.

95. What is the use of the command “ls -x chapter[1-5]”
Ans: ls stands for list; so it displays the list of the files that starts with ‘chapter’ with suffix ’1′ to ’5′, chapter1, chapter2, and so on.

96. Is ‘du’ a command? If so, what is its use?
Ans: Yes, it stands for ‘disk usage’. With the help of this command you can find the disk capacity and free space of the disk.

97. Is it possible to count number char, line in a file; if so, How?
Ans: Yes, wc-stands for word count.
wc -c for counting number of characters in a file.
wc -l for counting lines in a file.

98. Name the data structure used to maintain file identification?
Ans: ‘inode’, each file has a separate inode and a unique inode number.

99. How many prompts are available in a UNIX system?
Ans: Two prompts, PS1 (Primary Prompt), PS2 (Secondary Prompt).

100. How does the kernel differentiate device files and ordinary files?
Ans: Kernel checks ‘type’ field in the file’s inode structure.

101. How to switch to a super user status to gain privileges?
Ans: Use ‘su’ command. The system asks for password and when valid entry is made the user gains super user (admin) privileges.

102. What are shell variables?
Ans: Shell variables are special variables, a name-value pair created and maintained by the shell.
Example: PATH, HOME, MAIL and TERM

103. What is redirection?
Ans: Directing the flow of data to the file or from the file for input or output.
Example : ls > wc

104. How to terminate a process which is running and the specialty on command kill 0?
Ans: With the help of kill command we can terminate the process.
Syntax: kill pid
Kill 0 – kills all processes in your system except the login shell.

105. What is a pipe and give an example?
Ans: A pipe is two or more commands separated by pipe char ‘|’. That tells the shell to arrange for the output of the preceding command to be passed as input to the following command.
Example : ls -l | pr
The output for a command ls is the standard input of pr.
When a sequence of commands are combined using pipe, then it is called pipeline.

106. Explain kill() and its possible return values.
Ans: There are four possible results from this call:
‘kill()’ returns 0. This implies that a process exists with the given PID, and the system would allow you to send signals to it. It is system-dependent whether the process could be a zombie.
‘kill()’ returns -1, ‘errno == ESRCH’ either no process exists with the given PID, or security enhancements are causing the system to deny its existence. (On some systems, the process could be a zombie.)
‘kill()’ returns -1, ‘errno == EPERM’ the system would not allow you to kill the specified process. This means that either the process exists (again, it could be a zombie) or draconian security enhancements are present (e.g. your process is not allowed to send signals to *anybody*).
‘kill()’ returns -1, with some other value of ‘errno’ you are in trouble! The most-used technique is to assume that success or failure with ‘EPERM’ implies that the process exists, and any other error implies that it doesn’t.
An alternative exists, if you are writing specifically for a system (or all those systems) that provide a ‘/proc’ filesystem: checking for the existence of ‘/proc/PID’ may work.

Data Structure Questions 1

1. What is data structure?
Ans: The logical and mathematical model of a particular organization of data is called data structure. There are two types of data structure
i) Linear
ii) Nonlinear

2. What are the goals of Data Structure?
Ans: It must rich enough in structure to reflect the actual relationship of data in real world.
The structure should be simple enough for efficient processing of data.

3. What does abstract Data Type Mean?
Ans: Data type is a collection of values and a set of operations on these values. Abstract data type refer to the mathematical concept that define the data type.
It is a useful tool for specifying the logical properties of a data type.
ADT consists of two parts
1) Values definition
2) Operation definition
Example:-The value definition for the ADT RATIONAL states that RATIONAL value consists of two integers, second doesn’t equal to zero.
The operator definition for ADT RATIONAL includes the operation of creation (make rational) addition, multiplication and test for equality.

4. What is the difference between a Stack and an Array?
Ans:
i) Stack is a ordered collection of items
ii) Stack is a dynamic object whose size is constantly changing as items are pushed and popped .
iii) Stack may contain different data types
iv) Stack is declared as a structure containing an array to hold the element of the stack, and an integer to indicate the current stack top within the array.
ARRAY
i) Array is an ordered collection of items
ii) Array is a static object i.e. no of item is fixed and is assigned by the declaration of the array
iii) It contains same data types.
iv) Array can be home of a stack i.e. array can be declared large enough for maximum size of the stack.

5. What do you mean by recursive definition?
Ans: The definition which defines an object in terms of simpler cases of itself is called recursive definition.

6. What is sequential search?
Ans: In sequential search each item in the array is compared with the item being searched until a match occurs. It is applicable to a table organized either as an array or as a linked list.

7. What actions are performed when a function is called?
Ans: When a function is called
i) arguments are passed
ii) local variables are allocated and initialized
ii) transferring control to the function

8. What actions are performed when a function returns?
Ans:
i) Return address is retrieved
ii) Function’s data area is freed
iii) Branch is taken to the return address

9. What is a linked list?
Ans: A linked list is a linear collection of data elements, called nodes, where the linear order is given by pointers. Each node has two parts first part contain the information of the element second part contains the address of the next node in the list.

10. What are the advantages of linked list over array (static data structure)?
Ans:
The disadvantages of array are
i) unlike linked list it is expensive to insert and delete elements in the array
ii) One can’t double or triple the size of array as it occupies block of memory space.

In linked list
i) each element in list contains a field, called a link or pointer which contains the address of the next element
ii) Successive element’s need not occupy adjacent space in memory.


11. Can we apply binary search algorithm to a sorted linked list, why?
Ans: No we cannot apply binary search algorithm to a sorted linked list, since there is no way of indexing the middle element in the list. This is the drawback in using linked list as a data structure.

12. What do you mean by free pool?
Ans: Pool is a list consisting of unused memory cells which has its own pointer.

13. What do you mean by garbage collection?
Ans: It is a technique in which the operating system periodically collects all the deleted space onto the free storage list.
It takes place when there is minimum amount of space left in storage list or when CPU is ideal.
The alternate method to this is to immediately reinsert the space into free storage list which is time consuming.

14. What do you mean by overflow and underflow?
Ans: When new data is to be inserted into the data structure but there is no available space i.e. free storage list is empty this situation is called overflow.
When we want to delete data from a data structure that is empty this situation is called underflow.

15. What are the disadvantages array implementations of linked list?
Ans:
i) The no of nodes needed can’t be predicted when the program is written.
ii) The no of nodes declared must remain allocated throughout its execution

16. What is a queue?
Ans: A queue is an ordered collection of items from which items may be deleted at one end (front end) and items inserted at the other end (rear end).
It obeys FIFO rule there is no limit to the number of elements a queue contains.

17. What is a priority queue?
Ans: The priority queue is a data structure in which the intrinsic ordering of the elements (numeric or alphabetic)
Determines the result of its basic operation. It is of two types
i) Ascending priority queue- Here smallest item can be removed (insertion is arbitrary)
ii) Descending priority queue- Here largest item can be removed (insertion is arbitrary)

18. What are the disadvantages of sequential storage?
Ans:
i) Fixed amount of storage remains allocated to the data structure even if it contains less element.
ii) No more than fixed amount of storage is allocated causing overflow

19. What are the disadvantages of representing a stack or queue by a linked list?
Ans:
i) A node in a linked list (info and next field) occupies more storage than a corresponding element in an array.
ii) Additional time spent in managing the available list.

20. What is dangling pointer and how to avoid it?
Ans: After a call to free(p) makes a subsequent reference to *p illegal, i.e. though the storage to p is freed but the value of p(address) remain unchanged .so the object at that address may be used as the value of *p (i.e. there is no way to detect the illegality).Here p is called dangling pointer.
To avoid this it is better to set p to NULL after executing free(p).The null pointer value doesn’t reference a storage location it is a pointer that doesn’t point to anything.

21. What are the disadvantages of linear list?
Ans:
i) We cannot reach any of the nodes that precede node (p)
ii) If a list is traversed, the external pointer to the list must be persevered in order to reference the list again

22. Define circular list?
Ans: In linear list the next field of the last node contain a null pointer, when a next field in the last node contain a pointer back to the first node it is called circular list.
Advantages – From any point in the list it is possible to reach at any other point

23. What are the disadvantages of circular list?
Ans:
i) We can’t traverse the list backward
ii) If a pointer to a node is given we cannot delete the node

24. Define double linked list?
Ans: It is a collection of data elements called nodes, where each node is divided into three parts
i) An info field that contains the information stored in the node
ii) Left field that contain pointer to node on left side
iii) Right field that contain pointer to node on right side

25. Is it necessary to sort a file before searching a particular item ?
Ans:
If less work is involved in searching a element than to sort and then extract, then we don’t go for sort
If frequent use of the file is required for the purpose of retrieving specific element, it is more efficient to sort the file.
Thus it depends on situation.

26. What are the issues that hamper the efficiency in sorting a file?
Ans: The issues are
i) Length of time required by the programmer in coding a particular sorting program
ii) Amount of machine time necessary for running the particular program
iii)The amount of space necessary for the particular program .

27. Calculate the efficiency of sequential search?
Ans: The number of comparisons depends on where the record with the argument key appears in the table
If it appears at first position then one comparison
If it appears at last position then n comparisons
Average=(n+1)/2 comparisons
Unsuccessful search n comparisons
Number of comparisons in any case is O (n).

28. Is any implicit arguments are passed to a function when it is called?
Ans: Yes there is a set of implicit arguments that contain information necessary for the function to execute and return correctly. One of them is return address which is stored within the function’s data area, at the time of returning to calling program the address is retrieved and the function branches to that location.

29. Parenthesis is never required in Postfix or Prefix expressions, why?
Ans: Parenthesis is not required because the order of the operators in the postfix /prefix expressions determines the actual order of operations in evaluating the expression

30. List out the areas in which data structures are applied extensively?
Ans:
Compiler Design,
Operating System,
Database Management System,
Statistical analysis package,
Numerical Analysis,
Graphics,
Artificial Intelligence,
Simulation

31. What are the major data structures used in the following areas : network data model & Hierarchical data model.
Ans:
RDBMS – Array (i.e. Array of structures)
Network data model – Graph
Hierarchical data model – Trees

32. If you are using C language to implement the heterogeneous linked list, what pointer type will you use?
Ans: The heterogeneous linked list contains different data types in its nodes and we need a link, pointer to connect them. It is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is capable of storing pointer to any type as it is a generic pointer type.

33. Minimum number of queues needed to implement the priority queue?
Ans: Two. One queue is used for actual storing of data and another for storing priorities.

34. What is the data structures used to perform recursion?
Ans: Stack. Because of its LIFO (Last In First Out) property it remembers its ‘caller’ so knows whom to return when the function has to return. Recursion makes use of system stack for storing the return addresses of the function calls.
Every recursive function has its equivalent iterative (non-recursive) function. Even when such equivalent iterative procedures are written, explicit stack is to be used.

35. What are the notations used in Evaluation of Arithmetic Expressions using prefix and postfix forms?
Ans: Polish and Reverse Polish notations.

36. Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent Prefix and Postfix notations.
Ans: Prefix Notation:
^ – * +ABC – DE + FG
Postfix Notation:
AB + C * DE – – FG + ^


37. Sorting is not possible by using which of the following methods?
(a) Insertion
(b) Selection
(c) Exchange
(d) Deletion

Ans: (d) Deletion.
Using insertion we can perform insertion sort, using selection we can perform selection sort, using exchange we can perform the bubble sort (and other similar sorting methods). But no sorting method can be done just using deletion.

38. List out few of the Application of tree data-structure?
Ans:
The manipulation of Arithmetic expression,
Symbol Table construction,
Syntax analysis.

39. List out few of the applications that make use of Multilinked Structures?
Ans: Sparse matrix, Index generation.

40. in tree construction which is the suitable efficient data structure?
(A) Array (b) Linked list (c) Stack (d) Queue (e) none
Ans: (b) Linked list



41. What is the type of the algorithm used in solving the 8 Queens problem?
Ans: Backtracking

42. In an AVL tree, at what condition the balancing is to be done?
Ans: If the ‘pivotal value’ (or the ‘Height factor’) is greater than 1 or less than –1.

43. There are 8, 15, 13, 14 nodes were there in 4 different trees. Which of them could have formed a full binary tree?
Ans: 15
In general:
There are 2n-1 nodes in a full binary tree.

By the method of elimination:
Full binary trees contain odd number of nodes. So there cannot be full binary trees with 8 or 14 nodes, so rejected. With 13 nodes you can form a complete binary tree but not a full binary tree. So the correct answer is 15.
Note: Full and Complete binary trees are different. All full binary trees are complete binary trees but not vice versa.

44. In RDBMS, what is the efficient data structure used in the internal storage representation?
Ans: B+ tree. Because in B+ tree, all the data is stored only in leaf nodes, that makes searching easier. This corresponds to the records that shall
be stored in leaf nodes.

45. One of the following tree structures, which is, efficient considering space and time complexities?
a) Incomplete Binary Tree.
b) Complete Binary Tree.
c) Full Binary Tree.
Ans:
b) Complete Binary Tree.
By the method of elimination:
Full binary tree loses its nature when operations of insertions and deletions are done. For incomplete binary trees,
extra property of complete binary tree is maintained even after operations like additions and deletions are done on it.

46. What is a spanning Tree?
Ans: A spanning tree is a tree associated with a network. All the nodes of the graph appear on the tree once. A minimum spanning tree is a spanning tree organized so that the total edge weight between nodes is minimized.

47. Does the minimum spanning tree of a graph give the shortest distance between any 2 specified nodes?
Ans: No.
Minimal spanning tree assures that the total weight of the tree is kept at its minimum. But it doesn’t mean that the distance between any two nodes involved in the minimum-spanning tree is minimum.

48. Whether Linked List is linear or Non-linear data structure?
Ans: According to Storage Linked List is a Non-linear one.

OS Related Questions

1.What is an operating system?
Ans: An operating system is a program that acts as an intermediary between the user and the computer hardware. The purpose of an OS is to provide a convenient environment in which user can execute programs in a convenient and efficient manner.It is a resource allocator responsible for allocating system resources and a control program which controls the operation of the computer h/w.

2.What are the various components of a computer system?
Ans:
1. The hardware
2. The operating system
3. The application programs
4. The users.

3.What is purpose of different operating systems?
Ans:The machine Purpose Workstation individual usability &Resources utilization Mainframe Optimize utilization of hardware PC Support complex games, business application Hand held PCs Easy interface & min. power consumption

4.What are the different operating systems?
Ans:
1. Batched operating systems
2. Multi-programmed operating systems
3. timesharing operating systems
4. Distributed operating systems
5. Real-time operating systems

6.What is a boot-strap program?

7.What is BIOS?

8.Explain the concept of the batched operating systems?
Ans: In batched operating system the users gives their jobs to the operator who sorts the programs according to their requirements and executes them. This is time consuming but makes the CPU busy all the time.

9.Explain the concept of the multi-programmed operating systems?
Ans: A multi-programmed operating systems can execute a number of programs concurrently. The operating system fetches a group of programs from the job-pool in the secondary storage which contains all the programs to be executed, and places them in the main memory. This process is called job scheduling. Then it chooses a
program from the ready queue and gives them to CPU to execute. When a executing program needs some I/O operation then the operating system fetches another program and hands it to the CPU for execution, thus keeping the CPU busy all the time.

10.Explain the concept of the timesharing operating systems?
Ans: It is a logical extension of the multi-programmed OS where user can interact with the program. The CPU executes multiple jobs by switching among them, but the switches occur so frequently that the user feels as if the operating system is running only his program.

11.Explain the concept of the multi-processor systems or parallel systems?
Ans: They contain a no. of processors to increase the speed of execution, and reliability, and economy. They are of two types:
1. Symmetric multiprocessing
2. Asymmetric multiprocessing
In Symmetric multi processing each processor run an identical copy of the OS, and these copies communicate with each other as and when needed.But in Asymmetric multiprocessing each processor is assigned a specific task.

12.Explain the concept of the Distributed systems?
Ans: Distributed systems work in a network. They can share the network resources,communicate with each other

13.Explain the concept of Real-time operating systems?
Ans: A real time operating system is used when rigid time requirement have been placed on the operation of a processor or the flow of the data; thus, it is often used as a control device in a dedicated application. Here the sensors bring data to the computer. The computer must analyze the data and possibly adjust controls to
modify the sensor input.
They are of two types:
1. Hard real time OS
2. Soft real time OS
Hard-real-time OS has well-defined fixed time constraints. But soft real time operating systems have less stringent timing constraints.

14.Define MULTICS?
Ans: MULTICS (Multiplexed information and computing services) operating system was developed from 1965-1970 at Massachusetts institute of technology as a computing utility. Many of the ideas used in MULTICS were subsequently used in UNIX.

15.What is SCSI?
Ans: Small computer systems interface.

16.What is a sector?
Ans: Smallest addressable portion of a disk.

17.What is cache-coherency?
Ans: In a multiprocessor system there exist several caches each may containing a copy of same variable A. Then a change in one cache should immediately be reflected in all other caches this process of maintaining the same value of a data in all the caches s called cache-coherency.

18.What are residence monitors?
Ans: Early operating systems were called residence monitors.

19.What is dual-mode operation?
Ans: In order to protect the operating systems and the system programs from the malfunctioning programs the two mode operations were evolved:
1. System mode.
2. User mode.
Here the user programs cannot directly interact with the system resources, instead they request the operating system which checks the request and does the required task for the user programs-DOS was written for / intel 8088 and has no dual-mode. Pentium provides dual-mode operation.

20.What are the operating system components?
Ans:
1. Process management
2. Main memory management
3. File management
4. I/O system management
5. Secondary storage management
6. Networking
7. Protection system
8. Command interpreter system



21.What are operating system services?
Ans:
1. Program execution
2. I/O operations
3. File system manipulation
4. Communication
5. Error detection
6. Resource allocation
7. Accounting
8. Protection

22.What are system calls?
Ans: System calls provide the interface between a process and the operating system. System calls for modern Microsoft windows platforms are part of the win32 API, which is available for all the compilers written for Microsoft windows.

23.What is a layered approach and what is its advantage?
Ans: Layered approach is a step towards modularizing of the system, in which the operating system is broken up into a number of layers (or levels), each built on top of lower layer. The bottom layer is the hard ware and the top most is the user interface.The main advantage of the layered approach is modularity. The layers are
selected such that each uses the functions (operations) and services of only lower layer. This approach simplifies the debugging and system verification.

24.What is micro kernel approach and site its advantages?
Ans: Micro kernel approach is a step towards modularizing the operating system where all nonessential components from the kernel are removed and implemented as system and user level program, making the kernel smaller.The benefits of the micro kernel approach include the ease of extending the operating system. All new services are added to the user space and consequently do not require modification of the kernel. And as kernel is smaller it is easier to upgrade it. Also this approach provides more security and reliability since most services are running as user processes rather than kernel’s keeping the kernel intact.

25.What are a virtual machines and site their advantages?
Ans: It is the concept by which an operating system can create an illusion that a process has its own processor with its own (virtual) memory. The operating system implements virtual machine concept by using CPU scheduling and virtual memory.

1. The basic advantage is it provides robust level of security as each virtual machine is isolated from all other VM. Hence the system resources are completely protected.
2. Another advantage is that system development can be done without disrupting normal operation. System programmers are given their own virtual machine, and as system development is done on the virtual machine instead of on the actual
physical machine.
3. Another advantage of the virtual machine is it solves the compatibility problem.
EX: Java supplied by Sun micro system provides a specification for java virtual machine.

26.What is a process?
Ans: A program in execution is called a process. Or it may also be called a unit of work. A process needs some system resources as CPU time, memory, files, and i/o devices to accomplish the task. Each process is represented in the operating system by a process control block or task control block (PCB).Processes are of two types:
1. Operating system processes
2. User processes

27.What are the states of a process?
Ans:
1. New
2. Running
3. Waiting
4. Ready
5. Terminated

28.What are various scheduling queues?
Ans:
1. Job queue
2. Ready queue
3. Device queue

29.What is a job queue?
Ans: When a process enters the system it is placed in the job queue.


30.What is a ready queue?
Ans: The processes that are residing in the main memory and are ready and waiting to execute are kept on a list called the ready queue.

31.What is a device queue?
Ans: A list of processes waiting for a particular I/O device is called device queue.

32.What is a long term scheduler & short term schedulers?
Ans: Long term schedulers are the job schedulers that select processes from the job queue and load them into memory for execution. The short term schedulers are the CPU schedulers that select a process form the ready queue and allocate the CPU to one of them.

33.What is context switching?
Ans: Transferring the control from one process to other process requires saving the state of the old process and loading the saved state for new process. This task is known as context switching.

34.What are the disadvantages of context switching?
Ans: Time taken for switching from one process to other is pure over head. Because the system does no useful work while switching. So one of the solutions is to go for threading when ever possible.

35.What are co-operating processes?
Ans: The processes which share system resources as data among each other. Also the processes can communicate with each other via interprocess communication facility generally used in distributed systems. The best example is chat program used on the www.

36.What is a thread?
Ans: A thread is a program line under execution. Thread sometimes called a light-weight process, is a basic unit of CPU utilization; it comprises a thread id, a program counter, a register set, and a stack.

37.What are the benefits of multithreaded programming?
Ans:
1. Responsiveness (needn’t to wait for a lengthy process)
2. Resources sharing
3. Economy (Context switching between threads is easy)
4. Utilization of multiprocessor architectures (perfect utilization of the multiple processors).

38.What are types of threads?
Ans:
1. User thread
2. Kernel thread
User threads are easy to create and use but the disadvantage is that if they perform a blocking system calls the kernel is engaged completely to the single user thread blocking other processes. They are created in user space.Kernel threads are supported directly by the operating system. They are slower to create and manage. Most of the OS like Windows NT, Windows 2000, Solaris2, BeOS, and Tru64 Unix support kernel threading.

39.Which category the java thread do fall in?
Ans: Java threads are created and managed by the java virtual machine, they do not easily fall under the category of either user or kernel thread……


40.What are multithreading models?
Ans: Many OS provide both kernel threading and user threading. They are called multithreading models. They are of three types:
1. Many-to-one model (many user level thread and one kernel thread).
2. One-to-one model
3. Many-to –many
In the first model only one user can access the kernel thread by not allowing multi-processing. Example: Green threads of Solaris.The second model allows multiple threads to run on parallel processing systems. Creating user thread needs to create corresponding kernel thread (disadvantage).Example: Windows NT, Windows 2000, OS/2.The third model allows the user to create as many threads as necessary and the corresponding kernel threads can run in parallel on a multiprocessor.
Example: Solaris2, IRIX, HP-UX, and Tru64 Unix.

41.What is a P-thread?
Ans: P-thread refers to the POSIX standard (IEEE 1003.1c) defining an API for thread creation and synchronization. This is a specification for thread behavior, not an implementation. The windows OS have generally not supported the P-threads.

42.What are java threads?
Ans: Java is one of the small number of languages that support at the language level for the creation and management of threads. However, because threads are managed by the java virtual machine (JVM), not by a user-level library or kernel, it is difficult to classify Java threads as either user- or kernel-level.

43.What is process synchronization?
Ans: A situation, where several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place, is called race condition. To guard against the race condition we need to ensure that only one process at a time can be manipulating
the same data. The technique we use for this is called process synchronization.

44.What is critical section problem?
Ans: Critical section is the code segment of a process in which the process may be changing common variables, updating tables, writing a file and so on. Only one process is allowed to go into critical section at any given time (mutually exclusive).The critical section problem is to design a protocol that the processes can use to
co-operate. The three basic requirements of critical section are:
1. Mutual exclusion
2. Progress
3. bounded waiting
Bakery algorithm is one of the solutions to CS problem.

45.What is a semaphore?
Ans: It is a synchronization tool used to solve complex critical section problems. A semaphore is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: Wait and Signal.

46.What is bounded-buffer problem?
Ans: Here we assume that a pool consists of n buffers, each capable of holding one item. The semaphore provides mutual exclusion for accesses to the buffer pool and is initialized to the value 1.The empty and full semaphores count the number of empty and full buffers, respectively. Empty is initialized to n, and full is initialized to 0.

47.What is readers-writers problem?
Ans: Here we divide the processes into two types:
1. Readers (Who want to retrieve the data only)
2. Writers (Who want to retrieve as well as manipulate)
We can provide permission to a number of readers to read same data at same time.But a writer must be exclusively allowed to access. There are two solutions to this problem:
1. No reader will be kept waiting unless a writer has already obtained permission to use the shared object. In other words, no reader should wait for other readers to complete simply because a writer is waiting.
2. Once a writer is ready, that writer performs its write as soon as possible. In other words, if a writer is waiting to access the object, no new may start reading.

48.What is dining philosophers’ problem?
Ans: Consider 5 philosophers who spend their lives thinking and eating. The philosophers share a common circular table surrounded by 5 chairs, each belonging to one philosopher. In the center of the table is a bowl of rice, and the table is laid with five single chop sticks. When a philosopher thinks, she doesn’t interact with her colleagues.
From time to time, a philosopher gets hungry and tries to pick up two chop sticks that are closest to her .A philosopher may pick up only one chop stick at a time. Obviously she can’t pick the stick in some others hand. When a hungry philosopher has both her chopsticks at the same time, she eats without releasing her chopsticks. When she is finished eating, she puts down both of her chopsticks and start thinking again.

49.What is a deadlock?
Ans: Suppose a process request resources; if the resources are not available at that time the process enters into a wait state. A waiting process may never again change state, because the resources they have requested are held by some other waiting processes. This situation is called deadlock.

50.What are necessary conditions for dead lock?
Ans:
1. Mutual exclusion (where at least one resource is non-sharable)
2. Hold and wait (where a process hold one resource and waits for other resource)
3. No preemption (where the resources can’t be preempted)
4. circular wait (where p[i] is waiting for p[j] to release a resource. i= 1,2,…n
j=if (i!=n) then i+1
else 1 )


51.What is resource allocation graph?
Ans: This is the graphical description of deadlocks. This graph consists of a set of edges E and a set of vertices V. The set of vertices V is partitioned into two different types of nodes P={p1,p2,…,pn}, the set consisting of all the resources in the system, R={r1,r2,…rn}.A directed edge Pi?Rj is called a request edge; a directed edge Rj?
Pi is called an assignment edge. Pictorially we represent a process Pi as a circle, and each resource type Rj as square.Since resource type Rj may have more than one instance, we represent each such instance as a dot within the square.When a request is fulfilled the request edge is transformed into an assignment edge. When a process releases a resource the assignment edge is deleted. If the cycle involves a set of resource types, each of which has only a single instance, then a deadlock has occurred. Each process involved in the cycle is deadlock.

52.What are deadlock prevention techniques?
Ans:
1. Mutual exclusion : Some resources such as read only files shouldn’t be mutually
exclusive. They should be sharable. But some resources such as printers must be
mutually exclusive.
2. Hold and wait : To avoid this condition we have to ensure that if a process is
requesting for a resource it should not hold any resources.
3. No preemption : If a process is holding some resources and requests another
resource that cannot be immediately allocated to it (that is the process must wait),
then all the resources currently being held are preempted(released autonomously).
4. Circular wait : the way to ensure that this condition never holds is to impose a
total ordering of all the resource types, and to require that each process requests
resources in an increasing order of enumeration.

53.What is a safe state and a safe sequence?
Ans: A system is in safe state only if there exists a safe sequence. A sequence of processes is a safe sequence for the current allocation state if, for each Pi, the resources that the Pi can still request can be satisfied by the currently available resources plus the resources held by all the Pj, with j

54.What are the deadlock avoidance algorithms?
Ans: A dead lock avoidance algorithm dynamically examines the resource-allocation state to ensure that a circular wait condition can never exist. The resource allocation state is defined by the number of available and allocated resources, and the maximum demand of the process.There are two algorithms:
1. Resource allocation graph algorithm
2. Banker’s algorithm
a. Safety algorithm
b. Resource request algorithm

55. What are the basic functions of an operating system?
Ans : Operating system controls and coordinates the use of the hardware among the various applications programs for various uses. Operating system acts as resource allocator and manager. Since there are many possibly conflicting requests for resources the operating system must decide which requests are allocated resources to operating the computer system efficiently and fairly. Also operating system is control program which controls the user programs to prevent errors and improper use of the computer. It is especially concerned with the operation and control of I/O devices.

56.Explain briefly about, processor, assembler, compiler, loader, linker and the functions executed by them.
Ans :
Processor:–A processor is the part a computer system that executes instructions .It is also called a CPU
Assembler: — An assembler is a program that takes basic computer instructions and converts them into a pattern of bits that the computer’s processor can use to perform its basic operations. Some people call these instructions assembler language and others use the term assembly language.
Compiler: — A compiler is a special program that processes statements written in a particular programming language and turns them into machine language or “code” that a computer’s processor uses. Typically, a programmer writes language statements in a language such as Pascal or C one line at a time using an editor. The file that is created contains what are called the source statements. The programmer then runs the appropriate language compiler, specifying the name of the file that contains the source statements.
Loader:–In a computer operating system, a loader is a component that locates a given program (which can be an application or, in some cases, part of the operating system itself) in offline storage (such as a hard disk), loads it into main storage (in a personal computer, it’s called random access memory), and gives that program control of the compute
Linker: — Linker performs the linking of libraries with the object code to make the object code into an executable machine code.

57. What is a Real-Time System?
Ans : A real time process is a process that must respond to the events within a certain time period. A real time operating system is an operating system that can run real time processes successfully

58. What is the difference between Hard and Soft real-time systems?
Ans : A hard real-time system guarantees that critical tasks complete on time. This goal requires that all delays in the system be bounded from the retrieval of the stored data to the time that it takes the operating system to finish any request made of it. A soft real time system where a critical real-time task gets priority over other tasks and retains that priority until it completes. As in hard real time systems kernel delays need to be bounded

59. What is virtual memory?
Ans : A virtual memory is hardware technique where the system appears to have more memory that it actually does. This is done by time-sharing, the physical memory and storage parts of the memory one disk when they are not actively being used

60. What is cache memory?
Ans : Cache memory is random access memory (RAM) that a computer microprocessor can access more quickly than it can access regular RAM. As the microprocessor processes data, it looks first in the cache memory and if it finds the data there (from a previous reading of data), it does not have to do the more time-consuming reading of data

61.Differentiate between Complier and Interpreter?
Ans : An interpreter reads one instruction at a time and carries out the actions implied by that instruction. It does not perform any translation. But a compiler translates the entire instructions.

62.What are different tasks of Lexical Analysis?
Ans : The purpose of the lexical analyzer is to partition the input text, delivering a sequence of comments and basic symbols. Comments are character sequences to be ignored, while basic symbols are character sequences that correspond to terminal symbols of the grammar defining the phrase structure of the input

63. Why paging is used?
Ans : Paging is solution to external fragmentation problem which is to permit the logical address space of a process to be noncontiguous, thus allowing a process to be allocating physical memory wherever the latter is available.

64. What is Context Switch?
Ans : Switching the CPU to another process requires saving the state of the old process and loading the saved state for the new process. This task is known as a context switch.Context-switch time is pure overhead, because the system does no useful work while switching. Its speed varies from machine to machine, depending on the memory speed, the number of registers which must be copied, the existed of special instructions(such as a single instruction to load or store all registers).

65. Distributed Systems?
Ans : Distribute the computation among several physical processors.
Loosely coupled system – each processor has its own local memory; processors communicate with one another through various communications lines, such as high-speed buses or telephone lines
Advantages of distributed systems:
->Resources Sharing
->Computation speed up – load sharing
->Reliability
->Communications

66.Difference between Primary storage and secondary storage?
Ans :
Main memory: – only large storage media that the CPU can access directly.
Secondary storage: – extension of main memory that provides large nonvolatile storage capacity.

67. What is CPU Scheduler?
Ans :
->Selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them.
->CPU scheduling decisions may take place when a process:
1.Switches from running to waiting state.
2.Switches from running to ready state.
3.Switches from waiting to ready.
4.Terminates.
->Scheduling under 1 and 4 is nonpreemptive.
->All other scheduling is preemptive.

68. What do you mean by deadlock?
Ans : Deadlock is a situation where a group of processes are all blocked and none of them can become unblocked until one of the other becomes unblocked.The simplest deadlock is two processes each of which is waiting for a message from the other

69. What is Dispatcher?
Ans :
->Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves:
Switching context
Switching to user mode
Jumping to the proper location in the user program to restart that program
Dispatch latency – time it takes for the dispatcher to stop one process and start another running.

70. What is Throughput, Turnaround time, waiting time and Response time?
Ans :
Throughput – number of processes that complete their execution per time unit
Turnaround time – amount of time to execute a particular process
Waiting time – amount of time a process has been waiting in the ready queue
Response time – amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)


81. What is Memory-Management Unit (MMU)?
Ans :Hardware device that maps virtual to physical address.
In MMU scheme, the value in the relocation register is added to every address generated by a user process at the time it is sent to memory.
->The user program deals with logical addresses; it never sees the real physical addresses

82. What are Dynamic Loading, Dynamic Linking and Overlays?
Ans :
Dynamic Loading:
->Routine is not loaded until it is called
->Better memory-space utilization; unused routine is never loaded.
->Useful when large amounts of code are needed to handle infrequently occurring cases.
->No special support from the operating system is required implemented through program design.
Dynamic Linking:
->Linking postponed until execution time.
->Small piece of code, stub, used to locate the appropriate memory-resident library routine.
->Stub replaces itself with the address of the routine, and executes the routine.
->Operating system needed to check if routine is in processes’ memory address.
->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.

83. What is fragmentation? Different types of fragmentation?
Ans : 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
->Shuffle memory contents to place all free memory together in one large block.
->Compaction is possible only if relocation is dynamic, and is done at execution time.

84. Define Demand Paging, Page fault interrupt, and Trashing?
Ans :
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,”

85. Explain Segmentation with paging?
Ans : 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).

86. Under what circumstances do page faults occur? Describe the actions taken by the operating system when a page fault occurs?
Ans : 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

87. 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?
Ans : 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.