Interprocess Communication and Synchronization

Introduction

In this article, we are going to introduce interprocess communication(IPC)—a mechanism for processes to synchronize and communicate with each other. After reading this article you will understand:

  • Why do we need interprocess communication(IPC)
    [Ans: Synchronization & Communication]
  • Two approaches for IPC
    [Ans: Shared memory & Message passing]
  • Why do we need synchronization for shared memory methods
    [Ans: Race condition]
  • Methods for shared memory synchronization
    [Ans: Mutex, Semaphore, Monitor]
  • Differences among shared memory synchronization methods
  • What message passing methods do we have
    [Ans: In linux: Pipe, Message queue, socket…]
  • How to categorize message passing methods
    [Ans: Blocking, Addressing, Queuing]

Let me show you a mind map for interprocess communication. It also shows the structure of this article.
You may download the PDF Version Here

Why Interprocess Communication

Cooperating processes frequently need to communicate with each other to ensure works are correctly done. Sometimes,the correctness of the executing results depend on the executing sequence of cooperating processes. At this scenario, we need to enforce synchronization to make sure we can get the correct results. Sometimes the execution of one process may require the result of another process. At this scenario, we need a communication mechanism for those processes to talk to each other.

Two Approaches for IPC

Here is where IPC comes to rescue. There are two approaches that can be used for IPC. One is shared memory, and the other is message passing. We will address the details of them in the following sections.

Shared Memory IPC

Cooperating processes may communicate by sharing the same piece of memory. One process can write some data to a piece of shared memory, and another process can read from the same piece of memory directly. When doing so, you need to be careful. Otherwise, The executing result may not be the same as your expectation. To understand why, we explain the concept of race condition first.

Race Condition

A race condition occurs when multiple processes or threads try to read and write data items at the same piece of shared memory, so that the final result depends on the order of execution of instructions.

Example:
Suppose process 1 and process 2 are sharing the same data counter , race condition may happens as follows:
Race Condition 1
The satements can be break down into three lines of assembly instructions correspondingly:
Race Condition2
When context switch happens in the middle of the three lines of instructions, unexpected results may happens(Try it!). This demonstrate the so called race condition.

Critical Section Problem

To solve race condition problem, we define a problem called critical section problem.
Definition:
Critical section is the part of program where shared memory is accessed.
Definition:
Critical section problem: Find solutions that arrange the cooperating processes properly, so that no two processes were ever in their critical sections at the same time.

Solution Criteria

To satisfy the requirements of critical section problems and other concerns like fairness, efficiency, our solutions should try to fulfill the three criteria below:

  1. Mutual Exclusion: No two processes can enter their critical sections at the same time.
  2. Progress: If no process is executing its critical section, then one of the waiting processes can enter its critical section.
  3. Bounded Waiting: No infinite wait for a process.

Hardware Supports for Shared Memory Synchronization

We are going to introduce two hardware supports for shared memory synchronization. They may be used for implementing software synchronization algorithms like mutex, semaphore. You may wonder what is hardware supporting for software synchronization algorithms. The answer is that hardware provides atomic operation for software algorithms. So the following hardware functionalities are all atomic operations.

Test and Set

Definition:

Notes: Test and set is supported by hardware, which ensures that it runs atomically.

Compare and Swap

Definition:

Notes: Compare and swap is supported by hardware, which ensures that it runs atomically.

Software solutions for Shared Memory Synchronization

Remind you again, this article is not explaining the details of these algorithms, but to relate them together. We divide them into two parts— primitive and advanced. Advanced algorithms are supported by primitive algorithms/mechanisms as well as hardware algorithms like test and set. There are four primitive algorithms/mechanisms: Lock variables, Taking turns, Peterson’s algorithm and Bakery algorithm; and three advanced algorithms: Mutex, Semaphore and Monitor. We will illustrate them one by one in the following sections. Before then, we would like to show you the relationships among them first:
Synchronization Algorithm Relationship

Now, let’s define them one by one:

Lock Variable Mechanism

Definition:

Taking Turns Mechanism

Definition:

Peterson’s Algorithm

Definition:

Bakery Algorithm

Definition:

Mutex

Difinition:

Notes: The two operations(entry_section() and exit_section()) must be atomic, which can be implemented by test and set or compare and swap.

Semaphore

Definition:

Notes: The two operations must be atomic, which can be implemented by test and set or compare and swap.

Monitor

Definition:
Monitor is an abstract data type that provides mutual exclusive operations. The monitor construct ensures that only one process at a time is active within the monitor. Monitors are provided by operating systems, programmers do not need to worry about how to implement them.

Put them Altogether

Putting all of the synchronization algorithms/mechanisms together:
You may download the PDF Version Here
Synchronization Algorithm Properties

The following table shows the properties of those software synchronization algorithms above:
You can also download its PDF Version Here
Synchronization Algorithm Properties

Message Passing IPC

To communicate with other processes, shared memory IPC enforces many synchronization constraints. For message passing IPC, we do not need to care much about synchronization problems(we do, but not much). We can categorize message passing IPC methods from three dimensions: blocking , addressing, queuing.

Blocking

The blocking property describes how message passing processes are synchronized.

Sender:

  • Blocking: The sending process is blocked until message is received.
  • Nonblocking: Send and go away.

Receiver:

  • Blocking: If no waiting message present, the receiver process is blocked until message come.
  • Nonblocking: Try to receive, and go away.

Addressing

The addressing property describes the destination of the message. A message may be delivered to the receiver directly or to a mail-box for the receiver to collect later on(Indirectly).

Queuing

The queuing property describes the receiving order of messages on the receiver side. It may be FIFO or priority based.

Linux Message Passing IPC

In linux system, there are about five basic types of message passing IPC methods: anonymous pipe, named pipe, signal, message queue and socket. The following table is trying to compare them by the three properties discussed above.
Linux IPC Methods Properties

Conclusion

//Todo

DataMing Note 1 Data Mining Basics

Introduction

This note is going to explain some basic concepts of data mining. After reading it, you should be able to answer these questions:

  • What’s data mining?
    –> Section[What’s Data Mining]
  • How to do data mining step by step?
    –> Section[KDD Process]
  • How’s the architecture of data mining system looks like?
    –> Section[Architecture of Data Mining System]
  • What algorithms can we apply to search for the pattern(model) that we want?
    –> Section[What do we do in each part of KDD process]

What’s Data Mining

Data mining helps us to extract useful information from large databases. It’s a step within the KDD process.

Definition: Knowledge discovery in database(KDD) is the process of finding useful information and knowledge in data.

Definition: Data mining is the use of algorithms to extract patterns or models in KDD process.

KDD Process

There are totally six steps in KDD process as is shown on below:
Steps of KDD
The KDD process can be divided into three parts. The first part is data preprocessing including step 1-3. The second part is data mining where many data mining algorithms involve. And the last part is evaluation and presentation. We will be mainly focus on the first and second parts in our data mining notes.

The following figures illustrates the overall KDD process in more details:
KDD Process

KDD Process in Parts

Bear in mind that KDD process is extremely important for your study of data mining. Your get to know what you are doing from KDD points of view at each steps. Always ask yourself why the techniques that you are studying helps for a better result.

Architecture of Data Mining System

Here is the architecture of data mining system:
Architecture of Data Mining System

What do we do in each part of KDD process

Data Preprocessing

Data Preprocessing

Data Mining

Data Mining

Evaluation and Presentation

Not addressed in this note at this time.

Conclusion

This notes briefly introduces the KDD process and data mining system architecture. In later notes we will illustrate data preprocessing and data mining algorithms in more details, if you are interested in them, please refer to kelvin.ink for more details.

Uniprocessor Scheduling Algorithms

Your may download all of the tables(key points) of this article by clicking this link:
PDF Quick Reference:
Download tables

Introduction

In this article, we are going to introduce several short-term scheduling algorithms that are widely used in uniprocessor computers. After reading this article, your should be able to answer the following questions: What’s process state? What’s short-term scheduling? When to do short-term scheduling? What kinds of scheduling algorithms do we currently have? How do we choose a scheduling algorithm and based on what criteria? The following table indicates which sections in this article are trying to answer these questions correspondingly.
Contents Indicating Table

Process States

  • New: A process is created.
    Program code are moved from disk to main memory.
  • Ready: The process is waiting to be scheduling to a processor.
    Program code reside in main memory.
  • Running: Instructions are being executed in CPU.
    Instructions reside in CPU.
  • Waiting: The process is blocked and waiting for some events to occur(signal)
    Program code are in main memory or has been swapped out to virtual memory.
  • Terminated: The process has finished execution.
    Program code are removed from memory.

This is the state transition diagram of the process states.
State Transition Diagram

The table below shows where do program code mainly reside at each state.
Program Code Location

Types of Scheduling

There are three kinds of scheduling including long-term scheduling , medium-term scheduling and short-term scheduling. This article is mainly focus on short-term scheduling.

This table shows when do we do the three scheduling in terms of state transitions.
Scheduling and State Transition

We mark them on the state transition diagram:
Scheduling on State Transition

Short-Term Scheduling

Scheduling Criteria

There are a bunch of scheduling criteria that we need to consider when choosing a scheduling algorithm.

  • CPU utilization (u%)
  • Throughput (process/second)
  • Turnaround time (seconds/process)
  • Waiting time (seconds)
  • Response time (seconds)
  • Deadline
  • Fairness
  • Predictability
  • Policy enforcement
  • Balance

Criteria for Different Systems

Different systems should follow different criteria based on their own requirements.
Criteria for Different Systems

Scheduling Algorithms

We will introduce four scheduling algorithms with examples. In next section, we will explain the details of these algorithms.

1. First-Come-First-Serve (FCFS)

Selection Function: Select the process with the minimum arrival time. (Non-preemptive)
Example for FCFS:
Suppose there are four processes whose arrival time and service time are listed in the table.
FCFS Processes Table
The scheduling result in Gantt chart:
FCFS Scheduling Result

2. Round-Robin (RR)

Selection Function: Each process execute for fixed length of time quantum. (Preemptive)
Example for RR:
Suppose there are four processes whose arrival time and service time are listed in the table.
Round-Robin Processes Table
The scheduling result in Gantt chart:
Round-Robin Scheduling Result

3. Shortest-Job-First (SJF)

Selection Function: Select the process with the minimum service time (Non-preemptive)
Example for SJF:
Suppose there are four processes whose arrival time and service time are listed in the table.
SJF Processes Table
The scheduling result in Gantt chart:
SJF Scheduling Result

4. Preemptive-Shortest-Job-First (PSJF)

Selection Function: Select the process with the minimum remaining service time (Preemptive)
Example for PSJF:
Suppose there are three processes whose arrival time and service time are listed in the table.
PSJF Processes Table
The scheduling result in Gantt chart:
PSJF Scheduling Result

Scheduling Algorithm Properties

We define some terms first.

  • a : arrival time of a process
  • e : time spent in execution so far
  • s : total service time required by the process, including e

The following table shows the corresponding properties to the scheduling algorithms.
Scheduling Algorithm Properties

Scheduling Algorithm Selection

Based on the criteria for different systems and scheduling algorithm properties, we can decide what kind of algorithms we should choose for each kind of systems. As is shown from below:
Systems and Scheduling Algorithms

Why Why Why

Why Multiprograming

Some processes are CPU bound, and some are I/O bound. An I/O bound process will be blocked when it tries to do I/O. To improve CPU utilization rate, engineers proposed the concept of Multiprograming. That is to say — we load many processes into the main memory at the same time. When a running process is blocked by I/O operation, we switch to run other processes. Multiprograming is the root cause that we need to do short-term scheduling.

What’s the differences between Multiprograming and Multithreading

Multiprograming is for improving CPU utilization, while Multithreading is for many other reasons. For example: share resources, parallelism, simplify code structure, improve concurrency and many others.