News

• Peterson's algorithm operational and assertional analysis.
• Bakery algorithm operational analysis.
• Background notes on classical synchronization problems.
• Introduction to Assertional Reasoning.
• Chapters 6 and 7.
• Transport Layer Principles
• Graded hw 1 in folder outside my office door. Grading and distribution below.
• Project description (ps)
• I'm regrading exam 1 problem 1a, so hand it back to me. (Basically, A4 by itself is an adequate B, and A1, A2, A3 are not needed. So A4 itself will be worth 10 points, and most of you would get more points. Note that A1-A3 would be needed for progress.)
• Exam 2 will be held at the officially scheduled time of 10:30-12:30, Saturday December 16, in the usual classroom. The snow date is Sunday, December 17, same time, same place.
• HOT  Grades

Overview

We apply this to concurrency problems in networking and operating systems for example, TCP, routing, ad-hoc networks, distributed shared memory, sequential consistency, transaction processing, atomic commits and serializability, etc.

Projects involve specification, analysis, and testing of services and systems. Testing projects will involve programming in Java, specifically with threads.

Texts

• Notes and papers distributed in class.
• Online JAVA material
• Introduction to Assertional Reasoning(174K ps.gz). This is a tutorial to doing assertional proofs of concurrent algorithms. It was originally in an extinct troff, so expect some formatting problems. The table of contents is at the end.
• Chapters 6 and 7 (47K ps.gz) . Contains updated table of contents, replacement page 16, chapter 6 (service specifications), chapter 7 (service satisfaction condition).
• Transport Layer Principles (41K ps.gz)

Grading

• Exam 1 --- 30%
• Exam 2 --- 40%
• Projects --- 30%

Projects/Homeworks

• Hw 1 (do by first week of class, not to be handed in)
• Hw 2 (not to be handed in). Peterson's 2-process mutual exclusion algorithm: operational and assertional analysis of safety and progress. Solution (15K ps.gz)
• Hw (not to be handed in). Bakery algorithm: operational and assertional analysis of safety and progress. Solution: Operational analysis.
• Hw (not to be handed in). The following notes are from my 412 (operating systems) course. They cover various classical synchronization problems and their operational analyses. Read them and solve problems mentioned in them.
  • Note 8: Low-level ready-modify-write atomicty
  • Note 9: Semaphores
  • Note 10: Binary Semaphores
  • Note 11: No Busy Waiting
  • Note 12: Bounded-buffer Producer-Consumer Problem
  • Note 13: Readers-Writers Problem
  • Note 14: Dining Philosophers Problem
  • Note 15: East-West Bridge Problem
• Hw 3 (handed in) grading and distribution. The grade is out of 20 points, distributed equally among problem 1 safety, problem 1 progress, problem 2 safety, problem 2 progress, and presentation (neatness, margins, single side,...). So your score is indicated by 5 numbers (each between 0 to 4) and their sum.

  The grade distribution is: 10,10, 9, 8, 7,7,7, 6,6, 5, 4, 3, 2,2,2.

• Project description (ps)

MS Comp

This page and all problem sets, lecture notes, and exams linked to it are copyrighted. Use of these pages for the class CMSC712 at the University of Maryland is permitted. Any other use requires permission of the author (Udaya Shankar, shankar@cs.umd.edu).