Physiccal Memory Organisation and Address Generation

Intel introduced its first 4-bit microprocessor in 1971 and 8-bit microprocessor in 8008 in 1972. 

However, this microprocessor could not survive due to its design and performance limitations. 

Later, the launch of the first 8-bit general purpose registers 8080 in 1974 by Intel is considered to be the first stepping stone towards the development of advanced microprocessors. 

The microprocessor 8085 was followed by 8080, with a few more added features to its architecture, which resulted in a functionally complete microprocessor.

Some Basic Terminologies in 8086 Physical Memory Organization

Below are some basic terminologies that are used in 8086 Physical Memory Organization

Memory Segment

It is a portion of memory that is used to address the data and instructions.

Offset Address

It is a part of the address that is added to the segment address to point to a specific location inside the segment.

The logical address are used to calculate physical address.

For example: If the segment address is 1000H and offset address is 3000H then the memory location becomes 13000H( 10*1000H + 3000H)

Effective Address

It can be defined as the address of the data operand in the memory. It can be calculated from the formula

( Effective Address = Segment Register + Offset Address). 

In 8086 the segment registers are DS(Data segment), CS( code segment), ES( Extra Segment),SS (Stack segment).

Physical Address

It is defined as the actual address of the data or instruction where it is stored physically in the memory and calculated by (Physical Address = 10* segment Address + Offset Address).

Segmentation

It is a process of dividing the memory into segments and each segment can have a size of 64Kb( starting Address-0000H, last Address-FFFFH).

Brief Description About Physical Memory Organization

In 8086 one megabyte is physically organized as an odd bank and an even bank, each of 512Kbytes, addresses in parallel by a processor. Byte data with even address transferred on D7-D0 , while byte data with odd address is transferred on D15-D8 bus lines. To select an even or odd bank its has BHE and Ao as selector lines. Instruction stream is fetched from memory as words and is addressed internally by a processor. If it fetches a word from memory, the different possibilities are

1.     Both bytes may be data operands

2.     Both bytes may contain opcode

3.     One is opcode while other may be data

All these possibilities are taken care of by internal decoder circuit of microprocessor. This decoder detects the operand and data opcodes and derives the input for timing and control unit. The timing and control unit then derives signal required for execution of instruction. If the word is located in even address only one read or write cycle is required and if the word is located at odd address first read or write required for accessing lower byte while second one is required for accessing upper byte. Thus, two bus cycles are required if the word is located at an odd address.

8086 is a 16-Bit microprocessor and hence can access 2 bytes of data in one memory I/O read or write operation. But commercially available chips are only byte size i.e. they can store only one byte in memory location. To store 16-Bit data, two successive memory locations are used and lower byte of 16-Bit microprocessor is stored in first memory location while second byte is stored in next location. In 16-Bit read or write operation both of these bytes will read or write in single machine cycle. A map of 8086 memory system starts at 00000H and ends at FFFFFH. To achieve 16-Bit transfer using 8-Bit memory, in parallel map of system by the memory address will obviously be divided into memory bank as shown in the below figure.

Physical Memory Organization

16-Bit data is stored at first address of map 00000H and it is to be transferred over D0-D7 of microprocessor which is in 8-bit memory. Higher byte of 16-bit data is stored in next address 00001H, it is to be transferred over D8-D15 of microprocessor bus. It is to be observed that all lower bytes are stored at even address and higher address are stored at odd address. If 8086 transfers a 16-bit data from/to memory both even and odd banks are selected for 16-bit operation. However, to maintain an upward compatibility with 8085, 8086 must able to implement 8-bit operation. Two signals Ao and BHE solve the problem of selection of appropriate memory banks as shown in the following figure.

Bus high enable and Ao

Certain locations are reserved for specific CPU operations. Locations FFFF0H-FFFFFH are reserved for operation including jump to initialization program. Locations 00000H-003FFH reserved for interrupt vector table. The interrupt structure provides space for a total of 256 interrupt vectors and these vectors need 4-bytes for storing it in the interrupt table. Hence 256 types of interrupt require 003FFH (1 Kbyte) locations for the complete interrupt vector table.

Following are the examples to calculate Physical Address:

1. The code segment(CS) is at 1000H and the destination index(DI) is at 4000H the physical address can be calculated by

PA = CS * 10 + DI +Displacement(if any)

CS = 1000H

DI = 4000H

Displacement = 0

PA = 1000H* 10 + 4000H + 0

PA = 14000H

2. The data segment is present at 3000H and source index is at 3000H then the physical address is

PA = DS * 10 + SI + Displacement( if any)

DS = 3000H

SI = 3000H

Displacement = 0

PA = 3000H * 10 + 3000H +0

PA = 33000H 

Sets

 Sets in Python

A Set in Python is used to store a collection of items with the following properties.

·        No duplicate elements. If try to insert the same item again, it overwrites previous one.

·        An unordered collection. When we access all items, they are accessed without any specific order and we cannot access items using indexes as we do in lists.

·        Internally use hashingSets in Python

A Set in Python is used to store a collection of items with the following properties.

·        No duplicate elements. If try to insert the same item again, it overwrites previous one.

·        An unordered collection. When we access all items, they are accessed without any specific order and we cannot access items using indexes as we do in lists.

·        Internally use hashing that makes set efficient for search, insert and delete operations. It gives a major advantage over a list for problems with these operations.

·        Mutable, meaning we can add or remove elements after their creation, the individual elements within the set cannot be changed directly.

Example of Python Sets

s = {10, 50, 20}

print(s)

print(type(s))

Type Casting with Python Set method

The Python set() method is used for type casting.

# typecasting list to set

s = set(["a", "b", "c"])

print(s)

# Adding element to the set

s.add("d")

print(s)

Check unique and  Immutable with Python Set

Python sets cannot have duplicate values. While you cannot modify the individual elements directly, you can still add or remove elements from the set.

# Python program to demonstrate that

# a set cannot have duplicate values 

# and we cannot change its items

# a set cannot have duplicate values

s = {"Geeks", "for", "Geeks"}

print(s)

# values of a set cannot be changed

s[1] = "Hello"

print(s)

Heterogeneous Element with Python Set

Python sets can store heterogeneous elements in it, i.e., a set can store a mixture of string, integer, boolean, etc datatypes.

# Python example demonstrate that a set

# can store heterogeneous elements

s = {"Geeks", "for", 10, 52.7, True}

print(s)

Python Frozen Sets

Frozen sets in Python are immutable objects that only support methods and operators that produce a result without affecting the frozen set or sets to which they are applied. It can be done with frozenset() method in Python.

While elements of a set can be modified at any time, elements of the frozen set remain the same after creation. 

If no parameters are passed, it returns an empty frozenset.

# Python program to demonstrate differences

# between normal and frozen set

# Same as {"a", "b","c"}

s = set(["a", "b","c"])

print("Normal Set")

print(s)

# A frozen set

fs = frozenset(["e", "f", "g"])

print("\nFrozen Set")

print(fs)

# Uncommenting below line would cause error as

# we are trying to add element to a frozen set

# fs.add("h")

Methods for Sets

Adding elements to Python Sets

Insertion in the set is done through the set.add() function, where an appropriate record value is created to store in the hash table. Same as checking for an item, i.e., O(1) on average. However, in worst case it can become O(n).

# A Python program to

# demonstrate adding elements

# in a set

# Creating a Set

people = {"Jay", "Idrish", "Archi"}

print("People:", end = " ")

print(people)

# This will add Daxit

# in the set

people.add("Daxit")

# Adding elements to the

# set using iterator

for i in range(1, 6):

    people.add(i)

print("\nSet after adding element:", end = " ")

print(people)

Union operation on Python Sets

Two sets can be merged using union() function or | operator. Both Hash Table values are accessed and traversed with merge operation perform on them to combine the elements, at the same time duplicates are removed. The Time Complexity of this is O(len(s1) + len(s2)) where s1 and s2 are two sets whose union needs to be done.

# Python Program to

# demonstrate union of

# two sets

people = {"Jay", "Idrish", "Archil"}

vampires = {"Karan", "Arjun"}

dracula = {"Deepanshu", "Raju"}

# Union using union()

# function

population = people.union(vampires)

print("Union using union() function")

print(population)

# Union using "|"

# operator

population = people|dracula

print("\nUnion using '|' operator")

print(population)

Intersection operation on Python Sets

This can be done through intersection() or & operator. Common Elements are selected. They are similar to iteration over the Hash lists and combining the same values on both the Table. Time Complexity of this is O(min(len(s1), len(s2)) where s1 and s2 are two sets whose union needs to be done.

# Python program to

# demonstrate intersection

# of two sets

set1 = set()

set2 = set()

for i in range(5):

    set1.add(i)

for i in range(3,9):

    set2.add(i)

# Intersection using

# intersection() function

set3 = set1.intersection(set2)

print("Intersection using intersection() function")

print(set3)

# Intersection using

# "&" operator

set3 = set1 & set2

print("\nIntersection using '&' operator")

print(set3)

Finding Differences of Sets in Python

To find differences between sets. Similar to finding differences in the linked list. This is done through difference() or – operator. Time complexity of finding difference s1 – s2 is O(len(s1))

# Python program to

# demonstrate difference

# of two sets

set1 = set()

set2 = set()

for i in range(5):

    set1.add(i)

for i in range(3,9):

    set2.add(i)

# Difference of two sets

# using difference() function

set3 = set1.difference(set2)

print(" Difference of two sets using difference() function")

print(set3)

# Difference of two sets

# using '-' operator

set3 = set1 - set2

print("\nDifference of two sets using '-' operator")

print(set3)

Clearing Python Sets

Set Clear() method empties the whole set inplace.

# Python program to

# demonstrate clearing

# of set

set1 = {1,2,3,4,5,6}

print("Initial set")

print(set1)

# This method will remove

# all the elements of the set

set1.clear()

print("\nSet after using clear() function")

print(set1)

Get the Length of a Set

To determine how many items a set has, use the len() function.

thisset = {"apple", "banana", "cherry"}



print(len(thisset))

type()

From Python's perspective, sets are defined as objects with the data type 'set':

<class 'set'>

Example

myset = {"apple", "banana", "cherry"}

print(type(myset))

The set() Constructor

It is also possible to use the set() constructor to make a set.

Example

#Using the set() constructor to make a set:

thisset = set(("apple", "banana", "cherry")) # note the double round-brackets

print(thisset)

The set() Constructor

It is also possible to use the set() constructor to make a set.

Example

#Using the set() constructor to make a set:

thisset = set(("apple", "banana", "cherry")) # note the double round-brackets

print(thisset)

Operators for Sets

Sets and frozen sets support the following operators:

Operators	Notes
key in s	containment check
key not in s	non-containment check
s1 == s2	s1 is equivalent to s2
s1 != s2	s1 is not equivalent to s2
s1 <= s2	s1 is subset of s2
s1 < s2	s1 is proper subset of s2
s1 >= s2	s1 is superset of s2
s1 > s2	s1 is proper superset of s2
s1 | s2	the union of s1 and s2
s1 & s2	the intersection of s1 and s2
s1 – s2	the set of elements in s1 but not s2
s1 ˆ s2	the set of elements in precisely one of s1 or s2

  that makes set efficient for search, insert and delete operations. It gives a major advantage over a list for problems with these operations.

·        Mutable, meaning we can add or remove elements after their creation, the individual elements within the set cannot be changed directly.

Example of Python Sets

s = {10, 50, 20}

print(s)

print(type(s))

Type Casting with Python Set method

The Python set() method is used for type casting.

# typecasting list to set

s = set(["a", "b", "c"])

print(s)

# Adding element to the set

s.add("d")

print(s)

Check unique and  Immutable with Python Set

Python sets cannot have duplicate values. While you cannot modify the individual elements directly, you can still add or remove elements from the set.

# Python program to demonstrate that

# a set cannot have duplicate values 

# and we cannot change its items

# a set cannot have duplicate values

s = {"Geeks", "for", "Geeks"}

print(s)

# values of a set cannot be changed

s[1] = "Hello"

print(s)

Heterogeneous Element with Python Set

Python sets can store heterogeneous elements in it, i.e., a set can store a mixture of string, integer, boolean, etc datatypes.

# Python example demonstrate that a set

# can store heterogeneous elements

s = {"Geeks", "for", 10, 52.7, True}

print(s)

Python Frozen Sets

Frozen sets in Python are immutable objects that only support methods and operators that produce a result without affecting the frozen set or sets to which they are applied. It can be done with frozenset() method in Python.

While elements of a set can be modified at any time, elements of the frozen set remain the same after creation. 

If no parameters are passed, it returns an empty frozenset.

# Python program to demonstrate differences

# between normal and frozen set

# Same as {"a", "b","c"}

s = set(["a", "b","c"])

print("Normal Set")

print(s)

# A frozen set

fs = frozenset(["e", "f", "g"])

print("\nFrozen Set")

print(fs)

# Uncommenting below line would cause error as

# we are trying to add element to a frozen set

# fs.add("h")

Methods for Sets

Adding elements to Python Sets

Insertion in the set is done through the set.add() function, where an appropriate record value is created to store in the hash table. Same as checking for an item, i.e., O(1) on average. However, in worst case it can become O(n).

# A Python program to

# demonstrate adding elements

# in a set

# Creating a Set

people = {"Jay", "Idrish", "Archi"}

print("People:", end = " ")

print(people)

# This will add Daxit

# in the set

people.add("Daxit")

# Adding elements to the

# set using iterator

for i in range(1, 6):

    people.add(i)

print("\nSet after adding element:", end = " ")

print(people)

Union operation on Python Sets

Two sets can be merged using union() function or | operator. Both Hash Table values are accessed and traversed with merge operation perform on them to combine the elements, at the same time duplicates are removed. The Time Complexity of this is O(len(s1) + len(s2)) where s1 and s2 are two sets whose union needs to be done.

# Python Program to

# demonstrate union of

# two sets

people = {"Jay", "Idrish", "Archil"}

vampires = {"Karan", "Arjun"}

dracula = {"Deepanshu", "Raju"}

# Union using union()

# function

population = people.union(vampires)

print("Union using union() function")

print(population)

# Union using "|"

# operator

population = people|dracula

print("\nUnion using '|' operator")

print(population)

Intersection operation on Python Sets

This can be done through intersection() or & operator. Common Elements are selected. They are similar to iteration over the Hash lists and combining the same values on both the Table. Time Complexity of this is O(min(len(s1), len(s2)) where s1 and s2 are two sets whose union needs to be done.

# Python program to

# demonstrate intersection

# of two sets

set1 = set()

set2 = set()

for i in range(5):

    set1.add(i)

for i in range(3,9):

    set2.add(i)

# Intersection using

# intersection() function

set3 = set1.intersection(set2)

print("Intersection using intersection() function")

print(set3)

# Intersection using

# "&" operator

set3 = set1 & set2

print("\nIntersection using '&' operator")

print(set3)

Finding Differences of Sets in Python

To find differences between sets. Similar to finding differences in the linked list. This is done through difference() or – operator. Time complexity of finding difference s1 – s2 is O(len(s1))

# Python program to

# demonstrate difference

# of two sets

set1 = set()

set2 = set()

for i in range(5):

    set1.add(i)

for i in range(3,9):

    set2.add(i)

# Difference of two sets

# using difference() function

set3 = set1.difference(set2)

print(" Difference of two sets using difference() function")

print(set3)

# Difference of two sets

# using '-' operator

set3 = set1 - set2

print("\nDifference of two sets using '-' operator")

print(set3)

Clearing Python Sets

Set Clear() method empties the whole set inplace.

# Python program to

# demonstrate clearing

# of set

set1 = {1,2,3,4,5,6}

print("Initial set")

print(set1)

# This method will remove

# all the elements of the set

set1.clear()

print("\nSet after using clear() function")

print(set1)

Get the Length of a Set

To determine how many items a set has, use the len() function.

thisset = {"apple", "banana", "cherry"}

print(len(thisset))

type()

From Python's perspective, sets are defined as objects with the data type 'set':

<class 'set'>

Example

myset = {"apple", "banana", "cherry"}

print(type(myset))

The set() Constructor

It is also possible to use the set() constructor to make a set.

Example

#Using the set() constructor to make a set:

thisset = set(("apple", "banana", "cherry")) # note the double round-brackets

print(thisset)

The set() Constructor

It is also possible to use the set() constructor to make a set.

Example

#Using the set() constructor to make a set:

thisset = set(("apple", "banana", "cherry")) # note the double round-brackets

print(thisset)

Operators for Sets

Sets and frozen sets support the following operators:

Operators	Notes
key in s	containment check
key not in s	non-containment check
s1 == s2	s1 is equivalent to s2
s1 != s2	s1 is not equivalent to s2
s1 <= s2	s1 is subset of s2
s1 < s2	s1 is proper subset of s2
s1 >= s2	s1 is superset of s2
s1 > s2	s1 is proper superset of s2
s1 | s2	the union of s1 and s2
s1 & s2	the intersection of s1 and s2
s1 – s2	the set of elements in s1 but not s2
s1 ˆ s2	the set of elements in precisely one of s1 or s2