Operating Systems and Computer Structures G2
Tutorial Exercises, 1995

• Week 2
• Week 3
• Week 4
• Week 5
• Week 6
• Week 7
• Week 10
• Week 11
• 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

1. There are a number of graphical editors available under Unix. A simple one is ted, which will edit a single file using a single window. A more complex one is axe which will allow multiple files in many windows. The most sophisticated is emacs. Choose one of these an use the online help to explore the editor.
2. Start the mail program, and read the messages that have been sent to you. Use the mail program to send messages to other people, using their login id.
3. Use the news program to read some interesting groups. A group that you can post to is uc.ise.os
4. Use the online manual to find out what the following commands do: at compress du file
5. 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. Compare the shell language recognised by the MSDOS command interpreter command.com to the bash language. How does command.com handle pipelines? Hint: see the ``Batch Processing Commands'' of the MSDOS User Guide. Would it be possible to have an Ada-like or Pascal-like command interpreter?
2. The Unix and MSDOS command interpreters use positional arguments in most commands. Some other command languages use keyword arguments instead. Discuss the advantages and disadvantages of each method.
3. Write a command ask which asks its arguments as a question, reads a reply and returns an exit code of zero if the reply began with `y' or `Y', but otherwise returns a non-zero exit code.
4. Write a command that behaves the same as ``rm -i'' that prompts for removal of a file first.
5. Write a shell script which takes a file name as first argument and a list of patterns as successive arguments. The script is to perform a ``grep'' for each pattern in turn on the file. Hint: see ``shift'' in the shell documentation.

Laboratory Week 4

1. Create shell commands for questions 4.3, 4.4 and 4.5. Test each of them by running the command testit Question-number filename where Question-number is one of 4.3, 4.4 and 4.5, and the filename is the name of the file containing your shell script.
2. You can customise your environment using the files .profile, .bashrc, xinitrc, .mwmrc and .Xdefaults. What does each of these files do?

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. The following programs in Ada and C print the odd numbers from 1 to 39 inclusive. Discuss the similarities and differences between the two.
   Ada: WITH Text_IO; WITH My_Int_IO; PROCEDURE OddNumbers IS BEGIN -- OddNumbers OddNumber: Integer; OddNumber := 1; WHILE OddNumber <= 39 LOOP My_Int_IO.Put(Item => OddNumber, Width => 3); OddNumber := OddNumber + 2; END LOOP; Text_IO.New_Line; END OddNumbers; C: #include <stdio.h> int main(int argc, char *argv[]) { int OddNumbers; OddNumbers = 1; while (OddNumbers <= 39) { printf(" %d", OddNumbers); OddNumbers += 2; } putchar('\n'); }
5. Write a C program which reads characters from standard input and writes to standard output. It converts the characters read in the following way: all upper case characters to the equivalent lower case, all lower case to the equivalent upper case, and all others left unaltered.
6. Write a program that reads characters from standard input, checking that they are all digits. The program should exit with a zero exit status if it reaches end-of-line and all characters read are digits. If it reads a non-digit character it should cease reading and exit with a non-zero exit status.
7. Write a function ``int tolower(int ch)'' that takes a single character and converts it to lower case. If the character is not an upper-case character it is unchanged.
8. Write a function to calculate the factorial of a positive integer. If the number is negative it should return zero, otherwise it should calculate the factorial using the recusive formula 0! = 1 n! = n * (n-1)!

Laboratory Week 5

1. 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.
2. The following program has a common and very serious error. What is it? What happens when you attempt to run it? int main(int argc, char *argv[]) { char *p; *p = 'a'; }
3. Create and compile the tutorial questions. Use the debugger ``ups'' or ``gdb'' to step through program execution.
4. Write a simple ``main'' program for question 8 that will read integers from standard input until EOF is reached and prints the corresponding factorial.

Tutorial Week 6

1. Write a program using an array to read in a set of numbers terminated by EOF and print them out in reverse order. Assume that no more than 100 numbers need to be read.
2. Write a function to emulate strcmp to compare two null-terminated strings. It should return -1 if the first string is lexicographically less than the second, 1 if it is greater, and 0 if they are the same.
3. Write a program to store an array of records containing student names and IDs. The program should read upto 100 records. It should then enter a loop reading student IDs and printing the corrresponding name if found.
4. Write a program to read in strings (one per line), store pointers to them in an array and print them out. NB:You will need to use ``malloc'' to create heap space to store copies of the strings.

Laboratory Week 6

1. 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.
2. 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?
3. 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 7

1. Discuss the MSDOS file system from these three viewpoints:
   1. The users view of the file system.
   2. The Microsoft C programmers API for directory manipulation (see the attached pages from the Microsoft C Programmers Reference manual).
   3. The underlying implementation of the file system (see the textbook).
2. How do MSDOS utilities such as Norton's ``undelete'' work. This utility attempts to recover a deleted file. How effective would this be in a multi-user timesharing environment? How could a file undelete program work in such an environment?
3. 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.
4. 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?
5. 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.

Laboratory Week 7

1. Write a Unix program to open, read and close a directory using the system calls ``opendir'', ``readdir'' and ``closedir''. Print the names of the files in the directory.
2. Write a Unix program that will read a filename and use the system call ``stat'' to gain information about the file. Use the macro ``S_ISDIR'' to test if the file is actually a directory.

Tutorial Week 10

1. What is the difference between internal and external fragmentation?
2. 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?
3. Which of first fit, best fit or worst fit is used by MSDOS? Why? (See the textbook.)
4. Discuss an algorithm to implement ``realloc''. What assumptions does this make about a memory allocation scheme?
5. 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 Figure in here

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

Laboratory Week 10

Tutorial Week 11

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. 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?
6. How do Terminate and Stay Resident processes in MSDOS work?

Laboratory Week 11

1. Write your own version of the call ``system'' using ``fork'' and ``wait''. What is the return value of the Unix call? How can ``wait'' determine the exit value of a child?
2. Create a child that keeps looping forever printing a message. Pause it by sending it the SIGSTOP signal. Resume it by sending SIGCONT, and then finally kill it.

Tutorial Week 12

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?

Laboratory Week 12

1. When an editor opens a file for editing, it makes a private copy and works on that. Multiple editors can be started on a single file, each with their own private copy. This can lead to inconsistent states between them. What does this mean? Write a program safe_edit that uses a lock file to allow only one process to edit a given file at a time. The program should take one argument that is the file name, look for a suitable lock file and only execute the editor if the lock is not set. What should the program do on exit? What happens if it crashes?

Tutorial Week 13

1. Suppose a network is organised as a binary tree. What is the best-case communication delay? The worst case? How is the worst case related to the number of nodes in the tree?
2. What imformation is contained in addresses that will allow a message to be routed from jan@canberra.edu.au to bill_gates@microsoft.com?
3. Because a file server may crash, the file system may be replicated on another server. What are the advantages and disadvantages of this?
4. How many IP addresses can there be? The Internet is estimated to have about 10 million computers attached to it, but it is running out of addresses. How can this be?
5. A large software project may have n files. To speed up compilation compilation could be done on multiple machines. What is the maximum number that could profitably be used? What is the maximum speedup that could be obtained? What could stop you getting this speedup?

Laboratory Week 13

1. Use xcwis to get the telephone numbers of people on campus, and then at ANU.
2. Use netfind to find if there is anyone at ADFA with the surname Bearman.
3. Experiment with xarchie to see if you can locate interesting files.
4. The anonymous ftp site rtfm.mit.edu to examine the directory /pub/usenet-by-hierarchy. This contains information culled from the network news. For example, comp.windows.x would be in comp/windows/x. Find some interesting files.
5. From a PC lab, use ftp to transfer files to and from Unix.

Tutorial Week 14

1. If a server wishes to broadcast a message to all clients, what are the advantages and disadvantages of
   a) connection-oriented
   b) connectionless transmission?
2. A server may wish to receive requests on more than one port. How can this be done?
3. If a process is sending debit and credit requests as individual messages, should a connection-oriented or connectionless protocol be used?
4. How can a two-byte short integer be encoded into a four-byte word so that it can be read correctly on both big-endian and little-endian machines? How can two machines (that each know their own ordering) decide whether to byte-swap incoming messages?

Laboratory Week 14

1. The ``finger'' service can use either TCP or UDP. With TCP, it expects to be sent an empty line, that is a buffer with just a newline in it. It returns a list of all people logged in and then closes the connection. Write a TCP finger client that takes an Internet address and prints who is logged on at that host.
2. A coca-cola machine has been connected to the Internet, so that when you finger it, it returns the number of cans it contains, etc. Its address is coke@cs.cmu.edu. Another one is at drink@drink.csh.rit.edu. Use your finger program to connect to these.

Tutorial Week 15

1. A procedure ``incr2'' takes two arguments, and adds one to each argument. Discuss what happens in the procedure call incr2(x, x) if the parameters are
   a) call by value.
   b) call by reference.
   c) IN OUT parameters.
2. If a remote procedure call attempts to read the first block of a file, this can be re-done any number of times, so that ``at least once'' semantics can be used for retries. How about writing the first block? Writing a later block?
3. How can the ``session semantics'' method be implemented for a client running on a different machine to the server? How can session semantics be implemented locally, using say the Unix file system?
4. Suppose clients cache files while making changes to them. A way of resolving the cache coherence problem could be to examine the ``last modified'' time of the file on the host and in the cache to decide if the server copy is correct. Are there any problems in this?
5. When a request to open a file is made on a local (Unix) file system, the file system uses the information in the inode such as owner, group and permission flags to determine whether the file access can be made. What security mechanisms could be used in a distributed file system? Is there a difference in a remote file system where the server maintains state, versus a stateless system?

Laboratory Week 15