Kotlin Language Features Related to Null Handling

-
Any software engineer with a Java background would find the null handling features in the Kotlin language interesting. Let's summarize this topic with some examples. Nullable types: In Kotlin, types are non-nullable by default. If you want a variable to be able to hold a null value, you need to explicitly declare its type as nullable using the Type? syntax. For example, String? denotes a nullable string, while String represents a non-nullable string. Safe calls (?.): Kotlin introduces the safe call operator (?.) for handling nullable types. It allows you to safely invoke a method or access a property on a nullable object. If the object is null, the expression returns null instead of throwing a NullPointerException. Example: data class Person(val name: String, val age: Int, val address: String?) fun main() {     // Create a person with a nullable address     val person1 = Person("John Doe", 25, "123 Main Street")     val person2 = Person("Jane Doe", 30,
Post a Comment

Virtual Memory

-

The main memory can act as a “cache” for the secondary storage, usually implemented with magnetic disks. This technique is called virtual memory. There were two major motivations for virtual memory: to allow efficient and safe sharing of memory among multiple programs, and to remove the programming burdens of a small, limited amount of main memory.

Lets consider a collection of programs running all at once on a computer. Of course, to allow multiple programs to share the same memory, we must be able to protect the programs from each other, ensuring that a program can only read and write the portions of main memory that have been assigned to it. Main memory need contain only the active portions of the many programs, just as a cache contains only the active portion of one program. Virtual memory allows us to efficiently share the processor as well as the main memory.

We cannot know which programs will share the memory with other programs when we compile them. In fact, the programs sharing the memory change dynamically while the programs are running. Because of this dynamic interaction, we would like to compile each program into its own address space—a separate range of memory locations accessible only to this program. Virtual memory
implements the translation of a program’s address space to physical addresses. This translation process enforces protection of a program’s address space from other programs.

Protection:  A set of mechanisms for ensuring that multiple processes sharing the processor, memory,
or I/O devices cannot interfere, intentionally or unintentionally, with one another by reading or writing each other’s data. These mechanisms also isolate the operating system from a user process.

The second motivation for virtual memory is to allow a single user program to exceed the size of primary memory. In the past, if a program became too large for memory, it was up to the programmer to make it fit. Programmers divided programs into pieces and then identified the pieces that were mutually exclusive. These overlays were loaded or unloaded under user program control during execution, with the programmer ensuring that the program never tried to access an overlay that was not loaded and that the overlays loaded never exceeded the total size of the memory. This responsibility was a substantial burden on programmers. Virtual memory, which was invented to relieve programmers of this difficulty, automatically manages the two levels of the memory hierarchy represented by main memory (sometimes called physical memory to distinguish it from virtual memory) and secondary storage.

A virtual memory block is called a page, and a virtual memory miss is called a page fault. With virtual memory, the processor produces a virtual address, which is translated by a combination of hardware and software to a physical address, which in turn can be used to access main memory. This process is called address mapping or address translation.

Virtual memory also simplifies loading the program for execution by providing relocation. Relocation maps the virtual addresses used by a program to different physical addresses before the addresses are used to access memory. This relocation allows us to load the program anywhere in main memory. Furthermore, all virtual memory systems in use today relocate the program as a set of fixed-size blocks (pages), thereby eliminating the need to find a contiguous block of memory to allocate to a program; instead, the operating system need only find a sufficient number of pages in main memory.

offset: The number of address locations added to a base address in order to get to a specific absolute address. In this (original) meaning of offset, only the basic address unit, usually the 8-bit byte, is used to specify the offset's size. In this context an offset is sometimes called a relative address.

Example: Lets assume we have 12 bit for offset number. This means our page size is 2^12
Lets assume our virtual page number consists of 20 bits, so the number of pages allowed is 2^20
Lets assume our physical page number has 18 bits, so the number of pyhsical pages allowed is 2^18
The point is, number of virtual pages allowed is higher than the number or physical pages.

Many design choices in virtual memory systems are motivated by the high cost of a miss, which in virtual memory is traditionally called a page fault. This leads to several key decisions in designing virtual memory systems:
  • Pages should be large enough to try to amortize the high access time. Sizesfrom 4 KB to 16 KB are typical today.
  • Organizations that reduce the page fault rate are attractive. The primary technique used here is to allow fully associative placement of pages in memory.
  • Write-through will not work for virtual memory, since writes take too long. Instead, virtual memory systems use write-back.
Because of the incredibly high penalty for a page fault, designers reduce page fault frequency by optimizing page placement. If we allow a virtual page to be mapped to any physical page, the operating system can then choose to replace any page it wants when a page fault occurs. The ability of the operating system to use a clever and flexible replacement scheme reduces the page fault rate and simplifies the use of fully associative placement of pages.

The difficulty in using fully associative placement is in locating an entry, since it can be anywhere in the upper level of the hierarchy. A full search is impractical. In virtual memory systems, we locate pages by using a table that indexes the memory; this structure is called a page table, and it resides in memory. Each program has its own page table, which maps the virtual address space of that program to main memory. To indicate the location of the page table in memory, the hardware includes a register that points to the start of the page table; we call this the page table register.

The page table, together with the program counter and the registers, specifies the state of a program. If we want to allow another program to use the processor, we must save this state. Later, after restoring this state, the program can continue execution. We often refer to this state as a process. The process is considered active when it is in possession of the processor; otherwise, it is considered inactive.

The process’s address space, and hence all the data it can access in memory, is defined by its page table, which resides in memory. Rather than save the entire page table, the operating system simply loads the page table register to point to the page table of the process it wants to make active. Each process has its own page table, since different processes use the same virtual addresses. The operating system is responsible for allocating the physical memory and updating the page tables, so that the virtual address spaces of different processes do not collide.

Page Faults

If the valid bit for a virtual page is off, a page fault occurs. The operating system must be given control. This transfer is done with the exception mechanism. Once the operating system gets control, it must find the page in the next level of the hierarchy (usually magnetic disk) and decide where to place the requested page in main memory.

Because we do not know ahead of time when a page in memory will be replaced, the operating system usually creates the space on disk for all the pages of a process when it creates the process. This disk space is called the swap space.

The operating system also creates a data structure that tracks which processes and which virtual addresses use each physical page. When a page fault occurs, if all the pages in main memory are in use, the operating system must choose a page to replace. Because we want to minimize the number of page faults, most operating systems try to choose a page that they hypothesize will not be needed in the near future. Using the past to predict the future, operating systems follow the least recently used (LRU) replacement scheme,

Comments

Post a Comment

Popular posts from this blog

Trie Data Structure and Finding Patterns in a Collection of Words

-
Image
 I faced a very hard problem recently about finding substrings based on a collection of patterns.  Example For  words = ["Apple", "Melon", "Orange", "Watermelon"]  and  parts = ["a", "mel", "lon", "el", "An"] , the output should be  findSubstrings(words, parts) = ["Apple", "Me[lon]", "Or[a]nge", "Water[mel]on"] . While  "Watermelon"  contains three substrings from the  parts  array,  "a" ,  "mel" , and  "lon" ,  "mel"  is the longest substring that appears first in the string. Note: Number of words and number of parts can be huge! A brute force method or careless usage of Java String methods would make it impossible to handle a large number of words and parts (patterns). Solution Approach Whenever we want to search patterns inside a string, we should think about the Trie data structure:  https://en.wikipedia.
Read more

swapLexOrder: Finding lexicographically largest string

-
The following coding question is really amazing: Given a string  str  and array of  pairs  that indicates which indices in the string can be swapped, return the  lexicographically largest  string that results from doing the allowed swaps. You can swap indices any number of times. Example For  str = "abdc"  and  pairs = [[1, 4], [3, 4]] , the output should be swapLexOrder(str, pairs) = "dbca" . By swapping the given indices, you get the strings:  "cbda" ,  "cbad" ,  "dbac" ,  "dbca" . The lexicographically largest string in this list is  "dbca" . Input/Output [execution time limit] 3 seconds (java) [input] string str A string consisting only of lowercase English letters. Guaranteed constraints: 1 ≤ str.length ≤ 10 4 . [input] array.array.integer pairs An array containing pairs of indices that can be swapped in  str  (1-based). This means that for each  pairs[i] , you can swap elements in  str  that have the indices  p
Read more