Operating Systems
and Computer Structures G2
Tutorial Week 2
What are the two main functions of an Operating System?
To provide management of hardware resources, and to provide management of software
resources (programs, files, etc).
In handling tasks such as printing, why is spooling used?
To allow orderly processing of jobs, so that they can be printed in some sort
of order and without trying to simultaneously access the hardware.
List some differences between PC Operating Systems and mainframe Operating
Systems.
Multi-user; multi-tasking; security; address capability; batch processing
Why is the shell not part of the Operating System?
Shell functionality is not inherent in the O/S. It allows different shells
to be used.
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?
Video cards of different types; floppy disks of different sizes. Need a common
abstraction above this (open, write, close) to hide the differences.
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.
DIR, COPY, REN, TYPE, DEL, CD, MKDIR, RMDIR. Options are signalled by /option
instead of -option. Range of options is usually smaller.
Is Microsoft Windows an Operating System? Is Windows NT an Operating System?
What are some of the differences between Microsoft Windows and Windows NT?
MS Windows: No; Windows NT: Yes. NT: flat memory model, support for multi-tasking.
How does Microsoft Windows allow the user to perfrom the common commands given
in the lecture?
Use the File Manager.
List some of the differences between Unix file name globbing and the similar
pattern matching mechanism in MSDOS.
Unix performs globbing in the shell, MSDOS by individual applications. Unix
allows as many wildcards as wanted in the pattern, MSDOS does not.
Laboratory Week 2
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. Choose one of these
an use the online help to explore the editor.
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.
Use the news program to read some interesting groups. A group that you can
post to is uc.ise.os
Use the online manual to find out what the following commands do:
at, compress du, file,
at - run a command at a later time
compress - compress a file to use less space
du - report on disk usage
file - find the type of a file (program, C text, etc)
What do the following commands do:
ls -R, ls -t, ls -rta
-R - recursive listing
-t - order by time modified instead of alphabetic
-rta - all files (including starting with .), reversed time order.
Tutorial Week 3
Write a command ``dir'' to perform a long listing of files in the current directory.
Shell script file contains
ls -l
Write a pipeline to count the number of files in the current directory.
ls | wc -l
Write a shell script that uses a pipeline to count the total number of bytes
in all files in the current directory.
cat * | wc -c
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.
grep $1 $2 | head -1
Write a shell script that takes two arguments to show the differences in file
names between two directories.
ls $1 > /tmp/tmp1$$
ls $2 > /tmp/tmp2$$
diff /tmp/tmp1$$ /tmp/tmp2$$
rm -f /tmp/tmp*
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.
find . -name '*' -exec grep -l $1 {} \;
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.
new=`echo $1 | tr "A-Z" "a-z"`
mv $1 $new
Laboratory Week 3
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
Compare the shell language recognised by the MSDOS command interpreter command.com
to the zsh 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?
command.com has ``batch'' processing commands ECHO, FOR, GOTO, IF, PAUSE, REM,
SHIFT. This is smaller than the zsh set. command.com does not have `grave'
redirection. If a .bat file is executed from within another, it does not return
to the first one on completion. command.com can use ERRORLEVEL, string equality,
EXIST and NOT in IF commands. Apart from these, they have quite similar functionality.
command.com handles pipelines by running each command sequentially from left
to right, storing output in temporary files along the way.
There already exist Ada equivalents, which are Ada interpreters with additional
bits. The strong typing of Ada means that you have to declare all types and
variables as you go, making it a bit more cumbersome.
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.
Keyword advantages: easier to understand, don't have to remember meanings of
positions. Disadvantages: more cumbersome to type.
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.
echo $*
read answer
case $answer in
Y*)) exit 0;;
y*)) exit 0;;
*)) exit 1;;
esac
Write a command that behaves the same as ``rm -i'' that prompts for removal
of a file first.
if ask "remove file $i"
then
rm $i
fi
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.
file=$1
shift
for i
do
grep $i $file
done
Laboratory Week 4
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.
You can customise your environment using the files .profile, .zshrc, xinitrc,
.mwmrc and .Xdefaults. What does each of these files do?
.profile - read by zsh at login time, is the startup shell script
.zshrc - a shell script read and executed by any zsh when it starts.
.xinitrc - a shell script read and executed by X when it starts
.mwmwrc - the control file for the mwm window manager
.Xdefaults - the general control file for all X applications.
Tutorial Week 5
What features are desirable of a language designed for writing Operating Systems?
Ans:
At the low level: ability to read/write to absolute hardware addresses; use
data types that correspond to machine hardware types (unsigned/signed ints,
etc); be able to link with Assembler routines; ability to have inline Assembler.
At the high level: be able to offer a high-level API to applications.
What features are desirable of an applications programming language that needs
to use Operating System services?
Ans:
It must be able to link with the O/S libraries.
Must the languages used to write applications be the same as the language used
to write the O/S?
Ans:
Of course not - MSDOS is written in Assembler, but most programs are in Pascal
or C. You may lose the ability to exploit all of the O/S services if, for example,
the application programming language is unable to use the data types in the
O/S API.
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
int main(int argc, char *argv[])
{
int OddNumbers;
OddNumbers = 1;
while (OddNumbers <= 39) {
printf(" %d", OddNumbers);
OddNumbers += 2;
}
putchar('\n');
}
Ans:
The obvious differences are syntactic, with operators like += in C, {...} instead
of LOOP...END LOOP, etc. The Ada exmple shows size formatting in the output
- the C printf can also do that, but it isn't shown. Ada does not have a predefined
entry point to a program so it defines a Procedure, whereas C has to have ``main''
as entry point. Ada uses the IO packages, and the Ada environment should elaborate
these automatically on linking. In C, the standard library is automatically
linked, and an O/S specific linker would also link in the O/S kernel libraries.
However, any other libraries may have to be linked explicitly. Note: I am using
the ``Indian Hill'' style for programs, and so is the recommended reading of
Kelley and Pohl. Use whatever style you want, but be consistent.
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.
Ans:
I use the library functions here cos I am lazy. The studnets may be better
off expanding them out. NB Use ANSI C, not K&R C. This is a change from last
year.
#include
int main(int argc, char *argv[])
{ int ch;
while ((ch = getchar()) != EOF) {
if (isupper(ch)) putchar(tolower(ch));
else if (islower(ch)) putchar(toupper(ch));
else putchar(ch);
}
exit(0);
}
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.
Ans:
#include
int main(int argc, char *argv[])
{
int ch;
while ((ch = getchar()) != '\n')
if (! isdigit(ch)) exit(1);
exit(0);
}
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.
Ans:
int tolower(int ch)
{
if ('A' <= ch && ch <= 'Z')
return (ch + 'a' - 'A');
return ch;
}
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)!
Ans:
The type should probably be long for a real factorial function.
int factorial(int n)
{
if (n == 0)
return 1;
return n * factorial(n - 1);
}
Laboratory Week 5
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.
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';
}
Ans:
It crashes because the pointer is uninitialised and is probably pointing to
junk
Create and compile the tutorial questions. Use the debugger ``ups'' to step
through program execution.
Write a simple ``main'' program for question 8 that will read integers from
standard input until EOF is reached and prints the corresponding factorial.
If you have any left-over assignments that belong to students who moved to
other tutorials, can you give them to me so that I can spread them around?
If you have any marks too, pass them in and I will enter them into the marks
database.
Tutorial Week 6
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.
Ans:
#include
#define MAXNUM 100
int main(int argc, char *argv[])
{
int numbers[MAXNUM];
int number, count;
count = 0;
while (count < MAXNUM && scanf("%d", &number) != EOF) {
numbers[count++] = number;
}
while (count > 0)
printf("%d\n", numbers[--count];
exit 0);
}
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. For the second assignment,
note the library function strncmp that compares a maximum number of elements
of the strings.
Ans:
int strcmp(char *s1, char *s2)
{
while (*s1 != '\0' && *s2 != '\0') {
if (*s1 < *s2) return -1;
if (*s1 > *s2) return 1;
s1++;
s2++;
}
if (*s1 != '\0') return 1; /* s1 still has chars */
if (*s2 != '\0') return -1; /* s2 still has chars */
return 0;
}
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.
Ans:
#include
struct student_t {
char *name[100];
int ID; /* will need to be long if int is 16 bits */
} students[MAXSTUDENT];
etc
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.
Ans:
If you don't use malloc, but just use one string, everything in the array will
end up pointing to the string.
#include
#define MAX 100
int main(void)
{
char *strings[MAX];
char str[1024]; /* hope this is long enough */
int count = 0;
int n;
while (count < MAX && scanf("%1023s", str) != EOF) {
strings[count] = malloc(strlen(str) + 1); /* space for null char */
strcpy(strings[count], str);
count++;
}
for (n = 0; n < count; n++)
puts(strings[n]);
exit(0);
}
Laboratory Week 6
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.
Ans:
#include
#include
int main(void)
{
char dir[MAXPATHLEN];
if (getwd(dir) == NULL) {
fprintf(stderr, "cant find current dir\n");
exit(1);
}
puts(dir);
exit(0);
}
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?
Ans:
This will recognise ., .. patterns but not ~ - only the shells do that one
too. MAXPATHLEN is used again to give a reasonable size.
#include
#include
int main(void)
{
char path[MAXPATHLEN];
while (gets(path) != NULL) {
if (chdir(path) == 0)
printf("changed to %s\n", path);
else printf("failed to change to %s\n");
}
exit(0);
}
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?
Ans:
Each command is handled by a new shell - chdir cahnges for the new shell which
then exits, so it has no effect on the current environment. You can combine
the last three solutions to get a simple interpreter of your own.
#include
int main(void)
{ char path[2048]; /* they'll never type this much... */
while (gets(path) != NULL)
system(path);
exit(0);
}
Tutorial Week 7
I have been trying to stress to the students that C belongs to the same language
paradigm as Ada and Pascal (procedural, imperative) and so the design techniques
that they have used for Pascal or Ada programs also work for C, with the main
differences being the syntax, the ability to nest expressions and the emphasis
that C allows for error checking. So to write a C program they should design
an algorithm using structured English (or similar) first and then translate
that design into C. If you haven't been doing it that way, could you please
do so. Thanks!
Discuss the MSDOS file system from these three viewpoints:
a) The users view of the file system.
b) The Microsoft C programmers API for directory manipulation (see the attached
pages from the Microsoft C Programmers Reference manual).
c) The underlying implementation of the file system (see the textbook).
Ans:
a) the user sees a hierarchical file system with mountable file systems (ie
they can stick floppies in and out). File names have a maximum length that
is too short, and there are no real security measures to protect them against
carelessness, viruses (viri?) etc.
b) What they need to undestand is the example program at the end of the _dos_find
function descriptions, because that is how they traverse directories in MSDOS.
It is different to Unix, although it accomplishes much the same thing. _dos_findfirst
both does an open of the directory and also does a read to find the first file.
Note that this also allows pattern matching of file names. The description
also mentions an implementation detail: this uses an interrupt to MSDOS to
do the work. The information returned corresponds to the MSDOS directory information
and gives you all that the directory has. (In contrast, in Unix you have to
make two calls to get file info because such info is stored in inodes, not
in the directory.)
c) Check that they can find out how to read say the second block of a file,
given a pathname such as C:\windows\win.com
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?
Ans:
When a file is deleted, the first character of the file name is overwritten
to show that the file is deleted. The actual blocks are not cleared. This allows
the utility to restore the file as long as none of the freed blocks have been
overwritten by later calls. This works because MSDOS users often ``freeze''
when they have incorrectly removed a file so it has a good chance of not being
overwritten. In a timesharing environment this will not help, because the longer
you wait the more chance there is that another process overwrites the file.
Undelete could only work by making a copy in a secret place and then deleting
it later. Undelete would just restore from the copy.
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.
Ans:
It would slow performance because all blocks would have to be cleared. It is
a security hole if they are not cleared because the information may still remain.
It depends on your secrecy requirements (eg drug dealers would probably want
full erasure, the cops don't).
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?
Ans:
Copying takes extra time. It also uses up extra file space while the copy is
made. This may make it impossible to rename a file this way.
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.
Ans:
Fixed length makes implementation easy because you can use fixed size directory
records. This makes deleting and reusing the space easy. It also allows easier
searching, because you can get from one record to the next quickly. It would
be very tedious for a user if every filename had to have the same number of
characters in it! A maximum length would have the same advantages for implementation
if stored as fixed size and would be nicer for the user, but would waste disk
space. If variable sized records were used (they would have to be in the first
case) then deletion of files would leave variable-sized ``holes'' in the directory
that would require compaction at times.
Laboratory Week 7
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.
Ans:
This is for the current directory:
#include
#include
int main(void)
{
DIR *dp;
struct dirent *direntry;
if ((dp = opendir(".")) == NULL) {
fprintf(stderr, "cant open .\n");
exit(1);
}
while ((direntry = readdir(dp)) != NULL)
puts(direntry->d_name);
closedir(dp);
exit(0);
}
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.
Ans:
#include
#include
#include
#include
int main(void)
{
struct stat buf;
char name[MAXPATHLEN];
printf("Enter a file name:");
gets(name);
if (stat(name, &buf) != 0) {
fprintf(stderr, "cant stat %s\n", name);
exit(1);
}
if (S_ISDIR(buf.st_mode))
printf("%s is a directory\n", name);
else
printf("%s is not a directory\n", name);
exit(0);
}
Tutorial Week 8
What is the difference between internal and external fragmentation?
Ans:
Internal fragmentation is when a process is given memory and is not using all
of it, as in the buddy system. External fragmentation is when their are lots
of small entries on the free list that cannot easily be used.
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?
Ans:
First fit: 20k, 10k, 18k, 8k hole left in 20k hole; left- 4k, 9k, 7k, 9k, 12k,
15k
Best fit: 12k, 10k, 9k, 15k; left - 4k, 20k, 18k, 7k, 7k
Worst fit: 20k, 18k, 15k; left - 10k, 4k, 8k, 8k, 7k, 9k, 8k, 6k
Which of first fit, best fit or worst fit is used by MSDOS? Why? (See the textbook.)
Ans:
All of them. Because of the horrible memory model. You may need a different
strategy for badly fragmented upper memory to ordinary memory.
Discuss an algorithm to implement ``realloc''. What assumptions does this make
about a memory allocation scheme?
Ans:
if new_size == old_size
return old_ptr
if new_size < old_size
free spare blocks at the top
return old_ptr
if there is a free block size (new_size - old_size)
above and contiguous to the old one,
remove this from free list
return old_ptr
get a block from free list of new_size
set new_ptr to it
copy old to new
return new_ptr
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
Ans:
LA 20 ! PA 02020; LA 4100 ! PA 05100; LA 010300 ! PA 04300; LA 05376 ! page
frame fault.
Laboratory Week 8
There is no formal laboratory this week. Use it to catch up on outstanding
tutorial or laboratory material.
Tutorial Week 9
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?
Ans:
time action
0 P0 starts
20 P0 is stopped, with 50 remaining
21 P1 starts
41 P1 is stopped with 5 remaining
42 P2 starts
62 P2 is stopped with 25 remaining
63 P0 restarts
83 P0 is stopped with 30 remaining
84 P1 restarts
89 P1 terminates
90 P2 restarts
110 P2 is stopped with 5 remaining
111 P0 restarts
131 P0 is stopped with 10 remaining
132 P2 restarts
137 P2 terminates
138 P0 restarts
148 P0 terminates
There are 8 context switches in 148 units. So the switching overhead is 8/148
* 100% ~ 5%. The average to completion is (89 + 137 + 148)/3.
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.
Ans:
The sequence of running (with priorities is)
T3(18), T3(17), T3(16), T3(15), T3(14), T1(15), T1(14), T1(13), T3(13), T3(12),
T1(12), T1(11), T3(11), T3(10), T1(10), T1(9), T2(9), T3(9), ... as in round
robin
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.
Ans:
runnable
swapped
blocked
swapped
running
runnable
memory
blocked
memory
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?
Ans:
Round robin: starvation cannot occur because a process will eventually reach
the fornmt of the queue; shortest-first: a long process couyld be starved if
shorter ones can be continually added; priority: yes, if higher priority jobs
keep getting added that run for short enough that their priority never falls
low enough.
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?
Ans:
A refernence count should be used for each piece of memory. When a new process
starts using a piece of memory the count is increased, and decreased on termination.
When the count is zero, it can be removed.
How do Terminate and Stay Resident processes in MSDOS work?
Ans:
A TSR is loaded in the normal way. Upon exit, its memory space is not recalimed
but is left there (stay resident). When first loaded a TSR replaces the code
for some interrupt so taht the TSR is trigered when the interrupt occurs instead
of the original code. It should do its work then call the original interrupt
code itself. Note that TSRs have much potential to ``misbehave''. They should
allocate all required data space on startup, not throw away original interrupt
code, etc. In terms of process models, the process that called the interrupt
is ``suspended'' while the TSR executes.
Laboratory Week 9
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?
Ans:
if ((pid = fork()) == 0) {
execlp(command);
} else {
while (wait(&status) != pid)
;
return WEXITSTATUS(status);
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.
Ans:
if ((pid = fork()) == 0 {
while (1)
printf("Running forever\n");
} else {
sleep(5);
kill(pid, SIGSTOP);
sleep(5);
kill(pid, SIGCONT);
sleep(5);
kill(pid, SIGINT);
}
Tutorial Week 12
Write an algorithm for implementing a simple binary semaphore using
a) a hardware SWAP instruction
b) A hardware Test and Set lock.
Ans:
A h/w swap interchanges two memory locations as an indivisible operation. So
you load one location with 1, swap and see what you had in the other location.
If 0, then the semaphore was free, else in use.
DOWN(s)
x=1
SWAP(x, s)
if x == 1
place this process on sleeping queue
UP(s)
s=0
remove a process from sleeping queue and
let it run DOWN again.
Ans:
DOWN(s)
if TEST-AND-SET(s, 1) == 1
place this process on sleeping queue
UP(s)
if there is a process on sleeping queue
remove process from queue
s=0
let process run
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?
Ans:
Yes they can, but it means that a process at the bottom of the stack may suffer
starvation.
If an Operating System can disable interrupts, how can semaphores be implemented?
Ans:
When a DOWN is attempted, interrupts are switched off. The process can then
examine a piece of memory to see what its value is, and reset it to another
value if desired. Interrupts are then switched back on and the proces continues.
Note that they should only be switched off while the semaphore is being examined/modified.
If you just tried keeping them off all the time the process executes, then
effectively only one semaphore is allowed.
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.
Ans:
Deadlock may occur if A's account is locked to debit it, and then B's account
is locked. In the meantime, there may be a transfer the other way that results
in the lock being placed on B first. This can be avoided by either (a) releasing
all current locks if you can't get the next one, (b) ordering the locks, say
by account number
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?
Ans:
One semaphore can be used to control access to the head of the queue, and another
to the tail. Conflict may occur when the queue is empty, as both refer to the
same location, or full. At these extremes both semaphores may need to be held
at once, and you need to decide on an order eg head first.
Laboratory Week 12
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?
Ans:
A suitable lock file is one based on the file name, eg made from the file name
appended with ``.lock" This name has to be unique, but can be generated uniquely
from the filename (or other processes would not be able to find the lock!).
Attempt to create the file in read-only mode. If it succeeds, you have the
lock. If it fails, you don't. Remove the lock file on exit. You will have to
trap interrupts so that even if the user types ctrl-C you can still remove
the lock. Your program should never crash of its own accord :-)
Operating Systems
and Computer Structures G2
Tutorial and Laboratory Exercises Week 13
Tutorial Week 13
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?
Ans:
Best case is when two nodes are adjacent. Worst case is when they are both
at the bottom connected only by the root. In this case there are 2*height nodes
to traverse. The worst case path is 2*height, but the number of nodes in a
balanced tree is proportional to 2 to the power of height. The measn that the
length is logarithmic in the number of nodes, which is pretty good. A square
mesh for example is only proportional to the square root. The downside is that
the root acts as a bottleneck as any message from the left to the right of
the tree passes through the root.
What imformation is contained in addresses that will allow a message to be
routed from jan@canberra.edu.au to bill_gates@microsoft.com?
Ans:
The message originates in Oz and is destined for the US. So it must pass through
the gateway in Melbourne. Once in the US, it belongs in the commercial domain,
so its location can be found from a name server keeping tracks on this domain.
Once in the Microsoft network their own name server can locate bill_gates mail
account.
Because a file server may crash, the file system may be replicated on another
server. What are the advantages and disadvantages of this?
Ans:
Advantages: speed, reliability. Disadvantages: ensuring the two file systems
contain the same info. Often writes would be allowed to one only, and the other
``mirrors'' this one.
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?
Ans:
Class A networks use one-bit to signify this, so 231 addresses are available
to these. Class B use 2 bits to signify this, so 230 addresses are available.
Class C use 3 bits to signal class, so 229 addresses are available. Class D
allows 228 addresses. All told - a lot! Neverhtheless, it is running out. It
is to do with the structuring of addresses. There are 216 (65536) Class B addresses,
and within a Class B network there are 64k possible machines. We have a Class
B, but only 1000 (?) machines on campus. So we waste a lot. So does everyone-else.
Moving to Class D would leave us with too few addresses. So the wastage is
the reason.
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?
Ans:
Run one compile per machine, gives a speedup of a maximum of n. It may be less
because: one compile may be huge and the others tiny, so it uses all the time
anyway; the files may need to be sent out to the other machines, and for short
compiles this may not be worth it; linking would have to be performed back
on one machine.
Laboratory Week 13
Use xcwis to get the telephone numbers of people on campus, and then at ANU.
Use netfind to find if there is anyone at ADFA with the surname Bearman.
Experiment with xarchie to see if you can locate interesting files.
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.
From a PC lab, use ftp to transfer files to and from Unix.
Tutorial Week 14
If a server wishes to broadcast a message to all clients, what are the advantages
and disadvantages of
a) connection-oriented
b) connectionless
transmission?
Ans:
In a connection-oriented system, all clients would have to connect to the server,
which would be impractical as they would not know that a message was coming.
Alternatively, the server would have to connect to all clients, assuming that
it knew them all. So this looks ot so good. On the other hand, this would ensure
that all clients did get tbe message, or at least that the server would know
about it. In connectionless broadcast, the server would not know if anybody
missed a message, and would not have any security on who received it. On the
other hand, it would not have to do anything special.
A server may wish to receive requests on more than one port. How can this be
done?
Ans:
It would have to poll each port in turn, looking to see if anything comes on
any one of them. ie this must be non-blocking reads/selects from the port.
If a process is sending debit and credit requests as individual messages, should
a connection-oriented or connectionless protocol be used?
Ans:
In a connectionless system there is no guarantee that messages will arrive
in the order sent. So to ensure that a debit is done before the credit, a connection-oriented
version would be used.
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?
Ans:
Encode the two-byte xy as the 4-byte xyyx. That way either way of reading will
get xy. If the first word is an ``order'' flag eg 1001 for big, 0110 for little,
then the receiver will be able to determine the byte order of the incoming
message and hence whether or not to swap it.
Laboratory Week 14
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.
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. Random Star Trek quotes are given
by franklin@ug.cs.dal.ca. Use your finger program to connect to these.
Tutorial Week 15
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.
Ans:
a) no changes are made externally. b) x gets incremented twice, becaussse it
is referenced twice from within the procedure. c) x gets incremented once.
Each local copy of x is incremented, and then the two local copies are restored.
(Ada is apparently ambiguous as to whether (b) or (c) is done in that language.)
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?
Ans:
The first block can be done any number of times, as it always starts at zero.
Later blocks probably could not if the server keeps track of the file pointer,
but could if the client did.
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?
Ans:
A copy would be made, changed, and replaced. Locally, it would probably have
to be done the same way, with at least some of the inode info copied (eg block
pointers). Some could be ignored, such as owner, date, etc.
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?
Ans:
The two clocks must be logically synchronised or this breaks down.
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?
Ans:
Locally, Unix uses the user-id. This would be meaningless on a remote system
because user-ids may not be the same. The name would have to be used. This
would need validation on the server side. If the client was ``trusted'' then
that might be enough, if untrusted,a password may be needed. In a stateless
system, some verification would be needed for each transaction. This would
have to be fast.
Laboratory Week 15
There will be no laboratory this wek. Use the time for completing tutorial
exercises,
lab exercises, or revision.