並列・分散プログラミング
担当教員
授業の到達目標及びテーマ
The goal of this course is to provide good lectures, software tools and exercises for students to design and implement concurrent programs. The students are expected to master many basic concept and modeling skills for monitoring and controlling the current systems or events. The course was motivated by dissatisfaction with lack of practical and accessible techniques that aid reasoning about designs for concurrent software.
授業の概要と方法
In this course, students will learn how to model and to implement concurrent programs for a concurrent system. The state machine is used for modeling the behaviors of a concurrent system, and a software package, LTSA (Labeled Transition System Analyzer), is used for mechanically verifying the model. Java is used to implement current programs due to its availability and many in-built concurrent constructs. Many Java examples are provided to demonstrate the skills for designing, modeling and implementing a concurrent system.
授業計画
前期
| 回 | テーマ | 内容 |
|---|---|---|
| 1 | Introduction of the modeling approach | A model is a simplified representation of the real world. The models are based on finite state machines. The concepts of concurrency are presented in a careful, systematic manner. Every chapter uses examples to illustrate the concepts, models and programs. |
| 2 | Processes and Threads | A process is the execution of a sequential program. A process transforms its state by executing an action. The order in which actions are allowed to occur is determined by a transition graph. A process is implemented by a thread in Java. |
| 3 | Concurrent execution | The execution of a concurrent program consists of multiple processes active at the same time. Parallel composition is used to model concurrency. The interaction among processes is done by shared actions. A structure diagram is used for the outline of a concurrent system. |
| 4 | Share objects and mutual exclusion | We study the issues involved in constructing concurrent programs in which threads interact to communicate and cooperate. The simplest way to model shared objects is to use mutual exclusion via a lock. Synchronized methods have to acquire a lock and release the lock before and after accessing the object. |
| 5 | Monitors and conditional synchronization | Monitors are language features for concurrent programming. A monitor encapsulates data, which can only be observed and nodified by monitor access procedures. Monitors support conditional synchronization in addition to ensuring mutual exclusion. |
| 6 | Monitors and semaphores | A semaphore is an integer variable that can take only non-negative values. The only operations permitted are up and down defined by increment and decrement of the value. When multiple semaphores are used, the nested monitor problem (a kind of deadlock) might occur. |
| 7 | Deadlock | Deadlock occurs in a system when all its processes are blocked. There are four necessary and sufficient conditions for the occurrence of deadlock. We introduce a tool for deadlock analysis. We illustrate deadlock by the dining philosopher problem. |
| 8 | Safety property | A property is an attribute of a program that is true for every possible execution of that program. A safety property asserts that nothing bad happens during execution. We use the single-lane bridge problem to study and analyze the safety property of a concurrent monitor. |
| 9 | Liveness property | A liveness property asserts that something good eventually happens. In concurrent programming, we are concerned with systems that do not terminate. One of the liveness properties that is of special interest is called progress property. We introduce the tool for checking progress property. |
| 10 | Model-based approach | We introduce design of a cruise control system for a car based on the model-based approach. Concrete and clear pictures from requirements to models and from models to implementations are provided. Tools for model checking are used from time to time during the design. |
| 11 | Project assignment and the demo | A project for designing and implementing a concurrent system is given. A project sample will be shown with detailed explanation. Students are expected to complete the project in about a month. |
| 12 | Introduction to timed systems | We introduce how to moswl timed system. The key process in timed system is time manager. The duty of the time manager is to maintain time tables and to check timing consistency. The design of many concurrent systems including computer games can be simplified when timed system is used. |
| 13 | Design example: Parcel router | We introduce a design of timed systems called parcel router. The parcel router is a simple parcel-sorting device. Parcels are dropped from the top of the router and fall through the chutes. Each parcel has a destination code that can be read by sensors. The switch following the sensor is set to route the parcel to the correct destination. |
| 14 | Design example: Space invaders | The last example of a timed system is a simple video arcade game. Video games involve many active entities, called sprites, which move around independently and concurrently. Each sprite has an opportunity to move once per clock cycle. It is simple and efficient to use sprite for screen updates. |
| 15 | Present the design and submit the report for the project | Students are required to present their designs at the class, and then submit a report for the project. |
授業外に行うべき学習活動
Students are recommended to read the lecture notes before the class. There will be six exercises and a project assignments for students to do outside the class as homework.
テキスト
Lecture Notes at http://cis.k.hosei.ac.jp/~speng
参考書
Concurrency: State Models & Java Programs by Jeff Magee and Jeff Kramer, John Wiley & Sons Ltd, 2003
成績評価基準
1.Attendance: 10%
2.Exercises: 60%
3.Project: 30%