Assignment:

Question 1: Write an algorithm/programs that accept an input a decimal number and converts it into hexadecimal representation.

Solution 1:

Introduction

 This question is based on number system so let's take a look at number system. When we say '11' then we often think '11' as a number which is equivalent to 'eleven' but it is not correct because '11' might represent 'three' in binary representation or even 'seventeen' in hexadecimal representation. The only difference that makes various number systems distinct is the just how many unique digits they have. So! The number system which has 10 digits is called decimal system or the one having 2 digits (0 and 1) is called binary and so on. Let's take an example of octal system. Look! We have 'eight' digits namely 0, 1, 2, 3, 4, 5, 6, 7. Now, when we finished counting up to '7' we write '10' to tell that we have used all digits at first place 1 times. So '10' in octal represents: 1 * 8 (the total number of digits) + 0 = 8. And, in this way the third place tells about the second place; fourth place tells about third place and so on. As we go further towards left the degree of the place increases exponentially so in octal '123' is: 1*8²+2*8¹+3*8⁰ = 83. How we represent any number in a particular number system is just reverse of the above logic. So! Let's write a simple algorithm for representing a number in hexadecimal representation.

Algorithm

1. Start
2. Initialize H as an empty string
3. Get a number N from user
4. Divide N by 16 and store remainder in R (R = N mod 16)
5. Divide N by 16 and store integer part of result in N (N = N div 16)
6. Insert R in front of the string H
7. Check if N is not zero then go to step 4
8. Output the string H to user
9. Stop

Program in 'C'

01 #include<stdio.h>       // For printf(); etc.
02 #include<string.h>      // For strcat(); etc.
03 #include<stdlib.h>      // For malloc(); etc.
04 
05 char *dec2hex(int dn){
06 char *hex_num, *tmp_hex_num;
07 int hex_digit;
08 // We are using malloc() here to use realloc() in future.
09     hex_num=(char*)malloc(sizeof(char));
10     tmp_hex_num=(char*)malloc(sizeof(char));
11     *hex_num='\0';
12     *tmp_hex_num='\0';
13     if(dn == 0){
14         hex_num = (char*)realloc(hex_num, sizeof(char) * 2);
15         *hex_num = '0';
16         *(hex_num + 1) = '\0';
17         return hex_num;
18     }
19     while(dn != 0){
20         hex_digit = dn % 16;
21         dn = dn / 16;
22 // Allocate memory (old size + 1 char for new digit + 1 for '\0')
23         tmp_hex_num = (char*)realloc(tmp_hex_num,
24                                 strlen(hex_num) + sizeof(char) * 2);
25         if(hex_digit <= 9 && hex_digit >= 0)
26             *tmp_hex_num = (char)((int)'0' + hex_digit);
27         else if(hex_digit <= 15 && hex_digit >= 10)
28             *tmp_hex_num = (char)((int)'A' + hex_digit - 10);
29         *(tmp_hex_num + 1) = '\0';
30 // Insert the old string behind the new digit
31         (void)strcat(tmp_hex_num,hex_num);
32         hex_num = (char*)realloc(hex_num, strlen(tmp_hex_num) + 1);
33         (void)strcpy(hex_num,tmp_hex_num);
34     }
35 return hex_num==NULL?"":hex_num;
36 }
37 
38 main(){
39 int dec_num;
40     printf("Enter a decemal number to be converted in Hex: ");
41     (void)scanf("%d",&dec_num);
42     printf("The equivelent Hex number is: %s\n",dec2hex(dec_num));
43 return 0;
44 }

Conclusion

 It was known to us that as we go further towards left the degree of the place increases exponentially so in order do the reverse action we divide the number with the base. We take the remainder as our next digit and result as the new number for next iteration. In this way we actually chop off the digit from the number so we need not increase the base exponentially.

Question 2: Consider the following set of processes that arrive in the ready queue at the same time:

Consider the following scheduling algorithms:
First Come First Serve (FCFS), Shortest Job First (SJF) and Round Robin (Quantum=1).
What is the turnaround time of each process for each of the above scheduling algorithms? What is the waiting time of each process for each of the above scheduling algorithms?

Solution 2:

Introduction

 We are assigned to compare these three scheduling algorithms in terms turnaround time and waiting time. Before we study these scheduling algorithms, let me define the turnaround time and the waiting time first.

Turnaround Time

 Actually, turnaround time is the total lifetime of a process. It is the time from the startup of the process to its end. Turnaround time includes the time spent while loading the process into the memory and the time while waiting in the ready queue or for the I/O to be completed. But, since we are not informed about all these situations, we will assume the turnaround time as the sum of CPU Time and waiting time in the ready queue.

Waiting Time

 Waiting time is the all that time in which the process was waiting to get the CPU for its processing. In single process system a process might wait for CPU while it is performing I/O or any system specific job but in a multiprocessing system it must also wait until other processes have taken their time. Since all other aspects have been ignored in this problem, we have to roughly define the waiting time as turnaround time minus CPU time.

Response Time

 Although not asked in the question, I am defining it because one of the scheduling algorithms (Round Robin) has been developed to optimize the response time. Response time is the time that an interactive system takes to feedback the user's action (command, request etc.).

 Now, let us one by one understand each specified scheduling algorithm and calculate the corresponding turnaround time and waiting time with the help of the given ready queue of five jobs.

First Come First Serve (FCFS)

 This is the simplest scheduling algorithm ever. It takes the first job from the read queue and run it until it terminates then takes the next one from the queue and so on until all the jobs in the queue has been completed

Shortest Job First (SJF)

 There is no difference between FCFS and SJF except that SJF sort the queue before doing anything. It dose so just to reduce the waiting time. Actually in FCFS even a very small job like JOB5 suffers a turnaround time of 23 units while it needs only 2 units of CPU time due to long waiting time.

Round Robin

 The biggest difference between the above two scheduling algorithms and this is that, unlike FCFS and SJF, Round Robin is a preemptive scheduling algorithm. Preemption means being prepared in advance. Instead of running a process till its end, the Round Robin algorithm takes control from the process after a fixed interval and gives it to the another one. Since it rotate the control between the processes it dose better distribution of CPU time.

Comparative Study

 Now let us look at the performance differences of the above scheduling algorithms by means of their turnaround time and waiting time. Look at the table below. In this table bold figures are the smallest and underlined figures are the biggest values of their category.
 

	FCFS	SJF	Round Robin
Average Waiting Time	10.40	6.60	12.60
Average Turnaround Time	15.00	11.20	17.20
Standard Deviation of Waiting Time	7.39	5.78	3.38
Standard Deviation of Turnaround Time	6.60	7.57	5.19

The above table shows that SJF is best on the scale of average turnaround and waiting time but as soon as we come to even distribution (Standard Deviation) of CPU time nothing can beat the Round Robin.

Conclusion

 Here is an interesting fact to understand that average of a list if numbers does not have much statistical significance because a single datum can make a big change to the average of a list of data. That is why we also used standard deviation so that we may find out about the scheduling algorithm which distribute the CPU time most evenly between the processes. Round Robin algorithm is best on that scale and that is the reason behind its popularity. Most advanced operating systems like Unix/Linux, Windows NT, OS-X etc. uses Round Robin algorithm for scheduling their processes.

Question 3: Write a shell program to generate the first n terms of the following sequence without using multiplication.

Solution 3:

Introduction

 So! Here is the shell script. It is written as to be compatible with System V 3.2 but since it is a very old version and hard to find so I just tested them on Linux's ash (a Bourne shell clone) and bash (Bourne Again SHell), and it is working fine. I have used read command to get data input instead of command-line parameters because it is more interactive and user friendly. I have used a better mechanism for specifying the shell. Instead of using '#' (for 'C' Shell) and ':' (for Bourne Shell), I have used '#!' which can be used to specify the path to the shell to be used.

Script

$ cat sequence.sh
#!/bin/sh
echo -----------------------------------------------------------------------
read -p "Type the number of terms and then press Enter: " terms
num=1
index=0
while [ $index -lt $terms ];do
    echo -n $num" "
    num=$((num+num))
    index=$((index+1))
done	
echo
echo -----------------------------------------------------------------------

$ _

Conclusion

 This script is as simple as addition of two numbers. It simply runs a loop to the given number of times and every time it doubles the number $num to generate the desired series. Since use of multiplication is prohibited in the constraint given in the assignment we have used addition to the number itself to make it double for each iteration.

Question 4: Discuss the features of UNIX operating system that have made them such phenomenally successful operating system.

Solution 4:

Introduction

 Before we come to the features let me tell you about the background that the UNIX operating system has. UNIX was not developed commercially and I think that this is a big reason behind its success because its creators were not overwhelmed with unworthy user requirements and marketing strategies (as Microsoft). Since they were developing the system for their selves, they were free to design it as they wish. Programming is an art and no one can do one's best programming until one is free to think and design the software at will. This thing led the programmers (Ken Thompson & Dennis M. Ritchie) of UNIX operating system to design some really good features which made it such phenomenally successful operating system. Here I will also say about the features that were not in original UNIX but build on its philosophy and now they are the essential features of UNIX (sockets for example). Some of these features are given below:

Portability

 Before UNIX all operating systems were written in assembly language of their own machine that is why they were non-portable but UNIX was the first operating systems that was written in a high level language called 'C'. Due to this UNIX become very portable and that is why it is ported to almost all types of systems from small PCs to large mainframes and supercomputers.

Programmer Friendly

 Another big reason behind its success is its programmer friendly environment. Since, as I have told you before that UNIX was not developed as a commercial product, it was fully developed by programmers to support their selves. It means instead of being user friendly like other operating systems it is a programmer friendly OS. A user friendly operating system doesn't have any good impact on its development process but being a programmer friendly OS, UNIX speed up its own development process at geometric rate. In this way many outstanding programs were developed for UNIX to make it successful.

Simple Yet Powerful File System

 One of the principle philosophies of UNIX is "Everything is file". It elevates the importance of file system in UNIX. UNIX file system is fully hierarchical and always stays in a single hierarchy. Even multiple file systems also never used as different hierarchies, instead, UNIX has "mount" system call to merge then down to a single hierarchy. This makes UNIX so flexible that a system administrator may easily and seamlessly add more storage devices to increase the system's secondary memory if required.

Preemptive Multitasking

 UNIX was not the first OS that uses preemptive multitasking but it used it so nicely that it became one of the reasons behind its success. UNIX uses priority based round robin scheduler to schedule its processes. One more interesting thing was the shell layers which allowed users to run multiple interactive programs in parallel. Although only one of them could remain in foreground, it provided hot-keys to switch between processes. Now a days UNIX shells itself has these facilities (CTRL-Z to stop, bg to send in background and fg to bring in foreground etc.).

IPC

 This is a something for which people will always owe to UNIX. In the beginning there were pipes, then came the sockets and they shrunk the glob (See §Communication for details). Almost all operating systems of these days are imitating techniques like pipes and sockets for interprocess communications and I am sure that in the future also they have to imitate nothing but the UNIX.

Communication

 UNIX was a networking capable operating system. Initially it used some simple techniques to communicate like UUCP (User to User CoPy) but as the time passed more powerful techniques like sockets (developed at Berkeley University) came into view and become the path of almost all communication on the Internet. Even before Internet there was a network called USENET, which is still comparable to Internet. USENET was fully a UNIX network and still it makes a big part of Internet. Almost all Internet protocols are so close to UNIX that sometime you feel that you are programming in UNIX while you develop any Internet application.

Multiuser Environment

 UNIX not only support multiuser environment but it can be used to simultaneously access the system through multiple terminals by different users which made it a fully multiuser operating system. Remote login and Telnet features are also available to access the machine from a different machine or OS. To manage multiple users it provide best security ever (See §Security for details).

Security

 UNIX provides tree levels for making your things secure means you can give different privileges to the user group and others. There are at least four types of privileges as well named "read", "write", "execute" and "set user id". With these privileges you can safely work with many users. What makes you recognized to the system is your user id and password. Password is the key to your security. Although, I can break the root password within a few minutes, I still say that UNIX has the best security features in the world. You might think that what a stupid thing is this but read the following before thinking so.

UNIX was not designed to stop you from doing stupid things, because that would also stop you from doing clever things.

-- Doug Gwyn

 Security is not about restricting you to do but it is to check whether the right person is doing it or not. For example suppose the system administrator has been fired and nobody except him knows the password. On other operating systems you might have to reinstall the system. But on UNIX you need not to do such stupid things but the new system administrator can easily break the password. Actually UNIX philosophy is to assume everyone as system administrator who has physical access to the server. Normally all servers are physically secured so there is no need to restrict a person who has a physical access. Although even after getting physical access it is not a child's play to break the password.

Conclusion

 The success of UNIX operating system is not in providing any complex features but in showing that how small programs can be used to solve the complex problems. In other words the success of UNIX lies not so much in new inventions but rather in the full exploitation of a carefully selected set of fertile ideas, and especially in showing that they can be keys to the implementation of a small and yet powerful operating system. One more secret behind the success of UNIX is an unofficial rule of thumb that is very famous among hackers. UNIX follow this rule to KISS (Keep It Simple Stupid) and that is the greatest reason behind its success.