A garbage collector is a dynamic storage allocator that automatically frees allocated blocks that are no longer needed by the program. Such blocks are known as garbage and hence the term garbage collector. The process of automatically reclaiming heap storage is known as garbage collection.
A garbage collector views memory as a directed reachability graph. The nodes of the graph are partitioned into a set of root nodes and a set of heap nodes. Each heap node corresponds to an allocated block in the heap. Root nodes correspond to locations not in the heap that contain pointers into the heap. Those locations can be registers, variables on the stack, or global variables in the read-write data area of virtual memory. The role of a garbage collector is to maintain some representation of the reachability graph and periodically reclaim the unreachable nodes by freeing them and returning them to the free list.
Mark & Sweep algorithm (by McCarthy): A Mark&Sweep Garbage Collector consists of a mark phase, which marks all reachable and allocated descendants of the root nodes, followed by a sweep phase, which frees each unmarked allocated block by iterating over each block in the heap and freeing any unmarked allocated blocks that it encounters.
Sunday, November 25, 2007
Wednesday, November 21, 2007
Dynamic memory allocation
Computer Systems
10.9.5 Implementation issues
A practical allocator that strikes a better balance between throughput and utilization must consider the following issues:
Any practical allocator needs some data structure that allows it to distinguish block boundaries and to distinguish between allocated and free blocks. Most allocators embed this information in the block themselves. An example is as follow.
A block consists of a one-word (4 bytes) header, the payload, and possibly some additional padding. The header encodes the block size as well as whether the block is allocated or free. If we impose a double-word alignment constraint, then the block size is always a multiple of eight and the three low-order bits of the block size are always zero.
This organization is called implicit free list because the free blocks are linked implicitly by the size fields in the headers. The allocator can indirectly traverse the entire set of free blocks by traversing all of the blocks in the heap. We also need some kind of specially marked end block. The advantage of an implicit free list is simplicity. A significant disadvantage is the cost of any operation, such as placing allocated blocks, requires a search of the free list will be linear in the total number of allocated and free blocks in the heap.
10.9.7 Placing Allocated Blocks
Three common placement policies are: first fit, next fit and best fit. All of them have advantages and disadvantages.
10.9.8 Splitting Free Blocks
If the fit is not good, then the allocator will usually opt to split the free block into two parts. The first part becomes the allocated block, and the remainder becomes a new free block.
10.9.9 Getting Additional Heap Memory
If the allocator is unable to find a fit for the requested block, it will ask the kernel for additional memory, either by calling the mmap or sbrk functions.
10.9.10 Coalescing Free Blocks
There are free blocks adjacent to the newly freed block, which is known as false fragmentation. Coalescing comes in to rescue this phenomenon by merge adjacent free blocks. When to perform such operations??? Immediate coalescing Vs Defer coalescing. The former could introduce a form of thrashing, where a block is repeatedly coalesced and then split soon thereafter.. Fast allocators often opt for some form of deferred coalescing.
10.9.11 Coalescing with Boundary Tags
Coalescing the next free block is straightforward and efficient. How would we coalesce the previous block? Knuth developed boundary tags, which allows for constant-time coalescing of the previous block. The idea is to add a footer (the boundary tag) at the end of each block, where the footer is a replica of the header. If each block includes such a footer, then the allocator can determine the starting location and status of the previous block by inspecting its footer, which is always one word away from the start of the current block.
10.9.14 Segregated Free Lists (A popular choice with production-quality allocators such as GNU malloc)
Segregated storage: maintain multiple free lists, where each list holds blocks that are roughly the same size. Two basic approaches: simple segregated storage and segregated fits.
Simple segregated storage: the free list for each size class contains same-sized blocks, each the size of the largest element of the size class.
Segregated Fits: Each list contains potentially different-sized blocks whose sizes are members of the size class.
10.9.5 Implementation issues
A practical allocator that strikes a better balance between throughput and utilization must consider the following issues:
- Free block organization: how do we keep track of free blocks?
- Placement: How do we choose an appropriate free block in which to place a newly allocated block?
- Splitting: After we place a newly allocated block in some free block, what do we do with the remainder of the free block?
- Coalescing: What do we do with a block that has just been freed?
Any practical allocator needs some data structure that allows it to distinguish block boundaries and to distinguish between allocated and free blocks. Most allocators embed this information in the block themselves. An example is as follow.
A block consists of a one-word (4 bytes) header, the payload, and possibly some additional padding. The header encodes the block size as well as whether the block is allocated or free. If we impose a double-word alignment constraint, then the block size is always a multiple of eight and the three low-order bits of the block size are always zero.
This organization is called implicit free list because the free blocks are linked implicitly by the size fields in the headers. The allocator can indirectly traverse the entire set of free blocks by traversing all of the blocks in the heap. We also need some kind of specially marked end block. The advantage of an implicit free list is simplicity. A significant disadvantage is the cost of any operation, such as placing allocated blocks, requires a search of the free list will be linear in the total number of allocated and free blocks in the heap.
10.9.7 Placing Allocated Blocks
Three common placement policies are: first fit, next fit and best fit. All of them have advantages and disadvantages.
10.9.8 Splitting Free Blocks
If the fit is not good, then the allocator will usually opt to split the free block into two parts. The first part becomes the allocated block, and the remainder becomes a new free block.
10.9.9 Getting Additional Heap Memory
If the allocator is unable to find a fit for the requested block, it will ask the kernel for additional memory, either by calling the mmap or sbrk functions.
10.9.10 Coalescing Free Blocks
There are free blocks adjacent to the newly freed block, which is known as false fragmentation. Coalescing comes in to rescue this phenomenon by merge adjacent free blocks. When to perform such operations??? Immediate coalescing Vs Defer coalescing. The former could introduce a form of thrashing, where a block is repeatedly coalesced and then split soon thereafter.. Fast allocators often opt for some form of deferred coalescing.
10.9.11 Coalescing with Boundary Tags
Coalescing the next free block is straightforward and efficient. How would we coalesce the previous block? Knuth developed boundary tags, which allows for constant-time coalescing of the previous block. The idea is to add a footer (the boundary tag) at the end of each block, where the footer is a replica of the header. If each block includes such a footer, then the allocator can determine the starting location and status of the previous block by inspecting its footer, which is always one word away from the start of the current block.
10.9.14 Segregated Free Lists (A popular choice with production-quality allocators such as GNU malloc)
Segregated storage: maintain multiple free lists, where each list holds blocks that are roughly the same size. Two basic approaches: simple segregated storage and segregated fits.
Simple segregated storage: the free list for each size class contains same-sized blocks, each the size of the largest element of the size class.
Segregated Fits: Each list contains potentially different-sized blocks whose sizes are members of the size class.
Saturday, November 17, 2007
Thursday, November 15, 2007
Concurent Programming with Threads
Each thread associated with a process has its own stack, registers, condition codes, stack pointer, program counter and thread ID (TID). A thread context switch is faster than a process context switch.
Reaping Terminated Threads
pthread_join (pthread_t tid, void **thread_return);
The pthread_join function blocks until thread tid terminates and then reaps any memory resources held by the terminated thread.
Joinable Vs Detached Thread
A thread is either joinable or detached. A joinable thread can be reaped and killed by other threads. Its memory resources are NOT freed until it is reaped by another thread. A detached thread cannot be reaped or killed by other threads. Its memory resources are freed automatically by the system when it terminates. By default, threads are created joinable. Threads can detach themselves by call pthread_detach(pthread_self()).
Protecting Shared Variables with Semaphores
A semaphore, s, is a global variable with a nonnegative values can only be manipulated by two special operations, called P (to test) and V (increment):
Signaling with Semaphores
A classic example is producer-consumer interaction, which is common in real systems. For the producer-consumer interaction, we typically need two semaphores, called full and empty.
Producer:
P(empty);
write buffer;
V(full)
Consumer:
P(full)
read buffer;
V(empty)
-------------------------------------------------------------
Synchronizing Threads with Mutex and Condition Variables
Mutex is used to protect sharing and like a binary semaphore. And condition variables are used for signaling. To understand condition variables, we will take pthread as an example.
pthread_cond_init(pthread_cond_t * cond, pthread_condattr_t *attr);
pthread_cond_wait(pthread_cond_t * cond, pthread_mutex_t *mutex);
pthread_cond_signal(pthread_cond_t * cond);
Pthreads require that a mutex variable be associated with the condition variable cond, and that a call to pthread_cond_wait must always be protected by that mutex:
pthread_mutex_lock(&mutex);
pthread_cond_wait(&cond, &mutex);
pthread_mutex_unlock(&mutex);
some thread later indicates that the condition associated with cond has become true by making a call pthread_cond_signal(&cond), which wakes up exactly one of the waiting threads.
Reentrant Functions: DO NOT reference any shared data when they are called by multiple threads and thus they require no synchronization operations.
Other synchronization errors
Races: A race occurs when the correctness of a program depends on one thread reaching point x in its control flow before another thread reaches point y. A golden rule is that threaded programs must work correctly for any feasible trajectory in the progress graph.
Deadlock: a collection of threads are blocked, waiting for a condition that will never be true.
Reaping Terminated Threads
pthread_join (pthread_t tid, void **thread_return);
The pthread_join function blocks until thread tid terminates and then reaps any memory resources held by the terminated thread.
Joinable Vs Detached Thread
A thread is either joinable or detached. A joinable thread can be reaped and killed by other threads. Its memory resources are NOT freed until it is reaped by another thread. A detached thread cannot be reaped or killed by other threads. Its memory resources are freed automatically by the system when it terminates. By default, threads are created joinable. Threads can detach themselves by call pthread_detach(pthread_self()).
Protecting Shared Variables with Semaphores
A semaphore, s, is a global variable with a nonnegative values can only be manipulated by two special operations, called P (to test) and V (increment):
- P(s): while (s <= 0) ; s-- ;
- V(s): s++;
Signaling with Semaphores
A classic example is producer-consumer interaction, which is common in real systems. For the producer-consumer interaction, we typically need two semaphores, called full and empty.
Producer:
P(empty);
write buffer;
V(full)
Consumer:
P(full)
read buffer;
V(empty)
-------------------------------------------------------------
Synchronizing Threads with Mutex and Condition Variables
Mutex is used to protect sharing and like a binary semaphore. And condition variables are used for signaling. To understand condition variables, we will take pthread as an example.
pthread_cond_init(pthread_cond_t * cond, pthread_condattr_t *attr);
pthread_cond_wait(pthread_cond_t * cond, pthread_mutex_t *mutex);
pthread_cond_signal(pthread_cond_t * cond);
Pthreads require that a mutex variable be associated with the condition variable cond, and that a call to pthread_cond_wait must always be protected by that mutex:
pthread_mutex_lock(&mutex);
pthread_cond_wait(&cond, &mutex);
pthread_mutex_unlock(&mutex);
some thread later indicates that the condition associated with cond has become true by making a call pthread_cond_signal(&cond), which wakes up exactly one of the waiting threads.
Reentrant Functions: DO NOT reference any shared data when they are called by multiple threads and thus they require no synchronization operations.
Other synchronization errors
Races: A race occurs when the correctness of a program depends on one thread reaching point x in its control flow before another thread reaches point y. A golden rule is that threaded programs must work correctly for any feasible trajectory in the progress graph.
Deadlock: a collection of threads are blocked, waiting for a condition that will never be true.
Wednesday, November 14, 2007
TCP/IP
TCP Protocol runs only in the end systems and not in the intermediate network elements, the intermediate network elements do not maintain TCP connection state. A TCP connection is also always point-to-point, between a single sender and a single receiver.
Three-way handshake connection-establishment procedure: the client first sends a special TCP segment, the server responds with a second special TCP segment, and finally the client responds again with a third special segment. The first two segments carry no payload, that is, no application data; the third of these segments may carry a payload.
TCP segment structures: 1) source port # 2) dest port # 3) sequence number 4) acknowledge number 5) receive window 6)checksum 7)Sign bits: ack urg, psh,rst,syn, fin8) header length 9)options 10)data 11)urgent data pointer
Sequence numbers: TCP views data as an unstructured, but ordered, stream of bytes. Sequence number for a segment is therefore the byte-stream number of the first byte in the segment.
Acknowledge numbers: The acknowledgment number that Host A puts in its segment is the sequence number of the next byte Host A is expecting from Host B. Because TCP only acknowledges bytes up to the first missing byte in the stream, TCP is said to provide cumulative acknowledgments.
TCP Congestion Control: TCP congestion-control mechanism has each side of a connection keep track of an additional variable, the congestion window, which imposes a constraint on the rate at which a TCP sender can send traffic into the network. 1) additive-increase, multiplicative-decrease 2) Slow start, the TCP sender begins by transmitting at a slow rate(hence the term slow start), but increases its sending rate exponentially. 3) reaction to timeout events. After a timeout event, a TCP sender enters a slow-start phase. TCP manages a variable called Threshold, which determines the window size at which slow start will end and congestion avoidance will begin. The canceling of the slow-start phase after a triple duplicate ACK is called fast recovery.
Three-way handshake connection-establishment procedure: the client first sends a special TCP segment, the server responds with a second special TCP segment, and finally the client responds again with a third special segment. The first two segments carry no payload, that is, no application data; the third of these segments may carry a payload.
TCP segment structures: 1) source port # 2) dest port # 3) sequence number 4) acknowledge number 5) receive window 6)checksum 7)Sign bits: ack urg, psh,rst,syn, fin8) header length 9)options 10)data 11)urgent data pointer
Sequence numbers: TCP views data as an unstructured, but ordered, stream of bytes. Sequence number for a segment is therefore the byte-stream number of the first byte in the segment.
Acknowledge numbers: The acknowledgment number that Host A puts in its segment is the sequence number of the next byte Host A is expecting from Host B. Because TCP only acknowledges bytes up to the first missing byte in the stream, TCP is said to provide cumulative acknowledgments.
TCP Congestion Control: TCP congestion-control mechanism has each side of a connection keep track of an additional variable, the congestion window, which imposes a constraint on the rate at which a TCP sender can send traffic into the network. 1) additive-increase, multiplicative-decrease 2) Slow start, the TCP sender begins by transmitting at a slow rate(hence the term slow start), but increases its sending rate exponentially. 3) reaction to timeout events. After a timeout event, a TCP sender enters a slow-start phase. TCP manages a variable called Threshold, which determines the window size at which slow start will end and congestion avoidance will begin. The canceling of the slow-start phase after a triple duplicate ACK is called fast recovery.
Sunday, November 11, 2007
Subscribe to:
Posts (Atom)