STL Design Patterns in Embedded Systems II

来源：百度文库编辑：神马文学网时间：2024/05/01 09:10:53

STL Design Patterns II

Message Queue Documentation

Priority Message Documentation

Coldest First Resource Allocator Documentation

Hottest First Resource Allocator Documentation

STL Design Patterns II Source Code
We continue our discussion about STL designpatterns. In this article we willdiscuss queuing andresource managementpatterns that can be implemented with ease using the STL queue and priorityqueue adaptors. A simple implementation of the following design patterns will becovered in this article:
Message Queue Pattern
Priority Message Queue Pattern
Resource Allocator PatternColdest First
Hottest First
Container Adaptors
We will be using the following containeradaptors to implement our classes:
queue
queue container adaptor supports the standard queue operations, viz. add to queue, remove from queue. STL allows you to specify the underlying container used for implementing the queue. By changing one line of code you could change from a linked list implementation to an array like double ended queue!
priority_queue
Standard queue adds new arrivals at the tail of the queue. Priority queue however adds a new arrival according to its "priority". A higher priority entry is added before a lower priority entry in the queue. The "priority" for an entry is determined by invoking a user specified function.
stack
Stack implements the standard LIFO (Last In First Out) operations. Just like the other container adaptors you can choose the underlying container to be a vector or a linked list.
Message Queues are a very important design pattern in embedded and real-timesystems. Here we implement the Message Queue class as a very thin wrapperover the STL queue container adaptor.
Message Queue
00009 #include // STL header file for queue 00010 #include 00011 using namespace std; // Specify that we are using the std namespace 00012 00013 class Message; 00014 00027 00029 { ; 0003300035MsgQueTypem_msgQueue; 00036 00037 public:00044 voidAdd(Message *pMsg) 00045 { 00046 // Insert the element at the end of the queue 00047m_msgQueue.push(pMsg); 00048 } 0004900060 Message *Remove() 00061 { 00062 Message *pMsg = NULL; 00063 00064 // Check if the message queue is not empty 00065 if (!m_msgQueue.empty()) 00066 { 00067 // Queue is not empty so get a pointer to the 00068 // first message in the queue 00069 pMsg =m_msgQueue.front(); 00070 00071 // Now remove the pointer from the message queue 00072m_msgQueue.pop(); 00073 } 00074 return pMsg; 00075 } 0007600080 intGetLength() const 00081 { 00082 returnm_msgQueue.size(); 00083 } 00084 };
The Message Queue class always adds the message to the end of the queue. Inmany applications, the messages need to be queued according to the prioritysepcified at the time of additioni.e. when a high priority message arrives, it is enqueued before any previously present lowpriority messages.
We will be using the priority_queue container adaptor toimplement the Priority Message Queue class.
Function Objects (Functors)
The implementation of the Priority Message Queue is quite similar to theMessage Queue. Themost important change here is the introduction of a struct calledCompareMessages. This struct is a function object (functor), i.e. the solepurpose of this struct is to define a method for comparing the priorities of thetwo messages.
If you look closely you will see that the struct CompareMessages justoverloads the "()" operator, i.e. the method to be invoked whenCompareMessages struct is used along with the "()" operator. Thisprovides an extremely efficient mechanism for passing function code as aparameter. This mechanism has the following advantages over passing a functionpointer:
Function Objects are efficient, as they can even be inline. On the other hand, a function pointer will always have the overhead of a function call.
Function Objects provide a type safe implementation, there are no void pointers in this design.
Priority Message Queue
00008 #include // STL header file for queue 00009 #include 00010 using namespace std; // Specify that we are using the std namespace 00011 00012 class Message; 0001300024 classPriority_Message_Queue 00025 {00028 structEntry 00029 {00031 Message *pMsg;00034 intpriority; 00035 }; 0003600051 structCompare_Messages 00052 {00055 booloperator () (constEntry& left , constEntry& right) 00056 { 00057 return (left.priority < right.priority); 00058 } 00059 }; 0006000065 typedef priority_queue,Compare_Messages >Message_Queue_Type; 0006600068Message_Queue_Typem_message_Queue; 00069 00070 public: 0007100084 voidAdd(Message *pMsg, int priority) 00085 { 00086 // Make an entry 00087Entry entry; 00088 entry.pMsg = pMsg; 00089 entry.priority = priority; 00090 // Insert the element according to its priority 00091m_message_Queue.push(entry); 00092 } 0009300104 Message *Remove() 00105 { 00106 Message *pMsg = NULL; 00107 00108 // Check if the message queue is not empty 00109 if (!m_message_Queue.empty()) 00110 { 00111 // Queue is not empty so get a pointer to the 00112 // first message in the queue 00113 pMsg = (m_message_Queue.top()).pMsg; 00114 00115 // Now remove the pointer from the message queue 00116m_message_Queue.pop(); 00117 } 00118 return (pMsg); 00119 } 0012000123 size_tGet_Length() const 00124 { 00125 returnm_message_Queue.size(); 00126 } 00127 };
A simple Resource Allocator can be implemented by using the queue and thestack container adaptors. The container adaptors are used to maintain the freelist of resources.
The Resource Allocator supports the following interfaces:
Construction: When the Resource Allocator is constructed, it is a given a list of free resources. These resources are added to the free resource queue.
Allocate: When a resource is requested, it is removed from the free resource queue and the pointer to the resource is passed to the caller.
Free: When a resource is freed, it is added back to the free queue.
GetFreeResourceCount: Returns the total number of free resources currently available.
In coldest first resource allocation, the resource not allocated for maximumtime is allocated first. To implement this first in first out, FIFO type ofallocation, the resource allocating entity keeps the free resources in a queue.A resource allocation request is serviced by removing a resource from the headof the queue. A freed resource is returned to the free list by adding it to thetail of the queue.
The following code defines a simple "coldest first" resourceallocator:
Resource Allocator (Coldest First)
00008 #include // STL header file for queue 00009 #include 00010 using namespace std; // Specify that we are using the std namespace 00011 00012 class Resource; 0001300021 classCold_Resource_Allocator 00022 {00029 typedef queue >Free_Queue_Type; 0003000032Free_Queue_Typem_free_Resource_Queue; 00033 00034 public: 0003500041Cold_Resource_Allocator(int resource_Count, Resource *resource_Array[]) 00042 { 00043 for (int i = 0; i < resource_Count; i++) 00044 { 00045m_free_Resource_Queue.push(resource_Array[i]); 00046 } 00047 } 0004800053 Resource *Allocate() 00054 { 00055 Resource *pResource = NULL; 00056 00057 // Check if any free resources are available. 00058 if (!m_free_Resource_Queue.empty()) 00059 { 00060 // Queue is not empty so get a pointer to the 00061 // first resource in the queue 00062 pResource =m_free_Resource_Queue.front(); 00063 00064 // Now remove the pointer from the free resource queue 00065m_free_Resource_Queue.pop(); 00066 } 00067 return pResource; 00068 } 0006900074 voidFree(Resource *pResource) 00075 { 00076 // Insert the resource at the end of the free queue 00077m_free_Resource_Queue.push(pResource); 00078 } 0007900082 size_tGetFreeResourceCount() 00083 { 00084 returnm_free_Resource_Queue.size(); 00085 } 00086 };
In hottest first resource allocation, the resource last released is allocatedon next resource request. To implement this last in first out, LIFO type ofallocation, the list of free resources is maintained as a stack. An allocationrequest is serviced by popping a free resource from the stack. When a resourceis freed, it is pushed on the free resource list.
The "coldest first" resource allocator can be changed to"hottest first" resource allocator by simply replacing the queue witha stack. The following code illustrates the code for hottest first resourceallocator:
Resource Allocator (Hottest First)
00008 #include // STL header file for stack 00009 #include 00010 using namespace std; // Specify that we are using the std namespace 00011 00012 class Resource; 0001300021 classHot_Resource_Allocator 00022 { 0002800029 typedef stack >Free_Stack_Type; 0003000032Free_Stack_Typem_free_Resource_Stack; 00033 00034 public: 0003500041Hot_Resource_Allocator(int resource_Count, Resource *resource_Array[]) 00042 { 00043 for (int i = 0; i < resource_Count; i++) 00044 { 00045m_free_Resource_Stack.push(resource_Array[i]); 00046 } 00047 } 0004800053 Resource *Allocate() 00054 { 00055 Resource *pResource = NULL; 00056 00057 // Check if any free resources are available. 00058 if (!m_free_Resource_Stack.empty()) 00059 { 00060 // Queue is not empty so get a pointer to the 00061 // first resource in the stack 00062 pResource =m_free_Resource_Stack.top(); 00063 00064 // Now remove the pointer from the free resource stack 00065m_free_Resource_Stack.pop(); 00066 } 00067 return pResource; 00068 } 0006900074 voidFree(Resource *pResource) 00075 { 00076 // Insert the resource at the end of the free stack 00077m_free_Resource_Stack.push(pResource); 00078 } 0007900082 size_tGetFreeResourceCount() 00083 { 00084 returnm_free_Resource_Stack.size(); 00085 } 00086 };
Explore More ...

Message Queue Documentation

Priority Message Documentation

Coldest First Resource Allocator Documentation

Hottest First Resource Allocator Documentation

STL Design Patterns II Source Code

STL Design Patterns in Embedded Systems II Publish-Subscriber Design Patterns in Embedded Systems Design Patterns in C # Embedded Object Oriented Design Tips II Issues in Embedded and Realtime System Design Manager Design Pattern in Realtime Systems J2EE[tm] Design Patterns > Design Patterns Catalog Huston Design Patterns Realtime Task Design Patterns Timer Management Design Patterns Processor Architecture Patterns II Embedded Object Oriented Design Tips 分享：Scalable System Design Patterns Feature Coordination Realtime Design Patterns Patterns in Java Flash Filesystems for Embedded Linux Systems Thinking in Patterns with Java Current style in web design CS 764: Topics in Database Management Systems CS 764 - Topics in Database Management Systems Current Design Trends in Medical Electronics Design by Contract Programming in C A Taste of AOP from Solving Problems with OOP and Design Patterns (Part I) In ‘Design‘ vs. Darwinism, Darwin Wins Point in Rome