When to use semaphore/mutex:-
----------------------------
Here is how I remember when to use what -
Semaphore: Use a semaphore when you (thread) want to sleep till some other thread tells you to wake up. Semaphore 'down' happens in one thread (producer) and semaphore 'up' (for same semaphore) happens in another thread (consumer) e.g.: In producer-consumer problem, producer wants to sleep till at least one buffer slot is empty - only the consumer thread can tell when a buffer slot is empty.
Mutex: Use a mutex when you (thread) want to execute code that should not be executed by any other thread at the same time. Mutex 'down' happens in one thread and mutex 'up' must happen in the same thread later on. e.g.: If you are deleting a node from a global linked list, you do not want another thread to muck around with pointers while you are deleting the node. When you acquire a mutex and are busy deleting a node, if another thread tries to acquire the same mutex, it will be put to sleep till you release the mutex.
-------------------------------------------------------------------------------------------------------------------------------------
What are Conditional Variables in OS?
A conditional variable in operating system programming is a special kind of variable that is used to determine if a certain condition has been met or not. It is used to communicate between threads when certain conditions become true.
A conditional variable is like a queue. A thread stops its execution and enters the queue if the specified condition is not met. Once another thread makes that condition true, it sends a signal to the leading thread in the queue to continue its execution.
If there is no thread in the queue, the signal is wasted.
Supported actions
There are two types of actions that can be performed with condition variables:
wait
signal
We use the wait instruction in a thread if we want to halt the execution of that thread till a certain condition is met.
We use the signal instruction if we want to continue executing the leading thread in the waiting queue.
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
Difference between a conditional variable and a semaphore:--
Often semaphore is confused with the conditional variable. Some of the differences between a semaphore and a conditional variable are listed in the table below:
Conditional Variable:--
The thread waits till a certain condition is met.
The signal() is wasted if there is no thread waiting.
We can run all waiting threads using broadcast unlocking.
The wait() function almost always block its caller.
It is mostly used with mutex. It signals the change in state from one thread to another.
Semaphore:---
Only those threads wait which make the value of the semaphore less than or equal to 0.
The sem_post() is not wasted even if no thread is waiting. The value of the semaphore is increased.
We can not run all waiting threads using broadcast unlocking.
The wait() function does not always block its caller.
It is mostly used to solve critical section problems.
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
producer consumer problem:-
--------------------------
typedef struct
{
char buf[SIZE];
int occupied;
int nextin;
int nextout;
pthread_mutex_t mutex;
pthread_cond_t more;
pthread_cond_t less;
}buffer_t;
void producer ( buffer_t *b, int item)
{
pthread_mutex_lock(&b->mutex);
while ( b->occupied >= SIZE)
pthread_cond_wait ( &b->less, &b->mutex);
b->buf[b->nextin++] = item;
b->nextIn = b->nextIn % SIZE;
b->occupied++;
pthread_cond_signal( &b->more); // this will unblock eht consumer to read
pthread_mutex_unlock(&b->mutex);
}
char consumer( buffer_t *b)
{
char item;
pthread_mutex_lock(&b->mutex);
while ( b->occupied <= 0)
pthread_cond_wait(&b->more, &b->mutex);
item = buf[b->nextout++];
b->nextOut = b->nextOut%SIZE;
b->occupied--;
pthread_cond_signal(&b->less);
pthread_mutex_unlock(&b->mutes);
}
-------------------------------------------------------------------------------------------------
//arr is given find max consucitive sum of elements.
int maxConsecutiveSum ( int arr[])
{
int currentMax = arr[0], globalMax = arr[0];
for ( int i=0; i<n; i++)
{
if ( currentMax < 0 )
currentMax = arr[i];
else
currentMax = currentMax + arr[i];
if ( globalMax < currentMax)
globalMax = currentMax;
}
return globalMax;
}
-------------------------------------------------------------------------------------------------
Trees questions:-
-----------------
tree creations:-
struct node
{
int data;
struct node *left;
stcurt node *right;
};
node *createNode(int item)
{
node* newNode = new node();
newNode->data = item;
newNode->left = NULL;
newNode->right = NULL;
}
//sum of left leaves ....
int sumOfLeftLeaves ( node *root)
{
if ( root )
{
if ( root->left && !root->left->left && !root->left->right )
return root->left->data + sumOfLeftLeaves ( root->right);
return sumOfLeftLeaves ( root->left) + sumOfLeftLeaves ( root->right);
}
return 0;
}
//insert node in bst
struct node *insert(struct node *root, int item)
{
if (root == NULL)
return (createNode(item));
if ( item > node->data )
return insert(root->left, item);
else
return insert(root->right, item);
return root;
}
//connect nodes at same level and last nodes of each level with first node of next level...
//basically it will create a linkedlist like structure were first node will be root and last node will last node of last level...
void linkllNOdesLevelWise( node *root)
{
node *lastNode, *currentNode;
lastNode = currentNode = root;
while ( currentNode != NULL )
{
if ( currentNode->left != NULL )
{
lastNode->next = currentNode->left;
last = currentNode->left;
}
if ( currentNode->right != NULL)
{
last->next = currentNode->right;
last = currentNode->right;
}
lastNode->next = NULL;
currentNode = currentNode->next;
}
}
//
// Least common ancestor of two nodes in tree.
struct node *lca ( struct node *root, int n1, int n2 )
{
struct node *temp = root;
while ( temp != NULL )
{
if ( temp->data > n1 && temp->data > n2 ) // means lca will lie in left subtree of this node.
{
temp = temp -> left;
}
if else ( temp->data < n1 && temp->data < n2 )
{
temp = temp -> right;
}
else
break;
}
return temp;
}
time complexity - o(h)
//simple but incorrect
bool isBST(struct node *root)
{
if ( root == NULL )
retur true;
if ( (root->left && root->data < root->left->data) || (root->right && root->data > root->right->data ) )
{
return false;
}
if ( !isBST(root->left) || !isBST(root->right))
return false;
return true;
}
here there is a possibility that for each node it correct but if you see for whole tree then for some upper nodes its not correct.
so we need to check root->data with max(root->left) and root->data with min(root->right);
bool isBST(struct node *root)
{
if ( root == NULL )
retur true;
if ( (root->left && root->data <= maxValue(root->left) || (root->right && root->data >= minValue(root->right) ) )
{
return false;
}
if ( !isBST(root->left) || !isBST(root->right))
return false;
return true;
}
// Max depth or height of the tree
int maxHeight(strct node *root)
{
if ( root == NULL)
reutrn -1;
else
{
int ldepth = maxHeight( root->left);
int rdepth = maxHeight( root->right);
if ( ldepth > rdepth )
return ldepth + 1;
else
return rdepth + 1;
}
}
//Get max depth or heith using level wise traversal using queue.
1,NULL
int height ( strcut node *root)
{
int depth = 0;
queue <node*> q;
q.push(root);
q.push(NULL);
while ( !q.empty() )
{
node *temp = q.front();
q.pop();
if ( temp == NULL)
depth++;
if ( temp != NULL)
{
if ( temp -> left )
{
q.push(temp->left);
}
if ( temp->right)
{
q.push(temp->right);
}
}
else if ( !q.empty())
{
q.push(NULL);
}
}
return depth;
}
/////////////////////////////////////////
int findMin( struct node *root)
{
if ( root == NULL)
return INT_MIN;
int res = root->data;
int lres = findMin(root->left);
int rres = findMin(root->right);
if (lres > res)
res = lres;
if (rres > res)
res = rres;
return res;
}
///////////////////////////////////////////
Convert binary tree to BST
--------------------------
steps :-
inorder BT and store in arr
sort the arr
inorder traversal of tree take arr element and copy elements to tree
modified tree will be BST....
void BT_to_BST( struct node *root)
{
if ( root == NULL)
return;
int n = count( root); // count the number of nodes .
int *arr = new int[n];
int i =0;
storeInOrder ( root, arr, &i);
qsort ( arr, n );
//copy arr elements to BT
i = 0;
arrToBSt( arr, root, &1);
delete [] arr;
}
int count ( struct node * root)
{
if ( root == NULL)
return 0;
return count ( root->left ) + count ( root->right) + 1;
}
void storeInOrder ( strcut node * root, int inorder [], int *index )
{
if ( node == NULL)
return;
storeInorder ( root->left, inorder, index );
inorder [*index] = root->data;
(*index)++;
storeInOrder ( root->right, inorder, index);
}
void arrToBst( struct node *root, int *arr, int *index)
{
if ( root == NULL)
return;
arrToBST( root->left, arr, index);
root->data = arr[*index];
(*index)++;
arrToBST( root->right, arr, index);
}
int main()
{
node *root = NULL;
root = createNode(10);
root->left = createNode(8);
root->right = createNode(12);
root->left->left = createNode(6);
root->left->right = createNode (7);
return;
}
//////////////////////////////////////////////
Smart pointers in c++
----------------------
Smart pointer :-
class SmartPtr
{
private:
T* m_data;
public:
SmartPtr (T* pValue )
{
m_data = pValue;
}
~SmartPtr()
{
delete m_data;
}
T & operator*()
{
return *m_data;
}
T & operator->()
{
return m_data;
}
};
int main ()
{
SmartPtr<int> *ptr ( new int());
*ptr = 10;
ptr->display();
return 0;
}
--------------------------------------------------------------
Unique pointer:-
---------------
two pointers can not be point to same object at the same time.
Here one pointer can pass the control to other pointer.
ex:- P1 = object1
p2 = object1 // here p1 passed its control to p2.
class rectangle
{
int len;
int width;
public:
rectangle( int l, int b )
{
len = l;
width = b;
}
int area ( int l, int b)
{
return l * b;
}
};
int main ()
{
uniquePtr < rectangle > *ret1 = new rectangle ( 10, 5);
cout << ret1->area(); // it will print 50
uniquePtr < rectangle > *ret2;
ret2 = move ( ret1); // ret1 passed the control to ret2.
cout << ret2->area() // print 50
cout << ret1->area() // it will give an error as its not pointing to any object now.
return 0;
}
Shared Pointer:-
----------------
Here basically more than one pointer shares particular object.
It maintains the reference count.
class rectangle
{
int len;
int width;
public:
rectangle( int l, int b )
{
len = l;
width = b;
}
int area ( int l, int b)
{
return l * b;
}
};
int main ()
{
shared_ptr<rectangle> *p1 = new Rectangle(10, 5);
cout << p1->area() // print 50
shared_ptr<rectangle> *p2;
p2 = p1;
cout << p2->area(); // print 50
cout << p1->area(); // print 50, it will not give an error
cout << p1.useCount() // print 2 as reference count is 2
// Relinquishes ownership of p1 on the object
// and pointer becomes NULL
p1.reset();
cout << p1.get() << endl; // it will print null as it not pointing to any address now
cout << p2.use_count() << endl; // print 1
cout << p2.get() << endl; // it will give an address of object as its still pointing the same.
}
Weak pointer:-
--------------
This is used in place of shared_ptr in one problem - Cyclic dependency problem.
Here suppose we have two classs A and B and have one - one shared pointer in each class which can access to object of each others classes.
So here if we use shared pointer then it will always maintain a reference of each other and will not allow to delete the either of the objects.
So here weak pointer work if we declare either of one pointer as weak.
class Singleton
{
private:
static Singleton *Instance;
Singleton();
public:
Singleton *getInstance();
};
Singleton* Singleton::Instance = 0;
Singleton* Singleton::getInstance()
{
if ( Instance == NULL )
{
instance = new Singleton();
}
return instance;
}
singletone:-
-------------
#include <iostream>
class Singleton
{
private:
/* Here will be the instance stored. */
static Singleton* instance;
/* Private constructor to prevent instancing. */
Singleton();
public:
/* Static access method. */
static Singleton* getInstance();
};
/* Null, because instance will be initialized on demand. */
Singleton* Singleton::instance = 0;
Singleton* Singleton::getInstance()
{
if (instance == 0)
{
instance = new Singleton();
}
return instance;
}
Singleton::Singleton()
{}
int main()
{
//new Singleton(); // Won't work
Singleton* s = Singleton::getInstance(); // Ok
Singleton* r = Singleton::getInstance();
/* The addresses will be the same. */
std::cout << s << std::endl;
std::cout << r << std::endl;
--------------------------------------------------------------------------------------------------
Need to read about PKI --
-PKI - its a software, encryption technologies, security methods used by organization to secure their data or to secure their business communications.
-How PKI helpful:
PKI provides below things.
Confidentiality - by data encryption
Integrity - by digital signature -
1.sender calculate hash of data using any hash algorithm ( sha256). - this the part1
2.Sender encrypts the hash with its own private key and create a signature -- this is called a digital signature.
3.sender send the encrypted data by senders public key + hash + algo used in hash in plain text + its own digital signature.
4.reciever will decrypt the data with its own private key, calculate hash on date using same hash algorithm and calculate a hash.
5.Now reciever will decrpty the digital signatures by senders public key and get the hash. Now he will compare both the hash to check integrity.
Authenticity :- Its provided by digital signatures, hash algorithm - if reciever can decrypt the data it means that data is encrypted by its corresponding public key.
Non-repudiation:- Digital signatures or audit logs - sender cant deny that its not sent data.
Availability - multiple CAs are available to sign or allocate certificate to user/computer/program
- all component of PKI - Digital certificate, CA, digital signatures, hashing, message digest etc.
- How key length plays the role in security:-
Keys with more length will provide more security to data but it slows the encryption performance.
ex: RSA-2048 it will provide more security in encryption compared with 3DES ( 168 bits ) or AES-256 bits.
So what to do to achieve better security + better performance.
Do encryption of data with symmetric key algo ( like AES,3DES) + encrypt that symmetric key only with assymetric key ( RSA-2048).
- Use of ciphers which agreed in ssl handshake.
- Use of digital signature ..
Digital signature means - identity of user can be used in integrity/ authenticity
Hashing algorithms:-
MD5 -- 128 bbits to generate the hash
SHA0 -- 168 bits
SHA1 -- 168 bits -- 0 and 1 both got deprecated in 2017.
SHA2 -- now a days we are using SHA2 ( SHA-224 or SHA256 )
SHA3
- server and client verification through server/client certificates.
- Why KS required?
- about security tools - blackduck, qualys.
- How to prevent many well known attacks like ddos, sql injuction.
- How and which tools are helpful to use for prevention of such kind of attacks.
- difference between encoding and encryption
---------------------------------------------------------------------------------------------------
How ssl works:-
Client side:-
CA - certificate authorities will provide the public keys to browser venders , these vendor keep on updating these public keys to correspondign browser, in this way all browsers have public keys of all the CAs.
Server side:- When any one wants to make secure communication for his site then he first create a CSR ( certificate signinig request ) and get it signed by CA.
in signing process basically CA encrypts checksome of server ( CSR ) with its private key and corresponding public key shares with browser vender. So at this poing all the browser must have corresponding public key via which CA signs any server's CSR.
Now comes to communication part:- ( high level of SSL handshake )
Here once client wants to communicate wtih server, it send connect request.
server response with its certificate.
client verfies its certificate by looking up corresponding CA's public key. its decrypts the certs and find server cert checksome also create hash and calculate checksome. Now it compares both the checksome.
Structure of signatures:-
- Version
- serial number
- signature algo
- Issuer
-- issued to
-- issued by
- Vality
-- start date
-- end date
-Subject public key
- X509 extension
- Signature
-- Signatures algo
-- Signatures
PKCS -- things need to covers....
x509 formats and other formats ....
some ssl apis() need to cover ...
RSA vs ECC --
=====================================================================================================================================================
Bitwise operator :
-------------------
The following are many other interesting problems using XOR operator:
---------------------------------------------------------------------
Return true in case two numbers have opposite sign.
n1 = -13
n2= 10
Return true
for n1 = 8, n2 = 10 return false
--------------------
singbit of positive number is - 0
signbit of negative number is - 1
if we do xor ( eg: 1 xor 0 = 1, 1 xor 1 = 0, 0 xor 0 = 0 )
so do xor of these tow numbers - if result is < 0 ( negative ) means xor of signbits are 1 ( -ve num).
bool opposite( int num1, int num2)
{
return (( x ^ y) < 0);
}
int main ()
{
int num1 = -10;
int num2 = 5;
if ( oppositeSign( num1, num2) < 1 )
{
signs are opposite
}
else
signs are same
}
---------------------------------------------------------------------------------
