Description
CMPUT 379 – Assignment #1 A Simple Shell Program (first draft)
Objectives
This programming assignment is intended to give you experience in using Unix function calls that
manage processes (e.g., fork(), waitpid(), and execl()).
Program Specifications
Shell programs like Bourne shell (sh), C shell (csh), Bash, and Korn shell (ksh) provide powerful
interactive programming environments that allow users to utilize many of the services provided by
complex multiprocessing operating systems. In this assignment, you are asked to write a simple
shell program, called “a1shell”, in C/C++ that runs the commands described below. To implement your shell program, you need to familiarize yourself with some Unix functions including the
functions mentioned in the following table.
function Reference in Advanced Programming in the
Unix Environment [SR 3/E]
Time values Section 1.10
umask() Section 4.8 (see also, Fig. 4.11 in Sec. 4.9,
and the summary of file access permission
bits in Sec. 4.25)
chdir() and getcwd() Section 4.23
Time and date routines Section 6.10
getenv() Section 7.9
getrlimit() and setrlimit() Section 7.11
fork(), waitpid(), execl() Chapter 8: Process Control
times() Section 8.17
kill() Section 10.9
The a1shell program is invoked by the command line: “a1shell interval” where
interval is an integer number of seconds. After invocation, the program
1. Uses setrlimit() to set a limit on its CPU time (e.g., 10 minutes). The goal is to provide
some safeguard against a buggy process that may run forever.
2. Forks a child process, referred to as the a1monitor process in the explanation given below.
3. Runs the parent process, referred to as the a1shell process (explained below) until the user
quits the program.
1
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a
publicly-available Web site.
The a1monitor Process
This process gets the interval argument specified on the command line, and runs in a loop
until the parent terminates. Each iteration of the loop displays on the stdout the following
system status information:
a) The current date and time,
b) The average system load for the last 1, 5, and 15 minutes, and
c) The number of running processes, and the total number of processes in the system.
Use an output format of your choice. For example, you may display the output as
a1monitor: Mon, Sep 18, 2017 12:00:00 PM
Load average: 1.09, 1.08, 1.03
Processes: 2/291
After displaying the information, the process sleeps for the specified interval of seconds. A
new iteration begins when the process wakes up.
To obtain and format the current date and time, you should use suitable system calls from Section 6.10. To obtain information for (b) and (c), the process should read file ‘‘/proc/loadavg’’
maintained by the kernel.
The a1shell Process
When started, a1shell prints a prompt “a1shell% ” to the stdout, and waits for the user
to enter a command line on the stdin (at most 80 characters). After executing each command,
the shell prints its prompt string again and waits for the next command line. The shell processes
each command as described below.
1. cd pathname: Change the current working directory to the directory specified by the absolute or relative pathname. The specified pathname may begin with a shell environment
variable that needs expansion. For example, the pathname “$HOME/c379” requires the
expansion of environment variable HOME (the ’$’ is not part of the variable name). Implement this command using function chdir() (see the above table).
2. pwd: Print the current working directory. Implement this command using function getcwd()
(see the above table).
3. umask: Print the current file mode creation mask in octal (see function umask() above).
In addition, print in octal the value of the constants S IRWXU, S IRWXG, S IRWXO (see Fig.
4.11 in [SR 3/E]).
4. done: Exit the a1shell process.
5. cmd arg1 arg2 . . .: If cmd is not one of the above keywords then a1shell should try
to execute cmd by passing the entire command line to a child process that executes Bash
(program “/bin/bash” on lab machines). In addition, a1shell should report the real
time, user CPU time, and system CPU time required to execute cmd. More specifically,
a1shell should perform the following steps:
2
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a
publicly-available Web site.
(a) Call function times() (see the table above) to record the user and CPU times for the
current process (and its terminated children).
(b) Call fork() to create a child process. a1shell process should then call waitpid()
to wait for the child process to terminate.
(c) The child process should overlay itself with Bash by executing:
execl(“/bin/bash”, “bash”, “-c”,
“cmd arg1 arg2 …”, (char *) 0);
(d) Upon termination of the child process, process a1shell should resume execution and
call function times() again to obtain the user and system CPU times for itself and
its terminated children.
(e) Using a setup and output format similar to the program in Figure 8.31 of [SR 3/E],
a1shell should use the timing information recorded in steps (a) and (d) to compute
and print the following times in seconds:
i. the total time elapsed between steps (a) and (d),
ii. the user and system CPU times spent by a1shell in executing steps (b) and (c),
and
iii. the user and system CPU times spent by the child process in executing step (c).
More Details
1. This is an individual assignment. Do not work in groups.
2. Only standard include files and libraries provided when you compile the program using gcc
or g++ should be used.
3. Important: you cannot use system() or popen() to implement any of the above functionalities.
4. Although many details about this assignment are given in this description, there are many
other design decisions that are left for you to make. In such cases, you should make reasonable design decisions that do not contradict what we have said and do not significantly
change the purpose of the assignment. Document such design decisions in your source code,
and discuss them in your report. Of course, you may ask questions about this assignment
(e.g., in the Discussion Forum) and we may choose to provide more information or provide
some clarification. However, the basic requirements of this assignment will not change.
5. When developing and testing your program, make sure you clean up all processes before
you logout of a workstation. Marks will be deducted for processes left on workstations.
Deliverables
1. All programs should compile and run on Linux lab machines (e.g., ug[00 to 34].cs.ualberta.ca)
2. Make sure your programs compile and run in a fresh directory.
3
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a
publicly-available Web site.
3. Your work (including a Makefile) should be combined into a single tar archive ’submit.tar’.
(a) Executing ‘make’ should produce the a1shell executable
(b) Executing ‘make clean’ should remove unneeded files produced in compilation.
(c) Executing ‘make tar’ should produce the ‘submit.tar’ archive.
(d) Your code should include suitable internal documentation of the key functions.
(e) Typeset a project report (e.g., one to three pages either in HTML or PDF) with the
following (minimal set of) sections:
– Objectives: state the project objectives and value from your point of view (which
may be different from the one mentioned above)
– Design Overview: highlight in point-form the important features of your design
– Project Status: describe the status of your project; mention difficulties encountered
in the implementation
– Testing and Results: comment on how you tested your implementation, and discuss
the obtained timing results
– Acknowledgments: acknowledge sources of assistance
4. Upload your tar archive using the Assignment #1 submission/feedback link on the course’s
web page. Late submission (through the above link) is available for 24 hours for a penalty
of 10%.
5. It is strongly suggested that you submit early and submit often. Only your last successful
submission will be used for grading.
Marking
Roughly speaking, the breakdown of marks is as follows:
15% : successful compilation of a reasonably complete program that is: modular, logically organized, easy to read and understand, and includes error checking after important function
calls
05% : ease of managing the project using the makefile
25% : a1monitor: correctness of starting the monitor process, printing information specified
in (a), (b), and (c), and terminating the process
30% : a1shell: correctness of executing the built-in features and commands (setrlimit,
pwd, cd, expanding environment variables, and umask)
15% : a1shell: correctness of executing “/bin/bash -c commandline” using fork/execute
calls for handling non built-in commands, and reporting the required user and system CPU
times
10% : quality of the information provided in the project report
4
CMPUT 379 – Assignment #2 A Chat Program Using FIFOs (first draft)
Objectives
This programming assignment is intended to give you experience in developing client-server programs that utilize FIFOs for communication, and file locking for controlling access to the available
FIFOs.
Part 1: Experimenting with FIFOs in a Unix Environment
The client-server program specified in Part 2 relies on FIFOs (named pipes) for interprocess communication. In the classroom, we talked about creating FIFOs using the mkfifo shell command,
and discussed some of their properties. This part is intended to give you more experience with
their behaviour. To answer each question, you may need to design, implement and run a suitable
experiment on the lab machines. Below, processes A and B and the FIFOs are assumed to be
owned by the same user. In addition, the processes have access to the FIFOs. So, unless a process
chooses to open a FIFO in a restricted mode (e.g., a read-only mode), the process can read and
write to the FIFO.
1. Assume that process A sends a long stream of data to process B through a FIFO. Can one
detect the transmission activity by monitoring the “size” of the FIFO on the file system (e.g.,
by repeatedly issuing a “ls -l” command)?
2. Can two processes running on two different hosts in the lab communicate using a FIFO? As
mentioned above, both processes and the FIFO are assumed to be owned by the same user,
and both processes can open the FIFO.
3. Assume that A and B run on the same host. Process A first opens a FIFO in the O RDWR
mode and waits for input from the user (without writing to the FIFO). Subsequently, while
A is waiting for the user input, process B attempts to open the FIFO in a O RDONLY mode.
Does B block when calling open()?
4. Assume that A and B run on the same host. Process A first opens a FIFO in the O RDWR
mode, puts a lock on the FIFO using lockf(), described in the UNIX manual pages, and
then waits for input from the user. Can process B detect that the FIFO is locked while A is
waiting for the user input?
5. Each of the following loops are intended to read one line from the stdin, and then echoes
the line to the stdout using low level unbuffered I/O functions (commonly used in clientserver programs). Which loop (if any) works properly? Explain.
1
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a
publicly-available Web site.
(a) int len; char buf[80];
while(1) {
len= read(STDIN_FILENO, buf, sizeof(buf));
write(STDOUT_FILENO, buf, strlen(buf));
if (strstr(buf, “exit”) != NULL) exit(0);
}
(b) int len; char buf[80];
while(1) {
memset(buf, 0, sizeof(buf));
len= read(STDIN_FILENO, buf, sizeof(buf));
write(STDOUT_FILENO, buf, strlen(buf));
if (strstr(buf, “exit”) != NULL) exit(0);
}
In the deliverables, you need to describe your experimental work, and explain your answers (don’t
submit any separate code files for this part).
Part 2: A Chat Program
In this part you are asked to write a C/C++ program, called a2chat, that implements the chat
server and client functionalities specified below. The program can be invoked as a server using
“a2chat -s baseName nclient”, or as a client using “a2chat -c baseName”.
Data transmission from clients to the server uses at most NMAX (= 5) FIFOs called the inFIFOs: baseName-1.in, …, baseName-5.in. Data transmission in the other direction
(from the server to the clients) uses at most NAMX (= 5) FIFOs called the outFIFOs: baseName-1.out,
…, baseName-5.out. For simplicity, you may create the needed FIFOs (using some selected value for the baseName argument) before running the programs.
The argument nclient specifies the maximum number of clients that can be connected to the
server at any time (nclient ≤ NMAX=5).
Locking FIFOs
To guarantee that no two client programs write to the same inFIFO when sending data to the server,
each client is required to find an unlocked FIFO to use for sending data to the server. If an unlocked
inFIFO is found, say baseName-3.in, then the client uses the lockf() function (see the man
pages) to put a POSIX lock on the inFIFO. Subsequently, the client uses the corresponding outFIFO
(i.e., FIFO baseName-3.out) for receiving data from the server. Clients should unlock the held
inFIFO when a connection is closed.
The Client Loop
On start, the client prompts the user to enter a command line by displaying a suitable prompt
message (e.g., “a2chat client:”). Each iteration of the client loop polls the stdin for a
command line. The client sends each valid command line to the server, waits for the server’s
response line, and processes the response line. In addition, if the client is in a connected state, the
client also polls the specific outFIFO used for carrying incoming data from the server. If connected,
2
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a
publicly-available Web site.
the client also processes the chat lines received from the server. The prompt message should appear
after displaying any data to the user.
The Server Loop
On start, the server displays a suitable message indicating the nclient limit specified on the
command line.
Example: % a2chat -s fifo 3
Chat server begins [nclient= 3]
Each iteration of the server loop polls the stdin and the inFIFOs for command lines. The
server processes each command line, forms a response line (if needed), and sends the response
line to the client. Commands that cause the server to forward a chat line to multiple recipients
generate a line for each recipient. Note that all communication between clients go through the
server; there is no direct communication between any two clients. The exit command issued from
the server’s stdin terminates the server.
On a successful execution of a client’s command by the server, the server sends the client
a response line that starts with “[server]” followed by some suitable information about the
execution of the command (or, just “[server] done” if there is no such information). On a
failed execution of the command, the server’s response line starts with “[server] Error:”
followed by an explanation of the error.
The Chat Protocol
A chat client utilizes the chat service by issuing a sequence of command lines from the following
list. As mentioned above, each command line is typically transmitted to the server, and the client
program waits to display the server’s response.
1. open username: Request the server to open a new chatting session using the specified
username as the user’s name.
Example: % a2chat -c fifo
Chat client begins
a2chat_client: open ibm
FIFO [fifo-1.in] has been successfully locked by PID [15360]
[server] User ’ibm’ connected on FFIO 1
a2chat_client:
The command fails to open a new session in the following cases:
(a) No unlocked inFIFO is available for the client to use. In this case, the client should not
terminate, rather it should advise the user to try later, and reissues the prompt.
(b) The client has a session already going on.
(c) The server has reached the client limit specified by nclient.
(d) There is another client that uses the specified username for chatting.
3
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a
publicly-available Web site.
2. who: Get a list of the logged in users.
Example: a2chat_client: who
[server]: Current users: [1] ibm, [2] dell
In the example, the response line indicates the FIFO number used in each session.
3. to user1 user2 · · ·: Add the specified users to the list of recipients.
Example: a2chat_client: to apple ibm dell unknown
[server] recipients added: apple, ibm, dell
In the above example, there is no client with the name “unknown”. The server just ignores
such username.
4. < chat line: Send chat line to all specified recipients.
Example: a2chat_client: < Hello apple ibm dell
a2chat_client:
[dell] Hello apple ibm dell
a2chat_client:
In the example, user dell is both a sender and recipient. In response, the server forwards
the chat line prefixed with the sender’s name in brackets to all recipients.
5. close: Close the current chat session without terminating the client program. The user may
subsequently open a new session with a different username.
Example: a2chat_client: close
[server] done
a2chat_client:
Note: the server is not required to notify other clients that a session has been closed.
6. exit: Close the current chat session, and terminate the client program. If the exit command
is received from a client, the server does not generate a response line. Otherwise (if the
command is generated from the server’s stdin), the server terminates.
More Details
1. This is an individual assignment. Do not work in groups.
2. Although many details about this assignment are given in this description, there are many
other design decisions that are left for you to make. In such cases, you should make reasonable design decisions that do not contradict what we have said and do not significantly
change the purpose of the assignment. Document such design decisions in your source code,
and discuss them in your report. Of course, you may ask questions about this assignment
(e.g., in the Discussion Forum) and we may choose to provide more information or provide
some clarification. However, the basic requirements of this assignment will not change.
3. When developing and testing your program, make sure you clean up all processes before
you logout of a workstation. Marks will be deducted for processes left on workstations.
4
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a
publicly-available Web site.
Deliverables
1. All programs should compile and run on the lab machines (e.g., ug[00 to 34].cs.ualberta.ca)
using only standard libraries (e.g., standard I/O library, math, and pthread libraries are allowed).
2. Make sure your programs compile and run in a fresh directory.
3. Your work (including a Makefile) should be combined into a single tar archive ’submit.tar’.
(a) Executing ‘make’ should produce the a2chat executable file.
(b) Executing ‘make clean’ should remove unneeded files produced in compilation.
(c) Executing ‘make tar’ should produce the ‘submit.tar’ archive.
(d) Your code should include suitable internal documentation of the key functions.
4. Phase 1 Deliverables:
(a) Typeset a text, HTML, or PDF file “a2answers” containing the answers to the questions in Part 1. Explain your answers. You don’t need to submit any separate code files
for this part.
(b) Submit a restricted version of the chat program, called a2rchat with the following
restrictions:
i. For the “open username” command, the server is not required to check that another client is currently using the specified username for chatting, or that the
client has a session already going on.
ii. The restricted version is not required to support the “to” or “who” commands.
The server just echoes each received chat line to the sender.
Thus, the server in a2rchat works essentially as an echo server for each ongoing
session.
(c) There is no need to submit a project report. Describe the status of the project in a
“readme” file.
5. Phase 2 Deliverables
(a) Submit the complete version of the a2chat program.
(b) Typeset a project report (e.g., one to three pages either in HTML or PDF) with the
following (minimal set of) sections:
– Objectives: state the project objectives and value from your point of view (which
may be different from the one mentioned above)
– Design Overview: highlight in point-form the important features of your design
– Project Status: describe the status of your project; mention difficulties encountered
in the implementation
– Testing and Results: comment on how you tested your implementation
5
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a
publicly-available Web site.
– Acknowledgments: acknowledge sources of assistance
6. Upload your tar archive using the Assignment #2 (phase 1 or 2) submission/feedback
links on the course’s web page. For each phase, late submission is available for 24 hours for
a penalty of 10% of the points assigned to the phase.
7. It is strongly suggested that you submit early and submit often. Only your last successful
submission will be used for grading.
Marking
Roughly speaking, the breakdown of marks is as follows:
Phase 1 Deliverables:
20% : Answers to Part 1 questions
20% : Correct execution of the restricted chat program a2rchat
Phase 2 Deliverables:
10% : successful compilation of a complete program that is: modular, logically organized, easy
to read and understand, and includes error checking after important function calls
03% : ease of managing the project using the makefile
40% : correctness of executing the a2chat program
07% : quality of the information provided in the project report
6
CMPUT 379 – Assignment #3 A Chat Program Using TCP Sockets (first draft)
Objectives
This programming assignment is intended to give you experience in developing client-server programs that utilize TCP sockets for communication over the Internet, and I/O multiplexing to
achieve concurrency in data processing.
Details
The chat client-server program specified in Assignment 2 relies on FIFOs (named pipes) for interprocess communication. Thus, its use is limited to users that share the same host computer. In this
assignment you are asked to write a C/C++ program, called a3chat that extends the functionalities of a2chat so that multiple users on the same host, or on different hosts connected by the
Internet can chat with each other. The program can be invoked as a server or client using:
% a3chat -s portnumber nclient
% a3chat -c portnumber serverAddress
where
• portnumber specifies the port used by the server to listen to incoming connections. (To
avoid port number conflicts when running servers in the lab, use port number 9xxx where
xxx is the last 3 digits of your student ID number.)
• serverAddress is the IP address of the server’s host specified either as a symbolic name
(e.g., ui07.cs.ualberta.ca, or localhost), or in dotted-decimal notation (e.g.,
127.0.0.1).
• nclient specifies the maximum number of clients that can be connected to the server at
any instant. For simplicity, assume that nclient ≤ 5.
The Client Loop
On start, the client resolves serverAddress (e.g., by calling gethostbyname()) to get the
server’s IP address. The client then prompts the user to enter a command line by displaying a
suitable prompt message (e.g., “a3chat client:”).
Example: % a3chat -c 9123 ui07.cs.ualberta.ca
Chat client begins (server ’ui07.cs.ualberta.ca’ [129.128.41.37], port 9123)
a3chat_client:
1
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a
publicly-available Web site.
In general, each iteration of the client loop polls the stdin for a command line. The client
sends each valid command line to the server, waits for the server’s response line, and processes the
response line.
If the command is ’open username’, the client attempts to connect to the server. The
attempt may fail if the server is not running, or if the server responds with an error message (see
the ’open’ command below for more details).
In addition, if the client is in a connected state, the client also polls the specific (full duplex)
socket used for communication with the server. If connected, the client also processes the chat
lines received from the server. The prompt message should appear after displaying any data to the
user.
Detecting crashed clients. To help in detecting a client that has terminated unexpectedly,
we also require each client that has a TCP connection to the server to periodically send a special
message to the server, called the keepalive message (see the details below).
The Server Loop
On start, the server displays a suitable message indicating the values specified on the command
line.
Example: % a3chat -s 9123 5
Chat server begins [port= 9123] [nclient= 5]
Each iteration of the server loop polls its listening socket (used to detect incoming connections),
the stdin, and any possible connected client socket. The server processes each command line,
forms a response line (if needed), and sends the response line to the client. Commands that cause
the server to forward a chat line to multiple recipients generate a line for each recipient. Note
that all communication between clients go through the server; there is no direct communication
between any two clients. The exit command issued from the server’s stdin terminates the server.
On a successful execution of a client’s command by the server, the server sends the client
a response line that starts with “[server]” followed by some suitable information about the
execution of the command (or, just “[server] done” if there is no such information). On a
failed execution of the command, the server’s response line starts with “[server] Error:”
followed by an explanation of the error.
Detecting crashed clients. The server also keeps track of the periodic keepalive messages
received from each TCP connected client. If a connected client stops transmitting such messages
for a prescribed consecutive number of periods, the server assumes that the client has terminated
unexpectedly. The server should close the TCP connection, logs out the client (if the client has an
ongoing chat session), and releases any allocated resources.
The Chat Protocol
Similar to Assignment 2, a chat client utilizes the chat service by issuing a sequence of command
lines from the following list. As mentioned above, each command line is typically transmitted to
the server, and the client program waits to display the server’s response.
2
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a
publicly-available Web site.
1. open username: Attempts to open a TCP connection to the server. If successful, send the
command to request the server to open a new chatting session using the specified username
as the user’s name.
For an unconnected client, the command fails to establish a connection if the server is not
running. For a connected client, the command fails to open a new session if either (a) the
server has reached the client limit specified by nclient, (b) the client has a session already going on, or (c) there is another client that uses the specified username for chatting.
If the command succeeds, the server acknowledges both the connection establishment and
registering the user.
Example: % a3chat -c 9123 localhost
Chat client begins (server ’localhost’ [127.0.0.1], port 9123)
a3chat_client: open ibm
[server] connected
[server] User ’ibm’ logged in
2. who: Get a list of the logged in users.
Example: a3chat_client: who
[server]: Current users: ibm, dell
3. to user1 user2 · · ·: Add the specified users to the list of recipients.
Example: a3chat_client: to apple ibm dell unknown
[server] recipients added: apple, ibm, dell
In the above example, there is no client with the name “unknown”. The server just ignores
such username.
4. < chat line: Send chat line to all specified recipients.
Example: a3chat_client: < Let’s start the weekly meeting
a3chat_client:
[dell] Let’s start the weekly meeting
a3chat_client:
In the example, user dell is both a sender and recipient. In response, the server forwards
the chat line prefixed with the sender’s name in brackets to all recipients.
5. close: Close the current chat session without terminating the client program. The user may
subsequently open a new session with a different username.
Example: a3chat_client: close
[server] done
a3chat_client:
Note: the server is not required to notify other clients that a session has been closed.
6. exit: Close the current chat session, and terminate the client program. If the exit command
is received from a client, the server does not generate a response line. Otherwise (if the
command is generated from the server’s stdin), the server terminates.
3
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a
publicly-available Web site.
Keepalive Messages
As mentioned above, keepalive messages are sent periodically from each client with a TCP connection to the server. The following parameters defines the contents and periodicity of the messages
(with some example values):
#define KAL_char 0x6 // A non-printable character (e.g., ACK)
#define KAL_length 5 // Number of KAL_char in one keepalive message
#define KAL_interval 1.5 // Client sends a keepalive message every 1.5 seconds
#define KAL_count 5 // Number of consecutive keepalive messages that needs
// to be missed for the server to consider that the client
// has terminated unexpectedly
The parameters are used as follows:
– A keepalive message is composed of KAL length repetitions of character KAL char.
– A client with a TCP connection to the server is expected to send a keepalive message every
KAL interval seconds.
– If the server does not receive KAL count consecutive keepalive messages from the client
on time, the server assumes that the client has terminated unexpectedly. If so, the server logs
out the user (if the client has an ongoing chat session), closes the socket, and frees other
resources that may have been allocated to the client.
Activity Reports
In addition, the server is required to keep track of the last time a logged in client has sent a message
to the server, and display an activity report of all logged in clients and their recorded times. Keeping
track of the last time a logged in client has interacted with the server (by sending some command to
the server) enables the server to identify clients that become idle for prolonged times. As well, the
server should report any client that has been disconnected due to the lack of receiving the required
number of consecutive keepalive messages on time.
The activity report should be displayed periodically (approximately) every 15 seconds in an
automatic way. Note that the server does not use the recorded times for any purpose other than
displaying them periodically for information.
Example: …
activity report:
’ibm’ [sockfd= 4]:Tue Mar 2 21:42:34 2017
’dell’ [sockfd= 5]:Tue Mar 2 21:42:48 2017
’apple’ [sockfd= 6]:Tue Mar 2 21:42:00 2017
’LG’ [sockfd= 7]: loss of keepalive messages detected at …, connection closed
…
Note: You may implement this feature using, e.g., UNIX calendar times (see, e.g., functions
time() and ctime()), the alarm() system call, and/or threads.
4
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a
publicly-available Web site.
More Details
1. This is an individual assignment. Do not share code.
2. Although many details about this assignment are given in this description, there are many
other design decisions that are left for you to make. In such cases, you should make reasonable design decisions that do not contradict the specifications and do not significantly change
the purpose of the assignment. Document such design decisions in your source code, and
discuss them in your report. Of course, you may ask questions about this assignment (e.g.,
in the Discussion Forum) and we may choose to provide more information or provide some
clarification. However, the basic requirements of this assignment will not change.
3. When developing and testing your program, make sure you clean up all processes before
you logout of a workstation. Marks will be deducted for processes left on workstations.
Deliverables
1. All programs should compile and run on the lab machines.
2. Make sure your programs compile and run in a fresh directory.
3. Your work (including a Makefile) should be combined into a single tar archive ’submit.tar’.
(a) Executing ‘make’ should produce the required executable file(s).
(b) Executing ‘make clean’ should remove all files produced in compilation, and all unused
files.
(c) Executing ‘make tar’ should produce the ‘submit.tar’ archive.
(d) Your code should include suitable internal documentation of the key functions.
4. Typeset a project report (e.g., one to three pages either in HTML or PDF) with the following
(minimal set of) sections:
– Objectives: state the project objectives and value from your point of view (which may be
different from the one mentioned above)
– Design Overview: highlight in point-form the important features of your design
– Project Status: describe the status of your project; mention difficulties encountered in
the implementation
– Testing and Results: comment on how you tested your implementation
– Acknowledgments: acknowledge sources of assistance
5. Upload your tar archive using the Assignment #3 submission/feedback link on the course’s
web page. Late submission (through the above link) is available for 24 hours for a penalty
of 10%.
6. It is strongly suggested that you submit early and submit often. Only your last successful
submission will be used for grading.
5
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a
publicly-available Web site.
Marking
Roughly speaking, the breakdown of marks is as follows:
17% : successful compilation of a complete program that is: modular, logically organized, easy
to read and understand, and includes error checking after important function calls
03% : ease of managing the project using the makefile
70% : correctness of executing the a3chat program
10% : quality of the information provided in the project report
6
CMPUT 379 – Assignment #4 A Demand Paging Virtual Memory Simulator
Objectives
This programming assignment is intended to give you experience in developing a discrete event
simulation program that enables the study of key performance measures of a conceptual demand
paging virtual memory system.
The Simulator
In this assignment you are asked to design, implement, and test a C/C++ program, called ’a4vmsim’,
that simulates a number of local page replacement algorithms for managing a conceptual demand
paging virtual memory system. Each run of the program reads from the standard input a synthetic
reference string that models the behaviour of some hypothetical process and, upon termination,
the program writes to the standard output a number of statistics about the performance of the system in processing the input reference string. More specifically, the simulator makes the following
assumptions.
1. The length of each page in the system is a power of two between 256 bytes and 8192 bytes.
2. The CPU generates 32-bit addresses. Correspondingly, the reference string generator program generates a sequence of 32-bit binary words where each word encodes the page number used in a memory reference.
3. The CPU has a special accumulator register that is cleared to zero before the processing of
any reference string.
4. Since a valid page length is at least 256 bytes, the least significant byte of each generated
32-bit word is not used in computing the referenced page number. The generator program
utilizes such least significant byte in each generated word to encode information about the
operation performed by the CPU in that particular memory reference. In particular, the
generator utilizes the most significant two bits of each such byte to classify the operation
performed by the CPU as follows:
(a) 00 b5b4 · · · b0 : The operation increments the accumulator with the (unsigned) integer stored in bits b5b4 · · · b0.
(b) 01 b5b4 · · · b0 : The operation decrements the accumulator with the (unsigned) integer stored in bits b5b4 · · · b0.
(c) 10 ∗ ∗ · · · ∗ : The operation modifies the same page containing the reference word.
The least significant 6 bits are not used.
1
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a
publicly-available Web site.
(d) 11 ∗ ∗ · · · ∗ : The operation reads data from the same page containing the reference
word. The least significant 6 bits are not used.
Example. Assuming a 1024-byte page size, and a 32-bit reference word of 0x01220179, the
word is decoded into a page number, operation code, and operation value as follows:
0000 0001 0010 0010 0000 00 | {z }
page number
01
|{z}
unused bits
01
|{z}
operation
11 1001 | {z }
value
.
Since the operation code is 01, the reference specifies an operation that decrements the accumulator by a decimal value of 57.
Simulator Inputs
In each run, the simulator reads an input reference string from the standard input. As mentioned
above, the string is composed of a sequence of 32-bit binary words where each word encodes
a referenced page number and information about the operation performed by the CPU in that
particular reference.
Note. Reading from the standard input allows the output of the generator program to
be piped directly to the simulator to avoid storing a possibly huge reference string in a
file.
The program should be callable using the following parameters:
a4vmsim pagesize memsize strategy
where
• pagesize: is a power of two between 256 bytes and 8192 bytes, inclusively.
• memsize: is the size of the physical memory in bytes. Internally, the simulator should round
up this value to the nearest multiple of page size. For example, if pagesize = 512 and
memsize = 1000 then the system has two pages.
• strategy: is one of the following strings: none, mrand, lru, or sec. The corresponding
strategies are as follows:
– none: is a strategy that ignores the specified physical memory size, and assumes that
the system has enough memory to simulate the reference string. (This strategy is used
mainly to test basic functions of the program.)
– mrand: is a modified version of RAND where the victim page is selected at random
from all pages present in the physical memory, except the page(s) that have been referenced in the k = 3 references that occurred immediately before the fault. This strategy
applies when the physical memory has more than k = 3 pages.
– lru: is the LRU strategy.
– sec: is the Second Chance strategy.
2
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a
publicly-available Web site.
Simulator Outputs
After processing a reference string, the simulator prints the following statistics on the standard
output:
1. The total number of memory references in the input string, and the number of write operations in the input string.
2. The total number of page faults.
3. The total number of flushes, i.e., cases when a victim page has been modified since the last
time it was brought into memory.
4. The final value stored in the accumulator.
Reference String Generation
To generate synthetic reference strings, download and compile program ’mrefgen’ from the
WEB page. The program can be invoked as follows:
% mrefgen -m memsize -l locality -f focus -w wr -n nref
where
• memsize: specifies the maximum address to be generated. All addresses are in the range
[0, memsize − 1].
• locality: is a single digit [0 − 9] specifying the degree of locality of the generated reference
string.
• focus: is a single digit [0 − 9] specifying the likelihood of referencing a small “permanently
needed” memory area.
• wr: (the write ratio) is a floating point number in the range 0.0 to 1.0 specifying the fraction
of write references in the generated string.
• nref: is the total number of references generated.
The program writes the generated reference string to its standard output file descriptor, and
some statistics about the generated string to its standard error file descriptor. So, the reference
string alone (without the statistics) can be piped directly to the simulator program or saved in a
file.
Note. You don’t have to worry about the byte order (e.g., small or big endian) used to
represent the generated 32-bit binary values since the generator and the simulator will
be tested on the same machine.
3
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a
publicly-available Web site.
Example: Running a script “run.sh” that has the following settings:
#!/bin/sh
page=256
memsize=25600 # 100*page
policy=”lru”
virtual=2560000 # 100*memsize
nref=25600000 # 10*virtual address space
mrefgen -m $virtual -l 3 -f 3 -w 0.4 -n $nref | a4vmsim $page $memsize $policy
gives:
a4vmsim [page=256, mem= 25600, lru]
[mrefgen] 25600000 references generated, write count= 10239762
[mrefgen] Accumulator final value= -72878
[a4vmsim] 25600000 references processed using ’lru’ in 36.25 sec.
[a4vmsim] page faults= 15707259, write count= 10239762, flushes= 6943146
[a4vmsim] Accumulator= -72878
Note: mrefgen generates a new pseudo random reference string each time it runs.
Running Time
The running time of your solution is not an issue as long as it can process reference strings of 20
million references in less than 2 minutes when executed on a lab machine with no other major
programs running.
More Details
1. This is an individual assignment. Do not share code.
2. Although many details about this assignment are given in this description, there are many
other design decisions that are left for you to make. In such cases, you should make reasonable design decisions that do not contradict the specifications and do not significantly change
the purpose of the assignment. Document such design decisions in your source code, and
discuss them in your report. Of course, you may ask questions about this assignment (e.g.,
in the Discussion Forum) and we may choose to provide more information or provide some
clarification. However, the basic requirements of this assignment will not change.
3. When developing and testing your program, make sure you clean up all processes before
you logout of a workstation. Marks will be deducted for processes left on workstations.
Deliverables
1. All programs should compile and run on the lab machines.
2. Make sure your programs compile and run in a fresh directory.
3. Your work (including a Makefile) should be combined into a single tar archive ’submit.tar’.
4
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a
publicly-available Web site.
(a) Executing ‘make’ should produce the required executable file(s).
(b) Executing ‘make clean’ should remove all files produced by compilation, and all unused files.
(c) Executing ‘make tar’ should produce the ‘submit.tar’ archive.
(d) Your code should include suitable internal documentation of the key functions.
4. Typeset a project report (e.g., one to three pages either in HTML or PDF) with the following
(minimal set of) sections:
– Objectives: state the project objectives and value from your point of view (which may be
different from the one mentioned above)
– Design Overview: highlight in point-form the important features of your design
– Project Status: describe the status of your project; mention difficulties encountered in
the implementation
– Testing and Results: comment on how you tested your implementation
– Acknowledgments: acknowledge sources of assistance
5. Upload your tar archive using the Assignment #4 submission/feedback link on the course’s
web page. Late submission (through the above link) is available for 24 hours for a penalty
of 10%.
6. It is strongly suggested that you submit early and submit often. Only your last successful
submission will be used for grading.
Marking
Roughly speaking, the breakdown of marks is as follows:
17% : successful compilation of a complete program that is: modular, logically organized, easy
to read and understand, and includes error checking after important function calls
03% : ease of managing the project using the makefile
70% : correctness of executing the program (tentatively, around 20% for ’none’, 15% for ’mrand’,
20% for ’lru’, and 15% for ’sec’)
10% : quality of the information provided in the project report
5
