Semaphore

Initialize how many permissions you will use.

acquire() will add one permission.

release() will remove one permission.

Permission must ≥ 0.

Semaphore solution for the MEP

1. #criticalSection + permissions = 1
2. #criticalSection = #acquires − #releases

Mutual exclusion: #criticalSection ≤ 1 since #permission ≥ 0. Absence of deadlock: It never happens that #permission = 0 and #criticalSection = 0

Java

public class Turnstile extends Thread {
    static volatile int counter = 0; // keyword is recommended for variables that are shared
    static Semaphore mutex = new Semaphore (1);
    public void run() {
        for(int i = 0; i < 50; i++){
            mutex.acquire();
            counter ++;
            mutex.release();
            System.out.println(id+"- In comes: "+i );
        }
    }

    public static void main(String args[]) {
        try{
            Thread m1 = new Turnstile (1); m1.start();
            Thread m2 = new Turnstile (2); m2.start();
        } catch(Exception e){}
    }
}

Strong semaphore

Possibility of starvation is caused by the fact that blocked processes are placed in a set of processes. But this can be remedied by changing the set to be a queue.

Race condition

Multiple thread access one same variables of object concurrently and at least one does update.

Bad situation.

Atomic operation

An operation is atomic if it execute until it completion without interruption

Critical section

A part of program that accesses shared memory and which we which to execute automatically.

mutual exclusion problem (MEP)

1. Mutex: at and point in time, there is at most one thread in the critical section
2. Absence of livelock: If various of threads try to entry the critical section, at lease one of them will succeed.
3. Free from starvation: A thread trying to enter its critical section will eventually be able to do so.

Deadlock is not exit for a interleaving in a transition system.

Agile Vs Traditional SDLC Models

Agile is based on the adaptive software development methods, whereas the traditional SDLC models like the waterfall model is based on a predictive approach. Predictive teams in the traditional SDLC models usually work with detailed planning and have a complete forecast of the exact tasks and features to be delivered in the next few months or during the product life cycle.

Predictive methods entirely depend on the requirement analysis and planning done in the beginning of cycle. Any changes to be incorporated go through a strict change control management and prioritization.

Document constructor

$$f(x) = sin(x)$$

What is concurrency

Systems of interacting computer programs which share resource and run concurrently.

parallelism and concurrency

Parallelism: Occurring physically at the same time.

Concurrency: Occurring logically at the same time.

synchronization

Process synchronization: Ensure the instructions are executed in certain order.

Synchronization is irrelevant if processes do not interact with each other.

Concurrency, and hence process synchronized, is useful only when processes interact with each other.

interaction

Share memory is kind of interact.

See all algorithm click here

Mutating and Non-mutating algorithms

Mutating algorithms

Mutating algorithms means this algorithm will change the content that iterator pointed to. Like copy, swap, replace, fill, remove, permutation, partition, random shuffling and sort.

If your give these algorithms a const iterator, only error will be returned.

#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char const *argv[])
{
    std::vector<int> iv = {22,30,30,17,33,40,17,23,22,12,20};

    vector<int>::iterator ib = iv.begin();
    vector<int>::iterator ie = iv.end();

    sort(ib,ie); //works

    for (std::vector<int>::iterator i = iv.begin(); i != iv.end(); ++i)
    {
        cout << *i << ' ';
    }
    cout << endl;

    // vector<int>::const_iterator ib = iv.begin();
    // vector<int>::const_iterator ie = iv.end();

    // sort(ib,ie); // error
    return 0;
}

Non-mutating algorithm

Algorithm not change any element that iterator pointed to. Like: find, search, for_each, count, equal_mismatch, max, min.

Bit operator

Operator: &

x is a bit

x & 1 = x

x & 0 = 0

Usually use & as a filter. Suppose we have a number is X, X & 0011 will get the last two bits of X.

2-3 tree & 2-4 tree

2-node: 1 key and 2 children 3-node: 2 keys and 3 children 4-node: 3 keys and 4 children

A (2,4) tree (also called 2-4 tree or 2-3-4 tree) is a multi-way search with the following properties:

• Node-Size Property: every internal node has at most four children
• Depth Property: all the external nodes have the same depth

insertion

Example

increment and decrement operator

#include <iostream>
using namespace std;

class INT
{
private:
    int m_i;
public:
    INT(int i):m_i(i){};

    friend bool operator==(INT& test1, INT& test2){
        return test1.m_i == test2.m_i;
    }

    friend bool operator!=(INT& test1, INT& test2){
        return test1.m_i != test2.m_i;
    }

    friend INT operator+(INT& test1, INT& test2){
        int temp = test1.m_i + test2.m_i;
        INT res(temp);
        return res;
    }

    INT& operator=(INT& test){
        this->m_i = test.m_i;
        return *this;
    }

    int& operator*() const{
        return (int&)this->m_i;
    }
    // int a() const {}; This means a() cannot change any member in class.

    INT& operator++(){ //prefix. ++test;
        this->m_i += 1;
        return *this;
    }
    // Why prefix is not const. Because it always return original class and actually it support ++++test.

    const INT operator++(int){ //postfix. test++;
        INT temp = *this;
        // ++(*this);
        this->m_i += 1;
        return temp;
    }
    // Postfix must be const. Because it return a temporary variable and it not support test++++.
    // You can try int i = 1; i++++;
    // This is invalid.

    friend ostream& operator<<(ostream& s, const INT& i){
        s << '[' << i.m_i << ']';
        return s;
    }

};

int main(int argc, char const *argv[])
{
    INT test(1);
    INT test1(10);
    INT test2(3);
    cout << ++test << endl; //[2]
    cout << test++ << endl; //[2]
    cout << test << endl; //[3]
    cout << *test << endl; //3
    cout << (test + test2) << endl; //[6]
    cout << boolalpha << (test == test2) << endl; //true
    test = test1;
    cout << test << endl; //[10]
    return 0;
}

Second Example

convert operator

Classification

• Sequence container
  • array (build in)
  • vector
  • heap
  • priority queue
  • list
  • slist (not standard)
  • deque
  • stack (adopter)
  • queue (adopter)
• Associative container
  • RB-tree (not public)
  • set
  • map
  • multiset
  • multemap
  • hashtable (not standard)
  • hash_set (not standard)
  • hash_map (not standard)
  • hash_multimap (not standard)
  • hash_multiset (not standard)

Associative container have a key-value pair. It do not have back and front so they never have push_back, pop_back.

Vector

This is similar with grow array. Vector use sequential space.