Scribes: Lei Jin, Vasishta Jayanti, Soma Putera
This technique could potentially fail when newly forked processes are put at the start of the queue. A possible solution is to limit the processes given for forking, but this technique fails if the new processes fork and exit immediately. The simplest solution is to put the new fork at the end of the queue. As a side note, forking fails when the queue is full.
First, the lower the number of priority, the higher the process is in the queue. For example, priority 1 job is ahead of priority 2 job. However in Unix, priority is called niceness: niceness 1 job is higher priority than niceness 2 job. The default for niceness for most processes is 0. But then some processes can have default niceness less than 0, example: an xserver that interacts with the user or a process with high niceness would be background computation like UFO searching. Mean programs have negative priority or very high priority. For example music programs like itunes or just any program that interacts with the user are mean programs.
Actual priority: a combination of external and internal priority. In Bash: 'ps -ef' looks at the niceness number in the first column, and the 'prio' number or actual priority in the second column.
int main(int argc, char* argv)
{
set priority(10);
execvp(argv[1], argv);
}
The whole point of distinguishing different types of users is to apply different scheduling algorithms to different user sets. Each user type is put into a separate queue. This idea not popular on single cpu, because single CPU cannot be used in this way. But for a 1000 node cluster, we need to use this queue structure for better organization of priority. It is the operator's job to control which job gets to execute and when, moving a job from one queue to another.
There are two major types of real time schedulers.
First: Hard real time scheduler: the arrival of every job comes with a deadline and all the deadlines have to be met with all the programs. For example a program for the nuclear power plant cleanup will terminate in the next 10ms needs a hard real time scheduler. With the need for predictability, this tradeoff trumps performance.
Second: Soft real time scheduler: some deadlines can be missed at a cost. For example, lag from the media player playing a huge video have the soft real time scheduler implemented. Often this results in frame skips (cost) which is 'ok'. To implement this scheduler, we have the sooner deadline finish first. If the job(s) deadlines cannot be met, we discard those jobs and work on the next soonest job.
The common error in synchronization is when there are race conditions. The expression comes from race cars, and fast race cars take each own paths. When the paths of two race cars cross, then they crash and explode.
Coding Example: let's say we have a shared bank account: someone is depositing into the account, while someone is withdrawing money from the account: short sample code:
void deposit(unsigned int amt)
{
//check for overflow
balance += amt;
}
void withdraw(unsigned int amt)
{
//If we do not check ---->
if(amt <= balance)
//Then what happens?
{
balance -= amt;
return true;
}
else
return false;
}
}
In x86:
Deposit: Withdraw:
balance += amt; balance -= amt;
| three |
| instructions |
V V
ld balance, r2 ld balance, r2
add r2, r1, r2 sub r2, r1, r2
st r2, balance st r2, balance
Race Condition happened when:
| bankaccount: 10000 (pennies) -> | 1. B r2: 100.00 |
| scheduler switches to proc. A -> | 2. A r2: 100.00 |
| saved state of B and does A's -> | 3. A r2: 50.00 |
| calculation -> | 4. A balance 50.00 |
| A is finished, back to B -> | 5: B r2 110.00 |
| Does B's calculation -> | 6. B balance 110.00 |
End result? Food for free, while deposit of $10 worked.
Only the observable events meaning high level code count towards the implementation. If at the low level things get screwed up, we can later fix the program with high level checks. If we can explain the colliding results using events that do not collide and still have the same observable results, then we just need serialization.
Question: We can solve the above bank account problem using observability or serialization, but what about the harder cases? What if we also have a function that can transfer money from different account? Now any combination of two or three functions can cause race condition. How to solve this? We can use locks which may work for a small number, but what if we are doing audit and need to look at 10 accounts or more? Should we get locks on 10 or even 20 accounts? When solving the easy case we should keep in mind the hard case.
Partial Answers: