ECE 329 Computer Systems Structures

Fall 2006

In this course students will learn the basics of operating systems, including the creation, management, and scheduling of threads and processes; process communication and synchronization; memory management; file systems; and protection. Programming assignments connect the theory with practice and enable students to further develop their programming skills.

Syllabus

Schedule

Week	Topic	Assignment
1	introduction / overview
2	C/C++ programming languages and tools	assignment #1 (9/1 F)
3	computer and O/S structures (Ch. 1-3)
4	processes and threads on Windows	assignment #2 (9/20 W)
5	process synchronization I (Ch. 7)
6	process synchronization II (Ch. 7)	midterm (10/4 W)
7	processes (Ch. 4)
8	threads (Ch. 5)	assignment #3 (10/18 W)
9	C++ programming language
10	CPU scheduling I (Ch. 6)	assignment #4 (11/3 F)
11	CPU scheduling II (Ch. 6)
12	deadlocks (Ch. 8)	assignment #5 (11/17 F)
13	[break]
14	memory (Ch. 9 and 10)	assignment #6 (12/8 F)
15	file systems (Ch. 11 and 12)
16		final exam (12/15 F, 8:00 - 11:00 am)

Textbook and Resources

• Textbook:  A. Silberschatz, P. B. Galvin, and G. Gagne, Operating System Concepts, 6th edition, John Wiley and Sons, 2003. 
  Book web page, including slides.
• Software:  Microsoft Visual Studio Service Pack 6 download

Lectures and review questions courtesy of Bill Reid:
 

The C programming language	lecture
Chapter 1: Introduction	lecture	review questions
Chapter 2: Computer system structures	lecture	review questions
Chapter 3: Operating system structures	lecture	review questions
Chapter 4: Processes	lecture	review questions
Chapter 5: Threads	lecture	review questions
Chapter 6: CPU scheduling	lecture	review questions
Chapter 7: Process synchronization	part1  part2	review questions
Chapter 8: Deadlocks	lecture	review questions
Chapter 9: Memory management	lecture	review questions
Chapter 10: Virtual memory	lecture	review questions
Chapter 11: File system interface	lecture	review questions
Chapter 12: File system implementation	lecture	review questions

Assignments

To complement the theory with practice, students will implement several assignments in C/C++.  Code will be graded on whether it compiles, runs, produces the expected behavior, and is written cleanly.

To turn in your assignment, send a blank email to assign@assign.ece.clemson.edu with the subject line "ECE329-1,#n" (without quotes), where 'n' is the assignment number; and cc the instructor and grader.  (No one reads the body of the email, so anything there will be ignored.)  You must send this email from your Clemson account, because the assign server is not smart enough to know who you are if you use another account.  Attach a zip file containing a readme.txt file (listing the names of the files in your project along with a brief description of how to run your code and what output should be expected), all of your source files, and any other files needed to compile your project, to the email:  *.h, *.c, *.cpp, *.rc, *.dsp, *.dsw.  (Do not include the res, Debug, or Release directories.)  Be sure that this file is actually attached to the email rather than being automatically included in the body of the email (This behavior has been observed in Eudora, for example, but it can be turned off).  Also, be sure to change the extension of your zip file (e.g., change .zip to _zip) so that the server does not block the attachment!!!  We cannot grade what we do not receive.

Assignments:

• Programming assignment #1 (Visual C++)
  Create a console-based application that compiles under Visual C++ 6.0 that computes π using the formula
      π = 4 * (1 - 1/3 + 1/5 - 1/7 + 1/9 - ...)
  The approximation of π after incorporating each term should be printed to stdout in a while loop.  The program should continue computing indefinitely until the user hits a key, at which point the program should exit.  (Hint:  To find the function that tells you whether a key was hit, you might want to start your search here.)
   
• Programming assignment #2 (Windows threads) 
  Write an application that allows the user to start and terminate a Windows thread by pressing a button on a graphical user interface (GUI). The application should support two forms of terminating:  stop, which is non-preemptive and requires the thread to continuously check whether it should stop; and kill, which preemptively kills the thread.  Even though it is not necessary in this simple application, be sure to wrap access to any shared variables with a mutex in order to practice for more difficult scenarios.  The function to terminate the thread should not return until the thread is terminated (use a semaphore to signal that the thread is done).  The user should also be able to select the priority of the thread both before it runs and while it is running. While the thread is running, it should continuously and indefinitely display a counter on the GUI indicating the progress of the thread. 
  
  To implement this program, you will need some of the following functions from the Win32 API: 
  • CreateThread, CreateMutex, CreateSemaphore -- creates a thread, mutex, or semaphore
  • TerminateThread -- kills a thread
  • SetThreadPriority -- changes the priority of a thread
  • WaitForSingleObject -- locks a mutex; releases a semaphore
  • ReleaseMutex -- unlocks a mutex
  • ReleaseSemaphore -- signals a semaphore
  • CloseHandle -- cleans up an object (e.g., thread, mutex, or semaphore)
  Search the MSDN on-line help using the function names for more specific information.  (Be sure to click on the documentation for the function, not for the class method).

  To assist you in this project, you may start with this Visual C++ 6.0 project:  WinThreads.zip .  Unzip the file and double-click on WinThreads.dsw .  You will need to modify the four callbacks near the bottom of WinThreadsDlg.cpp .  For those wishing to use a different IDE, here is a screenshot of the application to build:  WinThreads.bmp .
  
  If you have trouble with your program freezing, it might be because the edit box is being used unpredictably by the main thread.  Feel free to replace your SetWindowText call with a TRACE statement.  TRACE is a Microsoft macro that has the same syntax as printf, and it prints to the output window.  To view the output, run Build -> Start Debug -> Go, and make sure the output window is visible (View->Output) which it should be by default.
   

• Programming assignment #3 (producer / consumer)
  Create a console-based application that compiles under Visual C++ 6.0 that spawns two threads:  a producer and a consumer.  The producer should open an input file and repeatedly copy values to a circular buffer.  The consumer should open an output file and repeatedly copy values from the same circular buffer to the file.  For both the producer and consumer, a random number of bytes between 1 and n, inclusive, should be copied each iteration, where n is specified by the user.  The number of bytes should be randomized each iteration.  If the producer is unable to write to the buffer (because it does not contain enough empty elements), or if the consumer is unable to read from the buffer (because it does not contain enough unread items), then it should proceed to the next iteration, choosing a new random number of bytes to copy.  (Exception:  Once the producer has already read the entire file, then the consumer does not have to continue generating random numbers until it gets an exact hit; instead, it should write the rest of the buffer to complete the copy.)  When the program completes, the output file should be an exact copy of the input file.
  
  The syntax of the program should be as follows:
      copyfile input output n m
  where
      copyfile is the name of your executable
      input is the name of the input file
      output is the name of the output file
      n is the maximum number of bytes to copy in any given iteration (described above)
      m is the size of the circular buffer, in bytes  
   
• Programming assignment #4 (C++)
  Implement the following classes:
  • A class called Mutex with the following interface:
        Mutex();       // creates mutex
        ~Mutex();      // destroys mutex
        void Lock();      // locks mutex (waits infinite)
        void Unlock();  // unlocks mutex
  • A class called Semaphore with the following interface:
        Semaphore();      // creates semaphore
        ~Semaphore();    // destroys semaphore   
        bool Wait( int timeout );  // waits until semaphore is signaled
                                                           // timeout is in milliseconds, negative value means infinite
                                                           // returns true if signaled, false if timed out
        void Signal();  // signals the semaphore
  • A base class called Thread with the following interface:
        Thread();            // creates and runs thread
        ~Thread();          // destroys thread (after terminating it if still running)
        Semaphore* GetExitSemaphore();  // returns a pointer to the semaphore that is signaled
                                                                      // ... when the thread exits its main routine
    For implementation, the class should have
    • a protected pure virtual method called MainRoutine that is called when the thread starts:
          virtual DWORD MainRoutine() = 0;
    • a static method called StaticThreadProc that calls MainRoutine:
          static DWORD WINAPI StaticThreadProc( void* param );
      
    Your code should derive from Thread two classes, called ProducerThread and ConsumerThread, which provide the necessary implementation of MainRoutine().
  • A class called ByteArray with the following interface:
        ByteArray( int n );                                  // allocates array of n bytes
        ~ByteArray();                                              // frees array
        unsigned char& operator[]( int i );  // returns the ith byte
        int size() const;                                      // returns the number of bytes in the array
  Re-implement the previous assignment using these C++ classes.  The functionality should be the same, but the code should be much cleaner.  You may make slight modifications to the interface (e.g., adding parameters to methods, adding methods, etc.), but changes should be kept to a minimium.
   
• Programming assignment #5 (shared memory: clipboard)
  Write a Dialog-based application that cuts, copies, and pastes text from the clipboard to an edit box on the dialog using three buttons on the dialog.
  • To create a Dialog-based application, File -> New -> Project -> MFC AppWizard (exe), insert 'Project name, Dialog based -> uncheck 'ActiveX Controls' and 'About box'
  • To add edit box, ResourceView -> drag the icon labeled 'ab|' onto dialog.  Right-click on edit box -> Properties -> Styles -> check 'multiline'.  Then to associate it with a variable, View -> ClassWizard -> Member Variables -> IDC_EDIT1 -> Add Variable -> type 'm_editbox' -> Category: Control
  • To add a button, drag button icon to dialog.  To change button label, right-click on button -> Properties -> General -> Caption.  To add callback, View -> ClassWizard -> Message Maps -> IDC_BUTTON1 -> BN_CLICKED -> Add Function -> OK -> Edit Code.
  • To access the clipboard, see the MSDN help for the Windows clipboard (OpenClipboard, SetClipboardData, GetClipboardData, CloseClipboard).  You might also find the specific help on Using the clipboard helpful.
  • To get and set text in the edit box, see the MSDN help for CWnd::SetWindowText and CWnd::GetWindowText.  The version with CString is the easiest to use.
  • Note:  For this assignment, you are not allowed to use the Cut, Copy, and Paste methods of the CEdit class.
     
• Programming assignment #6 (named shared memory)
  Write a Dialog-based program that cuts, copies, and pastes text between instances of the application using named shared memory.  The program should not use the built-in Clipboard, nor should it use the Cut, Copy, or Paste methods of the CEdit class.
  • To create and use named shared memory, see the MSDN help on Sharing files and memory and the functions CreateFileMapping, OpenFileMapping, MapViewOfFile, UnmapViewOfFile, CopyMemory, and CloseHandle.

Grading breakdown:  See the grading chart.

• The MSDN on-line help contains extremely helpful documentation on the interfaces to specific functions in the Win32 API and the MFC classes. 
   

Instructor: Stan Birchfield, 207-A Riggs Hall, 656-5912, email:  stb at clemson
Grader: Nikhil Rane, 219 Riggs Hall, 650-6726, email:  nrane at clemson
Lectures: 8:00-9:00am MWF, 227 Riggs Hall