Explain the methods for free space management? – Part 2

- Managing the free space is easy only when the space that has to be managed is divided in to units of fixed size. 

- If this is the case, the list of these fixed size units can be kept. 

- The first entry can be returned if it is requested by the client. 

- Managing free space gets difficult when the space to be managed consists of units of variable sizes. 

- This is the case with the memory allocation library at the user level. 

- This is also the case in the physical memory where the segmentation is used for the implementation of the virtual memory. 

- In such cases, external fragmentation is the main problem. 

- This leads to the splitting up of the disk space in to pieces of variable size. 

- The next coming requests might fail because of unavailability of contiguous free space. 

- For example, the request might fail even if 20 bytes are available and the request requires only 15 bytes because this 20 bytes space is non-contiguous. 

- Thus, the main problem is how the free space should be managed while satisfying the variable sized variables. 

How these strategies can manage free space while at the same time keeping the fragmentation in control.

Low level Mechanisms: 

- Most of the allocator use some common mechanisms as these: coalescing and splitting.

- Here, the free list consists of a set of elements describing about all the free spaces available in the heap. 

- Once a pointer to a space is handed over to the program, the determination of the pointers to this space becomes somewhat difficult. 

- These pointers are stored either in the registers or in the variables at some point of execution. 

- However, this is not the case of garbage collected and strongly typed languages as a measure for enabling compaction for combating fragmentation. - Suppose the program makes a request for a single byte of memory.

- In such a case the action performed by the allocator is called splitting. 

- Here a free memory chunk is searched for and split in to two. 

- The first one is returned to the calling request and the second one stays in the list itself. 

- This approach is used in the allocators where small requests are made requesting space that is of size smaller than the chunk. 

- Most of the allocators use a corollary mechanism called the coalescing of the free space. 

- Suppose a small heap is given and an application calls a function to obtain some memory. 

- This function returns the space available in the middle of the heap. 

- All these strategies are based up on simple policies. 

- An ideal allocator is the one that both minimizes fragmentation and is fast. 

- But since it is possible for the stream of free requests and allocation to be arbitrary, any strategy would go wrong if wrong inputs are given. 

- Thus, the best approach cannot be described. 

There are 4 major approaches in this regard:

1. Best fit: 

- Simplest and first searches the list for free chunks of memory that might be bigger than the size requested. 

- The smallest one in the searched ones is returned and this is known as the best fitting chunk or smallest fitting too. 

- One pass is enough for finding the appropriate block to be returned.

2. Worst fit: 

- This one is just the opposite of the best fit. 

- It looks for the largest chunk and returns the amount requested while keeping the remaining memory space.

3. First fit: 

- This one also looks for the first bigger block and out of it allocates the amount requested by the thread.

4. Next fit: 

- Here, one extra pointer is kept at the location where the last search was done. 

Explain the methods for free space management? – Part 1

- For efficient working of the programs and the entire operating system, it is important that the memory of the system should be managed. 

- When the files and programs are allocated memory space, some free space is left in the storage area. 

- It is required that these free spaces must be managed properly. 

- Since there is a limitation to the disk space, this same space has to be used again and again after deleting and creating new files. 

- A free space list is maintained by the operating system for keeping the track of the available free space. 

- All the free disk spaces are listed in free space list. 

- For the creation of a new file this free space list is searched in order to get the amount of space needed and then if the space is available, it is allocated to the file to be created. 

- In the case of deletion, after deleting the file, its space is added to the list of free spaces.

Methods for Free Space Management

There are 4 methods for the management of free space namely:

- Bit vector

- Linked list

- Grouping

- Counting

What is Bit Vector?

- Quite a many times, the free space list about which we mentioned above, is implemented as the bit vector (also known as the bitmap). 

- Here, 1 bit is used for representing each block. 

- If a particular block has been allocated to some file or program, its representative bit is set to 0 and when the block is available, the bit is set to one.

- Consider an example, suppose the following disk blocks are free and rest are allocated: 1, 2, 4, 5, 6, 7, 9, 10, 12, 13, 14, 18, 19, 21, 26, 27, 28. 

- Then for this allocation we have the following free – space bit map:

01101111011011100011010000111…

- This method of free space management is relatively simple and has good efficiency. 

- This method is known for its efficiency to locate the n consecutive free blocks or the first free block available in the storage area. 

- But this method can be inefficient if it is not kept in the main memory of the system. 

- Also, when required occasionally for the recovery needs, this map can also be written to the disk. 

- Keeping such maps in the physical memory is an easy thing if the system has a small memory but this is not always possible in the case of the systems with larger memories.

What is a Linked list?

- In this method, all the free spaces are linked together and the first block in this linked list is assigned a pointer which is stored in the cache memory. 

- Similarly, the pointer to the second block is stored in the first block.

What is Grouping?

- This method is a modified version of the free list approach and it stores the addresses of the all the free blocks in the first block that is free. 

- Here, actually the first n- 1 blocks only are free and the address of another n free blocks is stored in the last block. 

- This lets the system to find the addresses of a number of free blocks which is not possible in the case where the approach being used is the linked list approach.

What is Counting?

- This approach takes advantage of the simultaneous allocation or freeing of the contiguous blocks through clustering or by using contiguous allocation algorithm. 

- Thus, it requires only to keep the address of the first free block and the rest of the blocks follow it. 

Explain the structure of the operating systems.

We all are addicted to using computers but we all never really bother to known what is actually there inside it i.e., who is operating the whole system. Then something inevitable occurs. Your computer system crashes and the machine is not able to boot. Then you call a software engineer and he tells you that the operating system of the computer has to be reloaded. You are of course familiar with the term operating system but you know what it is exactly. 

About Operating System

- Operating system is the software that actually gives life to the machine. 

- Basic intelligence is the requirement of every computer system to start with. 

- Unlike we humans, computers do not have any inborn intelligence. 

- This basic intelligence is required because this is what the system will use to provide essential services for running the programs such as providing access to various peripherals, using the processor and allocation of memory and so on. 

- One type of service is also provided by the computer system for the users. 

- As a user, you may require to create, copy or delete files. 

- This is the system that manages the hardware of the computer system. 

- It also sets up a proper environment in which the programs can be executed. 

- It is actually an interface between the software and the hardware of the system.

- On booting of the computer, the operating system is loaded in to the main memory. 

- This OS remains active as long as the system is running. 

Structure of Operating Systems

- There are several components of the operating system about which we shall discuss in this article.

- These components make up the structure of the operating system.

1. Communications: 

- Information and data might be exchanged by the processes within the same computer or different computers via a network. 

- This information might be shared via memory if in the same computer system or via message passing if through some computer network. 

- In message passing, the messages are moved by the operating system.

2. Error detection: 

- The operating system has to be alert about all the possible errors that might occur. 

- These errors may occur anywhere ranging from CPU to memory hardware devices in the peripheral devices in the user application. 

- For all types of error, proper action must be taken by the operating system for ensuring that correct and consistent computing takes place. 

- The users and the abilities of the programmers are enhanced greatly by the debugging facilities.

3. Resource allocation: 

- Resources have to be allocated to all of the processes running. 

- A number of resources such as the main memory, file storage, CPU cycles etc have some special allocation code while other resources such as I/O devices may have request and release codes.

4. Accounting: 

- This component is responsible for keeping the track of the computer resources being used and released.

5. Protection and Security: 

- The owners of data and information might want it to be protected and secured against theft and accidental modification.

- Above all, there should be no interference of the processes with working of each other. 

- The protection aspect involves controlling the access to all the resources of the system. 

- Security involves ensuring safety concerning user authentication in order to prevent devices from invalid attempts.

6. Command line interface or CLI: 

- This is the command interpreter that allows for the direct entry of the command. 

- This is either implemented by systems program or by the kernel.

- There are a number of shells also for multiple implementations.

7. Graphical User Interface: 

This is the interface via which the user is actually able to interact with the hardware of the system. 

Define a system call? List the different types of the system calls?

- A program can request for services from the kernel of the operating system through a system call. 

- These services include all the following:

1. Hardware related services such as data access from the HDD.
2. Creation and execution of processes
3. Communication with integral services of the kernel such as scheduling.

- An essential interface is provided by the system call that lies between the operating system and the process. 

- The modern microprocessor architecture consists of a security model specifying multiple levels of privileges for the execution of the software. 

- For example, a program has limitations of its own address space so even by accident it does not modify or access the programs that are executing or the OS. 

- This way the direct manipulation of the hardware devices (such as the network devices and frame buffer etc.) by the program will also be avoided. 

- However, this is not the only case.

- There are situations where the programs really need access to these devices. - This is why the system calls are made available to the programs. 

- System calls ensure that such operations are safely implemented and are well defined. 

- The level at which the operating system executes is the highest privilege level.

- Therefore, the applications requests for the devices to the operating system through the system calls. 

- The execution of the system calls is carried out through the interrupts that would automatically put the CPU at the required level of the privilege. 

- After this, the control is passed on to the kernel. 

- From here the kernel determines whether or not the requested service should be granted to the calling program. 

- If the program is granted the service it requested, a specific instruction set is executed by the kernel which cannot be directly controlled by the calling program.

- These instructions return the privilege level down to that of the program that invoked the call. 

- Finally, the control is returned to the calling program.

- Generally, an API or a library is provided between the operating system and the normal programs. 

- The purpose of this library is to provide wrapper functions for the calls. 

- The names of these functions are same as that of the system calls. 

- The purpose of these functions is to expose a subroutine through which the system call can be used.

- These functions also provide modularity to the system call. 

- But above all, the primary function of the wrapper is placing the arguments in their proper processor registers that are to be passed on to the system call.

- A unique system call number is set that will be called by the kernel. 

- In this way, the portability is increased by the help of this library.

- Making direct system calls in the code of the application is very difficult and so requires embedded assembly code.

- In systems based up on ex-kernel, library is as important as the intermediary as they provide resource management, abstractions and shields the application from a low level kernel. 

- A control transfer involving features specific to the architecture is required for the implementation of the system call. 

- A way of implementing this is by using a software trap. 

- RISC processors can only use the implementation technique via interrupts. 

- But there are some other additional techniques for processors with CISC architectures. 

- One example is of the following two sets developed independently by Intel and AMD respectively for serving the same purpose:

SYSRET/ SYSEXIT

SYSCALL/ SYSENTER

- These were actually control transfer instructions and very fast indeed. 

What is a thread? What is meant by multi-threading?

About Thread

- A thread is a smaller instance of a process i.e., a sequence of instructions and an operating system scheduler can manage it independently. 

- A thread is sometimes also called as the light weight process. 

- The way these threads and processes are implemented is different for different operating systems. 

- But in majority of the cases threads are contained within a process. 

- The same process can have more than one thread. 

- These threads have to share the resources including memory while different processes may not share these. 

- In simple words, we can say that the instructions or code and the context or the values of the process are shared by its constituting threads. 

In this article we focus on threads and multi-threading.

- Multi-threading is a task of multiprocessor systems.

- But even single processor systems can do it by time division multiplexing just like the multitasking. 

- In TDM context switch occurs between the many threads. 

- This happens many times and so it seems to the user that a number of processors are being executed concurrently.

- However, in multiprocessor systems concurrency can be truly achieved since every processor processes one thread and so many threads are executed simultaneously. 

- Both multiprocessor and time threading is supported by most of the modern operating systems with help from the process scheduler. 

- The threads can only be manipulated through a system and this all is facilitated by the kernel of the operating system. 

- This is why some implementations have been named as the kernel thread. 

- An example of kernel thread is the LWP or the lightweight process and it shares same state as well as info. 

- Some programs even use user space threads when threading with the help of signals and timers etc. 

- These programs perform a kind of ad hoc time slicing. 

- Some may take threads and processes to be the same but there is a considerable difference between the two:

1. Processes are independent whereas the threads are a subset of the processes.
2. More state information is contained in threads whereas the same process state, resources and memory are shared by all the threads contained in that process.
3. Address spaces of different processes are different whereas the same address space is also shared by the threads.
4. IPC or the inter–process communication is the only medium for the processes to communicate with each other.
5. The threads within the same process are switched with context switch which is faster than that of the processes.

Features of Multi-threading

- Multi-threading is now among the widespread programming models. 

- The major characteristic feature of this model is that multiple threads can execute within the same process context. 

- Even though the resources of the process are shared by the threads, they execute independently. 

- The most widespread application of this model is in parallel computing.

- Full advantage of this technology can be taken only when it is applied to a multiprocessor system or a distributed system. 

- This is so because the program threads have a natural tendency to heed to the true concurrent execution. 

- But in these cases, necessary precautions must be taken for avoiding the race conditions and other undesirable behavior. 

- For the correct manipulation of data thread synchronization is also important. - Mutually exclusive operations are another requirement of the threads for preventing the simultaneous modification of the common data. 

- If these primitives are used carelessly, then it can lead the system to a deadlock. 

- Another feature of multi-threading is that it is always responsive to I/P. 

- This can be contrasted with the single threaded applications where if one block occurs, the whole program freezes.

What are features of Hyper-Threading technology?

The HT technology or the hyper–threading technology is a proprietary SMT (simultaneous multi–threading) implementation developed by Intel in order to make improvements in the pluralization of the computations that are carried out by the microprocessors in PC. It was first included in the Xeon server processes and then in Pentium 4 processors, atom, Itanium, core I series etc. Two logical or virtual cores are addressed by the operating system for each physical processor core present. The workload is shared among these two whenever required and possible.

Features of Hyper Threading Technology

1. Hyper–threading technology reduces the number of instructions in the pipeline that are dependent in nature. This is also its main purpose.
2. Architecture: The hyper – threading technology is based on the super scalar architecture. This kind of architecture is capable of operate multiple instructions in parallel with separate data. It appears as if there are two processors, thus letting the OS operate with two processes simultaneously.
3. Resource sharing: The same resources can be shared by the two or more processors available. Re–allocation of the resources can be done up on the failure of one of the processes.
4. Support for SMT: Hyper–threading implies the support for SMT through an OS that is SMT supportable. The OS needs to be specially optimized for this technology. It is recommended by Intel to disable the HTT if the OS have not been optimized for HTT.
5. Two processors: Certain processor sections are duplicated by the HTT. These are the sections in which the architectural states are stored. The main execution resources are not duplicated. Because of this, the HT processor appears as two processors to the OS namely, the physical and the logical processor. So the OS is able to process two threads at the same time without messing up. When a current task is not using the execution resources and the HTT and when the processor is stalled (because of data dependency, cache miss or branch mis-prediction), those resources can be used by the HT processor in execution of some other task scheduled earlier.
6. Support for SMP: SMP stands for symmetric multiprocessing which is mandatory for taking full advantage of the hyper – threading processing.
7. Transparency: There is a lot of transparency between the OS, its programs and this technology.
8. Easy optimization: HTT allows easy optimization of the behavior of the OS on HTT capable systems running on multiprocessors.
9. Provides support for multi–threaded code thus improving both the response time and reaction.
10. Application – dependent performance: It works well in improving the performance of most of the MPI applications. The improvement in the performance depends largely on the nature of the running application and its cluster configuration. The performance gain can also be negative. Using performance tools would be beneficial for understanding the factors contributing to performance gain and degradation.
11. Security: A timing attack can be used by some malicious thread for monitoring the other thread’s memory access patterns. This is nothing but the stealing of the cryptographic info. This can be avoided by changing the cache eviction strategy of the processor. 

The hyper – threading technology has been criticized heavily for being energy inefficient. It has been stated by ARM that power consumption in SMT is more than in the dual – core designs by a margin of 46%. It was also claimed that cash thrashing is also increased by a margin of 42% in SMT when compared to a 37% decrease in the case of dual core processors. However, on the other side, Intel has claimed the HTT to be highly efficient since it puts the ideal resources to use. 

What are different types of operating system?

Developing an operating system is one of the most complicated activities and favorite of most of the computing hobbyists. For a hobby OS, its code is not directly derived from the already existing Oss. Some entirely new concepts might also be included in the OS development. It may also start from modeling an existing one. Whatever the case maybe, the hobbyist is his own active developer. Application software might be developed specifically for an OS or hardware. Therefore, when the application has to be ported to some OS that may implement its required functionality differently, the application might be required to be changed, adapted or maintained. 

Types of Operating System

There are many types of operating about which we shall discuss in this article.

1. Real time operating system: 

- It is a multi – tasking OS aimed at the execution of the applications that are real time. 

-These operating systems work on scheduling algorithms written exclusively for them. 

- This is done so as to make them achieve a behavior that is deterministic in nature. 

- Their main objective is to give a quick response to the events that is also predictable in nature. 

- The design which is implemented is event driven and employs the idea of time sharing and sometimes both. 

- The system that is event driven switches among the different tasks according to the priorities assigned to them. 

- On the other hand, the systems following the time sharing methodology switch between the tasks based up on the clock interrupts.

2. Multi–user and single user operating systems: 

- In the multi–user operating systems the same computer system can be accessed by multiple users at the same time. 

- Systems that can be classified under the multi–user systems are the internet servers and the time sharing systems since using the time sharing principle they allow multiple users to access the system. 

- There are other types of operating systems that allow only one user to execute a number of programs simultaneously and are called the single – user operating systems.

3. Multi–tasking and single–tasking operating systems: 

- The operating systems that allow multiple programs to be executed simultaneously (as per the human time scales) are termed as the multi – tasking OS.

- In the single–taking OS, only one program can be run at a time. 

- Multi –taking can be done in the following two ways:

Ø  Pre–emptive multi –tasking: The CPU time is sliced and each of the time slots are given to each of the programs that are to be executed. This kind of multi–tasking is supported by the operating systems such as Linux, AmigaOS and Solaris.

Ø  Co–operative multi–tasking: Systems following this rely on one process for giving time to the other processors but in a pre–defined manner. This multi–tasking type was used by the MS windows 16 – bit version, Mac OS preceding OS X.

There are Oss that used to support both of these namely win9x and Windows NT.

4. Distributed operating system: 

- This kind of OS is used to manage a group of computers that are independent of each other and makes them seem like one single system.

- This OS led to the development of networked computers which could link to and communicated with one another.

- These computers in turn paved way for distributed computing. 

- They carried out computations on more than one computer. 

- Computers working in cooperation with each other, together make up a distributed system.

5. Embedded Operating System: 

It is used in embedded computer systems such as in PDAs.

What is an Operating System?

- A collection of small and large software that help in the management of the computer hardware resources is called an operating system. 

- As the term suggests it operates or drives the system. 

- The basic common services required by the computer programs are offered by this OS only. 

- Without an OS, the application programs would fail to function. 

- Operating systems are of many types. 

- One such type is the time sharing OS that schedules the tasks to be done so that the processor time, printing, mass storage and so on resources could be utilized efficiently. 

- It is an intermediate thing between the hardware and the user. 

- It is through the OS that you are able to actually communicate with the computer hardware. 

- Functions such as memory allocation and basic input output operations are dependent totally on the OS. 

- Even though the hardware directly executes the application code, it does frequently involve the OS or OS itself interrupts in between. 

- Any device containing a computer do has an OS such as video game consoles, mobile phones, web servers, super computers and so on.

- Some popular OS are:

Ø  Android

Ø  BSD

Ø  Linux

Ø  iOS

Ø  Microsoft windows

Ø  Windows phone

Ø  Mac OS X

Ø  IBM z/ OS

All the OS have relation with UNIX save windows and z/OS.

- Types of Operating systems are:

1. Real time OS
2. Multi – user OS
3. Multi – tasking OS
4. Single  - tasking OS
5. Distributed OS
6. Embedded OS

- It was in 1950 that the basic operating systems came in to existence such as parallel processing, interrupts and run time libraries.

- Assembly language was used for writing the UNIX OS. 

- There are many sub–categories in the Unix like family of the operating systems:

1. System V
2. BSD
3. Linux and so on.

- A number of computer architectures are supported by these Unix – like systems. 

- They come in heavy use in the following fields:

1. Servers in business
2. Work stations in academic
3. Engineering environments

- Few UNIX variants are available for free such as BSD, Linux etc. and are quite popular. 

- The holder of the Unix trademark is the open group and it has certified four Oss as Unix so far. 

- Two of the original system V Unix descendants are IBM’s AIX and HP’s HP – UX and they run only on the hardware provided by their manufacturer. 

- Opposite to these is the sun microsystem’s Solaris OS that can be used on different hardware types (inclusive of the Sparc and x86 servers etc. and PCs). - The POSIX standard was established to the sought the inter-operability of the Unix. 

- This standard is applicable for any OS now, even though originally it was developed especially for the variants of Unix.

- Berkeley Software Distribution or BSD family is a Unix sub–group. 

- It includes the following:

1. FreeBSD
2. NetBSD
3. OpenBSD

- The major use of all of these is in the web servers. 

- Furthermore, they are also capable of functioning as a PC OS. 

- BSD has made a great contribution in the existence of the internet. 

- Most of the protocols were refined and implemented in BSD. 

What is the difference between Purify and traditional debuggers?

The IBM Rational Purify grants power to the developers to deliver a product whose quality, reliability and performance matches with the expectations of the users. The purify plus combines the following and provides 3 benefits:

1. Bug finding capabilities from the rational purify,
2. Performance tuning effects from the rational quantify and
3. Testing rigors from the rational pure coverage.

Together these three things make purify a different debugger that what the traditional debuggers we have. The above mentioned 3 benefits are measured in the terms of the faster development times, less number of errors and better code. 

About IBM Rational Purify

- The purify is actually a memory debugger by nature and is particularly used for the detection of the memory access errors especially in the programs that have been written in languages such as C and C++. 

- This software was originally developed by Reed Hastings, a member developer of the pure software organization. 

- However, Rational Purify exhibits the similar functionality as that of the Valgrind, bounds checker, Insure++.

- A process called dynamic verification using which the errors that occur during the execution can be discovered by a program is supported by the rational purify just like a debugger.

- However, there is another process called the static verification which is just the opposite of the dynamic verification and is also supported by the rational purify. 

- This process works by digging out inconsistencies present in the program logic. 

- Whenever there is a linking between a program and purify, the correct version of the verified code is automatically inserted in to the executable part of the code by either adding it to the object code or by parsing. 

- So, if whenever an error occurs, the location of the error, its memory address and other relevant info will be printed out by the tool. 

- Similarly, whenever a memory leak is detected by the purify it generates a leak report towards the exit of the program.

Difference between Rational Purify and Traditional Debuggers

- The major difference between the rational purify and the traditional debuggers is the ability of detecting the non – fatal errors. 

- The traditional debuggers only show up the sources which can cause the fatal errors such as a de-referencing to a null pointer can cause a program to crash and they are not effective in finding out the non – fatal memory errors. 

However, there are certain things for which the traditional debuggers are more effective than the rational purify for e.g., 

- The debuggers can be used to step line by line through the code and to examine the memory of the program at any particular instance of time. 

- It would not be wrong if we say that these two tools are complementary to each other and can work great for a skilled developer. 

- The purify comes with other functionality which can be used for more general purposes rather than the debuggers which can be used only for the code.

- One thing to be noted about the purify is that it is more effective for the programming languages in which the memory management is left to the program developer. 

- This is the reason why the occurrence of the memory leaks is reduced in the programs written in languages such as java, visual basic and lisp etc. 

- It is not like these languages will never have memory leaks, they do have which occur because of the objects being referred to unnecessarily (this prevents the re – allocation of the memory.). 

- IBM has provided solution for these kind of errors also in the form of its another product called the rational application developer.

- Errors such as the following are covered by the purify:

1. Array bounds
2. Access to un-allocated memory
3. Freeing the memory that is un-allocated
4. Memory leaks and so on.