Index

SchoolNotes

  1. CS225
    1. Introduction
    2. Lesson 1
    3. Lesson 2
    4. Lesson 3
    5. Lesson 4
  2. CS251
    1. The Beginning
  3. CS180
    1. Introduction
    2. Midterm Revision
    3. Finals Revision
    4. CS251
    5. Memory
    6. ELF Format
    7. History of Computers
    8. Stuff to Research
    9. Quiz To-Do
    10. OS Architectures
    11. Week 3
    12. Week 4
    13. Week 5
    14. Week 6 (Threads)
    15. Week 7 (Scheduling)
    16. Week 8 (Thread Scheduling)
    17. Week 9 (Memory Management)

OLD SHIT

  1. CS225 (OLD ONE IGNORE THIS)
    1. OOP
      1. Inheritance
      2. R-Value References
    2. Misc Notes
    3. Size/Offsets of Structs/Classes
    4. Week 4
  2. CS200 (IGNORE THIS TOO)
    1. Introduction
    2. Scan Conversion
    3. Quiz 01
  3. GAM200 (YEAH, IGNORE THIS TOO)
    1. Notes

Week 8 (Thread Scheduling)

volatile means that it can be changed in one of 3 scenarios:
1. Variable is in the status register
2. Interrupt of a while(status) (status being the volatile int)
3. In a multithread scenario and multiple threads are touching the same data

volatile will not be optimized in any way by the CPU, it is mainly used when interfacing with hardware.

solution criteria
- Criteria
→ Mutual Exclusion
⇒ Once one process enters into critical section, nobody else is allowed in
→ Progress
⇒ When there is no other process entering the critical section selection of the process, selection of the process for processes that are entering into the critical section will not be postponed
→ Bounded Waiting
⇒ Bounded waiting is : There exists a bound, or limit, on the number of times other processes are allowed to enter their critical sections after a process has made request to enter its critical section and before that request is granted.
- Assumptions
→ Speed independence
⇒ independent of the instruction speed


Progress means that process should eventually be able to complete.

Bounded waiting means no process should wait for a resource for infinite amount of time.


1) Progress is : If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder section can participate in deciding which will enter its critical section next, and this selection cannot be postponed indefinitely.
And
2) Bounded waiting is : There exists a bound, or limit, on the number of times other processes are allowed to enter their critical sections after a process has made request to enter its critical section and before that request is granted.

http://stackoverflow.com/questions/33143779/what-is-progress-and-bounded-waiting-in-critical-section (GOOD EXPLANATION)

https://en.wikipedia.org/wiki/Peterson's_algorithm (important)

https://en.wikipedia.org/wiki/Test-and-set

https://en.wikipedia.org/wiki/Compare-and-swap

In concurrent programming, an operation (or set of operations) is atomic, linearizable, indivisible or uninterruptible if it appears to the rest of the system to occur instantaneously. Atomicity is a guarantee of isolation from concurrent processes. Additionally, atomic operations commonly have a succeed-or-fail definition—they either successfully change the state of the system, or have no apparent effect.

test and set and compare and swap are hardware instructions and therefore they are atomic

test and set works by the following:
For progress lets say, PO is in the critical section and P1,P2 and P3 are waiting. As soon as PO leaves, it sets lock to false and just after that the next process exits the while condition and enters the critical section. For bounded waiting, I am not sure of but if lets say, P4 with a high priority comes and repeatedly requests to enter the critical section. Then, P1,P2,P3 will never get the chance to enter the section. Hence, they'll wait infinitely.

If busy waiting for test and set and compare and swap take a short amount of time, then its a good idea to use them (similar to polling)

Sleep and wakeup - blocking the calling process is equivalent to going into a wait state.
waking up is making a process go from waiting state to ready via a signal

priority inversion is fixed by giving the process which is in the critical section a higher priority - this is reverted after it exits the critical section.

the initialized value of s is the maximum number of processes that can be entered into the critical section, it obviously has to be more than 0, more than 0 is a counting/general semaphore, if its 1 then its a binary semaphore (and also a counting/general semaphore)
mutex is a binary semaphore.

Think of semaphores as bouncers at a nightclub. There are a dedicated number of people that are allowed in the club at once. If the club is full no one is allowed to enter, but as soon as one person leaves another person might enter.

empty semaphores do not necessarily have to be binary. (to be used to make sure there is something to be produced)
full semaphores also do not necessarily have to be binary. (to be used to make sure there is something to be consumed)

busy waiting is always gonna be there

https://en.wikipedia.org/wiki/Spinlock

haircut solution

barbers, customers and seats

mutex b;
semaphores e=N,f=0;
array int seats[N]
int num = 0
while(true)
{
f.wait(); //wait till there some full seats
b.wait();
barber.cut();
seats[--num]=0;
b.signal();
e.signal();
}

while(true)
{
e.wait(); //wait till no empty seats
seats[num++]=id
f.signal(); //increase number of full seats
}


dining philosophers just rank the fucking forks goddammit