What is claimed is:
1. A method for managing computer memory comprising the steps of:
maintaining multiple sets of free blocks of memory wherein free blocks are added to sets based on size of the free blocks;
in response to a request for a free block of a request size exceeding a first threshold, searching a set for a free block which is at least as large as the request size but smaller than the request size plus a second threshold; and
if the free block is found, allocating the free block in its entirety.
2. The method as recited in claim 1, wherein the step of maintaining multiple sets of free blocks includes the steps of maintaining the multiple sets of free blocks on a disk.
3. The method as recited in claim 1, wherein the step of maintaining multiple sets of free blocks includes the steps of maintaining the multiple sets of free blocks in main memory.
4. The method as recited in claim 1, further comprising the steps of:
if the free block is not found but at least one block at least as large as the request size is found, splitting the at least one block at least as large as the request size; and
satisfying the request with a second block resulting from the splitting step.
5. The method as recited in claim 4, wherein the at least one block being split is a smallest found block larger than the request size.
6. The method as recited in claim 1, wherein the multiple sets include a set of largest blocks and the first threshold is larger than or equal to a smallest permitted block size for the set of largest blocks and further comprising the step of searching the set of largest blocks to satisfy the request.
7. The method as recited in claim 1, wherein the step of searching includes the step of searching the set which includes a list, the list including memory block allocation information for the set.
8. The method as recited in claim 1, further comprising the step of dynamically adjusting at least one of the first and the second thresholds to tune performance.
9. The method as recited in claim 1, further comprising the steps of:
maintaining a contiguous block of memory;
selecting the set of free blocks based on the request size;
in response to the set of free blocks being non-empty, allocating at least part of a first block located in the set; and
in response to the set being empty, satisfying the request from the contiguous block of memory.
10. The method as recited in claim 9, further comprising the steps of:
maintaining a pointer to the contiguous block for a first pointer location;
in response to a request for storage of a given size,
incrementing the pointer by the given size to point to a second pointer location; and
satisfying the request using a part of the contiguous block beginning at the first pointer location.
11. The method as recited in claim 1, further comprising the step of deallocating an allocated block to a new set of free blocks based on the size of the allocated block.
12. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for managing computer memory, the method steps comprising:
maintaining multiple sets of free blocks of memory wherein free blocks are added to sets based on size;
in response to a request for a free block of a request size exceeding a first threshold, searching a set for a free block which is at least as large as the request size but smaller than the request size plus a second threshold; and
if the free block is found, allocating the free block in its entirety.
13. The program storage device as recited in claim 12, wherein the step of maintaining multiple sets of free blocks includes the steps of maintaining the multiple sets of free blocks on a disk.
14. The program storage device as recited in claim 12, wherein the step of maintaining multiple sets of free blocks includes the steps of maintaining the multiple sets of free blocks in main memory.
15. The program storage device as recited in claim 12, further comprising the steps of:
if the free block is not found but at least one block at least as large as the request size is found, splitting the at least one block at least as large as the request size; and
satisfying the request with a second block resulting from the splitting step.
16. The program storage device as recited in claim 15, wherein the at least one block being split is a smallest found block larger than the request size.
17. The program storage device as recited in claim 12, wherein the multiple sets include a set of largest blocks and the first threshold is larger than or equal to a smallest permitted block size for the set of largest blocks and further comprising the step of searching the set of largest blocks to satisfy the request.
18. The program storage device as recited in claim 12, wherein the step of searching includes the step of searching the set which includes a list, the list including memory block allocation information for the set.
19. The program storage device as recited in claim 12, further comprising the step of dynamically adjusting at least one of the first and second thresholds to tune performance.
20. The program storage device as recited in claim 12, further comprising the steps of:
maintaining a contiguous block of memory;
selecting the set of free blocks based on the request size;
in response to the set of free blocks being non-empty, allocating at least part of a first block located in the set; and
in response to the set being empty, satisfying the request from the contiguous block of memory.
21. The program storage device as recited in claim 20, further comprising the steps of:
maintaining a pointer to the contiguous block for a first pointer location;
in response to a request for storage of a given size,
incrementing the pointer by the given size to point to a second pointer location; and
satisfying the request using a part of the contiguous block beginning at the first pointer location.
22. The program storage device as recited in claim 12, further comprising the step of deallocating an allocated block to a new set of free blocks based on the size of the allocated block.
23. A method for managing a block of contiguous persistent memory comprising the steps of:
maintaining a first pointer in main memory for determining a first free byte in a first block of memory;
maintaining headers in the persistent storage for a plurality of blocks wherein the headers include at least one code byte; and
allocating a second block from the first block by setting the at least one code byte for the second block to indicate that the second block is no longer part of the first block and updating the first pointer in the main memory.
24. The method as recited in claim 23, further comprising the step of adding a block, b, to the first block, the step adding comprising the steps of:
modifying a code byte corresponding to b to indicate that b is part of the first block;
updating the first pointer in the main memory.
25. The method as recited in claim 23, wherein the at least one code byte serves other functions in addition to indicating that the second block is no longer part of the first block.
26. The method as recited in claim 23, further comprising the step of periodically updating a second pointer in the persistent memory based on the value of the first pointer in the main memory.
27. The method as recited in claim 26, further comprising the step of, in response to a system failure, updating the first and second pointers by examining the at least one code byte.
28. The method as recited in claim 23, wherein the headers are initialized using a single block write.
29. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for managing a block of contiguous persistent memory comprising a main memory and at least one disk memory device, the method steps comprising:
maintaining a first pointer in main memory for determining a first free byte in a first block of memory;
maintaining headers in the persistent storage for a plurality of blocks wherein the headers include at least one code byte; and
allocating a second block which from the first block by setting the at least one code byte for the second block to indicate that the second block is no longer part of the first block and updating the first pointer in the main memory.
30. The program storage device as recited in claim 29, further comprising the step of adding a block, b, to the first block, the step adding comprising the steps of:
modifying a code byte corresponding to b to indicate that b is part of the first block;
updating the first pointer in the main memory.
31. The program storage device as recited in claim 29, wherein the at least one code byte serves other functions in addition to indicating that the second block is no longer part of the first block.
32. The program storage device as recited in claim 29, further comprising the step of periodically updating a second pointer in the persistent memory based on the value of the first pointer in the main memory.
33. The program storage device as recited in claim 32, further comprising the step of, in response to a system failure, updating the first and second pointers by examining the at least one code byte.
34. The program storage device as recited in claim 29, wherein the headers are initialized using a single block write.
35. A method for coalescing adjacent free blocks in persistent storage comprising the steps of:
maintaining a header for each block indicating a size and an allocation status of the block;
coalescing the free blocks by examining header information to combine adjacent free blocks; and
periodically storing information in the persistent storage indicating a level of coalescing achieved.
36. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps as recited in claim 35.
37. The method as recited in claim 35, further comprising the step of:
in response to a system failure during coalescing, reading information in the persistent storage to determine the level of coalescing achieved before the system failure; and
resuming coalescing at a point based on the information in the persistent storage.
38. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps as recited in claim 35.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A system for emulsion formation, comprising:
a microfluidic device having a plurality of emulsion formation units each including a sample well, a droplet well, a sample inlet channel extending from the sample well to a channel intersection, and a droplet outlet channel extending from the channel intersection to the droplet well; and
an instrument that operatively receives the microfluidic device and including a fluidics assembly having a pressure sensor, the instrument being configured (a) to apply pressure to the emulsion formation units in parallel with the fluidics assembly to drive parallel generation of droplets at the channel intersections of the emulsion formation units and parallel collection of emulsions of the droplets in the droplet wells of the emulsion formation units, (b) to monitor the pressure with the pressure sensor, and (c) to stop application of the pressure to all of the emulsion formation units when the pressure sensor detects a change in pressure indicative of air entering any one of the sample inlet channels from a corresponding sample well.
2. The system of claim 1, further comprising a gasket defining a plurality of orifices configured to provide fluid communication between the microfluidic device and the fluidics assembly such that pressure can be applied to the emulsion formation units by the fluidics assembly.
3. The system of claim 2, wherein the gasket is configured to be engaged with the microfluidic device such that an orifice of the gasket overlaps each droplet well.
4. The system of claim 1, wherein the instrument is configured to receive an actuation signal from a user, and wherein the actuation signal causes the instrument, without any further user input or participation, to apply the pressure, to monitor the pressure, and to stop application of the pressure.
5. The system of claim 1, wherein the fluidics assembly includes a pump that functions as a source of the pressure, and wherein the pressure is applied by the instrument to the emulsion formation units while the pump is fluidically isolated from the emulsion formation units.
6. The system of claim 1, wherein the instrument is configured to apply negative pressure to the droplet wells of the emulsion formation units.
7. The system of claim 1, wherein each emulsion formation unit includes an oil well to hold a continuous phase for an emulsion, and wherein the instrument is configured to apply positive pressure to the sample wells and the oil wells of the emulsion formation units.
8. The system of claim 1, wherein the instrument is configured to apply pressure to the emulsion formation units with a gas phase that contacts liquid contained by the microfluidic device.
9. The system of claim 8, wherein the gas phase is composed of air.
10. The system of claim 1, wherein the fluidics assembly includes a manifold providing a plurality of ports through which a negative pressure is applied to the droplet wells.
11. The system of claim 1, wherein the instrument is configured to concentrate the emulsions by selectively driving a continuous phase of an emulsion from each of the droplet wells.
12. The system of claim 1, wherein the fluidics assembly includes a valve, and wherein adjustment of the valve stops application of the pressure to all of the emulsion formation units.
13. The system of claim 12, wherein the fluidics assembly includes a pump operatively connected to a reservoir, wherein the reservoir is configured to apply a negative pressure to the droplet wells while fluidically isolated from the pump, and wherein adjustment of the valve fluidically isolates the reservoir from the emulsion formation units.
14. The system of claim 12, wherein the adjustment of the valve vents the droplet wells.
15. A method of emulsion formation performed with the system of claim 1, the method comprising:
applying pressure with the fluidics assembly to the emulsion formation units, to drive droplet formation at the channel intersections and collection of emulsions of the droplets in the droplet wells;
monitoring the pressure with the pressure sensor; and
stopping application of the pressure when the change in pressure is detected.