- .
Trees and Graphs Trees, Binary Search Trees, Balanced Trees, Graphs
- Svetlin Nakov
- Telerik Corporation
- www.telerik.com
-
2.
Table of Contents
- Tree-like Data Structures
- Trees and Related Terminology
- Implementing Trees
- Traversing Trees
- Balanced Trees
- Graphs
- 3. Tree-like Data Structures Trees, Balanced Trees, Graphs, Networks
-
4.
Tree-like Data Structures
- Tree-like data structures are
- Branched recursive data structures
- Consisting of nodes
- Each node can be connected to other nodes
- Examples of tree-like structures
- Trees: binary / other degree, balanced, etc.
- Graphs: directed / undirected, weighted, etc.
- Networks
- 5. Tree-like Data Structures Tree Graph 2 3 6 1 4 5 5 (20) 5 (10) 15 (15) 15 (30) 5 (5) 20(20) 10 (40) Network Project Manager Team Leader De-signer QA Team Leader Developer 1 Developer 2 Tester 1 Developer 3 Tester 2 7 19 21 14 1 12 31 4 11
- 6. Trees and Related Terminology Node, Edge, Root, Children, Parent, Leaf , Binary Search Tree, Balanced Tree
-
7.
Trees
- Tree data structure – terminology
- Node, edge, root, child, children, siblings, parent, ancestor, descendant, predecessor, successor, internal node, leaf, depth, height, subtree
-
8.
Binary Trees
- Binary trees : most widespread form
- Each node has at most 2 children
-
9.
Binary Search Trees
- Binary search trees are ordered
- For each node x in the tree
- All the elements of the left subtree of x are ≤ x
- All the elements of the right subtree of x are > x
- Binary search trees can be balanced
- Balanced trees have height of ~ log 2 ( x )
- Balanced trees have for each node nearly equal number of nodes in its subtrees
-
10.
Binary Search Trees (2)
- Example of balanced binary search tree
- If the tree is balanced, add / search / delete operations take approximately log( n ) steps
- 11. Implementing Trees Recursive Tree Data Structure
-
12.
Recursive Tree Definition
- The recursive definition for tree data structure:
- A single node is tree
- Tree nodes can have zero or multiple children that are also trees
- Tree node definition in C#
- 13. TreeNode<int> Structure TreeNode<int> int value List<TreeNode<int>> children 7 children 19 children 21 children 14 children 1 children 12 children 31 children 23 children 6 children
- 14. Implementing TreeNode <T> public TreeNode(T value) { this.value = value; this.children = new List<TreeNode<T>>(); } public T Value { get { return this.value; } set { this.value = value; } } public void AddChild(TreeNode<T> child) { child.hasParent = true; this.children.Add(child); } public TreeNode<T> GetChild(int index) { return this.children[index]; }
-
15.
- The class Tree<T> keeps tree's root node
-
16.
Building a Tree
- Constructing tree by nested constructors:
- 17. Tree Traversals DFS and BFS Traversals
-
18.
Tree Traversal Algorithms
- Traversing a tree means to visit each of its nodes exactly one in particular order
- Many traversal algorithms are known
- Depth-First Search (DFS)
- Visit node's successors first
- Usually implemented by recursion
- Breadth-First Search (BFS)
- Nearest nodes visited first
- Implemented by a queue
-
19.
- Depth-First Search first visits all descendants of given node recursively, finally visits the node itself
- DFS algorithm pseudo code
-
20.
DFS in Action (Step 1 )
- Stack: 7
- Output: (empty)
-
21.
DFS in Action (Step 2 )
- Stack: 7 , 19
- Output: (empty)
-
22.
DFS in Action (Step 3 )
- Stack: 7 , 19 , 1
- Output: (empty)
-
23.
DFS in Action (Step 4 )
- Stack: 7 , 19
- Output: 1
-
24.
DFS in Action (Step 5 )
- Stack: 7 , 19 , 12
- Output: 1
-
25.
DFS in Action (Step 6 )
- Stack: 7 , 19
- Output: 1 , 12
-
26.
DFS in Action (Step 7 )
- Stack: 7 , 19 , 31
- Output: 1 , 12
-
27.
DFS in Action (Step 8 )
- Stack: 7 , 19
- Output: 1 , 12 , 31
-
28.
DFS in Action (Step 9 )
- Stack: 7
- Output: 1 , 12 , 31 , 19
-
29.
DFS in Action (Step 10 )
- Stack: 7 , 21
- Output: 1 , 12 , 31 , 19
-
30.
DFS in Action (Step 11 )
- Stack: 7
- Output: 1 , 12 , 31 , 19 , 21
-
31.
DFS in Action (Step 12 )
- Stack: 7 , 14
- Output: 1 , 12 , 31 , 19 , 21
-
32.
DFS in Action (Step 13 )
- Stack: 7 , 14 , 23
- Output: 1 , 12 , 31 , 19 , 21
-
33.
DFS in Action (Step 14 )
- Stack: 7 , 14
- Output: 1 , 12 , 31 , 19 , 21 , 23
-
34.
DFS in Action (Step 15 )
- Stack: 7 , 14 , 6
- Output: 1 , 12 , 31 , 19 , 21 , 23
-
35.
DFS in Action (Step 16 )
- Stack: 7 , 14
- Output: 1 , 12 , 31 , 19 , 21 , 23 , 6
-
36.
DFS in Action (Step 17 )
- Stack: 7
- Output: 1 , 12 , 31 , 19 , 21 , 23 , 6 , 14
-
37.
DFS in Action (Step 18 )
- Stack: (empty)
- Output: 1 , 12 , 31 , 19 , 21 , 23 , 6 , 14 , 7
-
38.
- Breadth-First Search first visits the neighbor nodes, later their neighbors, etc.
- BFS algorithm pseudo code
-
39.
BFS in Action (Step 1 )
- Queue: 7
- Output: 7
-
40.
BFS in Action (Step 2 )
- Queue: 7 , 19
- Output: 7
-
41.
BFS in Action (Step 3 )
- Queue: 7 , 19 , 21
- Output: 7
-
42.
BFS in Action (Step 4 )
- Queue: 7 , 19 , 21 , 14
- Output: 7
-
43.
BFS in Action (Step 5 )
- Queue: 7 , 19 , 21 , 14
- Output: 7 , 19
-
44.
BFS in Action (Step 6 )
- Queue: 7 , 19 , 21 , 14 , 1
- Output: 7 , 19
-
45.
BFS in Action (Step 7 )
- Queue: 7 , 19 , 21 , 14 , 1 , 12
- Output: 7 , 19
-
46.
BFS in Action (Step 8 )
- Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31
- Output: 7 , 19
-
47.
BFS in Action (Step 9 )
- Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31
- Output: 7 , 19 , 21
-
48.
BFS in Action (Step 10 )
- Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31
- Output: 7 , 19 , 21 , 14
-
49.
BFS in Action (Step 11 )
- Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31 , 23
- Output: 7 , 19 , 21 , 14
-
50.
BFS in Action (Step 12 )
- Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31 , 23 , 6
- Output: 7 , 19 , 21 , 14
-
51.
BFS in Action (Step 13 )
- Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31 , 23 , 6
- Output: 7 , 19 , 21 , 14 , 1
-
52.
BFS in Action (Step 14 )
- Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31 , 23 , 6
- Output: 7 , 19 , 21 , 14 , 1 , 1 2
-
53.
BFS in Action (Step 15 )
- Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31 , 23 , 6
- Output: 7 , 19 , 21 , 14 , 1 , 1 2 , 31
-
54.
BFS in Action (Step 16 )
- Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31 , 23 , 6
- Output: 7 , 19 , 21 , 14 , 1 , 1 2 , 31 , 23
-
55.
BFS in Action (Step 16 )
- Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31 , 23 , 6
- Output: 7 , 19 , 21 , 14 , 1 , 1 2 , 31 , 23 , 6
-
56.
BFS in Action (Step 17 )
- Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31 , 23 , 6
- Output: 7 , 19 , 21 , 14 , 1 , 1 2 , 31 , 23 , 6
-
57.
Binary Trees DFS Traversals
- DFS traversal of binary trees can be done in pre-order, in-order and post-order
- Pre-order: left, root, right 6 , 9 , 12 , 17 , 19 , 25
- In-order: root, left, right 17 , 9 , 6 , 12 , 19 , 25
- Post-order: left, right, root 6 , 12 , 9 , 25 , 19 , 17
-
58.
Iterative DFS and BFS
- What will happen if in the Breadth-First Search (BFS) algorithm a stack is used instead of queue?
- An iterative Depth-First Search (DFS) – in-order
- 59. Trees and Traversals Live Demo
- 60. Balanced Search Trees AVL Trees, B-Trees, Red-Black Trees, AA-Trees
-
61.
Balanced Binary Search Trees
- Ordered Binary Trees ( Binary Search Trees )
- For each node x the left subtree has values ≤ x and the right subtree has values > x
- Balanced Trees
- For each node its subtrees contain nearly equal number of nodes nearly the same height
- Balanced Binary Search Trees
- Ordered binary search trees that have height of log 2 (n) where n is the number of their nodes
- Searching costs about log 2 (n) comparisons
- 62. Balanced Binary Search Tree – Example 33 18 15 24 3 17 20 29 54 42 60 37 43 59 85
-
63.
Balanced Binary Search Trees
- Balanced binary search trees are hard to implement
- Rebalancing the tree after insert / delete is complex
- Well known implementations of balanced binary search trees
- AVL trees – ideally balanced, very complex
- Red-black trees – roughly balanced, more simple
- AA-Trees – relatively simple to implement
- Find / insert / delete operations need log 2 (n) steps
-
64.
B-Trees
- B-trees are generalization of the concept of ordered binary search trees
- B-tree of order d has between d and 2*d keys in a node and between d+1 and 2*d+1 child nodes
- The keys in each node are ordered increasingly
- All keys in a child node have values between their left and right parent keys
- If the b-tree is balanced, its search / insert / add operations take about log(n) steps
- B-trees can be efficiently stored on the disk
-
65.
- B-Tree of order 2 , also known as 2 - 3 - 4 -tree:
-
66.
Balanced Trees in .NET
- .NET Framework has several built-in implementations of balanced search trees:
- SortedDictionary<K,V>
- Red-black tree based map of key-value pairs
- OrderedSet<T>
- Red-black tree based set of elements
- External libraries like "Wintellect Power Collections for .NET" are more flexible
- http://powercollections.codeplex.com
- 67. Graphs Definitions, Representation, Traversal Algorithms
-
68.
Graph Data Structure
- Set of nodes with many-to-many relationship between them is called graph
- Each node has multiple predecessors
- Each node has multiple successors
-
69.
Graph Definitions
- Node ( vertex )
- Element of graph
- Can have name or value
- Keeps a list of adjacent nodes
- Edge
- Connection between two nodes
- Can be directed / undirected
- Can be weighted / unweighted
- Can have name / value
-
70.
Graph Definitions (2)
- Directed graph
- Edges have direction
- Undirected graph
- Undirected edges
-
71.
Graph Definitions (3)
- Weighted graph
- Weight (cost) is associated with each edge
-
72.
Graph Definitions (4)
- Path (in undirected graph)
- Sequence of nodes n 1 , n 2 , … n k
- Edge exists between each pair of nodes n i , n i+1
- Examples:
- A, B, C is a path
- H, K, C is not a path
-
73.
Graph Definitions (5)
- Path (in directed graph)
- Sequence of nodes n 1 , n 2 , … n k
- Directed edge exists between each pair of nodes n i , n i+1
- Examples:
- A, B, C is a path
- A, G, K is not a path
-
74.
Graph Definitions (6)
- Cycle
- Path that ends back at the starting node
- Example:
- A, B, C, G, A
- Simple path
- No cycles in path
- Acyclic graph
- Graph with no cycles
- Acyclic undirected graphs are trees
-
75.
Graph Definitions (8)
- Two nodes are reachable if
- Path exists between them
- Connected graph
- Every node is reachable from any other node
-
76.
Graphs and Their Applications
- Graphs have many real-world applications
- Modeling a computer network like Internet
- Routes are simple paths in the network
- Modeling a city map
- Streets are edges, crossings are vertices
- Social networks
- People are nodes and their connections are edges
- State machines
- States are nodes, transitions are edges
-
77.
Representing Graphs
- Adjacency list
- Each node holds a list of its neighbors
- Adjacency matrix
- Each cell keeps whether and how tw o nodes are connected
- Set of edges
- 78. Representing Graphs in C# public class Graph { int[][] childNodes; public Graph(int[][] nodes) { this.childNodes = nodes; } } Graph g = new Graph(new int[][] { new int[] {3, 6}, // successors of vertice 0 new int[] {2, 3, 4, 5, 6}, // successors of vertice 1 new int[] {1, 4, 5}, // successors of vertice 2 new int[] {0, 1, 5}, // successors of vertice 3 new int[] {1, 2, 6}, // successors of vertice 4 new int[] {1, 2, 3}, // successors of vertice 5 new int[] {0, 1, 4} // successors of vertice 6 }); 0 6 4 1 5 2 3
-
79.
Graph Traversal Algorithms
- Depth-First Search (DFS) and Breadth-First Search (BFS) can traverse graphs
- Each vertex should be is visited at most once
- 80. Recursive DFS Graph Traversal void TraverseDFSRecursive(node) { if (not visited[node]) { visited[node] = true print node foreach child node c of node { TraverseDFSRecursive( c ); } } } vois Main() { TraverseDFS(firstNode); }
- 81. Graphs and Traversals Live Demo
-
82.
Summary
- Trees are recursive data structure – node with set of children which are also nodes
- Binary Search Trees are ordered binary trees
- Balanced trees have weight of log(n)
- Graphs are sets of nodes with many-to-many relationship between them
- Can be directed/undirected, weighted / unweighted, connected / not connected, etc.
- Tree / graph traversals can be done by Depth-First Search (DFS) and Breadth-First Search (BFS)
-
83.
Trees and Graphs
- Questions?
-
84.
Exercises
- Write a program to traverse the directory C:WINDOWS and all its subdirectories recursively and to display all files matching the mask *.exe . Use the class System.IO.Directory .
- Define classes File { string name, int size } and Folder { string name, File[] files , Folder[] childFolders } and using them build a tree keeping all files and folders on the hard drive starting from C:WINDOWS . Implement a method that calculates the sum of the file sizes in given subtree of the tree and test it accordingly. Use recursive DFS traversal.
-
85.
Exercises (2)
- Implement the recursive Depth-First-Search (DFS) traversal algorithm. Test it with the sample graph from the demonstrations.
- Implement the queue-based Breath-First-Search (BFS) traversal algorithm. Test it with the sample graph from the demonstrations.
- Write a program for finding all cycles in given undirected graph using recursive DFS.
- Write a program for finding all connected components of given undirected graph. Use a sequence of DFS traversals.
-
86.
Exercises (3)
- Write a program for finding the shortest path between two vertices in a weighted directed graph. Hint: Use the Dijkstra's algorithm .
- We are given a set of N tasks that should be executed in a sequence. Some of the tasks depend on other tasks. We are given a list of tasks { t i , t j } where t j depends on the result of t i and should be executed after it. Write a program that arranges the tasks in a sequence so that each task depending on another task is executed after it. If such arrangement is impossible indicate this fact.
- Example: { 1 , 2 }, { 2 , 5 }, { 2 , 4 }, { 3 , 1 } 3 , 1 , 2 , 5 , 4
- REF:http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-17-trees-and-graphs/#presentation-slides
Thursday, 26 February 2015
Friday, 2 January 2015
Microprocessor 80386
- 1. FEATURES OF 80386 : Two versions of 80386 are commonly available: 1) 80386DX 2)80386SX 80386DX 80386SX
- 32 bit address bus 1) 24 bit address bus 32bit data bus 16 bit data bus
- Packaged in 132 pin ceramic 2) 100 pin flat
- pin grid array(PGA) package
- 3 ) Address 4GB of memory 3) 16 MB of
- memory
- 2.
- 80386SX was developed after the DX for application that didn’t require the full 32-bit bus version.It is found in many PCs use the same basic mother board design as the 80286.Most application less than the 16MB of memory ,so the SX is popular and less costly version of the 80386 microprocessor.
- The 80386 cpu supports 16k no:of segments and thus total virtual memory space is 4GB *16 k=64 tera bytes
- Memory management section supports
- Virtual memory
- Paging
- 4 levels of protection
- 20-33 MHz frequency
- 3. Architecture of 80386
- The Internal Architecture of 80386 is divided into 3 sections.
- Central processing unit(CPU)
- Memory management unit(MMU)
- Bus interface unit(BIU)
- Central processing unit is further divided into Execution unit(EU) and Instruction unit(IU)
- Execution unit has 8 General purpose and 8 Special purpose registers which are either used for handling data or calculating offset addresses.
- 4.
- 5. • The Instruction unit decodes the opcode bytes received from the 16-byte instruction code queue and arranges them in a 3- instruction decoded instruction queue. • After decoding them pass it to the control section for deriving the necessary control signals. The barrel shifter increases the speed of all shift and rotate operations. • The multiply / divide logic implements the bit-shift-rotate algorithms to complete the operations in minimum time. • Even 32- bit multiplications can be executed within one microsecond by the multiply / divide logic.
- 6.
- • The Memory management unit consists of
- Segmentation unit and
- Paging unit.
- • Segmentation unit allows the use of two address components, viz. segment and offset for relocability and sharing of code and data.
- • Segmentation unit allows segments of size 4Gbytes at max.
- • The Paging unit organizes the physical memory in terms of pages of 4kbytes size each.
- • Paging unit works under the control of the segmentation unit, i.e. each segment is further divided into pages. The virtual memory is also organizes in terms of segments and pages by the memory management unit.
- 7. • The Segmentation unit provides a 4 level protection mechanism for protecting and isolating the system code and data from those of the application program. • Paging unit converts linear addresses into physical addresses. • The control and attribute PLA checks the privileges at the page level. Each of the pages maintains the paging information of the task. The limit and attribute PLA checks segment limits and attributes at segment level to avoid invalid accesses to code and data in the memory segments. • The Bus control unit has a prioritizer to resolve the priority of the various bus requests.This controls the access of the bus. The address driver drives the bus enable and address signal A0 – A31. The pipeline and dynamic bus sizing unit handle the related control signals.
- 8. • The data buffers interface the internal data bus with the system bus. Register Organisation : • The 80386 has eight 32 - bit general purpose registers which may be used as either 8 bit or 16 bit registers. • A 32 - bit register known as an extended register, is represented by the register name with prefix E. • Example : A 32 bit register corresponding to AX is EAX, similarly BX is EBX etc. • The 16 bit registers BP, SP, SI and DI in 8086 are now available with their extended size of 32 bit and are names as EBP,ESP,ESI and EDI. • AX represents the lower 16 bit of the 32 bit register EAX.
- 9. • BP, SP, SI, DI represents the lower 16 bit of their 32 bit counterparts, and can be used as independent 16 bit registers. • The six segment registers available in 80386 are CS, SS, DS, ES, FS and GS. • The CS and SS are the code and the stack segment registers respectively, while DS, ES,FS, GS are 4 data segment registers. • A 16 bit instruction pointer IP is available along with 32 bit counterpart EIP.
- 10.
- 11. • Flag Register of 80386 : The Flag register of 80386 is a 32 bit register. Out of the 32 bits, Intel has reserved bits D18 to D31, D5 and D3, while D1 is always set at 1.Two extra new flags are added to the 80286 flag to derive the flag register of 80386. They are VM and RF flags.
- 12. • VM - Virtual Mode Flag : If this flag is set, the 80386 enters the virtual 8086 mode within the protection mode. This is to be set only when the 80386 is in protected mode. In this mode, if any privileged instruction is executed an exception 13 is generated. This bit can be set using IRET instruction or any task switch operation only in the protected mode. • RF- Resume Flag : This flag is used with the debug register breakpoints. It is checked at the starting of every instruction cycle and if it is set, any debug fault is ignored during the instruction cycle. The RF is automatically reset after successful execution of every instruction, except for IRET and POPF instructions.
- 13.
- • Also, it is not automatically cleared after the successful execution of JMP, CALL and INT instruction causing a task switch. These instruction are used to set the RF to the value specified by the memory data available at the stack.
- 14. • Segment Descriptor Registers : This registers are not available for programmers, rather they are internally used to store the descriptor information, like attributes, limit and base addresses of segments. • The six segment registers have corresponding six 73 bit descriptor registers. Each of them contains 32 bit base address, 20 bit base limit and 9 bit attributes. These are automatically loaded when the corresponding segments are loaded with selectors. • Control Registers : The 80386 has three 32 bit control registers CR0, CR2 and CR3 to hold global machine status independent of the executed task. Load and store instructions are available to access these registers. • System Address Registers : Four special registers are defined to refer to the descriptor tables supported by 80386.
- 15. • The 80386 supports four types of descriptor table, viz. global descriptor table (GDT),interrupt descriptor table (IDT), local descriptor table (LDT) and task state segment descriptor (TSS). • Debug and Test Registers : Intel has provide a set of 8 debug registers for hardware debugging. Out of these eight registers DR0 to DR7, two registers DR4 and DR5 are Intel reserved. • The initial four registers DR0 to DR3 store four program controllable breakpoint addresses, while DR6 and DR7 respectively hold breakpoint status and breakpoint control information.
- 16. ADDRESSING MODES : The 80386 supports overall eleven addressing modes to facilitate efficient execution of higher level language programs. • In case of all those modes, the 80386 can now have 32-bit immediate or 32- bit register operands or displacements. • The 80386 has a family of scaled modes. In case of scaled modes, any of the index register values can be multiplied by a valid scale factor to obtain the displacement. • The valid scale factor are 1, 2, 4 and 8. • The different scaled modes are as follows. • Scaled Indexed Mode : Contents of the an index register are multiplied by a scale factor that may be added further to get the operand offset.
- 17. • Based Scaled Indexed Mode : Contents of the an index register are multiplied by a scale factor and then added to base register to obtain the offset. • Based Scaled Indexed Mode with Displacement : The Contents of the an index register are multiplied by a scaling factor and the result is added to a base register and a displacement to get the offset of an operand.
- 18. Real Address Mode of 80386 • After reset, the 80386 starts from memory location FFFFFFF0H under the real address mode. In the real mode, 80386 works as a fast 8086 with 32-bit registers and data types. • In real mode, the default operand size is 16 bit but 32- bit operands and addressing modes may be used with the help of override prefixes. • The segment size in real mode is 64k, hence the 32-bit effective addressing must be less than 0000FFFFFH. The real mode initializes the 80386 and prepares it for protected mode.
- 19.
- 20. • Memory Addressing in Real Mode : In the real mode, the 80386 can address at the most1Mbytes of physical memory using address lines A0-A19. • Paging unit is disabled in real addressing mode, and hence the real addresses are the same as the physical addresses. • To form a physical memory address, appropriate segment registers contents (16-bits) are shifted left by four positions and then added to the 16-bit offset address formed using one of the addressing modes, in the same way as in the 80386 real address mode. • The segment in 80386 real mode can be read, write or executed, i.e. no protection is available. • Any fetch or access past the end of the segment limit generate exception 13 in real address mode.
- 21. • The segments in 80386 real mode may be overlapped or non-overlapped. • The interrupt vector table of 80386 has been allocated 1Kbyte space starting from 00000H to 003FFH. Protected Mode of 80386: • All the capabilities of 80386 are available for utilization in its protected mode of operation. • The 80386 in protected mode support all the software written for 80286 to be executed under the control of memory management and protection abilities of 80386. • The protected mode allows the use of additional instruction, addressing modes and capabilities of 80386.
- 22.
- 23. ADDRESSING IN PROTECTED MODE : In this mode, the contents of segment registers are used as selectors to address descriptors which contain the segment limit, base address and access rights byte of the segment. • The effective address (offset) is added with segment base address to calculate linear address. This linear address is further used as physical address, if the paging unit is disabled, otherwise the paging unit converts the linear address into physical address. • The paging unit is a memory management unit enabled only in protected mode. The paging mechanism allows handling of large segments of memory in terms of pages of 4Kbyte size.
- 24. • The paging unit operates under the control of segmentation unit. The paging unit if enabled converts linear addresses into physical address, in protected mode. Segmentation: • Descriptor tables : These descriptor tables and registers are manipulated by the operating system to ensure the correct operation of the processor, and hence the correct execution of the program. • Three types of the 80386 descriptor tables are listed as follows: • GLOBAL DESCRIPTOR TABLE ( GDT ) • LOCAL DESCRIPTOR TABLE ( LDT ) • INTERRUPT DESCRIPTOR TABLE ( IDT )
- 25. • Descriptors : The 80386 descriptors have a 20-bit segment limit and 32-bit segment address. The descriptor of 80386 are 8-byte quantities access right or attribute bits along with the base and limit of the segments. • Descriptor Attribute Bits : The A (accessed) attributed bit indicates whether the segment has been accessed by the CPU or not. • The TYPE field decides the descriptor type and hence the segment type. • The S bit decides whether it is a system descriptor (S=0) or code/data segment descriptor ( S=1). • The DPL field specifies the descriptor privilege level.
- 26. • The D bit specifies the code segment operation size. If D=1, the segment is a 32-bit operand segment, else, it is a 16-bit operand segment. • The P bit (present) signifies whether the segment is present in the physical memory or not. If P=1, the segment is present in the physical memory. • The G (granularity) bit indicates whether the segment is page addressable. The zero bit must remain zero for compatibility with future process. • The AVL (available) field specifies whether the descriptor is for user or for operating system.
- 27. • The 80386 has five types of descriptors listed as follows: 1.Code or Data Segment Descriptors. 2.System Descriptors. 3.Local descriptors. 4.TSS (Task State Segment) Descriptors. 5.GATE Descriptors. • The 80386 provides a four level protection mechanism exactly in the same way as the 80286 does.
- 28.
- 29. Paging: • Paging Operation : Paging is one of the memory management techniques used for virtual memory multitasking operating system. • The segmentation scheme may divide the physical memory into a variable size segments but the paging divides the memory into a fixed size pages. • The segments are supposed to be the logical segments of the program, but the pages do not have any logical relation with the program. • The pages are just fixed size portions of the program module or data.
- 30. • The advantage of paging scheme is that the complete segment of a task need not be in the physical memory at any time. • Only a few pages of the segments, which are required currently for the execution need to be available in the physical memory. Thus the memory requirement of the task is substantially reduced, relinquishing the available memory for other tasks. • Whenever the other pages of task are required for execution, they may be fetched from the secondary storage. • The previous page which are executed, need not be available in the memory, and hence the space occupied by them may be relinquished for other tasks.
- 31. • Thus paging mechanism provides an effective technique to manage the physical memory for multitasking systems. • Paging Unit : The paging unit of 80386 uses a two level table mechanism to convert a linear address provided by segmentation unit into physical addresses. The paging unit converts the complete map of a task into pages, each of size 4K. The task is further handled in terms of its page, rather than segments. The paging unit handles every task in terms of three components namely page directory, page tables and page itself.
- 32. • Paging Descriptor Base Register : The control register CR2 is used to store the 32-bit linear address at which the previous page fault was detected. The CR3 is used as page directory physical base address register, to store the physical starting address of the page directory. The lower 12 bit of the CR3 are always zero to ensure the page size aligned directory. A move operation to CR3 automatically loads the page table entry caches and a task switch operation, to load CR0 suitably.
- 33. • Page Directory : This is at the most 4Kbytes in size. Each directory entry is of 4 bytes,thus a total of 1024 entries are allowed in a directory.The upper 10 bits of the linear address are used as an index to the corresponding page directory entry. The page directory entries point to page tables. • Page Tables : Each page table is of 4Kbytes in size and many contain a maximum of 1024 entries. The page table entries contain the starting address of the page and the statistical information about the page. • The upper 20 bit page frame address is combined with the lower 12 bit of the linear address. The address bits A12- A21 are used to select the 1024 page table entries. The page table can be shared between the tasks.
- 34. • The P bit of the above entries indicate, if the entry can be used in address translation. • If P=1, the entry can be used in address translation, otherwise it cannot be used. • The P bit of the currently executed page is always high. • The accessed bit A is set by 80386 before any access to the page. If A=1, the page is accessed, else unaccessed. • The D bit ( Dirty bit) is set before a write operation to the page is carried out. • The OS reserved bits are defined by the operating system software.
- 35. • The User / Supervisor (U/S) bit and read/write bit are used to provide protection. These bits are decoded to provide protection under the 4 level protection model. • The level 0 is supposed to have the highest privilege, while the level 3 is supposed to have the least privilege. • This protection provide by the paging unit is transparent to the segmentation unit.
- 36. 31 12 11 10 9 8 7 6 5 4 3 2 1 0 Page Directory Entry 31 12 11 10 9 8 7 6 5 4 3 2 1 0 Page Table Entry P R W U S 0 0 A D 0 0 OS RESERVED PAGE TABLE ADDRESS 31..12 P R W U S 0 0 A D 0 0 OS RESEVED PAGE FRAME ADDRESS31..12
- 37. Virtual 8086 Mode
- 38. • In its protected mode of operation, 80386DX provides a virtual 8086 operating environment to execute the 8086 programs. • The real mode can also used to execute the 8086 programs along with the capabilities of 80386, like protection and a few additional instructions. • Once the 80386 enters the protected mode from the real mode, it cannot return back to the real mode without a reset operation. • Thus, the virtual 8086 mode of operation of 80386, offers an advantage of executing 8086 programs while in protected mode. • The address forming mechanism in virtual 8086 mode is exactly identical with that of 8086 real mode.
- 39. • In virtual mode, 8086 can address 1Mbytes of physical memory that may be anywhere in the 4Gbytes address space of the protected mode of 80386. • Like 80386 real mode, the addresses in virtual 8086 mode lie within 1Mbytes of memory. • In virtual mode, the paging mechanism and protection capabilities are available at the service of the programmers. • The 80386 supports multiprogramming, hence more than one programmer may be use the CPU at a time.
Monday, 29 December 2014
For using graphics.h library in Ubuntu, you need to follow few simple steps given below:
First of all, you need to install few packages. For that, run command this on your terminal “sudo apt-get install libsdl-image1.2 libsdl-image1.2-dev guile-1.8 guile-1.8-dev”
Next you need to install libgraph package. Download libgraph-1.0.2.tar.gz from link:
download.savannah.gnu.org/releases/libgraph/libgraph-1.0.2.tar.gz
Extract this where you want. Now navigate to the folder, where you just extracted your libgraph-1.0.2.tar.gz using cd command. Run these commands on your terminal.
> cd libgraph-1.0.2
> ./configure
>sudo make
> sudo make install
> sudo cp /usr/local/lib/libgraph.* /usr/lib
And if you got error message “configure: error: *** SDL version 1.2.0 not found!”, try installing it using: “sudo apt-get install libsdl1.2-dev libsdl-image1.2-dev libsdl-mixer1.2-dev libsdl-ttf2.0-dev”
Another error which you can get is: “configure: cannot find guile-config; is Guile installed?” Solve this by using command“sudo apt-get install guile guile-dev”.
If this didn’t helped much, then we have another way to get it work in right way. Use synaptic package manager to install related files.

Now try compliling your C program.
#include<stdio.h>
#include<graphics.h>
int main()
{
int gd=DETECT,gm;
initgraph(&gd,&gm,NULL);
int i,x=10;
char str[3]=”0″;
setbkcolor(BLUE);
setcolor(12); //outline heart
circle(50,50,40);
circle(110,50,40);
line(22,80,80,140);
line(80,140,138,80);
floodfill(50,50,12); //fill heart
floodfill(110,50,12);
floodfill(80,50,12);
floodfill(80,100,12);
getch();
closegraph();
return 0;
}

First of all, you need to install few packages. For that, run command this on your terminal “sudo apt-get install libsdl-image1.2 libsdl-image1.2-dev guile-1.8 guile-1.8-dev”
Next you need to install libgraph package. Download libgraph-1.0.2.tar.gz from link:
download.savannah.gnu.org/releases/libgraph/libgraph-1.0.2.tar.gz
Extract this where you want. Now navigate to the folder, where you just extracted your libgraph-1.0.2.tar.gz using cd command. Run these commands on your terminal.
> cd libgraph-1.0.2
> ./configure
>sudo make
> sudo make install
> sudo cp /usr/local/lib/libgraph.* /usr/lib
And if you got error message “configure: error: *** SDL version 1.2.0 not found!”, try installing it using: “sudo apt-get install libsdl1.2-dev libsdl-image1.2-dev libsdl-mixer1.2-dev libsdl-ttf2.0-dev”
Another error which you can get is: “configure: cannot find guile-config; is Guile installed?” Solve this by using command“sudo apt-get install guile guile-dev”.
If this didn’t helped much, then we have another way to get it work in right way. Use synaptic package manager to install related files.

Now try compliling your C program.
#include<stdio.h>
#include<graphics.h>
int main()
{
int gd=DETECT,gm;
initgraph(&gd,&gm,NULL);
int i,x=10;
char str[3]=”0″;
setbkcolor(BLUE);
setcolor(12); //outline heart
circle(50,50,40);
circle(110,50,40);
line(22,80,80,140);
line(80,140,138,80);
floodfill(50,50,12); //fill heart
floodfill(110,50,12);
floodfill(80,50,12);
floodfill(80,100,12);
getch();
closegraph();
return 0;
}

Subscribe to:
Posts (Atom)
