Real Time Operating Systems

Dr. Anupriya Koneru,

Associate professor,

Department of IT

LBRCE

Reference : Douglas Wilhelm Harder, Jeff Zarnett, Vajih Montaghami and Allyson Giannikouris – A Practical Introduction to real time systems for undergraduate engineering

UNIT-II

• Static memory allocation:
• The requirements of a function
• The Cortex-M3 design
• set jump and long jump
• Summary of static memory allocation
• Dynamic memory allocation:
• Abstract dynamic memory allocator
• Allocation strategies
• Case study: Free RTOS
• Other features: clearing and Reallocation
• Summary of dynamic memory allocation

​

Static Memory Allocation

• All real-time and embedded systems require data acquisition from sensors, and that data must be stored and processed.
• Data can be categorized in terms of either temporary or persistent:

1. temporary data is that which must be reacted to, but once the action is performed, the data is no longer required,and

2. persistent data is that information that is being collected by the system for long-acquisition or subsequent data transfer to another system.

Static Memory Allocation

• In either case, data should be moved as seldom as possible. Ideally,
• temporary data is read into local memory and then discarded or into global memory or dynamic memory where it is subsequently overwritten or the memory is released and reused, while
• persistent data should only be read into global memory or dynamic memory, and if it is to be transferred to another system, it should be transferred from that memory.

Static Memory Allocation

• Memory is allocated in one of two ways:

1. In some cases, the compiler can make decisions about where to allocate memory. It may be either at an absolute address or at a relative address, but the need for such memory must be discernable from the code at compile time, and this is termed static memory allocation. The absolute addressing includes global and static local variables, while relative addressing is used for the local variables of functions.

2. In others, the requirement for memory cannot be determined at compile time. For example, when you open a new document in a word processor, this requires memory; however, the compiler cannot be aware of that. Consequently, this requires memory allocation at run time, or dynamic memory allocation.

The requirements of a function

The operation of a function requires, at a minimum: locations to store:

1. arguments,

2. local variables, and

3. a return value.

These must be passed to the function, and as a function may be called recursively, each function call requires a different location in memory.

In addition, as a function may be called from multiple locations, the processor must know where to return to when the function call returns; that is, you must store

4. the program counter as it was immediately prior to the function call

The requirements of a function

• Now, consider the nature of function calls.
• Suppose we want to calculate the sine of a complex number z.
• This requires us to calculate the cosine, sine and exponential of three real numbers, the calls to both sine and cosine will involve a call to a floating-point absolute value function, as is shown in Figure 4-1.
• These form a tree of function calls, but the only functions we must keep track of those on the path from the initial function call to the currently executing function.
• When we return, the path is shorted by one, and when another function is called, that path is extended by one.

The requirements of a function

• Thus, this mimics the behaviour of a stack (see Figure 4-2): the memory required in main is at the bottom of the stack, the memory required for the call to the complex sine is next, followed by the memory required for a double-precision floating-point sine, followed by a call to the absolute value function.
• If the absolute value function wanted to call another function, it could use the next available memory.

The requirements of a function

• Now, because the memory required for each function call changes, we need to track

5. a stack pointer to the current top of the stack.

• However, there are two variables involved here: the amount of memory required for arguments changes from function call to function call (as with printf) and the memory required for local variables changes, also. Thus, we require a second pointer,

6. a frame pointer that separates arguments from local variables.

• Now, usually both the stack pointer and frame pointer are stored in registers, however, the value of these registers must be temporarily stored as subsequent calls are made.
• Thus, with each function call, in addition to storing the old program counter, we will also have to store

The requirements of a function

7. the old stack pointer, and

8. the old frame pointer.

• In addition, the new function will require the use of registers—but when the function call is made, the registers are storing values being used by the previous function.
• Thus, we must also store

9. the previous values of any registers used.

• Later, we will see how the Cortex-M3 manages to avoid requiring both a stack and a frame pointer.
• Thus, a function call looks like what is shown in Figure 4-3.
• In this image, the most recent function call is displayed in vivid color, while the previous function call is grayed.

The requirements of a function

The requirements of a function

• When the function returns, it must place the return value in an expected location.
• In this case, the most obvious point is right on top of the previous stack pointer, as is shown in Figure 4-4.
• Note that you will never see the return value at this location: when the function returns, this will either

1. be assigned to a variable and copied to that location,

2. become the argument of another function call or operation, or

3. be ignored.

• The last case happens quite often: printf returns the number of characters printed—how often have you ever inspected this value?

​

The requirements of a function

• Once the return value is copied to an appropriate location, the function may continue growing or shrinking the memory required for local variables, as is shown in Figure 4-5.

The requirements of a function

• To view that local variables can be dynamic in size, consider the following function:

​

​

​

​

​

​

​

• With each subsequent call, additional memory is allocated for the array, and the previous memory is reused, as the previous array went out of scope

The Cortex-M3 design

• The Cortex-M3 is designed to work as an embedded system, and therefore numerous assumptions can be made.
• First, there is not likely going to be a significant number of parameters to functions.
• Also, it is assumed that functions will very quickly require the use of their parameters.
• Consequently, arguments are not passed through the call stack, but rather, they are passed through the first four registers.
• (If more arguments are required, the address of those arguments must be passed as one of the four registers.) Thus, the functions know where the parameters are stored when the function call is made.
• Similarly, the return value is stored in a register.

The Cortex-M3 design

• The compiler will deal with storing the values of the registers on the calling function’s call stack.
• This allows a single stack pointer to be used.
• Later we will see that there are two stack pointers, but one is to allow devices peripheral to the computer to interrupt the execution of the processor.
• The Cortex-M3processor is suitable for low cost micro controllers, which are commonly used in Automotive body systems, Industrial Control Systems, Consumer Products, Real time Systems, Data Communications, and Wireless Networking and Sensors.

The Cortex-M3 design

• ARM (Acorn RISC Machine) started as a new, powerful, CPU design for the replacement of the 8-bit 6502 in Acorn Computers (Cambridge, UK, 1985)
• First models had only a 26-bit program counter, limiting the memory space to 64 MB
• 1990 spin-off: ARM renamed Advanced RISC Machines
• ARM now focuses on Embedded CPU cores
• IP licensing: Almost every silicon manufacturer sells some microcontroller with an ARM core. Some even compete with their own designs.
• Processing power with low current consumption
• Good MIPS/Watt figure
• Ideal for portable devices
• Compact memories: 16-bit opcodes (Thumb)

The Cortex-M3 design

• New cores with added features
• Harvard architecture (ARM9, ARM11, Cortex)
• Floating point arithmetic
• Vector computing (VFP, NEON)
• Java language (Jazelle)
• 32-bit CPU
• 3-operand instructions (typical): ADD Rd,Rn,Operand2
• RISC design…
• Few, simple, instructions
• Load/store architecture (instructions operate on registers, not memory)
• Large register set
• Pipelined execution

The Cortex-M3 design

• Although with some CISC touches…
• Multiplication and Load/Store Multiple are complex instructions (many cycles longer than regular, RISC, instructions)
• And some very specific details
• No stack. Link register instead
• PC as a regular register
• Conditional execution of all instructions
• Flags altered or not by data processing instructions (selectable)
• Concurrent shifts/rotations (at the same time of other processing)

​

​

The Cortex-M3 design

​

​

Barel Shifter

Set jump and long jump

• The setjmp and longjmp features in C provide a mechanism that is more primitive than the throw and catch of C++.
• “Setjump” and “Longjump” are defined in setjmp.h, a header file in C standard library.
• setjump(jmp_buf buf) : uses buf to remember current position and returns 0.
• longjump(jmp_buf buf, i) : Go back to place buf is pointing to and return i .
• The following two examples show how longjmp returns to the location
• This is mainly used to implement exception handling in C.
• setjmp can be used like try (in languages like C++ and Java).
• The call to longjmp can be used like throw(Note that longjmp() transfers control to the point set by setjmp()).

Set jump and long jump

• ‘setjmp()’ and ‘longjmp()’ functions provide a powerful mechanism similar to ‘goto’ but not restricted to just current function.
• This mechanism is useful in situations where there’s a deeply nested function calls and when error gets detected, in some lower-level function, then control immediately transfers to top-level function without having to return and check for error code by intermediate functions.
• These functions work in pairs as follows:
1. setjmp(jmp_buf resume_here) must be called first. This initializes ‘resume_here’ with program state information viz. value of pointer to the top of the stack, value of program counter and some other info.

It returns ZERO when returns first time.

Set jump and long jump

2. longjmp(jmp_buf resume_here, int i) is then called. This says go back to place where to resume from defined by ‘resume_here’.

This makes it look like you’re returning from original ‘setjmp()’ but return value of integer ‘i’ to let code tell when you actually got back here via ‘longjmp()’.

3. After longjmp()’ed, contents of ‘jmp_buf’ variable ‘resume_here’ destroys.

​

• A goto statement implements a local jump of program execution, and the longjmp() and setjmp() functions implement a nonlocal, or far, jump of program execution.
• Generally, a jump in execution of any kind should be avoided because it is not considered good programming practice to use such statements as goto and longjmp in your program.

​

​

Set jump and long jump

Set jump and long jump

• The change in behaviour between normal function calls and longjmp is clear from the output:

Summary of static memory allocation

• The allocation of global and static local variables is dealt with quite easily by the compiler; however, the compiler can also set up the mechanism to make the allocation of memory required by local variables, and other aspects of function calls.
• The Cortex-M3 makes certain assumptions about parameters allowing them to be passed in registers.
• The C programming language setjmp and longjmp allow you to travel back down the call stack to a prearranged location

Dynamic Memory Allocation �

• Why DMA?

int a[5];

int i,n;

scanf(“%d”, &n);

For(i=0; i<n; i++)

{

scanf(“%d”, &a[i]);

}

​

​

​

Overflow

or

Underflow

Dynamic Memory Allocation �

Code Segment: Compiled program with executive instructions are kept in code segment. It is read only. In order to avoid over writing of stack and heap, code segment is kept below stack and heap.

Data Segment: Global variables and static variables are kept in data segment. It is not read only.

Stack: A stack is usually pre-allocated memory. The stack is a LIFO data structure. Each new variable is pushed onto the stack. Once variable goes out of scope, memory is freed. Once a stack variable is freed, that region of memory becomes available for other variables. The stack grows and shrinks as functions push and pop local variables. It stores local data, return addresses, arguments passed to functions and current status of memory.

Heap: Memory is allocated during program execution. Memory is allocated using new operator and deallocating memory using delete operator.

��Abstract dynamic memory allocation��

Memory Allocation :

• Allocation of Heap Memory using new Keyword
• Here we will learn how to allocate heap memory to a variable or class object using the new keyword.

​

Abstract dynamic memory allocation

Memory Deallocation:

Deallocation of memory using delete Keyword

• Once heap memory is allocated to a variable or class object using the new keyword, we can deallocate that memory space using the delete keyword.

​

Heap Memory allocation is slower than a stack.

In heap there is no particular order in which you can allocate memory as in stack

Dynamic memory allocation

• The situation when memory is being allocated or deallocated by various tasks at run time.
• Interface of an abstract dynamic memory allocator (Dynamic Memory allocator ADT), and then look at a number of implementations of this abstract data type.
• The appropriateness of the different implementations for real-time systems.
• The relevance of studying dynamic memory allocation to real-time systems is related to the non-functional requirements of safety, performance and scalability.
• Dynamic memory allocation is often complex and some approaches are simply incapable of delivering memory with guarantees as to the run time, thereby violating safety.
• Additionally, the approaches must be reasonably fast with the appropriate data structures supporting the process in a way that does not have serious consequences if the number of allocations or deallocations suddenly increases.

Abstract dynamic memory allocator

• An abstract dynamic memory allocator is a container that maintains a pool of memory and that satisfies, where possible, requests for memory and receives allocated memory when returned by its user.
• The interface for such an ADT has at least two signatures:

• Note that, in general, it is not possible to return a part of a block of memory, and generally the allocator records the size of the block that was allocated.
• In C++, this interface is provided through the new and delete operators. These are coupled together with the initialize and destruction of the instances of classes by appropriate calls to constructors and destructors, respectively.

Abstract dynamic memory allocator

• Other possible interfaces include:

void *allocate_clear_memory( size_t n );

• Like allocate_memory, but sets all bits to zero in the block that is allocated.

void *reallocate_memory( void *p_memory, size_t n );

• Allocate n bytes of memory either by expanding the memory allocated at address mem, if possible, or allocate new memory while copying over the contents at mem into that new memory.
• In either case, a pointer is returned to the first byte of that block of reallocated memory.
• Note that C++ does not offer these in conjunction with their new and delete interface.

Abstract dynamic memory allocator

• Recall the difference between static and dynamic memory allocation:

• We already saw previously that static memory allocation, when used in conjunction with function calls and returns, may be performed efficiently using a stack.
• This is not the case with dynamic memory allocation

Abstract dynamic memory allocator

• With respect to deallocation of memory, dynamic memory allocation may either

1. require manual deallocation by the developer, or

2. the system may perform automatic deallocation.

​

Manual allocation management:

​

• The first case is exemplified by C and C++: an explicit call to free(…) or delete … must be made.
• With such a scheme, the programmer is in complete control of any dynamic memory allocation.
• The drawback is that it is error-prone for developers, some of whom may not be entirely aware of the consequences of failing to delete memory.

Manual allocation management:�

• For example, a common scenario in which memory is allocated but never deallocated occurs when memory has been allocated by one part of the program and passed to another, but not deleted by the other task.
• There are four common sources of error that we must be aware of:

1. pointers that store addresses of memory that have not yet been initialized are referred to as wild pointers,

2. pointers that store addresses of memory that has been freed are referred to as dangling pointers,

3. the same memory being freed multiple times, and

4. memory that is allocated but not appropriately deallocated when it is no longer needed; that is, a memory leak.

Manual allocation management:�

a. Wild pointers –

• After memory is allocated, but before it is first used, the content of that memory is usually random–unknown junk values.
• Consequently, if the pointer is used as if it is referring to an initialized object, interesting things may or may not occur—especially on different platforms or with different parallel events.

Example:

int main()

{

int *p;

*p = 10;

return 0;

}

Manual allocation management:�

1. Wild pointers –
1. Consider, for example, a singly linked list used as follows:

single_list_t *p_list = (single_list_t *) malloc( sizeof( single_list_t ) ); single_list_push_front( p_list, 42 );

​

• If the memory allocated all happens to contain zero, this will function perfectly: any variable storing the size will have a value of zero, and the address of the head pointer will also be zero (NULL).
• However, if this code is run on another machine, the memory may not be zeroed, in which case, it may appear that the linked list has a non-zero number of objects.
• For example, if it is determined in the above case that the linked list is not empty, then a tail pointer would not be updated when the node containing 42 is inserted.

Manual allocation management:�

1. Wild pointers –
1. The solution is straight-forward:

int main()

{

Int var =10;

int *p;

*p = &var;

return 0;

}

• ensure that each call to malloc(…) is immediately associated with a call to an initializer.

single_list_t *p_list = (single_list_t *) malloc( sizeof( single_list_t ) );

single_list_init( p_list );

single_list_push_front( p_list, 42 );

• C++ solves this problem by having the new operator immediately call the constructor.
• Consequently it is not possible to allocate memory without initializing it

Manual allocation management:�

1. Wild pointers –
1. This can be solved in C using macros:

#define SINGLE_LIST( list ) single_list_t list; \

single_list_init( &list )

#define SINGLE_LIST_P( p_list ) \

single_list_t *p_list = (single_list_t *) malloc( sizeof( single_list_t ) ); \

single_list_init( p_list )

​

Now our code looks like:

​

SINGLE_LIST( list );

single_list_push_front( &list, 42 );

​

or

​

SINGLE_LIST( p_list );

single_list_push_front( &p_list, 42 );

Manual allocation management:

Dangling pointer

• A pointer pointing to a memory location that has been deleted (or freed) is called dangling pointer.
• Avoiding dangling pointers can be solved by always assigning a pointer the value NULL after the memory has been freed:

free( ptr );

ptr = NULL;

• If you want to assign these pointers to NULL only during development (where use of a dangling pointer can be caught during testing), but not in production code (where there is an unnecessary assignment), this can be done as follows:

free( ptr );

#ifdef DEVELOPMENT

ptr = NULL;

#endif

Manual allocation management:

Dangling pointer

• A reference to an address that has been deallocated has non-deterministic consequences: the operating system may

1. still flag that memory as allocated, so no issues occur,

2. cause the program to crash, or

3. have reallocated that memory to the same task, but it is now being used for a different purpose.

• The last is the most detrimental, as the other data structure can be corrupted

Manual allocation management:

Freeing the same location more than once :

• One possible consequence of dangling pointers is that they may be freed multiple times.
• This can have very different results, but usually one of two events will occur:

1. the allocator will cause the program to stop execution,

2. the memory may have since been allocated again, in which case, you would free memory that was not meant to be freed, or

3. heap corruption—the heap is in an inconsistent state and operations that mange it will be unpredictable.

• Again this is a matter that can be resolved by having as few persistent variable storing addresses and ensuring that when a call to free(…) is made, all of those variables must be set to null

Manual allocation management:

Memory leaks:

• The primary cause of a memory leak is when the last reference to memory is lost by the application.
• In C and C++, this may happen in one of two ways:
• The last pointer assigned the memory location is a local variable that then goes out of scope (often when a function returns), or
• The last pointer (local, member or global) assigned the memory location is overwritten.
• In either case, because the last value storing the address is lost, it is now impossible to call either free(…) or delete … to indicate to the operating system that the memory is no longer required.
• Consequently, as long as the application is running, the operating system will simply assume that the memory is being used by the application.

Manual allocation management:

Memory leaks:

• There are other instances where memory leaks can be more serious than one in an application being run:

1. in an embedded system where memory is more limited as compared to what one would expect from a desktop or laptop system,

2. in an embedded system that is meant to execute for an extended period of time (even years),

3. when memory may be shared by multiple processes and where the termination of one of these processes does not necessarily cause the memory to be collected, and

4. in a device driver.

• Numerous programs and tools are available to help find memory leaks.

Dynamic memory allocation

Automatic allocation management:

Automatic allocation management has two aspects:

1. automatic initialization, and
2. garbage collection.

Automatic initialization:

• In C, allocation of memory and initialization are two separate operations, often in the form:

Type *p_entry = (Type *) malloc( sizeof( Type ) );

type_init( p_entry, … );

• Accidently accessing a pointer to an object that has not been initialized is a form of memory corruption.

Dynamic memory allocation

Automatic initialization:

• In C++, the inclusion of a constructor prevents this: as soon as the memory is allocated, the constructor is called on the object prior to new returning a pointer to the calling function:
• Type *p_entry = new Type( … );
• In languages such as Java and C#, variables defined to be primitive data types are automatically initialized to zero.

Garbage collection:

• This second case is exemplified by the garbage collectors in programming languages such as Java and C#.
• Each time a reference to an object is assigned, additional work is done by the runtime environment to track references to allocated memory.

We will describe

• two algorithms for dealing with garbage collection, and
• some of the issues with garbage collections.

Dynamic memory allocation

Garbage collection:

Garbage collection algorithms:

There are two mechanisms for dealing with garbage collection:

1. reference counting, and
2. tracing algorithms.

Automatic allocation management

Automatic allocation management

Automatic allocation management

Dynamic memory allocation

Reference Counting:

• It is possible to implement reference counting in C++ by creating a class that behaves like pointers but where operators such as

1. the unary dereference operator *,

2. the assignment operator =,

3. the auto increment and decrement operators ++ and --, are overloaded.

• Issues with reference counting include:

1. cycles cannot be detected (what if head and ptr are set to NULL),

2. it requires O(n) additional memory where n is the number of pointers or references, and

3. it is not real-time, as the reference count of multiple objects may have be decremented even if none of them are eligible for garbage collection.

• Tracing algorithms solve the first problem

Tracing algorithm

​

• 1. all bits are set to zero,
• 2. each memory block referred to by a global or local variable is marked (the bit is set to 1),
• 3. the first time each block is marked, this algorithm is run recursively and any memory blocks referred to within this memory block are themselves marked.

​

Garbage collection in C

• The Boehm–Demers–Weiser non-real-time garbage collector can be implemented in most C programs by

1. installing and including the library with #include "gc.h";

2. initializing the garbage collection with a call to GC_INIT();

3. replacing all calls to malloc(…) with calls to

1. GC_MALLOC(…) if the object itself may contain pointers, or
2. GC_MALLOC_ATOMIC(…) if the object does not contain subsequent pointers;

4. replacing all calls to realloc(…) with calls to GC_REALLOC(…); and

5. remove all calls to free(…).

You can access the size of the heap with GC_get_heap_size().

Issues with Garbage collection

• One issue with garbage collection is that references to allocated memory may remain in data structures even if they are not accessible.
• The easiest solution is that any data structure that is used to implement an algorithm on a data structure should have a shorter life span than the data structure itself;
• however, if this is not possible, references in such intermediate data structures should be assigned null when they are no longer logically part of the data structure.

Allocation strategies

Reference from: https://www.javatpoint.com/memory-management-operating-system

Allocation strategies

Contiguous memory management schemes:

• In a Contiguous memory management scheme, each program occupies a single contiguous block of storage locations, i.e., a set of memory locations with consecutive addresses.

1. Single contiguous memory management schemes:

• The Single contiguous memory management scheme is the simplest memory management scheme used in the earliest generation of computer systems.
• In this scheme, the main memory is divided into two contiguous areas or partitions.
• The operating systems reside permanently in one partition, generally at the lower memory, and the user process is loaded into the other partition.

​

​

Allocation strategies

Advantages :

• Simple to implement.
• Easy to manage and design.
• In a Single contiguous memory management scheme, once a process is loaded, it is given full processor's time, and no other processor will interrupt it.

Disadvantages

• Wastage of memory space due to unused memory as the process is unlikely to use all the available memory space.
• The CPU remains idle, waiting for the disk to load the binary image into the main memory.
• It can not be executed if the program is too large to fit the entire available main memory space.
• It does not support multiprogramming, i.e., it cannot handle multiple programs simultaneously.

Allocation strategies

2. Multiple Partitioning:

• The single Contiguous memory management scheme is inefficient as it limits computers to execute only one program at a time resulting in wastage in memory space and CPU time.
• The problem of inefficient CPU use can be overcome using multiprogramming that allows more than one program to run concurrently.
• To switch between two processes, the operating systems need to load both processes into the main memory.
• The operating system needs to divide the available main memory into multiple parts to load multiple processes into the main memory.
• Thus multiple processes can reside in the main memory simultaneously.
• The multiple partitioning schemes can be of two types:
• Fixed Partitioning
• Dynamic Partitioning

​

Allocation strategies

• The allocation of memory by the operating system can be either fixed partition or variable partition.
• Like static and dynamic allocation, fixed partitioning is simpler to implement, but it has numerous restrictions, the most significant of which is internal fragmentation.
• We will look at using:

1. fixed block sizes,

2. variable block sizes,

3. a composition of these two schemes, and

4. other advanced memory allocation schemes.

Allocation strategies

Fixed Partitioning

Reference from: https://www.tutorialandexample.com/fixed-partitioning/

• The main memory is divided into several fixed-sized partitions in a fixed partition memory management scheme or static partitioning.

• These partitions can be of the same size or different sizes.
• Each partition can hold a single process.

​

• The number of partitions determines the degree of multiprogramming, i.e., the maximum number of processes in memory.

​

• These partitions are made at the time of system generation and remain fixed after that.

Allocation strategies

Fixed Partitioning

Advantages of Fixed Partitioning memory management schemes:

• Simple to implement.
• Easy to manage and design.

Disadvantages of Fixed Partitioning memory management schemes:

• Internal Fragmentation: – In fixed partitioning, the partitions will be wasted and remain unused if the process size is lesser than the total size of the partition. In this way, memory gets wasted, and this is called Internal fragmentation.
• External Fragmentation: – We cannot use the total amount of unused space of different partitions to put the process even in the situation when we have some space available, but not in contiguous form. We can see in the fixed partitioning diagram, that we cannot use the 1 MB remaining space of each of the partition to store the process of 4 MB. Instead of that, we have a space available to load the process, but we cannot load the process. Such type of fragmentation is known as External Fragmentation.

​

Allocation strategies

• Limitation on the Size of the Process: – Sometimes, when the size of the process is larger than the maximum partition size, then we cannot load that process into the memory. So, this is the main disadvantage of the fixed partition.
• Degree of Multiprogramming is Less: – We can understand from the degree of multiprogramming that it means at the same time, the maximum number of processes we can load into the memory. In Fixed Partitioning, the size of the partition is fixed, and we cannot vary it according to the process size; therefore, in fixed partitioning, the degree of multiprogramming is less and fixed.

​

Allocation strategies

Dynamic Partitioning

• The dynamic partitioning was designed to overcome the problems of a fixed partitioning scheme.
• In a dynamic partitioning scheme, each process occupies only as much memory as they require when loaded for processing.
• Requested processes are allocated memory until the entire physical memory is exhausted or the remaining space is insufficient to hold the requesting process.
• In this scheme the partitions used are of variable size, and the number of partitions is not defined at the system generation time.

Reference from: https://www.tutorialandexample.com/fixed-partitioning/

Allocation strategies

Dynamic Partitioning

Advantages of Dynamic Partitioning memory management schemes:

​

• No Limitation on the size of the process: – In fixed partitioning, if the size of the process is larger than the size of the partition, we cannot put or load the process into the memory. But if we talk about dynamic partitioning, the size of the process cannot be fixed, and we can change the size of partition according to the size of the process.

​

• The Degree of Multiprogramming is dynamic: -In Dynamic Partition, there is no internal fragmentation, so there is no unused space that is present in the partition. So at the same time, we can load more number of processes in the memory.

​

• No Internal Fragmentation: – In Dynamic Partitioning, the partitions are created dynamically as per the need for the process. So, in dynamic partitioning, internal fragmentation is not present, and the reason behind is that in dynamic partition, there is no space in the partition which remains unused.

Allocation strategies

Dynamic Partitioning

Disadvantages of Dynamic Partitioning:

​

Complex Memory Allocation: – In the case of dynamic partition, the task of allocation and deallocation is tough because the size of the partition varies whenever the partition is allocated to the new process. The operating system has to keep track of each of the partitions.

External Fragmentation: –  Suppose we have three processes P1 (1MB), P2 (3MB), and P3 (1MB), and we want to load the processes in the various   partitions of the main memory.

Now the processes P1 and P3 are completed, and space that is assigned to the process P1 and P3 is freed. Now we have partitions of 1 MB each, which are unused and present in the main memory, but we cannot use this space to load the process of 2 MB in the memory because space is not contiguous.

Allocation strategies

• Compaction is also known as Defragmentation. In dynamic Partitioning, there is a problem of external fragmentation, and due to external fragmentation, some critical problems can happen.
• Compaction is used to reduce the possibility of external fragmentation. In this, the partitions which are free are made contiguous, and all the partitions which are loaded are carried together.

Problem with Compaction

• Due to compaction, the system efficiency is decreased because we need to move all the free spaces from one place to other.

​

Reference from: https://examradar.com/memory-management-2/

Allocation strategies

• The Main concern for dynamic partitioning is keeping track of all the free and allocated partitions. However, the Operating system uses following data structures for this task.

Bit Map Linked List

Bit Map

• Bit Map is the least famous data structure to store the details. In this scheme, the main memory is divided into the collection of allocation units. One or more allocation units may be allocated to a process according to the need of that process. However, the size of the allocation unit is fixed that is defined by the Operating System and never changed. Although the partition size may vary but the allocation size is fixed.
• The main task of the operating system is to keep track of whether the partition is free or filled. For this purpose, the operating system also manages another data structure that is called bitmap.
• The process or the hole in Allocation units is represented by a flag bit of bitmap. In the image shown below, a flag bit is defined for every bit of allocation units. However, it is not the general case, it depends on the OS that, for how many bits of the allocation units, it wants to store the flag bit.

​

Allocation strategies

Bit Map

• The flag bit is set to 1 if there is a contiguously present process at the adjacent bit in allocation unit otherwise it is set to 0.
• A string of 0s in the bitmap shows that there is a hole in the relative Allocation unit while the string of 1s represents the process in the relative allocation unit.

​

Reference from: https://www.javatpoint.com/memory-management-operating-system

Allocation strategies

Bit Map

Disadvantages of using Bitmap

1. The OS has to assign some memory for bitmap as well since it stores the details about allocation units. That much amount of memory cannot be used to load any process therefore that decreases the degree of multiprogramming as well as throughput.

2. To identify any hole in the memory, the OS need to search the string of 0s in the bitmap. This searching takes a huge amount of time which makes the system inefficient to some extent

​

Allocation strategies

Linked List

• In this approach, the Operating system maintains a linked list where each node represents each partition. Every node has three fields.
• First field of the node stores a flag bit which shows whether the partition is a hole or some process is inside.
• Second field stores the starting index of the partition.
• Third filed stores the end index of the partition.
• If a partition is freed at some point of time then that partition will be merged with its adjacent free partition without doing any extra effort.
• There are some points which need to be focused while using this approach.

​

Reference from: https://www.javatpoint.com/memory-management-operating-system

Allocation strategies

Partitioning Algorithms

• There are various algorithms which are implemented by the Operating System in order to find out the holes in the linked list and allocate them to the processes.
• The explanation about each of the algorithm is given below.

1. First Fit Algorithm

• First Fit algorithm scans the linked list and whenever it finds the first big enough hole to store a process, it stops scanning and load the process into that hole. This procedure produces two partitions. Out of them, one partition will be a hole while the other partition will store the process.
• First Fit algorithm maintains the linked list according to the increasing order of starting index. This is the simplest to implement among all the algorithms and produces bigger holes as compare to the other algorithms.

Allocation strategies

Partitioning Algorithms

2. Next Fit Algorithm

• Next Fit algorithm is similar to First Fit algorithm except the fact that, Next fit scans the linked list from the node where it previously allocated a hole.
• Next fit doesn't scan the whole list, it starts scanning the list from the next node. The idea behind the next fit is the fact that the list has been scanned once therefore the probability of finding the hole is larger in the remaining part of the list.
• Experiments over the algorithm have shown that the next fit is not better then the first fit. So it is not being used these days in most of the cases.

3. Best Fit Algorithm

• The Best Fit algorithm tries to find out the smallest hole possible in the list that can accommodate the size requirement of the process. Using Best Fit has some disadvantages.

Allocation strategies

Partitioning Algorithms

1. It is slower because it scans the entire list every time and tries to find out the smallest hole which can satisfy the requirement the process.
2. Due to the fact that the difference between the whole size and the process size is very small, the holes produced will be as small as it cannot be used to load any process and therefore it remains useless.

4. Worst Fit Algorithm

• The worst fit algorithm scans the entire list every time and tries to find out the biggest hole in the list which can fulfill the requirement of the process.
• Despite of the fact that this algorithm produces the larger holes to load the other processes, this is not the better approach due to the fact that it is slower because it searches the entire list every time again and again.

The first fit algorithm is the best algorithm among all because

• It takes lesser time compare to the other algorithms.
• It produces bigger holes that can be used to load other processes later on.
• It is easiest to implement.

​

Case study: FreeRTOS

• The real-time operating system FreeRTOS (see http://www.freertos.org/) comes with five dynamic memory allocation schemes, existing in the files heap_1.c through heap_5.c.
• Before we go through these, we should consider how casting works in C.
• Suppose we have a data structure:

typedef struct block_link {

struct block_link *p_next_free; /* The next free block in the list. */

size_t size; /* The size of the free block. */

} block_link_t;

• Suppose that each of the fields is four bytes in size. In that case, suppose we take an arbitrary pointer ptr and it is pointing to an arbitrary location in memory, as is shown in Figure 5-13.

Case study: FreeRTOS

• If we now cast that pointer

block_link_t *p_cast_ptr = (block_link_t *) p_ptr;

then the compiler will treat this as a record of 8 bytes, as sis shown in Figure 5-14

• Thus, if we now assign:

p_cast_ptr->p_next_free = NULL;

p_cast_ptr->size = 42;

• then those values will be stored in the first eight bytes overwriting whatever was there previously, as is shown in Figure 5-15.

Case study: FreeRTOS

• FreeRTOS is a real-time operating system is a real-time operating system kernel is a real-time operating system kernel for embedded devices is a real-time operating system kernel for embedded devices that has been ported to 35 microcontroller is a real-time operating system kernel for embedded devices that has been ported to 35 microcontroller platforms. It is distributed under the MIT License.
• The FreeRTOS kernel was originally developed by Richard Barry around 2003, and was later developed and maintained by Barry's company, Real Time Engineers Ltd.
• In 2017, the firm passed stewardship of the FreeRTOS project to Amazon Web Services (AWS). Barry continues to work on FreeRTOS as part of an AWS team.

IMPLEMENTATION:

• FreeRTOS is designed to be small and simple. The kernel consists of only three source code files. it is mostly written in the C programming language to make it easy to port and maintain.
• It also comprises a few assembly language functions where needed, mostly in architecture-specific scheduler routines.

Case study: FreeRTOS

• FreeRTOS provides methods for multiple threadsFreeRTOS provides methods for multiple threads or tasksFreeRTOS provides methods for multiple threads or tasks, mutexesFreeRTOS provides methods for multiple threads or tasks, mutexes, semaphoresFreeRTOS provides methods for multiple threads or tasks, mutexes, semaphores and software timers.
• A tickless mode is provided for low power applications. Thread priorities are supported.
• FreeRTOS applications can be statically allocated, but objects can also be dynamically allocated with five schemes of memory management (allocation):
• allocate only;
• allocate and free with a very simple, fast, algorithm;
• a more complex but fast allocate and free algorithm with memory coalescence;
• an alternative to the more complex scheme that includes memory coalescence that allows a heap to be broken across multiple memory areas.
• and C library allocate and free with some mutual exclusion protection.

Case study: FreeRTOS

• RTOS typically does not have the more advanced features that are typically found in operating systemsRTOS typically does not have the more advanced features that are typically found in operating systems like LinuxRTOS typically does not have the more advanced features that are typically found in operating systems like Linux and Microsoft WindowsRTOS typically does not have the more advanced features that are typically found in operating systems like Linux and Microsoft Windows, such as device drivers, advanced memory management, user accounts. The emphasis is on compactness and speed of execution.
• FreeRTOS can be thought of as a thread library rather than an operating system, although command line interface and POSIX-like input/output (I/O) abstraction are available.
• FreeRTOS implements multiple threads by having the host program call a thread tick method at regular short intervals.
• The thread tick method switches tasks depending on priority and a round-robin scheduling scheme.
• The usual interval is 1 to 10 milliseconds (1/1000 to 1/100 of a second), via an interrupt from a hardware timer, but this interval is often changed to suit a given application.
• The software distribution contains prepared configurations and demonstrations for every port and compiler, allowing rapid application design.
• The project website provides documentation and RTOS tutorials, and details of the RTOS design.

​

​

Case study: FreeRTOS

Allocation only:

• The allocation strategy used in heap_1.c simply allocates memory from an array and never allows any form of deallocation:

1. First it checks to determine whether or not the allocated memory should be aligned with the word size of main memory. If so, it increases the size of n to a multiple of the word size.

2. Secondly, it ensures that the memory allocated neither exceeds the total memory that can be allocated nor causes an overflow.

3. Finally, if configured, it sets a hook (the error handling mechanism for FreeRTOS whereby this user-defined function is called) if the allocation failed.

• While apparently trivial, it is best for numerous embedded systems where

1. all tasks are created and

2. all memory including that for queues and semaphores is allocated

Case study: FreeRTOS

Allocation only:

• when the system boots. Therefore memory deallocation will never be needed.
• As deallocation is unnecessary, there is no need for an implementation of the code to handle it. One implementation is here:

Case study: FreeRTOS

Best fit without coalescence:

• This simply allocates memory using a simple best fit strategy where it maintains a list of unallocated blocks sorted in the order of the size.
• When a block is deallocated, it is simply placed back into the list. No attempt is made to coalesce adjacent free blocks.
• When a block is allocated, the linked list structure is left untouched.

• The code is reasonably straight-forward; however we will look at how the programmers used a macro to avoid an unnecessary function call while still maintaining functional independence and coherence.

​

• The names of fields, parameters and local variables have been simplified for clarity

Case study: FreeRTOS

Best fit without coalescence:

​

• In C++, this could be avoided by using inline functions. Visually, the blocks are stored as is shown in Figure 5-16.
• The list is actually a linked list with sentinels where the first (xStart) and last (xEnd) nodes are dummy nodes with the first having a size set to 0 and the last having a size set to the size of allocated memory.
• Thus, any allocated block will always be larger than the first and less than or equal to the last in size

Case study: FreeRTOS

Best fit without coalescence:

​

• Such a scheme can be used if most of the blocks dynamically allocated and deallocated after system initialization falls within a fixed number of block sizes.
• If blocks of memory for data structures such as queues may have arbitrary size, this scheme will quickly result in significant amount of fragmentation.

Case study: FreeRTOS

Standard library malloc and free:

• The third implementation creates a thread safe wrapper of the standard library implementations of malloc and free.

​

Case study: FreeRTOS

First fit with coalescence:

• In this implementation, we use a first-fit model, but also, the unallocated blocks are stored in address order.
• Consequently, at the same time a block is being deallocated, it can be checked with its neighbors to determine whether or not it can be coalesced.
• The schemes are similar to those already described, so we will focus on coalescence.
• Consider the memory allocated in Figure 5-17. Here, those blocks marked in red are allocated; those in black are unallocated.
• A linked list joins those that are unallocated and each block (allocated or unallocated) has a header with the size of the block and a pointer, which is only used if the block is unallocated.

Case study: FreeRTOS

First fit with coalescence:

• When an allocated block is freed, one would walk through the linked list until you have pointers to both the unallocated block immediately preceding the freed block in memory, and the one immediately following the freed block:

1. If all three are contiguous, they will be joined into a single block (so if the block of size 40 is unallocated, it would be merged with the two surrounding blocks forming one of size 16 + 40 + 24 = 80).

2. If the previous block is contiguous with the deallocated block, those two would be merged (so if the second block of size 16 is deallocated, it would be merged with the block of size 24).

3. If the next block is contiguous with the deallocated block, the would be merged (not shown).

4. Otherwise, the deallocated block becomes a link in the linked list (so if the block of size 56 is deallocated, it becomes another node in the linked list)

Case study: FreeRTOS

First fit with coalescence over multiple regions:

• This final version is identical to that described in the previous section, only it does not require the block of available memory to be one large contiguous block.
• The available memory can itself be separated throughout the memory of the system

Other features: Clearing and Reallocation

• In addition to malloc, there are two other related functions: calloc (clear allocate) and realloc (reallocation). By default, asking for memory through malloc will have the operating system find an appropriate block of memory, mark it as allocated, and return a pointer to the first address of that block.
• The contents of that block, however, are not modified. It contains whatever data may have previously been in that memory, which may or may not be meaningful or bogus data. T
• he call calloc sets all the bits in that block to zero.
• Suppose you allocated an array of size n, but then realize later you require an array of size n + m. Normally, this would require you to create a new array, copy the information over, and then destroy the old array.
• However, what if there is memory available immediately after the memory currently allocated?

Other features: Clearing and Reallocation

• Could not the operating system just expand the block of memory that has been allocated?
• The realloc command attempts to do this.
• If it is successful, the allocated memory is expanded.
• If that memory is not available, the operating system finds a sufficiently large block of memory and copies over the contents of the original array into that larger block (for example, using memcpy).

Reallocation in C++ and the move constructor and move assignment operator:

• Can you call realloc in C++? Generally, no: recall that when memory is allocated, it is also necessary to call any constructors.
• As objects may have pointers to themselves, it may not be possible to simply copy the memory over.

Other features: Clearing and Reallocation

• The vector class in C++ will allocate new memory and move the objects over; indeed, in C++-11, there is a new move constructor and a new move assignment operator—two functions that may assume that the previous objects are being destroyed anyway.
• A copy constructor may have to make a deep copy of larger data structures while the move constructor may be much easier.
• For example: The copy constructor for a binary search tree would have to make a complete copy of the entire tree—an O(n) operation.
• The move constructor, however, would only have to copy over the address of the root and a few other variables—an O(1) operation