Memory Management

  • Aim Of Chapter:

    • This chapter provides you with overview of the fundamental mechanisms used in Memory Management (MM) in any operating system
  • Memory management: the task of dividing the computer memory in order to accommodate processes
  • Any MM System Should Provide:

    • Relocation:

      • Ability to allocate memory for swapped processes when they came back into memory
    • Protection:

      • Ability to protect process memory from interference by other processes. Programs in other processes shouldn’t be able to reference memory locations in a process without permissions
      • The memory protection requirement must be satisfied by the processor rather than OS
    • Sharing:

      • Ability to allow several processes to access to access same portion of main memory
    • Logical Organization:

      • Ability to deal with programs as modules
      • Advantages of this feature:

        • Modules can be written and compiled independently
        • Few data overhead will be added to specify the module degree of protection
        • Sharing modules is more easier to the user because it’s his way to view the problem
      • Segmentation is the most readily MM mechanism that satisfies these conditions
    • Physical Organization:

      • Ability to organize flow of information between main memory and secondary memory
      • If this task is assigned to the programmer many disadvantages appear as:

        • The main memory available for a program plus it’s data may be insufficient

          • So the programmer will solve this problem using overlaying in which the program data should be organized in a way that all modules could share them
        • In multiprogramming environments, programmer doesn’t know amount of free space
  • Before reading the coming info read the table at the next page first
  • Fixed Partitioning:

    • Disadvantages:

      • If a program size doesn’t fit with the partition size, programmer should design the program with use of overlays so that only one portion of the program need to be in memory
      • The number of fixed partitions specify the number of active processes (not suspended)
    • These disadvantages are lessened by dynamic partitioning
    • This technique is not used nowadays and one of the successful OS that did use it was early IBM mainframe OS OS/MFT (Multiprogramming with a Fixed number of Tracks)
  • Dynamic Partitioning:

    • OS that was using this technique IBM’s mainframe OS, OS/MVT (Multithreading Variable # of Tracks)
    • Problem of external fragmentation is solved using compaction: from time to time OS shift processes so they are contiguous and free the unused memory in one block (this is time consuming and wasteful of processor time) also the MM should supply reallocation because all the processes will be shifted
    • Placement algorithms: First Fit, Best Fit and Next Fit

      • Next Fit: begins to scan memory from the location of the last placement and choose next suitable block
  • When using First-Fit compaction is needed frequently because at the end of the memory space is quickly broken up into small fragments
  • Memory Management Techniques:

  • Buddy Systems:

    • Here, the memory blocks are available of size words, , where:

      • smallest size block that is allocated
      • largest size block that is allocated; generally is the size of entire available memory
    • A modified form of buddy systems is used for UNIX kernel memory allocation
  • Logical address: reference to memory location independent of the current assignment of data to memory
  • Relative address: reference to memory location relative to known point usually a value in processor register
  • Physical address (absolute address): actual location in main memory
  • Working mechanism is displayed in the below figure:

  • One of advantage of the relative addressing is that each process image is isolated by the contents of base and bounds registers and safe from unwanted access by other processes
  • Simple Paging:

    • Before read this section please read the row of the simple paging in the previous table
    • OS holds the free frames in a list
    • Page Table is a table for each process that shows the frame location for each of the process pages
    • Within a program each logical address consists of a page number and offset within this page
    • The processor uses the page number/offset to produces frame/offset
    • Page size (hence frame size) is recommended to be a power of 2
    • Hardware Calculations for accessing memory using logical address n/m:

      • Extract page # as left most n bits of the logical address
      • Use page number as an index into the process page table to find it’s frame # k
      • The starting physical address of the frame is . The physical address of referenced byte is that number plus the offset
  • Simple Segmentation:

    • Before read this section please read the row of the simple segmentation in the previous table
    • Process segments could vary is length. Also there’s a max. segment length
    • Here the logical address consists of segment number and offset
    • Here the programmer should divide the program into segments and should take care of max. length
    • Address translation in segmentation:

      • Extract segment # as the left most n bits of the logical address
      • Use segment # as an index in the process segment table to find segment physical address
      • Compare offset (right most m bits) with the length of the segment
      • The desired physical address is the sum of the starting physical address of segment + offset
  • Buffer Overflow:

  • Buffer overflow occurs when a processes attempts to store data beyond the limits of a fixed-size buffer and consequently overwrites adjacent memory location. These locations could hold other program variables or data
  • The buffer could be located into: stack, heap or in the data section of the process
  • Stack overflow is a type of buffer overflow attacks
  • Further reading (Fuzzy): How could attacker break a password and get into the system (page 334)
  • Countermeasures:

  • Compile-time defines, which aim to harden programs to resist attacks in new programs
  • Run-time defines, which aims to detect and abort attacks in existing programs

Buffer Overflow

In computer security and programming, a buffer overflow, or buffer overrun, is an anomalous condition where a process attempts to store data beyond the boundaries of a fixed-length buffer. The result is that the extra data overwrites adjacent memory locations. The overwritten data may include other buffers, variables and program flow data, and may result in erratic program behavior, a memory access exception, program termination (a crash), incorrect results or ― especially if deliberately caused by a malicious user ― a possible breach of system security.

Buffer overflows can be triggered by inputs specifically designed to execute malicious code or to make the program operate in an unintended way. As such, buffer overflows cause many software vulnerabilities and form the basis of many exploits. Sufficient bounds checking by either the programmer, the compiler or the runtime can prevent buffer overflows.

The programming languages most commonly associated with buffer overflows are C and C++. They provide no built-in protection against accessing or overwriting data in any part of memory and do not check that data written to an array (the built-in buffer type) is within the boundaries of that array.

For more information visit the the link: Buffer Overflow

Overlay

In a general computing sense, overlaying means "replacement of a block of stored instructions or data with another" Overlaying is a programming method that allows programs to be larger than the central processing unit‘s main memory. An embedded system would normally use overlays because of the limitation of physical memory, which is internal memory for a system-on-chip.

The method assumes dividing a program into self-contained object code blocks called overlays. The size of an overlay is limited according to memory constraints. The place in memory where an overlay is loaded is called an overlay region or destination region. Although the idea is to reuse the same block of main memory, multiple region systems could be defined. The regions can be different sizes. An overlay manager, possibly part of the operating system, will load the required overlay from external memory into its destination region in order to be used. Some linkers provide support for overlays

Overlay programming requires the program designer to be very aware of the size of each part of the program. This meant using programming languages or assemblers that allow the designer or architect control over the size of the program and more importantly, the size of the overlay. This constraint added many design difficulties that do not exist with virtual memory.

As of 2007, most business applications are intended to run on platforms with virtual memory. A developer on such a platform can design a program as if the memory constraint does not exist unless the program’s working set exceeds the available physical memory. Most importantly, the architect can focus on the problem being solved without the added design difficulty of forcing the processing into steps constrained by the overlay size. Thus, the designer can use higher-level programming languages that do not allow the programmer much control over size (i.e. Java, C++, Smalltalk).

Still, overlays remain popular in embedded systems because many cannot use virtual memory. When a program enters a part that has been paged out, the virtual memory may not respond in time, causing a real-time computing system to miss deadlines. The delay of loading an overlay is more predictable. In addition, paging hardware is not without cost, and in many embedded systems sold in millions of units, the reduction in manufacturing costs from simpler hardware outweighs the extra cost of programmer time. Even on platforms with virtual memory, software components such as codecs may be decoupled to the point where they can be loaded in and out as needed.

Overlays as a solution is the past operating systems and the programmer was suffering from this issue

Principle of Locality

When a program executes on a computer, most of the memory references are not made uniformly to a small number of locations. Here the Locality of the reference does matter.
Locality of Reference, also known as the Principle of Locality, the phenomenon of the same value or related storage locations being frequently accessed. Locality occurs in time(temporal locality) and in space (spatial locality).

  • Temporal Locality:
    • refers to the reuse of specific data and/or resources within relatively small time durations.
  • Spatial Locality:
    • refers to the use of data elements within relatively close storage locations. Sequential locality, a special case of spatial locality, occurs when data elements are arranged and accessed linearly, eg, traversing the elements in a one-dimensional array.

To be very simple when exhibiting spatial locality, a program accesses consecutive memory locations and during temporal locality of reference a program repeatedly accesses the same memory location during a short time period. Both forms of locality occur in the following Pascal code segment:

  for i := 0 to 10 do   A [i] := 0;
In the above Pascal code, the variable 'i' is referenced several times in for loop where
'i' is compared against 10 to see if the loop is complete and also incremented by one at the end of the loop.
This shows temporal locality of reference in action since the CPU accesses 'i' at different points in a short time period.
This program also exhibits spatial locality of reference. The loop itself zeros out the elements of array A by writing a zero
to the first location in A, then to the second location in A, and so on. Assume Pascal stores elements of A into consecutive
memory locations then on each loop iteration it accesses adjacent memory locations.

Process Description and Control

 

  • Aim Of article:
    • OS keeps track of the process state by elaborate data structure describing each process. This article looks at the data structures and techniques used in a typical OS for process management
  • Process Definition:
    • A program in execution
    • An instance of a program running on a computer
    • The entity that can be assigned and executed on a processor
  • Process consists of:
    • Program Code
    • Set of data
    • Process control block
  • While the program is running process can specified by the Process Control Block (PCB) that contains:
    • Identifier: as ID number
    • Program Counter: the address of next instruction in the program to be executed
    • Memory Pointers: includes pointers to:-
      • Program code
      • Data associated with the process
      • Memory blocks shared with other processes
    • Context Data: data in the processor registers while the process executing
    • I/O Status Info: includes I/O requests, devices assigned to this process and files used by process
    • Accounting Info: includes amount of processor time, clock time used and time limits
    • State, Priority
  • Process Trace: the sequence of instructions that the process will execute
  • Dispatcher: OS Program that switches between processes
  • Reasons for process creation:
    • New patch job: a process is created in response to the submission of a job
    • Interactive logic: a process is created when a new user attempts to log on
    • Provide a service: when a program request a service (i.e. printing a paper(s))
    • Spawned by other process: Dictated by a user program (former called parent spawned as child)
  • Reasons for process termination:
    • Memory unenviable: the process requires more memory than the system can provide
    • Protection error: the process attempts to use protected resource (i.e. write to read-only file)
    • Time overrun: the process has waited longer than max. time for a certain event to occur
    • Invalid instruction: attempting to execute invalid instructions (i.e. executing data)
    • Privileged instruction: attempting to use an OS reserved instruction
    • Data misuse: using an uninitialized data or not suitable data type
    • Operator or OS intervention: terminated by OS (i.e. if deadlock happened)
    • Normal completion, time limit exceeded, bounds violation, arithmetic error, I/O failure
    • Parent termination, parent request
  • Process States:
    • Two-State Model: running and not running
    • Five State Model: new, ready, running, blocked, exit
  • Round-Robin:
    • Process is given amount of time, in turn to execute and then return to queue unless blocked
  • When the process is at the new state it’s program remains on the secondary storage
  • Preempted Process means that moving this process from running to ready state for priority reason
  • Blocked/Suspended State: The process in the secondary memory and awaiting an event
  • Ready/Suspended State: The process in the secondary memory and ready for execute
  • Reasons for process suspension:
    • Other OS Reasons: as if the process in a deadlock
    • Interactive user request, swapping, timing, parent process request
  • General structure of OS control tables:
    • Memory:
      • Used to keep track of the main and secondary memory
      • Memory tables must indicate the following information:
        • The allocation of main/secondary memory to process
        • Any protection attributes of blocks of main or virtual memory: sheared memory
        • Any information needed to manage virtual memory
    • Devices, Files and Processes
  • Process Control Structures: these knowledge are important so the OS can manage the processes
    • Process Location:
      • Process Image: the collection of program, data, stack and attributes (PCB)
    • Process Attributes (Process Control Block):
      • Process Identification: ID, parent ID and user ID
      • Process State Information:
        • User Visible Registers: EAX, EBX …
        • Control Status Registers: PC, Condition Codes (EFLAGS) and Status Information
        • Stack Pointers
      • Process Control Information:
        • Scheduling and State info: State, priority, scheduling info and event
        • Interprocess Communication:
          • Info related to the process communication with other processes
        • Process Privilege: contains accessible memory and valid type of instructions
        • Memory Management: pointers to the virtual memory used by this process
        • Resource ownership utilization: info about the resources used by the process
        • Data Structuring
  • The mode of processor execution is determined by the PSW
  • OS creates new process by:
    • Assign unique process ID to the new process
    • Allocate space for the process
    • Initialize the process control block
    • Set appropriate linkages: put the process in its appropriate queue (ready/ suspended…)
    • Create or expand other data structures
  • System Interrupts Types:
    • Interrupt:
      • Relates to the external from the current process (i.e. I/O operation)
    • Trap:
      • Relates to an errors or exception condition generated within currently running process
    • Supervisor call
  • The interrupt handler does the following as housekeeping to OS routine:
    • Clock Interrupt: OS determines if process has work for it’s specified max time limit or not
    • I/O Interrupt: changing processes states that is waiting for the current I/O action
    • Memory Fault:
      • When the OS encounters a null memory address then the process is blocked till data come
  • If an interrupt is pending then the processor does the following:
    • Sets the PC to the starting address of the interrupt handler
    • Switches the processor mode to kernel mode
  • Steps involved in process switching:
    • Save the contexts of the processor (PC and other registers)
    • Update the PCB of the current running process (state, reason of leaving)
    • Move the PCB of this process to the appropriate queue
    • Select another process for execution
    • Update PCB of the selected process
    • Update memory management data structures
    • Restore the context of the processor to that which existed at the time the selected process running
  • Execution of the OS processes:
    • Non-process Kernel
    • Execution within user process
      • Here the process image will also holds the program, data and stack of the kernel programs
    • Process Based OS
  • Security Issues:
    • System Access Threats
      • Malicious Software:
        • Parasitic: malware that depends on other program to work (virus, logic bombs)
        • Independent self-contained programs that can be operated by OS (Worms, bot)
      • Intruders (hacker or cracker):
        • Masquerader:
          • An individual who is not authorized to use the computer and access it to exploit legitimate user account
        • Misfeasor:
          • A legitimate user that access unauthorized data or misuse of authorized data
        • Clandestine user:
          • System supervisor who use his authority to evade from auditing and control
      • Intrusion Detection Systems (IDS):
        • Host-based IDS: monitor the host for suspicious activities
        • Network-based IDS: monitor the network for suspicious activities
      • IDS Logical Components:
        • Sensors:
          • Responsible for collecting data from network packets, log files, system call , send them to analyzer
        • Analyzer:
          • Responsible for determining if an intrusion occurred and provide info about what actions to take. Inputs from sensors and other analyzers
        • User Interface: enables the user to view output from the system or control behavior
    • Authentication
      • Any authentication process consists of tow steps:
        • Identification Step: as username
        • Verification Step: as user password

         

      • User Authentication Approaches:
        • Something the individual knows: password
        • Something the individual processes (token): smart cards, physical keys
        • Something the individual is (static biometrics): fingerprint, retina
        • Something the individual (dynamic biometrics): voice, handwriting

Access Control