Linux - Process Scheduling
Chaptor 10: Process Scheduling
From book Understanding the Linux KernelBy Daniel P. Bovet & Marco Cesati
Comparison of IOS and General Purpose OS like Linux
IOS Features
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The whole Operating System runs as a single process and kernel mode.
Monolithic
No Virtual Memory
Everything Runs in RAM
Cooperative Multitasking
Process relinquishes CPU on its own by calling --
Scheduler - Multilevel Priority queues
Four priority queues - CRITICAL, HIGH, NORMAL, LOW
Static priorities - decided at the time of creation of the process.
Can be changed thru cli/function call.
CPU HOG Message --- Trace from timer interrupt.....
Quantum 2 ms
Watchdog 2 minutes
I wrote function to print Stack trace from a interrupt handler---------.
---> Made some changes in timers - AVL tree and Timer wheel
---> Timers --- Timer wheeels
What are the advantages/disadvantages of cooperative multitasking
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Process does not have to worry about critical sections.
All processes have to be responsible. One process caught in loop will hog the CPU.
Is Cisco IOS an RTOS? Not really. Its is not hard real time system. It has
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
No virtual memory
Priority based scheduling
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The whole Operating System runs as a single process and kernel mode.
Monolithic
No Virtual Memory
Everything Runs in RAM
Cooperative Multitasking
Process relinquishes CPU on its own by calling --
Scheduler - Multilevel Priority queues
Four priority queues - CRITICAL, HIGH, NORMAL, LOW
Static priorities - decided at the time of creation of the process.
Can be changed thru cli/function call.
CPU HOG Message --- Trace from timer interrupt.....
Quantum 2 ms
Watchdog 2 minutes
I wrote function to print Stack trace from a interrupt handler---------.
---> Made some changes in timers - AVL tree and Timer wheel
---> Timers --- Timer wheeels
What are the advantages/disadvantages of cooperative multitasking
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Process does not have to worry about critical sections.
All processes have to be responsible. One process caught in loop will hog the CPU.
Is Cisco IOS an RTOS? Not really. Its is not hard real time system. It has
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
No virtual memory
Priority based scheduling
Real Time Systems
Introduction
Characteristics of real time operating system
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Process scheduling - Priority based
Resource access control - Aim is to keep the duration of every priority inversion bounded from above.
Memory allocation/deallocation - Memory fragmentation may cause indeterminism. Use preallocated buffers.
Does real-time mean as fast as possible?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The term "real-time" does not mean "as fast as possible" but rather "real-time" demands consistent, repeatable, known timing performance.
Resource access control (Chapter 8 of book Real Time Systems by Jane W. S. Liu)
Nonpreemptive Critical Section (NPCS) Protocol
Priority-Inheritance Protocol
Basic Priority-Ceiling Protocol
Differences between priority-inheritance protocols and priority-ceiling protocol
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Priority-inheritance rule of these are essentially same
The priority-inheritance protocol does not prevent deadlock.
Priority-ceiling blocking is sometimes referred to as avoidance blocking - blocking caused by the priority ceiling rule is the cost for avoidance of deadlocks among jobs.
Priority-inheritance is greedy while later is not.
Few Terms/Concepts
Priority-inversion
Priority ceiling of a resource
Priority ceiling of a system
Books/Articles/Links
"Tutorial on Hard Real-Time Systems", edited by John A. Stankovic and Krithi Ramamritham, IEEE Computer Society reprint series, Computer Society order number 819
Basic Concepts of Real-Time Operating Systems
Comp.RealTime NewsGroup FAQ
http://www.faqs.org/faqs/realtime-computing/faq/
Books --
Characteristics of real time operating system
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Process scheduling - Priority based
Resource access control - Aim is to keep the duration of every priority inversion bounded from above.
Memory allocation/deallocation - Memory fragmentation may cause indeterminism. Use preallocated buffers.
Does real-time mean as fast as possible?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The term "real-time" does not mean "as fast as possible" but rather "real-time" demands consistent, repeatable, known timing performance.
Resource access control (Chapter 8 of book Real Time Systems by Jane W. S. Liu)
Nonpreemptive Critical Section (NPCS) Protocol
Priority-Inheritance Protocol
Basic Priority-Ceiling Protocol
Differences between priority-inheritance protocols and priority-ceiling protocol
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Priority-inheritance rule of these are essentially same
The priority-inheritance protocol does not prevent deadlock.
Priority-ceiling blocking is sometimes referred to as avoidance blocking - blocking caused by the priority ceiling rule is the cost for avoidance of deadlocks among jobs.
Priority-inheritance is greedy while later is not.
Few Terms/Concepts
Priority-inversion
Priority ceiling of a resource
Priority ceiling of a system
Books/Articles/Links
"Tutorial on Hard Real-Time Systems", edited by John A. Stankovic and Krithi Ramamritham, IEEE Computer Society reprint series, Computer Society order number 819
Basic Concepts of Real-Time Operating Systems
Comp.RealTime NewsGroup FAQ
http://www.faqs.org/faqs/realtime-computing/faq/
Books --
Puzzles
Puzzle #1
Three identical boxes, one containing two black marbles, one containing a black marble and a white marble, and a third containing two white marbles, are placed side by side on a table. Originally each box had a label on it describing its contents, but so meone has mixed up the labels so that each one is incorrect (i.e., no label is correct). The problem is to determine the contents of each box by a sampling process: choosing one box, blindly removing one marble from it, and repeating the process as m any times as it takes to positively infer the contents of each box. What sampling procedure would you use to identify the contents of each box with the fewest number of draws?
Puzzle #2
A commuter is in the habit of arriving at his suburban station each evening at exactly five o'clock. His chauffeur always meets the train and drives him home. One day he takes an earlier train, arriving at the station at four. The weather is pleasant, so instead of telephoning home he starts walking along the route always taken by his driver. They meet somewhere along the way. He gets into the car and they drive home, arriving at the house ten minutes earlier than usual. Assuming that the chauffeur always drives at a constant speed, and had left just in time to meet the five o'clock train, can you determine how long the commuter walked before he was picked up?
Puzzle #3
The following conversation took place in a home supply/hardware type store like Lowe's or National Home Center:
"How much will one cost?"
"Seventy five cents," replied the clerk.
"And how much will twelve cost?"
"A dollar fifty."
"Okay, I'll take nine hundred and twelve."
"That will be two dollars and twenty five cents."
What was the customer buying?
Puzzle #4
An explorer walks one mile due south, turns and walks one mile due east, then walks one mile due north and finds himself back where he started. He then shoots a bear. What color is the bear? The age-old answer is white because he must have started at t he North Pole. Is there anywhere else on earth where one could walk a mile south, a mile east, and a mile north and be back at the exact same spot? Explain.
Puzzle #5
A carpenter, working with a power saw, wishes to cut a wooden cube, three inches on a side, into 27 one-inch cubes. He can easily do this by making six cuts through the cube, keeping the pieces together in the cube shape. Can he reduce the number of nec essary cuts by rearranging the pieces after each cut? Explain.
Puzzle #6
A cylindrical hole exactly 6 inches long has been drilled straight through the center of a solid sphere. What is the volume remaining in the sphere?
Puzzle #7
You have ten stacks of coins, each consisting of ten half-dollars. One entire stack is counterfeit, but you do not know which one. You know the weight of a genuine half-dollar in grams and you know that each fake one weighs one gram more than it should. You may weigh the coins on a scale that reads in grams. What is the smallest number of weighings required to identify the counterfeit stack?
Puzzle #8
A young man lives in Manhattan near a subway express station. He has two girlfriends, one in Brooklyn and one in The Bronx. To visit the girl in Brooklyn he takes a train on the downtown side of the platform; to visit the girl in The Bronx he takes a t rain on the uptown side of the same platform. Since he likes both girls equally well, he simply takes the first train that comes along. In this way he lets chance determine which girl he visits. He reaches the subway platform at a random time each Satu rday afternoon. Brooklyn and Bronx trains arrive at the station equally often - every ten minutes. Yet for some obscure reason he finds himself going to Brooklyn nine times out of ten. Can you think of a good reason why the odds so heavily favor Brookl yn?
Puzzle #9
Needing to find a successor, and having four equally intelligent and capable advisors to choose from, the leader of a mythical country devised a test to pick the best one: the four were tightly blindfolded and seated around a table. The leader then said , "I will now place either a blue mark or a red mark on each of your foreheads. You will then remove your blindfolds, and each of you who sees more blue marks than red marks on your companions will stand up. The first person who can correctly name his o wn color and the reason will be the next leader." The leader then placed the marks, the blindfolds were removed, the candidates looked around, and all four stood up. For several minutes, each stood silent, thinking. Finally, one of them spoke: "I have a blue mark." He then successfully explained how he had figured it out. How were the candidates marked, and how did one of them determine the color of his mark?
Puzzle #10
A logician vacationing in the South Seas finds herself on an island inhabited by two groups of people. Members of one group always tell the truth and members of the other group always lie. She comes to a fork in the road knowing that one of the forks le ads to town and the other into the wilderness. There is a man standing by the fork who belongs to one of the two groups on the island, but the logician can't tell by looking at him to which group he belongs. The logician thinks for a moment, then asks o ne question only. From the reply she knows which road to take. What question does she ask?
Puzzle #11
On last New Year's Day a mathematician was puzzled by the strange way in which his small daughter began to count on the fingers of her left hand. She started by calling the thumb 1, the index finger 2, the middle finger 3, the ring finger 4, the little f inger 5, then she reversed direction, calling the ring finger 6, middle finger 7, first finger 8, thumb 9, then back to the index finger for 10, middle finger for 11, and so on. She continued to count back and forth in this peculiar manner until she reac hed a count of 20 on her ring finger. "What in the world are you doing?" her father asked. The girl stamped her foot. "Now you've made me forget where I was. I'll have to start all over again. I'm counting up to 1995 to see what finger I'll end on." The mathematician closed his eyes and made a simple mental calculation. "You'll end on your _______," he said. When the girl finished her count and found that her father was right, she was so impressed by the predictive power of mathematics that she decided to work twice as hard on her arithmetic lessons. How did the father arrive at his prediction and what finge r did he predict?
Puzzle #12
A pirate ship capable of 20 knots is sitting motionless on an infinite sea in the fog. Another ship carrying tons of gold and a weak unarmed crew is sitting exactly 10 nautical miles away on one of the 360 degree radials corresponding to the degrees on a compass. It is capable of only 10 knots and immediately sets out to escape by setting a course directly away from the pirate ship at top speed. The pirate ship knows what's happening, but can't see the other ship (knowing how far away it is when it sta rts running, but not where). Is there a course the pirate ship can sail that will guarantee interception of the gold ship? They must be close enough to touch because of the fog. If so, describe the course/strategy.
Puzzle #13
Variation on #12: A pirate ship capable of 20 knots is sitting motionless on an infinite sea in the fog. Another ship carrying tons of gold and a weak unarmed crew is sitting exactly 10 nautical miles away on one of the 360 deg ree radials corresponding to the degrees on a compass. It is capable of only 10 knots and immediately sets out to escape by setting a course directly away from the pirate ship at a random speed (the gold ship may speed up or slow down or even stop, but i t cannot deviate from it's course). The pirate ship knows what's happening, but can't see the other ship (knowing how far away it is when it starts running, but not where). Is there a course the pirate ship can sail that will guarantee interception of t he gold ship? They must be close enough to touch because of the fog. If so, describe the course/strategy.
Puzzle #14
Find the digits that the various letters in the following represent to make the calculations correct:
NINE - TEN = TWO; NINE - ONE = ALL.
(Each letter represents a unique single digit)
Puzzle #15
A particular phonograph record (remember those?) measures exactly 12 inches in diameter. The center of it that contains the hole and the label is 2.5 inches in diameter. Assuming the remainder of the record is grooved uniformly and there are exactly 29 grooves per centimeter measuring radially, how many total grooves are there on the record?
Puzzle #16
If a hole is drilled through the center of a sphere such that the height of the resulting cylindrically shaped hole is exactly 6 inches, what is the remaining volume of the sphere?
Three identical boxes, one containing two black marbles, one containing a black marble and a white marble, and a third containing two white marbles, are placed side by side on a table. Originally each box had a label on it describing its contents, but so meone has mixed up the labels so that each one is incorrect (i.e., no label is correct). The problem is to determine the contents of each box by a sampling process: choosing one box, blindly removing one marble from it, and repeating the process as m any times as it takes to positively infer the contents of each box. What sampling procedure would you use to identify the contents of each box with the fewest number of draws?
Puzzle #2
A commuter is in the habit of arriving at his suburban station each evening at exactly five o'clock. His chauffeur always meets the train and drives him home. One day he takes an earlier train, arriving at the station at four. The weather is pleasant, so instead of telephoning home he starts walking along the route always taken by his driver. They meet somewhere along the way. He gets into the car and they drive home, arriving at the house ten minutes earlier than usual. Assuming that the chauffeur always drives at a constant speed, and had left just in time to meet the five o'clock train, can you determine how long the commuter walked before he was picked up?
Puzzle #3
The following conversation took place in a home supply/hardware type store like Lowe's or National Home Center:
"How much will one cost?"
"Seventy five cents," replied the clerk.
"And how much will twelve cost?"
"A dollar fifty."
"Okay, I'll take nine hundred and twelve."
"That will be two dollars and twenty five cents."
What was the customer buying?
Puzzle #4
An explorer walks one mile due south, turns and walks one mile due east, then walks one mile due north and finds himself back where he started. He then shoots a bear. What color is the bear? The age-old answer is white because he must have started at t he North Pole. Is there anywhere else on earth where one could walk a mile south, a mile east, and a mile north and be back at the exact same spot? Explain.
Puzzle #5
A carpenter, working with a power saw, wishes to cut a wooden cube, three inches on a side, into 27 one-inch cubes. He can easily do this by making six cuts through the cube, keeping the pieces together in the cube shape. Can he reduce the number of nec essary cuts by rearranging the pieces after each cut? Explain.
Puzzle #6
A cylindrical hole exactly 6 inches long has been drilled straight through the center of a solid sphere. What is the volume remaining in the sphere?
Puzzle #7
You have ten stacks of coins, each consisting of ten half-dollars. One entire stack is counterfeit, but you do not know which one. You know the weight of a genuine half-dollar in grams and you know that each fake one weighs one gram more than it should. You may weigh the coins on a scale that reads in grams. What is the smallest number of weighings required to identify the counterfeit stack?
Puzzle #8
A young man lives in Manhattan near a subway express station. He has two girlfriends, one in Brooklyn and one in The Bronx. To visit the girl in Brooklyn he takes a train on the downtown side of the platform; to visit the girl in The Bronx he takes a t rain on the uptown side of the same platform. Since he likes both girls equally well, he simply takes the first train that comes along. In this way he lets chance determine which girl he visits. He reaches the subway platform at a random time each Satu rday afternoon. Brooklyn and Bronx trains arrive at the station equally often - every ten minutes. Yet for some obscure reason he finds himself going to Brooklyn nine times out of ten. Can you think of a good reason why the odds so heavily favor Brookl yn?
Puzzle #9
Needing to find a successor, and having four equally intelligent and capable advisors to choose from, the leader of a mythical country devised a test to pick the best one: the four were tightly blindfolded and seated around a table. The leader then said , "I will now place either a blue mark or a red mark on each of your foreheads. You will then remove your blindfolds, and each of you who sees more blue marks than red marks on your companions will stand up. The first person who can correctly name his o wn color and the reason will be the next leader." The leader then placed the marks, the blindfolds were removed, the candidates looked around, and all four stood up. For several minutes, each stood silent, thinking. Finally, one of them spoke: "I have a blue mark." He then successfully explained how he had figured it out. How were the candidates marked, and how did one of them determine the color of his mark?
Puzzle #10
A logician vacationing in the South Seas finds herself on an island inhabited by two groups of people. Members of one group always tell the truth and members of the other group always lie. She comes to a fork in the road knowing that one of the forks le ads to town and the other into the wilderness. There is a man standing by the fork who belongs to one of the two groups on the island, but the logician can't tell by looking at him to which group he belongs. The logician thinks for a moment, then asks o ne question only. From the reply she knows which road to take. What question does she ask?
Puzzle #11
On last New Year's Day a mathematician was puzzled by the strange way in which his small daughter began to count on the fingers of her left hand. She started by calling the thumb 1, the index finger 2, the middle finger 3, the ring finger 4, the little f inger 5, then she reversed direction, calling the ring finger 6, middle finger 7, first finger 8, thumb 9, then back to the index finger for 10, middle finger for 11, and so on. She continued to count back and forth in this peculiar manner until she reac hed a count of 20 on her ring finger. "What in the world are you doing?" her father asked. The girl stamped her foot. "Now you've made me forget where I was. I'll have to start all over again. I'm counting up to 1995 to see what finger I'll end on." The mathematician closed his eyes and made a simple mental calculation. "You'll end on your _______," he said. When the girl finished her count and found that her father was right, she was so impressed by the predictive power of mathematics that she decided to work twice as hard on her arithmetic lessons. How did the father arrive at his prediction and what finge r did he predict?
Puzzle #12
A pirate ship capable of 20 knots is sitting motionless on an infinite sea in the fog. Another ship carrying tons of gold and a weak unarmed crew is sitting exactly 10 nautical miles away on one of the 360 degree radials corresponding to the degrees on a compass. It is capable of only 10 knots and immediately sets out to escape by setting a course directly away from the pirate ship at top speed. The pirate ship knows what's happening, but can't see the other ship (knowing how far away it is when it sta rts running, but not where). Is there a course the pirate ship can sail that will guarantee interception of the gold ship? They must be close enough to touch because of the fog. If so, describe the course/strategy.
Puzzle #13
Variation on #12: A pirate ship capable of 20 knots is sitting motionless on an infinite sea in the fog. Another ship carrying tons of gold and a weak unarmed crew is sitting exactly 10 nautical miles away on one of the 360 deg ree radials corresponding to the degrees on a compass. It is capable of only 10 knots and immediately sets out to escape by setting a course directly away from the pirate ship at a random speed (the gold ship may speed up or slow down or even stop, but i t cannot deviate from it's course). The pirate ship knows what's happening, but can't see the other ship (knowing how far away it is when it starts running, but not where). Is there a course the pirate ship can sail that will guarantee interception of t he gold ship? They must be close enough to touch because of the fog. If so, describe the course/strategy.
Puzzle #14
Find the digits that the various letters in the following represent to make the calculations correct:
NINE - TEN = TWO; NINE - ONE = ALL.
(Each letter represents a unique single digit)
Puzzle #15
A particular phonograph record (remember those?) measures exactly 12 inches in diameter. The center of it that contains the hole and the label is 2.5 inches in diameter. Assuming the remainder of the record is grooved uniformly and there are exactly 29 grooves per centimeter measuring radially, how many total grooves are there on the record?
Puzzle #16
If a hole is drilled through the center of a sphere such that the height of the resulting cylindrically shaped hole is exactly 6 inches, what is the remaining volume of the sphere?
Unix/Linx bootupand login
-------------------------
Process 0 - swapper
Process 1 - init
getty - monitors terminal line
user login procedure
getty execs a login shell for the user
-------------------------
Process 0 - swapper
Process 1 - init
getty - monitors terminal line
user login procedure
getty execs a login shell for the user
-------------------------
GNU Linux pthreads
pthread_t (object)
pthread_attr_t (object) --- pthread_attr_init,pthread_attr_destroy
Thread’s detach state.A thread may be created as a joinable
thread (the default) or as a detached thread.
pthread_attr_setdetachstate
pthread_detach
Even if a thread is created in a joinable state, it may later be
turned into a detached thread.To do this, call pthread_detach.
Once a thread is detached, it cannot be made joinable again.
pthread_create
pthread_self
pthread_equal
pthread_exit
pthread_cancel --> PTHREAD_CANCELED
A canceled thread may later be joined; in fact, you should join
a canceled thread to free up its resources, unless the thread is
detached
asynchronously cancelable.
synchronously cancelable - cancellation points.The thread will
queue a cancellation request until it
reaches the next cancellation point.
uncancelable
pthread_setcanceltype
PTHREAD_CANCEL_ASYNCHRONOUS OR PTHREAD_CANCEL_DEFERRED
pthread_testcancel - direct way to create a cancellation point
- process a pending cancellation in a
synchronously cancelable thread.
pthread_key_t(object) --- pthread_key_create,pthread_setspecific,pthread_getspecific
thread-specific data area.
pthread_join
pthread_attr_t (object) --- pthread_attr_init,pthread_attr_destroy
Thread’s detach state.A thread may be created as a joinable
thread (the default) or as a detached thread.
pthread_attr_setdetachstate
pthread_detach
Even if a thread is created in a joinable state, it may later be
turned into a detached thread.To do this, call pthread_detach.
Once a thread is detached, it cannot be made joinable again.
pthread_create
pthread_self
pthread_equal
pthread_exit
pthread_cancel --> PTHREAD_CANCELED
A canceled thread may later be joined; in fact, you should join
a canceled thread to free up its resources, unless the thread is
detached
asynchronously cancelable.
synchronously cancelable - cancellation points.The thread will
queue a cancellation request until it
reaches the next cancellation point.
uncancelable
pthread_setcanceltype
PTHREAD_CANCEL_ASYNCHRONOUS OR PTHREAD_CANCEL_DEFERRED
pthread_testcancel - direct way to create a cancellation point
- process a pending cancellation in a
synchronously cancelable thread.
pthread_key_t(object) --- pthread_key_create,pthread_setspecific,pthread_getspecific
thread-specific data area.
pthread_join
How many processes will be created-- fork?
sandesh@nextfour:~/labs> cat fork.c
#include
#include
#include
int count;
main()
{
int i;
for(i=0;i<3;i++)
fork();
count++;
printf("Hello %d\n",count);
}
sandesh@nextfour:~/labs> gcc fork.c
sandesh@nextfour:~/labs> ./a.out
Hello 1
Hello 1
Hello 1
Hello 1
Hello 1
Hello 1
Hello 1
Hello 1
sandesh@nextfour:~/labs>
#include
#include
#include
int count;
main()
{
int i;
for(i=0;i<3;i++)
fork();
count++;
printf("Hello %d\n",count);
}
sandesh@nextfour:~/labs> gcc fork.c
sandesh@nextfour:~/labs> ./a.out
Hello 1
Hello 1
Hello 1
Hello 1
Hello 1
Hello 1
Hello 1
Hello 1
sandesh@nextfour:~/labs>
Linux time keeping - Timer interrupt, jiffies, xtime
Under Linux system time is measured in "ticks" since the system was stated up. One tick represents 10 milliseconds, so the timer interrupt is triggered 100 times per second. The timer ticks are stored in the variable -
unsigned long volatile jiffies
jiffies
~~~~~~~
Every time a timer interrupt occurs, the value of the variable is
increamented. jiffies is initialised to 0 when the system boots, and
is thus the number of clock ticks since the computer was tured on.
unsigned long volatile jiffies
jiffies
~~~~~~~
Every time a timer interrupt occurs, the value of the variable is
increamented. jiffies is initialised to 0 when the system boots, and
is thus the number of clock ticks since the computer was tured on.
Segmentation Fault and Bus Error
Segmentation Fault
Wikipedia Page : http://en.wikipedia.org/wiki/Segmentation_fault
A segmentation fault occurs when your program tries to access memory locations that haven't been allocated for the program's use. Here are some common errors that will cause this problem:
scanf("%d", number);
In this case, number is integer. scanf() expects you to pass it the address of the variable you want to read an integer into. But, the writer has fogotten to use the `&' before number to give scanf the address of the variable. If the value of number happened to be 3, scanf() would try to access memory location 3, which is not accessible by normal users. The correct way to access the address of number would be to place a `&' (ampersand) before number:
scanf("%d", &number);
Another common segmentation fault occurs when you try to access an array index which is out of range. Let's say you set up an array of integers:
int integers[80];
If, in your program, you try to use an index (the number within the brackets) over 79, you will ``step out of your memory bounds'', which causes a segmentation fault. To correct this, rethink your array bounds or the code that is using the array.
Bus Error
Wikipedia Page : http://en.wikipedia.org/wiki/Bus_error
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
A SIGBUS is often caused by accessing data at an address that is not aligned to
a multiple of the width of the data. A 4 byte int must be aligned on a multiple
of 4. An 8 byte long must be aligned on a multiple of 8.
(processor) bus error - A fatal failure in the execution of a machine language
instruction resulting from the processor detecting an anomalous condition on its
bus. Such conditions include invalid address alignment (accessing a multi-byte
number at an odd address), accessing a physical address that does not correspond
to any device, or some other device-specific hardware error. A bus error
triggers a processor-level exception which Unix translates into a "SIGBUS"
signal which, if not caught, will terminate the current process.
From Cisco documentation
The system encounters a bus error when the processor tries to access a memory
location that either does not exist (a software error) or does not respond
properly (a hardware problem).
What is the difference between a Bus Error and a Segmentation Error?
Full Article:
Both are addressing errors, such as trying to address memory outside of your
legal address space. A segmentation error is detected by the kernel, while a
bus error is detected by the hardware.
These errors will occur when the program tries to access a memory location
outside its address space. That is, accessing uninitilized pointers, or even
mangled pointers (ones which have no reference or have been deleted).
The Bus error means that the kernel did not detecet the problem on its own;
the memory system realized the error.
Wikipedia Page : http://en.wikipedia.org/wiki/Segmentation_fault
A segmentation fault occurs when your program tries to access memory locations that haven't been allocated for the program's use. Here are some common errors that will cause this problem:
scanf("%d", number);
In this case, number is integer. scanf() expects you to pass it the address of the variable you want to read an integer into. But, the writer has fogotten to use the `&' before number to give scanf the address of the variable. If the value of number happened to be 3, scanf() would try to access memory location 3, which is not accessible by normal users. The correct way to access the address of number would be to place a `&' (ampersand) before number:
scanf("%d", &number);
Another common segmentation fault occurs when you try to access an array index which is out of range. Let's say you set up an array of integers:
int integers[80];
If, in your program, you try to use an index (the number within the brackets) over 79, you will ``step out of your memory bounds'', which causes a segmentation fault. To correct this, rethink your array bounds or the code that is using the array.
Bus Error
Wikipedia Page : http://en.wikipedia.org/wiki/Bus_error
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
A SIGBUS is often caused by accessing data at an address that is not aligned to
a multiple of the width of the data. A 4 byte int must be aligned on a multiple
of 4. An 8 byte long must be aligned on a multiple of 8.
(processor) bus error - A fatal failure in the execution of a machine language
instruction resulting from the processor detecting an anomalous condition on its
bus. Such conditions include invalid address alignment (accessing a multi-byte
number at an odd address), accessing a physical address that does not correspond
to any device, or some other device-specific hardware error. A bus error
triggers a processor-level exception which Unix translates into a "SIGBUS"
signal which, if not caught, will terminate the current process.
From Cisco documentation
The system encounters a bus error when the processor tries to access a memory
location that either does not exist (a software error) or does not respond
properly (a hardware problem).
What is the difference between a Bus Error and a Segmentation Error?
Full Article:
Both are addressing errors, such as trying to address memory outside of your
legal address space. A segmentation error is detected by the kernel, while a
bus error is detected by the hardware.
These errors will occur when the program tries to access a memory location
outside its address space. That is, accessing uninitilized pointers, or even
mangled pointers (ones which have no reference or have been deleted).
The Bus error means that the kernel did not detecet the problem on its own;
the memory system realized the error.
Semaphore, Mutex, Conditional variable, Spin lock
Difference between mutex and semaphore
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
A mutex has two possible states: unlocked (not owned by any thread), and locked (owned by one thread). A mutex can never be owned by two different threads simultaneously. A thread attempting to lock a mutex that is already locked by another thread is suspended until the owning thread unlocks the mutex first.
Example -
A shared global variable x can be protected by a mutex as follows:
int x;
pthread_mutex_t mut = PTHREAD_MUTEX_INITIALIZER;
All accesses and modifications to x should be bracketed by calls to pthread_mutex_lock and pthread_mutex_unlock as follows:
pthread_mutex_lock(&mut);
/* operate on x */
pthread_mutex_unlock(&mut);
TBD
Is it possible to implement semaphores without special machine instructions(compare and swap instruction(IBM 370) or atomic read
and clear instruction(AT &T 3B20))?
YES - Bach Chapter 12 Multiprocessor Systems
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
A mutex has two possible states: unlocked (not owned by any thread), and locked (owned by one thread). A mutex can never be owned by two different threads simultaneously. A thread attempting to lock a mutex that is already locked by another thread is suspended until the owning thread unlocks the mutex first.
Example -
A shared global variable x can be protected by a mutex as follows:
int x;
pthread_mutex_t mut = PTHREAD_MUTEX_INITIALIZER;
All accesses and modifications to x should be bracketed by calls to pthread_mutex_lock and pthread_mutex_unlock as follows:
pthread_mutex_lock(&mut);
/* operate on x */
pthread_mutex_unlock(&mut);
TBD
Is it possible to implement semaphores without special machine instructions(compare and swap instruction(IBM 370) or atomic read
and clear instruction(AT &T 3B20))?
YES - Bach Chapter 12 Multiprocessor Systems
Big Endian versus Little Endian
Big-endian means that the most significant byte is stored at the lowest memory address
0x12345678
(low address--->high address)
Read Wikipedia Page: http://en.wikipedia.org/wiki/Endianness
C program to find out whether a machine is big endian or little endian
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Is endian-ness bit level /byte-level/word-level?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
On a byte addressed machine it is byte level.
Examples of CPU Architectures
~~~~~~~~~~~~~~~~~~~~~~~
x86 processors use the little-endian format (sometimes called the Intel format).
Motorola processors have generally used big-endian. PowerPC (which includes Apple's Macintosh line prior to the Intel switch) and System/370 also adopt big-endian. SPARC historically used big-endian, though version 9 is bi-endian
Why different processor architectures choose different endian-ness? Is there any advantage of one over other?
0x12345678
(low address--->high address)
Read Wikipedia Page: http://en.wikipedia.org/wiki/Endianness
C program to find out whether a machine is big endian or little endian
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include
main () {
int i = 0x12345678;
if (*(char *)&i == 0x12)
printf ("Big endian\n");
else if (*(char *)&i == 0x78)
printf ("Little endian\n");
}
Is endian-ness bit level /byte-level/word-level?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
On a byte addressed machine it is byte level.
Examples of CPU Architectures
~~~~~~~~~~~~~~~~~~~~~~~
x86 processors use the little-endian format (sometimes called the Intel format).
Motorola processors have generally used big-endian. PowerPC (which includes Apple's Macintosh line prior to the Intel switch) and System/370 also adopt big-endian. SPARC historically used big-endian, though version 9 is bi-endian
Why different processor architectures choose different endian-ness? Is there any advantage of one over other?
Salient points about Unix/Linux
- Time sharing system
- Each user file is simply a sequence of bytes.
- Disk files and I/O devices are treated as similarly as possible.
- CPU scheduling is simple priority algorithm.
- For unix development intent was to have the kernel and libraries provide a small set of facilities that was sufficiently powerful to allow a person to build a more complex system if one were needed.
- -----------
- The kernel is not a separate set of processes that run in parallel to user processes, but is part of each user process.
- The kernel permanently resides in main memory as does the currently executing process (or part of it at least).
- Interrupt handler runs in the context of currently running process.
- All system calls return -1 on failure.
- When a process executes a system call, the execution mode of the process changes from user mode to kernel mode.
- .
- Every process except process 0 is created when another process executes the fork system call. Process 0 is a special process that is created bby hand when the system boots. After forking a child process (Process 1), process 0 becomes a swapper process. Process 1, known as init, is the ancestor of every other process.
- .
- .
- -----------------
- Kernel cannot preempt a process and switch context to another process while executing in kernel mode
- Kernel masks out interrupts when executing a critical region of code if an interrupt handler could corrupt kernel data structures.
- ..
Linux Terms/Concepts
Bottom Halves
Exceptions, traps, interrupts and signals
Exceptions
- Unexpected events causes by a process (internal source) such as addressing illegal memory, executing privileged instructions, dividing by zero
- Synchronous
- Exceptions happen in the middle of the execution of an instruction, and the system attempts to restart the instruction after handling the exception.
Interrupts
- Interrupts the CPU asynchronously
- I/O peripherals and system clock (from external sources) generated interrupts.
- Interrupts are considered to happen between the execution of two instructions, and the system continues with the next instruction after servicing the interrupt.
Signals
SIGINT - Stop Command before completion
SIGQUIT - Stops the currently executing program and dumps its current memory image to file name core in the current directory
SIGILL - Produced by illegal instruction
SIGSEGV - Attempt to address memory outside of the legal virtual memory space of process.
SIGKILL - Kill Signal (kill -9)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
17. Interrupts and Exceptions
"(with interrupts) the processor doesn't waste its time looking for
work - when there is something to be done, the work comes looking
for the processor."
- Peter Norton
INTERRUPTS AND EXCEPTIONS
Interrupts and exceptions both alter the program flow. The difference
between the two is that interrupts are used to handle external events
(serial ports, keyboard) and exceptions are used to handle instruction
faults, (division by zero, undefined opcode).
Interrupts are handled by the processor after finishing the current
instruction. If it finds a signal on its interrupt pin, it will look up
the address of the interrupt handler in the interrupt table and pass
that routine control. After returning from the interrupt handler
routine, it will resume program execution at the instruction after the
interrupted instruction.
Exceptions on the other hand are divided into three kinds. These are
Faults, Traps and Aborts. Faults are detected and serviced by the
processor before the faulting instructions. Traps are serviced after
the instruction causing the trap. User defined interrupts go into this
category and can be said to be traps; this includes the MS-DOS INT 21h
software interrupt, for example. Aborts are used only to signal severe
system problems, when operation is no longer possible.
See the below table for information on interrupt assignments in the
Intel 386, 486 SX/DX processors, and the Pentium processor. Type
specifies the type of exception.
------------------------------
Vector number Description
------------------------------
0 Divide Error (Division by zero)
1 Debug Interrupt (Single step)
2 NMI Interrupt
3 Breakpoint
4 Interrupt on overflow
5 BOUND range exceeded
6 Invalid Opcode
7 Device not available (1)
8 Double fault
9 Not used in DX models and Pentium (2)
10 Invalid TSS
11 Segment not present
12 Stack exception
13 General protection fault
14 Page fault
15 Reserved
16 Floating point exception (3)
17 Alignment check (4)
18 – 31 Reserved on 3/486, See (5) for Pentium
32 – 255 Maskable, user defined interrupts
------------------------------
(1) Exception 7 is used to signal that a floating point processor is
not present in the SX model. Exception 7 is used for programs
and OSs that have floating point emulation. In addition, the DX
chips can be set to trap floating point instructions by setting
bit 2 of CR0.
(2) Exception 9 is Reserved in the DX models and the Pentium, and is
only used in the 3/486 SX models to signal Coprocessor segment
overrun. This will cause an Abort type exception on the SX.
(3) In the SX models this exception is called 'Coprocessor error'.
(4) Alignment check is only defined in 486 and Pentiums. Reserved
on any other Intel processor.
(5) For Pentiums Exception 18 is used to signal what is called an
'Machine check exception'.
The other interrupts, (32-255) are user defined. They differ in use
from one OS to another.
For a list of MS-DOS interrupts, see 'Obtaining HELPPC' (Subject #6) or
Ralf Browns Interrupt List (Subject #11)
Contributor: Patrik Ohman, patrik@astrakan.hgs.se
Last changed: 10 Jan 95
CPU Scheduling -- Different types of CPU scheduling algorithms
Scheduling Criteria -
CPU Utilization:
Throughput: Measure of work done. Number of processes that are completed pe time unit.
Turnaround time: The interval from the time of submission of a process to the time of completion. Turnaround time is sum of the periods spent waiting to get into memory, waiting in the ready queue, executing on the CPU and doing I/O.
Waiting time: Waiting time is the sum of the periods spend waiting in the ready queue.
Response time: Time from submission of a request until the first response is produced. Good measure for interactive systems.
Scheduling Algorithms:
FCFS (First-Come First Served)
Shortest Job First
Priority Scheduling
Round-Robin Scheduling
Multilevel Queue Scheling
Multilevel Feedback Queue Scheduling
Real Time Scheduling -
Hard Real Time Systems
Soft Real Time System
Priority Inversion
Priority-Inheritance Protocol
CPU Utilization:
Throughput: Measure of work done. Number of processes that are completed pe time unit.
Turnaround time: The interval from the time of submission of a process to the time of completion. Turnaround time is sum of the periods spent waiting to get into memory, waiting in the ready queue, executing on the CPU and doing I/O.
Waiting time: Waiting time is the sum of the periods spend waiting in the ready queue.
Response time: Time from submission of a request until the first response is produced. Good measure for interactive systems.
Scheduling Algorithms:
FCFS (First-Come First Served)
Shortest Job First
Priority Scheduling
Round-Robin Scheduling
Multilevel Queue Scheling
Multilevel Feedback Queue Scheduling
Real Time Scheduling -
Hard Real Time Systems
Soft Real Time System
Priority Inversion
Priority-Inheritance Protocol
fork, vfork, copy-on-write and clone
From man page of fork in linux
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fork creates a child process that differs from the parent process only in its PID and PPID, and in the fact that resource utilizations are set to 0. File locks and pending signals are not inherited.
Under Linux, fork is implemented using copy-on-write pages, so the only penalty incurred by fork is the time and memory required to duplicate the parent's page tables, and to create a unique task structure for the child.
RETURN VALUE
On success, the PID of the child process is returned in the parent's thread of execution, and a 0 is returned in the child's thread of execution.
On failure, a -1 will be returned in the parent's context, no child process will be created, and errno will be set appropriately.
ERRORS
EAGAIN fork cannot allocate sufficient memory to copy the parent's page tables and allocate a task structure for the child.
ENOMEM fork failed to allocate the necessary kernel structures because memory is tight.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fork creates a child process that differs from the parent process only in its PID and PPID, and in the fact that resource utilizations are set to 0. File locks and pending signals are not inherited.
Under Linux, fork is implemented using copy-on-write pages, so the only penalty incurred by fork is the time and memory required to duplicate the parent's page tables, and to create a unique task structure for the child.
RETURN VALUE
On success, the PID of the child process is returned in the parent's thread of execution, and a 0 is returned in the child's thread of execution.
On failure, a -1 will be returned in the parent's context, no child process will be created, and errno will be set appropriately.
ERRORS
EAGAIN fork cannot allocate sufficient memory to copy the parent's page tables and allocate a task structure for the child.
ENOMEM fork failed to allocate the necessary kernel structures because memory is tight.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Inter-process communication
Signals -
Power point slide of this picture: pipe.ppt
FIFOs (Named pipes) - created by open() or mknod
File locking
System V IPC (which works on most unix flavours)
Spin Locks
Read Write Locks
Memory Mapped Files
Unix Sockets
- Signals inform processes of the occurrences of asynchcronous events.
- Process may send each other signal with the kill system call, or the kernel may send signals internally.
- 19 Signals are there in system V
- Only related processes, descendents ofa process that issued the pipe call, can share access to unnamed pipes.
Power point slide of this picture: pipe.ppt
FIFOs (Named pipes) - created by open() or mknod
- All processes can access a named pipe regardless of their relationship.
File locking
System V IPC (which works on most unix flavours)
- Message Queues:
- Semaphores:
- Shared Memory: Process share parts of their virtual address space. Processes read and write shared memory using the same machine instructions they use to read write regular memory. After attaching shared memory, it becomes part of the virtual address space of process, accessible in the same way other virtual addresses are.
Spin Locks
Read Write Locks
Memory Mapped Files
Unix Sockets
Subscribe to:
Posts (Atom)