Program Development using Unix
Tutorial Exercises, 1997

• Week 2
• Week 3
• Week 4
• Week 5
• Week 6
• Week 7
• Week 8
• Week 9
• Week 12
• Week 13
• Week 14
• Week 15

Tutorial Week 2

1. What are the two main functions of an Operating System?
2. In handling tasks such as printing, why is spooling used?
3. List some differences between PC Operating Systems and mainframe Operating Systems.
4. Why is the shell not part of the Operating System?
5. List several types of hardware components that may vary between different installations of the same computer type. How should these differences be handled by the Operating System?
6. List the MSDOS commands to perform the common operations given in the lecture. Which of these commands are executed by command.com? List some of the differences between these commands and their Unix equivalents.
7. Is Microsoft Windows an Operating System? Is Windows 95 an Operating System? Is Windows NT an Operating System? What are some of the differences between Microsoft Windows and Windows NT?
8. How does Microsoft Windows allow the user to perfrom the common commands given in the lecture?
9. List some of the differences between Unix file name globbing and the similar pattern matching mechanism in MSDOS.

Laboratory Week 2

2. Use the online manual to find out what the following commands do: at compress du file
3. What do the following commands do: ls -R ls -t ls -rta

Tutorial Week 3

1. Write a command ``dir'' to perform a long listing of files in the current directory.
2. Write a pipeline to count the number of files in the current directory.
3. Write a shell script that uses a pipeline to count the total number of bytes in all files in the current directory.
4. Write a pipeline which, given a pattern and a filename, will write to standard output the first line (and only the first line) of the file containing the pattern.
5. Write a shell script that takes two arguments to show the differences in file names between two directories.
6. Write a shell script that given a pattern will search all files recursively from the current directory and report the names of all files containing the pattern.
7. Write a shell script to change a filename given as argument to lower case, and rename the old file name to the new file name.

Laboratory Week 3

1. Create shell commands for each of the questions of the week 3 tutorial. Test each of them by running the command testit Question-number filename where Question-number is one of 3.1, 3.2, etc and the filename is the name of the file containing your shell script.

Tutorial Week 4

1. To create a temporary file, Unix has the call

   char *tmpnam(char *s);
         

   which returns the name of a unique file. This file can be opened for reading or writing with guarantee that no other process shoud be using this.
   1. Write a program to generate a unique file name and print it.
   2. Why is this not part of the standard library?
2. The Win32 library has two functions

   DWORD GetTempPath(DWORD bufferSize, LPTSTR buffer);
   UINT GetTempFileName(LPCTSTR path, LPCTSTR prefix,
                              UNIT unique, LPTSTR tempFile);
         

   to get a temporary path name. The path from the first call becomes the path for the second. The prefix is upto three chars that start the temporary file name. unique can be zero or non-zero. The temporary name is placed in tempFile. The function returns zero on error. Write a program that generates a unique name, and prints it.
3. The Win32 function

   DWORD GetLogicalDrives()
         

   returns a 32-bit value with each bit set if the drive is available: bit 1 is one if A is available, bit 2 is one if B is available, etc.
   1. Write a program to print the list of available drives.
   2. Why is this not part of the standard library?
4. The Unix API has a function

   #include <unistd.h>
   
   int access(const char *pathname, int mode);
         

   This takes the path of a file and a bit-mask for the mode of R_OK, W_OK, X_OK and F_OK for read, write, execute, or file existence.
   1. Write a program to test if a particular file can be executed.
   2. Why is this not part of the standard library?
5. The C standard library has a function

   #include <time.h>
   
   clock_t clock(void);
         

   The value returned is the CPU time used so far as a clock_t; to get the number of seconds used, divide by CLOCKS_PER_SEC.
   1. Use this to write a program that does something (anything) and then report on the number of seconds it took.
   2. Processor clocks run at different speeds. How is this machine dependency handled?
   3. Why is this call part of the standard library and not in machine specific libraries?

Tutorial Week 5

1. What features are desirable of a language designed for writing Operating Systems?
2. What features are desirable of an applications programming language that needs to use Operating System services?
3. Must the languages used to write applications be the same as the language used to write the O/S?
4. Look in the files /usr/include/limits.h. What are the largest and smallest integers that are supported? Write and test a program to print out their values.
5. Use the online manual to read the entry in section three for ``getwd''. Write a program to print your current working directory. Note the use of MAXPATHLEN - no complete pathname is allowed to be longer than that.
6. Use the online manual to read the entry in section two for ``chdir''. Write a program to read directory names from standard input until end-of-file and change the current working directory. What patterns are recognised out of `.', `..', `~', etc?
7. Write a program to read a single line of input and execute this as a command using the call ``system''. Can this handle ``cd'', or must you treat this as a special case?

Tutorial Week 6

1. When a file is erased its blocks are generally put back on the free list, but they are not erased. Do you think it would be a good idea to have the Operating System erase each block before releasing it? Consider both security and performance factors in your answer, and explain the effect of each.
2. Some systems provide a call to rename a file. Is there any difference between using such a function or just copying the old file and then deleting it?
3. An Operating System may allow filenames of unlimited length, only upto a maximum length or of a fixed length. Discuss how this affects entries in directory files with particular reference to adding and deleting files from the directory and searching for filenames in the directory.
4. An existing file can have extra bytes appended to the end of it, leaving the existing contents unaltered. Discus how this can be done using a. The MSDOS file system. b. The Unix file system.
5. Many computer viruses add their own code to existing files, changing their length. A simple way of detecting this is to compare file lengths before and after. Discuss the advantages and disadvantages of this.

Tutorial Week 7

1. The memory of a system is 128 blocks and is organised using the buddy system. Intitially all memory is free. Requests are received of

           obtain 6 blocks
           obtain 10 blocks
           obtain 16 blocks
           obtain 8 blocks
   

   Show the state of memory after each request.
2. Given a heap memory management scheme with the following free list: Free element Size in kb 1 100 2 500 3 200 4 300 5 600 The following process requests will be received in order: Process number Size in kb 1 212 2 417 3 112 4 426 Show the memory is allocated using the memory allocation schemes
   1. First Fit
   2. Best Fit
3. What is the difference between internal and external fragmentation?
4. Consider a variable size partition memory management scheme where the free list consists of the following partitions, ordered as given: 10k, 4k, 20k, 18k, 7k, 9k, 12k and 15k Which hole is taken for successive segment requests of 12k, 10k, 9k and 8k for first fit, best fit, worst fit. What holes are left?
5. Which of first fit, best fit or worst fit is used by MSDOS? Why? (See the textbook.)
6. Discuss an algorithm to implement ``realloc''. What assumptions does this make about a memory allocation scheme?

Tutorial Week 8

1. Consider a virtual memory paging scheme for a 6 page frame memory and a 12 page virtual address space with 512 (01000) pages. Using the following page table, what are the actual physical addresses of these virtual addresses? 020, 04100, 010300, 05376

   Virtual      Page
    page        index
   ------------------
     0           2
     1
     2           3
     3
     4           5
     5
     6
     7           0
     8           4
     9           1
   

Tutorial Week 9

1. Suppose processes can share pages (eg both using the same library code). How can the process manager tell that a page is no longer required by any process?
2. How can the C function system() by used to create asynchronous processes under Unix? (Hint: how can the user create asynchronous processes at the command prompt?) How many processes are created by doing this? What is happening to each, in terms of fork() and exec()?
3. Write a program in C to count how many processes it can create. It should repeatedly create new process till it fails. Then it should print the number of processes created and exit.
4. What fields can you explain in ps -l? What is the command ps -f showing?
5. The gdb debugger will track the parent process when a fork() is executed. A separate debugger can be started on a program by gdb program pid . Write a simple multi-process program and track each process using gdb.

1. Write a program in C/C++ that will read lines from standard input. Each line should be treated as the name of a program to execute. A new asymchronous process should be created to execute each program. Errors in executing each program should be reported.
2. Spend the rest of the tutorial entering and testing the program, to make sure you understand it. Test it on programs such as xclock, xterm, and other programs in /usr/bin/X11
3. If you have time, add a signal handler for SIGCHLD which will report when a child process terminates. See the man page for signal.

1. A shell command to count the number of processes you are running is

      ps | sed 1d | wc -l

   Rewrite this as a program in C
2. Enter and test this program.

1. Suppose a system takes one unit of time to perform a context switch, and switching is done after each process either terminates or has run for 20 units. There are three tasks in the system, and the first will require 70 units of time to run, the second will require 25 units and the third 45. Usiing round robin scheduler show which processes run and when. What percentage of time is spent in context switching? What is the average length of time for a process to complete execution?
2. In a priority scheduler, for each unit of time that a process runs its priority decreases by one. A running process is replaced when there is another process on the runnable list with a higher priority. The system starts with three processes of priority 15, 10 and 18 respectively. Show which processes run and when.
3. In a two-level scheduler with swapping, the states that a process can be in are runnable, but swapped out runnable, in main memory blocked, and swapped out blocked, in main memory running, in main memory Draw the state transition graph for this.
4. Starvation occurs when a process never gets a chance to run. Can starvation occur with round robin? with a shortest-first scheduler? with a priority scheduler?
5. How do Terminate and Stay Resident processes in MSDOS work?

Tutorial Week 15

1. Write an algorithm for implementing a simple binary semaphore using
   a) a hardware SWAP instruction
   b) A hardware Test and Set lock.
2. Semaphore waiting lists are often implemented as queues served in FIFO order. Could they be implemented as stacks? If so, what problems might it cause?
3. If an Operating System can disable interrupts, how can semaphores be implemented?
4. In an electronic funds transfer system, there are hundreds of processes that work as follows: each process reads a line of information specifying an amount of money, the account to be debited and the account to be credited. Then it locks both accounts and transfers the money, releasing the locks when done. Can this deadlock? If so, devise a scheme to avoid deadlock.
5. Suppose a shared queue is implemented using a wrap-around array. One way of controlling access to the queue is by a single semaphore that controls access to any part of the data structure. This means that it is not possible for one process to remove an element from the queue while another one simultaneously adds one. Would it be possible to use two or more semaphores to control access to each end of the queue independantly? If so, how?