最小bootloader的实现,完整源代码
最小bootloader的实现,完整源代码
热1已有 275 次阅读2009-12-30 15:18
我们整个ARM课程就分为三部分，这是第一部分，实现一个自己的最小bootloader
1.Read Me
一、实现功能
1.硬件初始化
2.延时判断加载操作系统还是进入Bootloader Shell
3.加载操作系统
4.Bootloadershell
二、Bootloader Shell 支持的命令
1.help 帮助，显示所有支持的命令，及命令格式
2.loadx 下载文件到开发板的内存,默认到0x32000000
3.led_on 点亮一个led灯
4.led_off 关闭一个led灯
5.led_test 测试所有led灯，全亮全灭循环3次
6.beep_test 测试蜂鸣器，响3声
7.seg7_test 测试7段数码管
8.dip4_test 测试4位拨码开关
9.flash_load 将NandFlash中的文件搬移到SDARAM中
10.flash_write 将SDRAM中的内容下载到NandFlash中
11.GO 跳到某地址执行,默认到0x32000000
三、文件结构
1.start.s 程序入口，负责硬件初始化，Bootloader自搬移
2.uart.c uart.h 串口驱动的实现
3.load.c 选择加载操作系统还是进入Shell
4.stdlib.h stdlib.c 标准库函数的实现
5.stdio.h stdio.c 标准输入输出函数的实现
6.shell.c shell.h shell命令的实现
7.dip4.h dip4.c 拨码开关相关底层函数
8.seg7.h seg7.c 7段数码管相关底层函数
9.copy_myself.c nan.h NandFlash底层函数
10.xmodem.h xmodem.c xmodem协议实现
11.Datatype.h 数据定义
12.os/os.c 模拟操作系统
13.Makefile
四、流程及设计思想
1.硬件初始化
2.Bootloader自搬移
3.延时，判断是否有输入
4.(1)无输入则加载操作系统，操作系统烧写于Nand Flash的第100块，即位于100*32*512 = 0x190000
操作系统加载到内存的Sdram中
(2)有输入则进入shell命令模式
5.解释命令，使用自己实现的标准库函数来匹配输入的命令
6.匹配函数，定义了一个包含字符指针以及函数指针的结构体，可以通过对应关系迅速调用命令对应的函数
所有函数为void fun(void *)形式。
五、测试条件及结果
1. 打开超级终端，给开发板上电，超级终端上打印提示信息
2. 超级终端上开始3秒倒计时，3秒内不动键盘，提示加载操作系统，模拟操作系统的闪灯程序运行，可观察到LED等一闪一灭
3. 重启开发板，3秒内按下任意键，可看到有T-Boot#提示符，程序进入Shell模式
4. 输入help,可看到10条命令的使用方法
5. 输入led_on 1可看到第一个led灯亮
6. 输入led_off 1可看到第一个led灯灭
7. 输入led_test 可看到所有led一闪一灭3次
8. 输入beep_test 可听到蜂鸣器响3声
9. 输入seg7_test 可看到7段数码管每个led循环点亮
10.输入dip4_test 拨动拨码开关可观察到7段数码管对应的LED亮
11.输入loadx,发送文件0x/0s.bin
12.输入go 0x32000000 可观察到led灯一亮一灭
13.输入flash_load 0x190000 0x32000000 0x1000 (0x190000模拟操作系统烧写位置)
14.go 0x32000000 可观察到led一亮一灭
16.输入flash_write 0x32000000 0x200000 0x1000
17.输入flash_load 0x200000 0x31500000 0x1000
18.输入go 0x31500000 可观察到led灯一亮一灭
六、函数接口及功能
1.底层接口函数
uart.h
void uart_init(void); 初始化串口
void uart_putc(char ch); 打印一个字符到终端
char uart_getc(void); 从终端接收一个字符
void uart_test(void); 串口测试
void sdram_test(void); sdram测试
nand.h
void reset_nand(void); 重置串口
void init_nand(void); 初始化串口
int nand_read_ll(unsigned char *buf, unsigned long start_addr, int size);
读nand flash 第一个参数为需要存放书籍的内存首地址，第二个参数为nand_flash的首地址，第三个参数为需要拷贝的大小
int nand_write_ll(unsigned char *buf, unsigned long start_addr, int
size);
写nand flash 第一个参数为需要存放书籍的内存首地址，第二个参数为nand_flash的首地址，第三个参数为需要拷贝的大小
dip.h
int dip_init(void); 初始化
int dip_num(void); 显示数字
int dip_test(void); 测试
seg7.h
int seg7_init(void); 初始化
int seg7_display_num(int num);显示数字
int seg7_test(void)；测试
2.库函数
stdio.h
char * uart_gets(char *buf); 打印字符串
void uart_puts(char *str); 接收字符串
void uart_printf(const char *str, ...);格式化输出
void uart_put_num(int num,int pow);打印数字
stdlib.h
int my_strcmp(char *src, char *dst);比较字符串，相等返回0 int my_atoi(char *str);转换字符串为数字
char * found_ch(char *str, char ch);在一个字符串中寻找一个字符int my_strlen(char *str);计算字符串长度
int is_number(char ch);一个字符是否数字
int pow(int num, int power);计算num的power次方
int my_atox(char *str);将一个字符串按16进制转为数字
3.协议
xmodem.h
int xmodem_receive(int argc, char *argv);
int get_record(void);
4.其他
命令对应的解释函数，为方便调用参数均为void *
void help(void *argv);
void go(void *argv);
void loadx(void *argv);
void beep_test(void *argv);
void led_off(void *argv);
void led_on(void *argv);
void seg7_on(void *argv);
void dip4_on(void *argv);
void shell(void);
void led_test(void * argv);
void flash_load(void *argv);
void flash_write(void *argv);
void delay(int);
2.start.s
Code:
1 ;s3c2440 bootloader
2 ;author: xxxx
3 ;time : 2009.12.22
4
5 AREA FIRST, CODE, READONLY
6 ENTRY
7 CODE32
8 IMPORT uart_test
9 IMPORT sdram_test
10
11START
12
13WatchDog
14 ;Close WatchDog
15 LDR R0, =0X53000000
16 MOV R1, #0X0
17 STR R1, [R0]
18
19Led_on
20 ;Make a Led on
21 LDR R2, =0x20800000
22 MOV R4, #0X1
23 STRB R4, [R2]
24
25 ;BL DELAY
26
27Beep_off
28 ;Close Beep
29 ;Control GPB0 output
30 LDR R0, =0x56000010
31 MOV R1, #0X1
32 STR R1, [R0]
33
34 LDR R0, =0X56000014
35 MOV R1, #0X0
36 STR R1, [R0]
37
38Interrupt_off
39 ;CLose Interrupt
40 LDR R0, =0X4A000008
41 LDR R1, =0XFFFFFFFF
42 STR R1, [R0]
43
44Init_Clock
45
46 ; Init Clock
47 ; Set Mode
48 MRC p15,0,R1,c1,c0,0
49 ORR R1,R1,#0XC0000000
50 MCR p15,0,R1,c1,c0,0
51
52 ;CAMDIVN
53 ;When Config the register CLKDIVN Nedd This Configre
54 LDR R0,=0x4c000018
55 MOV R1,#0x0
56 STR R1,[r0]
57
58
59 ;LOCKTIME PLL
60 LDR R0,=0x4c000000
61 LDR R1,=0x00ffffff
62 STR R1,[r0]
63
64 ;UPLLCON
65 LDR R0,=0x4c000008
66 LDR R1,=0x00038022
67 STR R1,[R0]
68 NOP
69 NOP
70 NOP
71 NOP
72 NOP
73 NOP
74 NOP
75
76 ;MPLLCON
77 LDR R0,=0x4c000004
78 LDR R1,=0x00044011
79 STR R1,[r0]
80
81 ;CLKCON
82 ;Witch divice need Clock
83 LDR R0,=0x4c00000c
84 LDR R1,=0x00fffff0
85 STR R1,[R0]
86
87 ;CLKSLOW
88 ;Low Clock
89 LDR R0,=0x4c000010
90 LDR R1,=0x00000004
91 STR R1,[R0]
92
93 ;CLKDIVN
94 ;HCLK = FCLK/3 PCLK = HCLK/2
95 LDR R0,=0x4c000014
96 LDR R1,=0x00000007
97 STR R1,[R0]
98
99;Uart0
100 ;Uart
101 ;LDR SP, =0x1000
102 ;LDR R2, =0x20800000
103 ;MOV R4, #0X7
104 ;STRB R4, [R2]
105 ;BL uart_test
106
107Memsetup
108
109 ;SDRAM Init
110 ldr r1,=MEM_CTL_BASE
111 adrl r2,mem_cfg_val
112 add r3,r1,#52
113
1141
115 ldr r4,[r2],#4
116 str r4,[r1],#4
117 cmp r1,r3
118 bne %1
119 nop
120 nop
121 nop
122 nop
123
124MEM_CTL_BASE EQU 0X48000000
125
126mem_cfg_val
127 DCD 0x22111110
128 DCD 0x00000700
129 DCD 0x00000700
130 DCD 0x00000700
131 DCD 0x00000700
132 DCD 0x00000700
133 DCD 0x00000700
134 DCD 0X00018005
135 DCD 0X00018005
136 DCD 0X008E0459
137 DCD 0X000000B1
138 DCD 0X00000030
139 DCD 0X00000030
140
141
142Nandflash
143
144 ;NandFlash，Bootloader CopyMyself 145 ldr sp,=0x33ef0000
146
147 IMPORT copy_myself
148
149;nand_begin=0x0
150;size=0x20000
151;sdram_begin=0x33f00000
152
153 BL copy_myself
154
155 ldr r1,=on_the_ram
156 add pc,r1,#0
157 nop
158 nop
159 nop
160
161on_the_ram
162
163 ;Select mode
164 IMPORT load
165 ldr sp,=0x33ef0000
166 BL uart_test
167 BL sdram_test
168 BL load
169
170 B .
171
172 END
2.Copy_myself.c
Code:
173/* NAND Flash registers 2440*/
174#include "DataType.h"
175#include "stdio.h"
176#define NFCONF (*(volatile unsigned int *)0x4e000000) 177#define NFCONT (*(volatile unsigned int *)0x4e000004) 178#define NFCMD (*(volatile unsigned char *)0x4e000008) 179#define NFADDR (*(volatile unsigned char *)0x4e00000c) 180#define NFDATA (*(volatile unsigned char *)0x4e000010) 181#define NFSTAT (*(volatile unsigned char *)0x4e000020) 182#define NFMECC0 (*(volatile unsigned *)0x4E00002C)
183#define NAND_CHIP_ENABLE (NFCONT &= ~(1<<1))
184#define NAND_CHIP_DISABLE (NFCONT |= (1<<1))
185#define NAND_CLEAR_RB (NFSTAT |= (1<<2))
186#define NAND_DETECT_RB { while(! (NFSTAT&(1<<0)) );}
187/* 在第一次实用NAND Flash前，复位一下NAND Flash */
188#define BUSY 1
189#define InitEcc() (NFCONT |= (1<<4))
190#define MEccUnlock() (NFCONT &= ~(1<<5))
191#define MEccLock() (NFCONT |= (1<<5))
192#define SEccUnlock() (NFCONT &= ~(1<<6))
193#define SEccLock() (NFCONT |= (1<<6))
194
195/*for 8 bit nand flash, only use NFMECC0*/
196#define RdNFMEcc() (NFMECC0)
197#define NAND_SECTOR_SIZE 512
198#define NAND_BLOCK_MASK (NAND_SECTOR_SIZE - 1)
199
200/*
201 inline void wait_idle(void)
202 {
203 while(!(NFSTAT & BUSY));
204 NFSTAT |= BUSY;
205 }
206 */
207
208
209void reset_nand(void)
210{
211 //int i=0;
212 // NFCONF &= ~0x800;
213 // for(; i<10; i++);
214
215 NFCONF = 0x1400;
216 NFCONT = 0x73;
217
218 NAND_CHIP_ENABLE;
219
220 NFCMD = 0xff; //reset command
221
222while(!(NFSTAT & BUSY));
223 NFSTAT |= BUSY;
224}
225
226
227/* 初始化NAND Flash */
228
229void init_nand(void)
230{
231
232 NFCONT = 0x73;
233 NAND_CHIP_DISABLE;
234 reset_nand();
235}
236
237/* low level nand read function */
238int nand_read_ll(unsigned char *buf, unsigned long start_addr, int size) 239{
240 int i, j;
241
242if ((start_addr & NAND_BLOCK_MASK) || (size & NAND_BLOCK_MASK)) { 243return -1; /* invalid alignment */
244 }
245
246 NAND_CHIP_ENABLE;
247
248for(i=start_addr; i < (start_addr + size);) {
249 /* READ0 */
250 NAND_CLEAR_RB;
251 NFCMD = 0;
252
253 /* Write Address */
254 NFADDR = i & 0xff;
255 NFADDR = (i >> 9) & 0xff;
256 NFADDR = (i >> 17) & 0xff;
257 NFADDR = (i >> 25) & 0xff;
258
259 NAND_DETECT_RB;
260
261for(j=0; j < NAND_SECTOR_SIZE; j++, i++) {
262 *buf = (NFDATA & 0xff);
263 buf++;
264 }
265
266 }
267 NAND_CHIP_DISABLE;
268return 0;
269}
270
271
272int NandErase(unsigned long start_addr)
273{
274if (start_addr & NAND_BLOCK_MASK) {
275return -1; /* invalid alignment */
276 }
277
278 NAND_CHIP_ENABLE;
279
280 NAND_CLEAR_RB;
281 NFCMD = 0x60;
282
283 NFADDR = (start_addr>> 9) & 0xff;
284 NFADDR = (start_addr>> 17) & 0xff;
285 NFADDR = (start_addr>> 25) & 0xff;
286
287
288
289 NFCMD = 0xd0;
290 NAND_DETECT_RB;
291 uart_printf("Erase 0x%x\r",start_addr);
292
293 NAND_CHIP_DISABLE;
294
295return 0;
296}
297
298int nand_write_ll(unsigned char *buf, unsigned long start_addr, int size) 299{
300 int i, j, k;
301
302if ((start_addr & NAND_BLOCK_MASK) || (size & NAND_BLOCK_MASK)) {
303return -1; /* invalid alignment */
304 }
305for(k = 0; k <= size / (16 * 1024); k++)
306 NandErase(start_addr + (k * 16 * 1024));
307 NAND_CHIP_ENABLE;
308
309for(i=start_addr; i < (start_addr + size);) {
310 /* READ0 */
311 // if(k % 32 == 0) NandErase(start_addr);
312
313 NAND_CLEAR_RB;
314 NFCMD = 0x80;
315
316 /* Write Address */
317 NFADDR = i & 0xff;
318 NFADDR = (i >> 9) & 0xff;
319 NFADDR = (i >> 17) & 0xff;
320 NFADDR = (i >> 25) & 0xff;
321
322
323for(j=0; j < NAND_SECTOR_SIZE; j++, i++) {
324 NFDATA = *buf;
325 buf++;
326 }
327 NFCMD = 0x10;
328 NAND_DETECT_RB;
329 }
330 NAND_CHIP_DISABLE;
331return 0;
332}
333
334
335void copy_myself(void)
336{
337 unsigned char *buf = ((unsigned char *)0x33f00000);
338 unsigned long start_addr = 0;
339 int size = 0x20000;
340
341 reset_nand();
342 init_nand();
343 nand_read_ll(buf,start_addr,size);
344
345}
3.dip.c
Code:
346/*
347 * dip.c - dip api & driver
348 *
349 * Board: akae2440
350 * environment: bootloader & ADS
351 * Author: akaedu
352 * Date: 2009-5-26
353 * web: https://www.sodocs.net/doc/048409187.html,
354 *
355 *
356 * GPIO address_MAP
357 *
358 * CPLD_MAP_BASE physical address is 0x20800000
359 * CPLD_LED physical address is 0x20800000
360 * CPLD_SEG physical address is 0x20800080
361 * CPLD_DIP physical address is 0x208000a0
362 *
363 * GPIO port_MAP
364 *
365 * GPA_PORT~GPB_PORT(130 multi-functional input port pins)
366 * GPIO_BASE : GPACON : 0x56000000
367 *
368 * NAME GPIO CPLD_IN CPLD_OUT GPIO_CON MODE_bit_CON
GPIO_DAT MODE_bit_DAT
369 * BEEP GPB0 TOUT0 BEEP 0x56000010 [1:0] 0x56000014 [0]
370 *
371 * GPIO key_scn_MAP
372 *
373 * NAME PORT_OUT PORT_IN
374 * KEY(sw1) KBOUT1 : GPB8 KBIN1 : ENT0 : GPF0
375 * KEY(sw2) KBOUT0 : GPB9 KBIN1 : ENT0 : GPF0
376 * KEY(sw3) KBOUT1 : GPB8 KBIN0 : ENT2 : GPF2
377 * KEY(sw4) KBOUT1 : GPB8 KBIN1 : ENT2 : GPF2
378 *
379 * GPIO_CON GPIO_DAT GPIO MODE_bit_CON
MODE_bit_DAT
380 * GPBCON : 0x56000010 GPBDAT : 0x56000014 GPB8 [17:16]
[8]
381 * GPBCON : 0x56000010 GPBDAT : 0x56000014 GPB9 [19:18]
[9]
382 * GPFCON : 0x56000050 GPBDAT : 0x56000054 GPF0 [1:0]
[0]
383 * GPFCON : 0x56000050 GPBDAT : 0x56000054 GPF2 [5:4]
[2]
384 *
385 */
386#include "dip.h"
387#include "seg7.h"
388
389#define CPLD_DIP *((volatile unsigned char *)0x208000a0)
390
391int dip_init(void)
392{
393return 0;
394}
395int dip_num(void)
396{
397return CPLD_DIP;
398}
399
400int dip_test(void)
401{
402 int dip_input;
403 int i = 5000000;
404 seg7_init();
405 dip_init();
406
407while(i--)
408 {
409 dip_input = dip_num();
410 seg7_display_num(dip_input);
411 }
412
413return 0;
414}
4.load.c
Code:
415#include "uart.h"
416#include "shell.h"
417#include "stdlib.h"
418#include "stdio.h"
419#include "nand.h"
420
421#define SEC 3
422#define LOAD_OS 0
423#define LOAD_SHELL 1
424#define OS_MEM_ADDR 0x31000000
425#define OS_ADDR (100 * 32 * 512) /*OS address*/
426#define OS_SIZE 0x20000
427
428/*Move OS to Sdram From NandFlash*/
429void os_test(void)
430{
431
432 unsigned char *buf = (unsigned char *)OS_MEM_ADDR;
433 unsigned long start = OS_ADDR;
434 int size = OS_SIZE;
435
436 uart_printf("\rcopy opration system to the sdrm from nanflash...\r"); 437
438 reset_nand();
439 init_nand();
440 nand_read_ll(buf, start, size);
441
442}
443
444/*Wait for User Enter Any Key to Login in the Shell of Bootloader*/
445int delay_p(int sec)
446{
447 int osec = 500000, i, j;
448
449 uart_printf("Enter any key to load in the shell of bootloader:%d", sec); 450for(i = 0; i < sec; i++)
451 {
452for(j = 0; j < osec; j++)
453 {
454if(UTRSTAT0 & UTRSTAT_R_READY){
455 uart_getchar();
456return LOAD_SHELL;
457 }
458 }
459
460 uart_printf("\b%d", sec - i);
461 }
462 //uart_printf("return");
463return LOAD_OS;
464}
465
466/*Shell or OS*/
467void load(void)
469 int load_stat;
470
471if((load_stat = delay_p(SEC)) == LOAD_OS)
472 {
473 os_test();
474 uart_printf("\rrun in the oprition system...\r");
475 go((void *)OS_MEM_ADDR);
476 }
477else
478 {
479 shell();
480 }
481}
5.seg7.c
Code:
482/*
483 * seg7.c - seg7 api & driver
484 *
485 * Board: akae2440
486 * environment: bootloader & ADS
487 * Author: akaedu
488 * Date: 2009-5-26
489 * web: https://www.sodocs.net/doc/048409187.html,
490 *
491 *
492 * GPIO address_MAP
493 *
494 * CPLD_MAP_BASE physical address is 0x20800000
495 * CPLD_LED physical address is 0x20800000
496 * CPLD_SEG7 physical address is 0x20800080
497 * CPLD_DIP physical address is 0x208000a0
498 *
499 * GPIO port_MAP
500 *
501 * GPA_PORT~GPB_PORT(130 multi-functional input port pins)
502 * GPIO_BASE : GPACON : 0x56000000
503 *
504 * NAME GPIO CPLD_IN CPLD_OUT GPIO_CON MODE_bit_CON
GPIO_DAT MODE_bit_DAT
505 * BEEP GPB0 TOUT0 BEEP 0x56000010 [1:0] 0x56000014 [0]
506 *
507 * GPIO key_scn_MAP
509 * NAME PORT_OUT PORT_IN
510 * KEY(sw1) KBOUT1 : GPB8 KBIN1 : ENT0 : GPF0
511 * KEY(sw2) KBOUT0 : GPB9 KBIN1 : ENT0 : GPF0
512 * KEY(sw3) KBOUT1 : GPB8 KBIN0 : ENT2 : GPF2
513 * KEY(sw4) KBOUT1 : GPB8 KBIN1 : ENT2 : GPF2
514 *
515 * GPIO_CON GPIO_DAT GPIO MODE_bit_CON
MODE_bit_DAT
516 * GPBCON : 0x56000010 GPBDAT : 0x56000014 GPB8 [17:16] [8]
517 * GPBCON : 0x56000010 GPBDAT : 0x56000014 GPB9 [19:18] [9]
518 * GPFCON : 0x56000050 GPBDAT : 0x56000054 GPF0 [1:0] [0]
519 * GPFCON : 0x56000050 GPBDAT : 0x56000054 GPF2 [5:4] [2]
520 *
521 */
522#include "seg7.h"
523#include "shell.h"
524
525#define CPLD_SEG7 *((volatile unsigned char *)0x20800080)
526
527
528/* delay for about one second */
529/*static void delay(int time)
530{
531 int i, j;
532
533 for(i = 0; i < time; i++)
534 for(j = 0; j < 500000; j++)
535 ;
536}*/
537
538int seg7_init(void)
539{
540 CPLD_SEG7 = 0x0;
541
542return 0;
543}
544
545/* display number on seg7 */
546int seg7_display_num(int num)
548 CPLD_SEG7 = 1< 549 550return 0; 551} 552 553int seg7_test(void) 554{ 555 int i; 556 557 seg7_init(); 558for(i = 0; i < 8; i++) 559 { 560 seg7_display_num(i); 561 delay(1); 562 } 563return 0; 564} 8.shell.c Code: 565#include "shell.h" 566#include "uart.h" 567#include "stdlib.h" 568#include "stdio.h" 569#include "xmodem.h" 570#include "dip.h" 571#include "seg7.h" 572#include "nand.h" 573 574#define START_ADDR 0x30000000 575#define END_ADDR 0x34000000 576#define MAX_LINE 256 577#define CMD_NUM 11 578#define LED_NUM 8 579#define START_FLASH 0x0 580#define END_FLASH 0x40000000 581#define START_MEM 0x30000000 582#define END_MEM 0x34000000 583#define MAX_SIZE (END_MEM - START_MEM - 0x20000) 584#define LED_ADDR *((volatile unsigned int *)0x20800000) 585#define GPB0 *((volatile unsigned int *)0x56000010) 586#define BEEP *((volatile unsigned int *)0x56000014) 587 588/*delay*/ 589void delay(int sec) 590{ 591 int i, j; 592for(i = 0; i < sec; i++) 593 { 594for(j = 0; j < 500000; j++) 595 ; 596 } 597} 598 599struct CMD{ 600 char *cmd_line; 601void (*fun)(void *); 602}cmd[CMD_NUM] ={ 603 {"help", help}, 604 {"loadx", loadx}, 605 {"go", go}, 606 {"led_on", led_on}, 607 {"led_off", led_off}, 608 {"beep_test", beep_test}, 609 {"led_test", led_test}, 610 {"seg7_test", seg7_on}, 611 {"dip4_test", dip4_on}, 612 {"flash_load", flash_load}, 613 {"flash_write", flash_write}, 614//{"flash_write", flash_write}, 615}; 616 617 618void flash_load(void *arg) 619{ 620 char *argv[4], *end; 621 int flash_start, mem_start, size; 622 623 argv[1] = arg; 624 uart_printf("the arg is %s\r", arg); 625if((end = found_ch(arg, ' ')) == NULL) 626 { 627 uart_printf("Uaseage1: 629 } 630else 631 { 632 *end = '\0'; 633 end++; 634 } 635 636 argv[2] = end; 637if((end = found_ch(end, ' ')) == NULL) 638 { 639 uart_printf("Uaseage2: 641 } 642else 643 { 644 *end = '\0'; 645 end++; 646 } 647 648 argv[3] = end; 649 650if((flash_start = my_atox(argv[1])) < START_FLASH || (mem_start = my_atox(argv[2])) < START_MEM ||(size = my_atox(argv[3])) > MAX_SIZE || (mem_start + size) > END_MEM) 651 { 652 uart_printf("Access Violation: Please check your address\r"); 653 uart_printf("flash_start = %x\rmem_start = %x\r size = %x\r", flash_start, mem_start, size); 654 } 655else 656 { uart_printf("flash_start = %x\rmem_start = %x\r size = %x\r", flash_start, mem_start, size); 657 nand_read_ll((unsigned char *)mem_start, flash_start, size); 658 } 659} 660#if 1 661void flash_write(void *arg) 662{ 663 char *argv[4], *end; 664 int flash_start, mem_start, size; 665 666 argv[1] = arg; 667 uart_printf("the arg is %s\r", arg); 668if((end = found_ch(arg, ' ')) == NULL) 669 { 670 uart_printf("Uaseage1: 672 } 673else 674 { 675 *end = '\0'; 676 end++; 677 } 678 679 argv[2] = end; 680if((end = found_ch(end, ' ')) == NULL) 681 { 682 uart_printf("Uaseage2: 684 } 685else 686 { 687 *end = '\0'; 688 end++; 689 } 690 691 argv[3] = end; 692 693if((flash_start = my_atox(argv[2])) < START_FLASH || (mem_start = my_atox(argv[1])) < START_MEM ||(size = my_atox(argv[3])) > MAX_SIZE || (mem_start + size) > END_MEM) 694 { 695 uart_printf("Access Violation: Please check your address\r"); 696 // reset_nand(); 697 // init_nand(); 698 uart_printf("flash_start = %x\rmem_start = %x\r size = %x\r", flash_start, mem_start, size); 699 } 700else 701 { 702 uart_printf("flash_start = %x\rmem_start = %x\r size = %x\r", flash_start, mem_start, size); 703 // reset_nand(); 704 // init_nand(); 705 nand_write_ll((unsigned char *)mem_start, flash_start, size); 706 } 707} 708 709#endif 710 711void loadx(void * argv) 712{ 713 int argc; 714 BootLoader引导程序 一、实验目的 1.学会配置linux下的minicom和windows下的超级终端 2.了解bootloader的基本概念和框架结构 3.了解bootloader引导操作系统的过程 4.掌握bootloader程序的编译方法 5.掌握bootloader程序的使用方法 二、实验内容 1. 学习x-loader 作用和编译过程 2.学习uboot作用和编译过程 3.学习bootloader的操作 三、实验设备 PentiumII以上的PC机， LINUX操作系统 四、BOOTLOADER程序说明 完整的系统由x-loader、u-boot、kernel（内核）、rootfs（根文件系统）组成，x-loader 是一级引导程序，其作用是初始化CPU，拷贝u-boot到内存，然后把控制权交给u-boot。当OMAP3530上电时，memory controller(内存控制器)还未初始化，这个任务便由完成的x-loader。初始化外部RAM控制器，把u-boot读到外部RAM，之后把控制入口交给。u-boot 是二级引导程序，其作用主要是引导内核，提供映像更新，同用户进行交互。系统结构图如 下： 1. BootLoader的作用 在嵌入式系统中，BootLoader的作用与PC机上的BIOS类似，其主要作用：（1）初始化硬件设备；（2）建立内存空间的映射图；（3）完成内核的加载，为内核设置启动参数。通过BootLoader可以完成对系统板上的主要部件如CPU、SDRAM、Flash、串行口等进行初始化，也可以下载文件到系统板上，对Flash进行擦除与编程。当运行操作系统时，它会在操作系统内核运行之前运行，通过它，可以分配内存空间的映射，从而将系统的软硬件环境带到一个合适的状态，以便为最终调用操作系统准备好正确的环境。 通常，BootLoader 是依赖于硬件而实现的，特别是在嵌入式系统中。因此，在嵌入式系统里建立一个通用的 BootLoader 几乎是不可能的，不同的处理器架构都有不同的 详解bootloader的执行流程与ARM Linux启动过程分析 ARM Linux启动过程分析是本文要介绍的内容，嵌入式Linux 的可移植性使得我们可以在各种电子产品上看到它的身影。对于不同体系结构的处理器来说Linux的启动过程也有所不同。 本文以S3C2410 ARM处理器为例，详细分析了系统上电后bootloader的执行流程及ARM Linux的启动过程。 1、引言 Linux 最初是由瑞典赫尔辛基大学的学生Linus Torvalds在1991 年开发出来的，之后在GNU的支持下，Linux 获得了巨大的发展。虽然Linux 在桌面PC 机上的普及程度远不及微软的Windows 操作系统，但它的发展速度之快、用户数量的日益增多，也是微软所不能轻视的。而近些年来Linux 在嵌入式领域的迅猛发展，更是给Linux 注入了新的活力。 一个嵌入式Linux 系统从软件角度看可以分为四个部分：引导加载程序（bootloader），Linux 内核，文件系统，应用程序。 其中bootloader是系统启动或复位以后执行的第一段代码，它主要用来初始化处理器及外设，然后调用Linux 内核。 Linux 内核在完成系统的初始化之后需要挂载某个文件系统做为根文件系统（Root Filesystem）。 根文件系统是Linux 系统的核心组成部分，它可以做为Linux 系统中文件和数据的存储区域，通常它还包括系统配置文件和运行应用软件所需要的库。 应用程序可以说是嵌入式系统的“灵魂”，它所实现的功能通常就是设计该嵌入式系统所要达到的目标。如果没有应用程序的支持，任何硬件上设计精良的嵌入式系统都没有实用意义。 从以上分析我们可以看出bootloader 和Linux 内核在嵌入式系统中的关系和作用。Bootloader在运行过程中虽然具有初始化系统和执行用户输入的命令等作用，但它最根本 算法设计与分析课程设计报告 学院计算机科学与技术 专业计算机科学与技术 年级2011 姓名XXX 学号 2013年5 月19 日 题目：最小生成树问题的算法实现及复杂度分析 摘要：该程序操作简单，具有一定的应用性。数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。而最小生成树算法是算法设计与分析中的重要算法，最小生成树也是最短路径算法。最短路径的问题在现实生活中应用非常广泛，如邮递员送信、公路造价等问题。本设计以Visual Studio 2010作为开发平台，C/C++语言作为编程语言，以邻接矩阵作为存储结构，编程实现了最小生成树算法。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM 经典算法的算法思想，最后用这种经典算法实现了最小生成树的生成。 引言：假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n（n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。一棵生成树的代价就是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。 最小生成树算法分析 一、生成树的概念 若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。 对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后一般不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。要访问其它顶点需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs 或dfs，这样得到的是生成森林。 由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。 可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。 二、求图的最小生成树算法 严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V， E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。 对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。 求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。 例1、城市公交网 [问题描述] 有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。 [输入] n（城市数，1<=n<=100） e（边数） 以下e行，每行3个数i,j,w ij，表示在城市i,j之间修建高速公路的造价。 [输出] n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。 [举例] 下面的图（A）表示一个5个城市的地图，图（B）、（C）是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树，其权和分别为20和33，前者比后者好一些，但并不是最小生成树，最小生成树的权和为19。 [问题分析] 出发点：具有n个顶点的带权连通图，其对应的生成树有n-1条边。那么选哪n-1条边呢？设图G的度为n，G=（V，E），我们介绍两种基于贪心的算法，Prim算法和Kruskal算法。 1、用Prim算法求最小生成树的思想如下： ①设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集； ②选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S； ③重复下列操作，直到选取了n-1条边： 选取一条权值最小的边（X，Y），其中X∈S，not (Y∈S)； 将顶点Y加入集合S，边（X，Y）加入集合TE； ④得到最小生成树T =（S，TE） Boot Loader的启动流程和开发经验总结 Windows CE最大程度继承了桌面版Windows的丰富功能，但是Windows CE并不是一个通用的安装版操作系统。在形形色色的嵌入式设备世界里，一款CE系统通常只会针对某一种硬 件平台生成。 一般来说，Windows CE的开发过程可以分为：0AL(OEM Abstraction Layer)、驱动、应用程序开发三个步骤。其中，0AL开发最基本的一步是板级支持包（BSP），而BootLoader 设计则在BSP开发中具有极为关键的地位。 1．什么是BootLoader 嵌入式系统的启动代码一般由两部分构成：引导代码和操作系统执行环境的初始化代码。其中引导代码一般也由两部分构成：第一部分是板级、片级初始化代码，主要功能是通过设置寄存器初始化硬件的工作方式，如设置时钟、中断控制寄存器等，完成内存映射、初始化MMU等。第二部分是装载程序，将操作系统和应用程序的映像从只读存储器装载或者拷贝到系统的RAM中并执行。 （1）什么是板级BSP? BSP(Board Support Package)是板级支持包,是介于主板硬件和操作系统之间的一层,主要是为了支持操作系统，使之能够更好的运行于硬件主板。不同的操作系统对应于不同形式的BSP,例如WinCE的BSP和Linux的BSP相对于某CPU来说尽管实现的功能一样,可是写法和接口定义是完全不同的。所以，BSP一定要按照该系统BSP的定义形式来写，这样才能与上 层OS保持正确的接口,良好的支持上层OS。 （2）什么是Boot Loader 在BSP中有一个重要的组成部分就是BootLoader,它是在操作系统内核运行之前运行的一段小程序。通过这段小程序，可以初始化硬件设备、建立内存空间的映射图，从而将系统的软硬件环境带到一个合适的状态，为调用操作系统内核准备好环境。 一般来说，在嵌入式世界里BootLoader 是严重地依赖于硬件的，因此想建立一个通用的 BootLoader 几乎是不可能的。不同的 CPU 体系结构有不同的BootLoader，而且除了依赖于 CPU的体系结构外，BootLoader还依赖于具体的嵌入式板级设备的配置。这也就是说，对于两块不同的嵌入式板而言，即使它们是基于同一种 CPU 结构而构建的，要想让运行在一块板子上的 BootLoader 程序也能运行在另一块板子上，通常也都需要修改 BootLoader 的源程序。 2．BootLoader在PC机与嵌入式的区别比较 （1）引导程序在PC机和嵌入式上的区别 一般来说，在PC的硬件平台上，由于硬件启动根本就不是通过BootLoader（而是通过BIOS），所以BootLoader就不需要对CPU加电后的初始化做任何工作。在桌面系统中，有以下几种设备可以作为启动设备使用：硬盘、USB盘、光盘驱动器、还有网卡的Boot ROM 等。但无论选择了哪一种启动设备，操作系统都会去将该设备起始地址的内容读入内存，BIOS 将控制移交给引导装载程序。如果启动设备是IDE硬盘，这时通常将引导装载程序装入第一个扇区(通常被称做主引导扇区，MBR），然后将内容读入内存再运行。 在嵌入式平台上，引导装载程序是在硬件上执行的第一段代码，通常将引导程序放置在不易丢失的存储器的开始地址或者是系统冷启动时PC寄存器的初始值。在嵌入式系统中，通常并没有像BIOS那样的固件程序，因此整个系统的加载启动任务就完全由BootLoader来完 最小生成树的两种经典算法的分析及实现 摘要：数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM和KRUSKAL的两种经典算法的算法思想，对两者进行了详细的比较，最后用这两种经典算法实现了最小生成树的生成。 关键词：连通图，赋权图，最小生成树，算法，实现 1 前言 假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n （n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。一棵生成树的代价就是树上各边的代价之和。 2图的概念 2.1 定义 无序积 在无序积中， 无向图，其中为顶点(结点)集，为边集，，中元素为无向边，简称边。 有向图，其中为顶点(结点)集，为边集，，中元素为有向边，简称边。 有时，泛指有向图或无向图。 2.2 图的表示法 有向图，无向图的顶点都用小圆圈表示。 无向边——连接顶点的线段。 有向边——以为始点，以为终点的有向线段。 2.3 概念 (1)有限图——都是有限集的图。 阶图——的图。 零图——的图。特别，若又有，称平凡图。 (2)关联 (边与点关系)——设边(或)，则称与(或)关联。 无环 孤立点——无边关联的点。 环——一条边关联的两个顶点重合，称此边为环 (即两顶点重合的边)。 悬挂点——只有一条边与其关联的点，所对应的边叫悬挂边。 (3)平行边——关联于同一对顶点的若干条边称为平行边。平行边的条数称为重数。 多重图——含有平行边的图。 简单图——不含平行边和环的图。 2.4 完全图 设为阶无向简单图，若中每个顶点都与其余个顶点相邻，则 称为阶无向完全图，记作。 若有向图的任一对顶点，既有有向边，又有有向边，则 称为有向完全图。 例如： Bootloader分析 ?熟悉BootLoader的实现原理?认识Bootloader的主要任务?熟悉BootLoader的结构框架?U-boot使用 引言本章详细地介绍了基于嵌入式系统中的OS启动加载程序――Boot Loader的概念、软件设计的主要任务以及结构框架等内容。 一个嵌入式Linux系统从软件的角度看通常可以分为四个层次： ?1.引导加载程序。包括固化在固件(firmware)中的boot代码(可 选)，和Boot Loader两大部分。 ?2.Linux内核。特定于嵌入式板子的定制内核以及内核的启动参数。 ?3.文件系统。包括根文件系统和建立于Flash内存设备之上文件 系统。通常用ram disk来作为root fs。 ?4.用户应用程序。特定于用户的应用程序。有时在用户应用程序和 内核层之间可能还会包括一个嵌入式图形用户界面。常用的嵌入式GUI有：MicroWindows和MiniGUI。 ?引导加载程序是系统加电后运行的第一段软件代码。回忆一下PC 的体系结构我们可以知道，PC机中的引导加载程序由BIOS(其本质就是一段固件程序)和位于硬盘MBR中的OS Boot Loader（比如，LILO和GRUB等）一起组成。 ?BIOS在完成硬件检测和资源分配后，将硬盘MBR中的Boot Loader读到系统的RAM中，然后将控制权交给OS Boot Loader。 Boot Loader的主要运行任务就是将内核映象从硬盘上读到RAM 中，然后跳转到内核的入口点去运行，也即开始启动操作系统。 而在嵌入式系统中，通常并没有像BIOS那样的固件程序（注，有的嵌入式CPU也会内嵌一段短小的启动程序），因此整个系统的加载启动任务就完全由Boot Loader来完成。 ?比如在一个基于ARM7TDMI core的嵌入式系统中，系统在上电 或复位时通常都从地址0x00000000处开始执行，而在这个地址 处安排的通常就是系统的Boot Loader程序。 一、树及生成树的基本概念 树是无向图的特殊情况，即对于一个N个节点的无向图，其中只有N-1条边，且图中任意两点间有且仅有一条路径，即图中不存在环，这样的图称为树，一般记为T。树定义有以下几种表述： (1)、T连通、无圈、有n个结点，连通有n－1条边；(2)、T无回路，但不相邻的两个结点间联以一边，恰得一个圈；(3)、T连通，但去掉任意一边，T就不连通了（即在点集合相同的图中，树是含边数最少的连通图）；(4)、T的任意两个结点之间恰有一条初等链。 例如：已知有六个城市，它们之间要架设电话线，要求任 意两个城市均可以互相通话，并且电话线的总长度最短。若用 六个点v1…v6代表这六个城市，在任意两个城市之间架设电话 线，即在相应的两个点之间连一条边。这样，六个城市的一个 电话网就作成一个图。任意两个城市之间均可以通话，这个图 必须是连通图，且这个图必须是无圈的。否则，从圈上任意去 掉一条边，剩下的图仍然是六个城市的一个电话网。图5-6是 一个不含圈的连通图，代表了一个电话线网。 生成树（支撑树） 定义：如果图G’是一棵包含G的所有顶点的树，则称G’是G的一个支撑树或生成树。例如,图5-7b是图5-7a的一个支撑树。 定理：一个图G有生成树的条件是G是连通图。 证明:必要性显然； 充分性:设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个生成树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一生成子图G1。若G1不含圈，则G1是G的一个生成树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一生成子图G2。依此类推，可以得到图G的一个生成子 图G K，且不含圈，从而G K是一个生成树。 寻找连通图生成树的方法： 破圈法：从图中任取一个圈，去掉一条边。再对剩下的图 重复以上步骤，直到不含圈时为止，这样就得到一个生成树。 取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3。在剩下的图 中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4。再从圈（v3,v4,v5,v3） 中去掉边e6。再从圈(v1,v2,v5,v4,v3,v1）中去掉边e7， 这样，剩下的图不含圈，于是得到一个支撑树，如图所示。 避圈法：也称为生长法，从图中某一点开始生长边，逐步扩展成长为一棵树，每步选取与已入树的边不构成圈的那些边。 实验5 最小生成树算法的设计与实现 一、实验目的 1、根据算法设计需要, 掌握连通图的灵活表示方法； 2、掌握最小生成树算法，如Prim、Kruskal算法； 3、基本掌握贪心算法的一般设计方法； 4、进一步掌握集合的表示与操作算法的应用。 二、实验内容 1、认真阅读算法设计教材和数据结构教材内容, 熟习连通图的不同表示方法和最小生成树算法； 2、设计Kruskal算法实验程序。 有n个城市可以用（n-1）条路将它们连通，求最小总路程的和。 设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止。 三、Kruskal算法的原理方法 边权排序: 1 3 1 4 6 2 3 6 4 1 4 5 2 3 5 3 4 5 2 5 6 1 2 6 3 5 6 5 6 6 1. 初始化时：属于最小生成树的顶点U={} 不属于最小生成树的顶点V={1，2，3，4，5，6} 2. 根据边权排序，选出还没有连接并且权最小的边（1 3 1），属于最小生成树 的顶点U={1，3}，不属于最小生成树的顶点V={2,4,5,6} 3. 根据边权排序，选出还没有连接并且权最小的边（4 6 2），属于最小生成树的顶点U={{1，3}，{4，6}}（还没有合在一起，有两颗子树），不属于最小生成树的顶点V={2,5} 4. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，3，4，6}（合在一起），不属于最小生成树的顶点V={2,5} 5. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，6},，不属于最小生成树的顶点V={5} 6. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，5，6}此时，最小生成树已完成 Kruskal算法求最小生成树（JA V A） 代码： package homework; import java.util.Scanner; import java.util.Arrays; import java.util.ArrayList; class Edge { public int start;//始边 public int end;//终边 public double cost;//权重 } public class MinSpanningTree_Kruskal{ private static int MAX = 100; private ArrayList Linux启动过程 许多人对Linux的启动过程感到很神秘，因为所有的启动信息都在屏幕上一闪而过。其实Linux的启动过程并不象启动信息所显示的那样复杂，它主要分成两个阶段： 1.启动内核。在这个阶段，内核装入内存并在初始化每个设备驱动器时打印信息。 2.执行程序init。装入内核并初始化设备后，运行init程序。init程序处理所有程序的启动， 包括重要系统精灵程序和其它指定在启动时装入的软件。 下面以Red Hat为例简单介绍一下Linux的启动过程。 一、启动内核 首先介绍启动内核部分。电脑启动时，BIOS装载MBR，然后从当前活动分区启动，LILO获得引导过程的控制权后，会显示LILO提示符。此时如果用户不进行任何操作，LILO将在等待制定时间后自动引导默认的操作系统，而如果在此期间按下TAB键，则可以看到一个可引导的操作系统列表，选择相应的操作系统名称就能进入相应的操作系统。当用户选择启动LINUX操作系统时，LILO就会根据事先设置好的信息从ROOT文件系统所在的分区读取LINUX映象，然后装入内核映象并将控制权交给LINUX内核。LINUX内核获得控制权后，以如下步骤继续引导系统： 1. LINUX内核一般是压缩保存的，因此，它首先要进行自身的解压缩。内核映象前面的一些代码完成解压缩。 2. 如果系统中安装有可支持特殊文本模式的、且LINUX可识别的SVGA卡，LINUX会提示用户选择适当的文本显示模式。但如果在内核的编译过程中预先设置了文本模式，则不会提示选择显示模式。该显示模式可通过LILO或RDEV工具程序设置。 3. 内核接下来检测其他的硬件设备，例如硬盘、软盘和网卡等，并对相应的设备驱动程序进行配置。这时，显示器上出现内核运行输出的一些硬件信息。 4. 接下来，内核装载ROOT文件系统。ROOT文件系统的位置可在编译内核时指定，也可通过LILO 或RDEV指定。文件系统的类型可自动检测。如果由于某些原因装载失败，则内核启动失败，最终会终止系统。 二、执行init程序 其次介绍init程序，利用init程序可以方便地定制启动其间装入哪些程序。init的任务是启动新进程和退出时重新启动其它进程。例如，在大多数Linux系统中，启动时最初装入六个虚拟的控制台进程，退出控制台窗口时，进程死亡，然后init启动新的虚拟登录控制台，因而总是提供六个虚拟登陆控控制台进程。控制init程序操作的规则存放在文件/etc/inittab中。Red Hat Linux缺省的inittab文件如下：# #inittab This file describes how the INIT process should set up the system in a certain #run-level. # # #Default runlevel.The runlevels used by RHS are: #0-halt(Do NOT set initdefault to this) #1-Single user mode #2-Multiuser,without NFS(the same as 3,if you do not have networking) #3-Full multiuser mode #4-unused #5-X11 #6-reboot(Do NOT set initdefault to this) Boot Loader Windows CE最大程度继承了桌面版Windows的丰富功能，但是Windows CE并不是一个通用的安装版操作系统。在形形色色的嵌入式设备世界里，一款CE系统通常只会针对某一种硬件平台生成。 一般来说，Windows CE的开发过程可以分为：0AL(OEM Abstraction Layer)、驱动、应用程序开发三个步骤。其中，0AL开发最基本的一步是板级支持包（BSP），而BootLoader 设计则在BSP开发中具有极为关键的地位。 1．什么是BootLoader 嵌入式系统的启动代码一般由两部分构成：引导代码和操作系统执行环境的初始化代码。其中引导代码一般也由两部分构成：第一部分是板级、片级初始化代码，主要功能是通过设置寄存器初始化硬件的工作方式，如设置时钟、中断控制寄存器等，完成内存映射、初始化MMU等。第二部分是装载程序，将操作系统和应用程序的映像从只读存储器装载或者拷贝到系统的RAM中并执行。 （1）什么是板级BSP? BSP(Board Support Package)是板级支持包,是介于主板硬件和操作系统之间的一层,主要是为了支持操作系统，使之能够更好的运行于硬件主板。不同的操作系统对应于不同形式的BSP,例如WinCE的BSP和Linux的BSP相对于某CPU来说尽管实现的功能一样,可是写法和接口定义是完全不同的。所以，BSP一定要按照该系统BSP的定义形式来写，这样才能与上层OS保持正确的接口,良好的支持上层OS。 （2）什么是Boot Loader 在BSP中有一个重要的组成部分就是BootLoader,它是在操作系统内核运行之前运行的一段小程序。通过这段小程序，可以初始化硬件设备、建立内存空间的映射图，从而将系统的软硬件环境带到一个合适的状态，为调用操作系统内核准备好环境。 课程设计报告 课程设计名称：数据结构课程设计 课程设计题目：最小生成树Kruskal算法 院（系）： 专业： 班级： 学号： 姓名： 指导教师： 目录 1 课程设计介绍 (1) 1.1课程设计内容 (1) 1.2课程设计要求 (1) 2 课程设计原理 (2) 2.1课设题目粗略分析 (2) 2.2原理图介绍 (4) 2.2.1 功能模块图 (4) 2.2.2 流程图分析 (5) 3 数据结构分析 (11) 3.1存储结构 (11) 3.2算法描述 (11) 4 调试与分析 (13) 4.1调试过程 (13) 4.2程序执行过程 (13) 参考文献 (16) 附录（关键部分程序清单） (17) 1 课程设计介绍 1.1 课程设计内容 编写算法能够建立带权图，并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。 1.2 课程设计要求 1.顶点信息用字符串，数据可自行设定。 2.参考相应的资料，独立完成课程设计任务。 3.交规范课程设计报告和软件代码。 2 课程设计原理 2.1 课设题目粗略分析 根据课设题目要求，拟将整体程序分为三大模块。以下是三个模块的大体分析： 1.要确定图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。 2.Kruskal算法。该算法设置了集合A，该集合一直是某最小生成树的子集。在每步决定是否把边（u,v）添加到集合A中，其添加条件是A∪{（u,v）}仍然是最小生成树的子集。我们称这样的边为A的安全边，因为可以安全地把它添加到A中而不会破坏上述条件。 3.Dijkstra算法。算法的基本思路是：假设每个点都有一对标号（d j,p j）,其中d是从起源点到点j的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；p j则是从s到j 的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下： 1）初始化。起源点设置为：①d s=0,p s为空；②所有其它点：d i=∞,p i=？； ③标记起源点s，记k=s，其他所有点设为未标记的。 2）k到其直接连接的未标记的点j的距离，并设置： d j=min[d j, d k+l kj] ?Bootloader是在单片机上电启动时执行的一小段程序。也称作固件，通过这段程序，可以初始化硬件设备、建立内存空间的映射图，从而将系统的软硬件环境带到一个合适的状态，以便为最终调用应用程序准备好正确的环境。 Boot代码由MCU启动时执行的指令组成。这里的loader指向MCU的Flash中写入新的应用程序。因此，Bootloader是依赖于特定的硬件而实现的，因此，在众多嵌入式产品中目前还不可能实现通用Bootloader。 Bootloader的最大优点是：在不需要外部编程器的情况下，对嵌入式产品的应用代码进行更新升级。它使得通过局域网或者Intemet远程更新程序成为可能。例如，如果有5 000个基于MCU的电能表应用程序需要更新，电能表制造商的技术人员就可以避免从事对每一个电能表重新编程的巨大工作量，通过使用Bootloader的功能，由控制中心通过电能表抄表系统网络，远程对5 000个电表重新编程。可见，Bootloader功能对于嵌入式系统的广泛应用具有十分重要的意义。 1 78K0/Fx2系列单片机简介 78K0/Fx2系列是带CAN控制器的8位单片机，该系列单片机广泛应用于汽车电子，智能仪表等领域。其内置POC（可编程上电清零电路）/LVI（可编程低电压指示器），单电压自编程闪存，引导交换功能（闪存安全保护），具有低功耗、宽电压范围、超高抗干扰等性能。 78K0系列单片机支持自编程（Self-programming）。所谓自编程，是指用Flash存储器中的驻留的软件或程序对Flash存储器进行擦除/编程的方法。通过单片机的自编程功能，可以设计Bootloader程序，通过串口等通信接口实现对产品重新编程、在线升级的功能。 以μPD78F0881为例。μPD78F0881为78KO/Fx2系列中的一款44管脚单片机，内置32 KB Flash ROM，2 KB RAM，自带2个串行通信接口。其内部Flash结构如图1所示。为了方便实现擦除和编程，人为地将整个Flash分成若干个block，每个block 大小为1 KB。block为自编程库函数中空白检测、擦除、校验的最小单位。blockO从地址0000H开始，程序都从0000H开始执行。block0～block3共4 KB存储空间为 Bootloader程序存储区域。block4～block31为应用程序存储区域。 最小生成树的算法 王洁 引言： 求连通图的最小生成树是数据结构中讨论的一个重要问题．在现实生活中，经常遇到如何得到连通图的最小生成树，求最小生成树不仅是图论的基本问题之一 ,在实际工作中也有很重要的意义，,人们总想寻找最经济的方法将一个终端集合通过某种方式将其连接起来 ,比如将多个城市连为公路网络 ,要设计最短的公路路线;为了解决若干居民点供水问题 ,要设计最短的自来水管路线等.而避开这些问题的实际意义 ,抓住它们的数学本质 ,就表现为最小生成树的构造。下面将介绍几种最小生成树的算法。 一，用“破圈法”求全部最小生成树的算法 1 理论根据 1.1 约化原则 给定一无向连通图 G =（V ,E ）（ V 表示顶点，E 表示边），其中 V={ 1v , 2v ,3v …… n v },E= { 1e , 2e , 3e …… n e }对于 G 中的每条边 e ∈ E 都赋予权ω（i e ）>0，求生成树 T = （V ,H ），H ? E ，使生成树所有边权最小，此生成树称为最小生成树． （1） 基本回路 将属于生成树 T 中的边称为树枝，树枝数为n -1，不属于生成树的边称为连枝．将任一连枝加到生成树上后都会形成一条回路．把这种回路称为基本回路，记为()cf e 。 基本回路是由 T 中的树枝和一条连枝构成的回路． （2） 基本割集 设无向图 G 的割集 S （割集是把连通图分成两个分离部分的最少支路集合） ，若 S 中仅包含有T 中的一条树枝，则称此割集为基本割集，记为()S e 。 基本割集是集合中的元素只有一条是树枝，其他的为连枝． （3） 等长变换 设T=(V,H),为一棵生成树，e ∈ H, 'e ∈ E, 'e ? H,当且仅当'e ∈()cf e ，也就是说 e ∈()S e ，则'T =T ⊕{e, ' e }也是一棵生成树。当()e ω='()e ω时，这棵生成树叫做等长变换。 等长变换就是从基本回路中选取与树枝等权边，并与此树枝对换后形成的生成树． 根据以上定理得出2个结论：①若在某个回路C 中有一条唯一的最长边，则任何一棵最小生成树都不含这条边；②若在某个边 e 的割集中有一条唯一最短边，则每棵生成树中都必须含这条边．由上面结论可以得到唯一性：若图 G 中的生成树T = （V ,H ）是唯一的一棵最小生成树，当且仅当任意一连枝e ∈ H, ' e ∈ E 都是其基本回路中唯一最长边，任意一条树边 e 都是其基本割集()S e 中的唯一最短边． Bootloader 设计分析 3.1 Bootloader 的操作模式 (Operation Mode) 大多数 Bootloader 都包含两种不同的操作模式[2]： (1). 启动加载（Boot loading）模式：也称为“自主”模式。即Bootloader 从目标机上的某个固态存储设备上将操作系统加载到 RAM 中运行，整个过程并没有用户的介入。 (2).下载（Downloading）模式：在这种模式下，目标机上的Bootloader将通过串口或网络连接等通信手段从主机（Host）下载内核映像和根文件系统映像等，然后保存到目标机上的FLASH 类固态存储设备中。Bootloader的这种模式通常在系统初次安装和更新时被使用，工作于这种模式下的Bootloader通常都会向它的终端用户提供一个简单的命令行接口。 在我们的Bootloader设计中我们同时支持这两种工作模式，采用的方法是：一开始启动时处于正常的启动加载模式，但并不立即启动进入uClinux内核，而是提示延时5秒，等待终端用户如果按下某一特定按键，则切换到下载模式，否则继续启动uCLinux 内核。 3.2 Bootloader 的启动及初始化 基于ARM的芯片多数为复杂的片上系统（SoC），这类复杂系统里的多数硬件模块都是可配置的[3]。因此大多数 Bootloader 都分为 stage1 和 stage2 两大部分。依赖于 CPU 体系结构的代码，通常都放在 stage1 中，而且在这一部分，我们直接对处理器内核和硬件控制器进行编程，因此常常都用汇编语言来实现。而stage2则通常用C语言来实现，这样可以实现更复杂的功能，而且代码会具有更好的可读性和可移植性。 3.2.1 Bootloader的stage1 这部分代码必须首先完成一些基本的硬件初始化，为stage2的执行以及随后的kernel 的执行准备好一些基本的硬件环境[2]。Bootloader的stage1一般通用的内容包括： * 定义程序入口点 * 设置异常向量表 * 初始化存储系统（包括地址重映射） * 初始化有特殊要求的端口，设备 * 初始化用户程序的执行环境 一．linux系统上电后启动过程： ---→启动引导加载程序bootloader（一些CPU在运行bootloader之前，会先运行一段固化的程序）。 --->启动内核 --->挂载根文件系统 其中，Boot paramoters分区中放置一些可设置的参数，比如，IP地址、串口波特率、要传递给内核的命令行参数等。 二．为什么要进行bootloader移植？ ---→bootloader的实现依赖于具体的硬件，而在嵌入式产品中硬件的配置千差万别，即使相同的CPU，它的外设也有可能不同，所以不可能有一个bootloader支持所有的CPU，即使是支持CPU架构比较多的U-Boot，也不是拿来就能用的，也需要做一些简单的移植。 三.Bootlader的启动过程分为两个阶段： 第一阶段： --->硬件设备的初始化（进入svc模式、关闭watchdog、禁中断、设置系统时钟频率、初始化存储控制器、初始化堆栈）。 --->uboot的代码重定位，从nand中拷贝至sdram中，默认是从norflash拷贝至sdram --->跳转到第二阶段c代码继续执行 第二阶段： --->初始化本阶段要使用的硬件设备（如串口）。 --->检测系统内存的映射（memory map）。 --->从flash读取内核镜像和文件系统到sdram中。 --->为内核设置启动参数。 --->启动内核。 注意：1、所谓检测内存映射，就是确定板子上使用了多少内存，它们的地址空间如何 2、存储在flash上的内核镜像可能是压缩的（如.cramfs 格式），在读到内存中就需要解压，但是对于带有自解压功能的内核来说，是不需要boorloader来解压。 3、将根文件系统拷贝到sdram中，这个不是必须的，具体看内核访问它的方式。 经典最小生成树prim与kruskal算法分析比较 例题 农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网， 并连接到所有的农场。当然，他需要你的帮助。 约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。 为了用最小的消费，他想铺设最短的光纤去连接所有的农场。 你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光 纤最短的方案。 输入格式 Input Format 输入格式经常会以两中形式 (1)采用邻接矩阵存储 第一行为农场的个数，N（3<=N<=100）。 接下去为一个N*N的矩阵,表示每个农场之间的距离。(农场之间的距离小于999， 0路线表示无法直接到达)。 (2)图采用边目录方式存储。 第一行N为农场的个数,M为农场与农场之间共有M条可以搭设光纤路线。 接下去的M行为中每行有3个数A，B，C。分别表示农场A到农场B的距离为B。 输出格式 Output Format 输出连接所有农场并所用光纤最短的方案。 (输出之后要求换行) 样例输入 Sample Input (1)采用邻接矩阵存储。 (2)采用边目录方 式存储。 6 6 7 0 3 0 0 0 2 1 2 3 3 0 5 0 2 0 2 3 5 0 5 0 1 0 0 3 4 1 0 0 1 0 4 0 4 5 4 0 2 0 4 0 1 2 5 2 2 0 0 0 1 0 6 5 1 1 6 2 样例输出 Sample Output （1）采用邻接矩阵存储（2）采用边目录方式存储。 10 10 (1)我的prim的代码采用邻接矩阵存储 prim适合采用邻接矩阵存储代码如下 var n,i,j,w,k,t,w1,m,min,p:longint; ch:char; lowcost,coset:array[1..100]of longint; bo:array[1..100]of boolean; map:array[1..100,1..100]of longint; {邻接矩阵图} begin while not eof do begin readln(n); if n=0 then break; for i:=1 to n do for j:=1 to n do //初始化 begin read(map[i,j]); if (i=j)or(map[i,j]=0)then map[i,j]:=maxlongint; //把不相连的点之间设为无穷大 end; for i:=1 to n do begin lowcost[i]:=map[1,i]; coset[i]:=1; bo[i]:=false; {初始化lowcost集合(即每个点到集合的最短距离)与bo数组和 coset(设这个点为A)到集合内于他连接的且最短距离的另一个点(这个点为b) 那么coset就是记录与点A的父亲节点B(B一定要具备上述条件）} end; bo[1]:=true; m:=0; for i:=1 to n-1 do begin min:=maxlongint; for j:=1 to n do if (bo[j]=false)and(lowcost[j]BootLoader引导程序
详解bootloader的执行流程与ARM Linux启动过程分析
最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)
最小生成树算法分析
bootloader
最小生成树经典算法
bootloader分析
最小生成树(Prim、Kruskal算法)整理版
(完整word版)实验5 最小生成树算法的设计与实现(报告)
Kruskal算法求最小生成树(java)
Linux启动全过程-由bootloader到fs
Boot_Loader介绍
数据结构课程设计报告最小生成树Kruskal算法[1]4545
单片机自编程及Bootloader设计
最小生成树的算法
bootloader流程
移植Bootloader过程总结
经典最小生成树prim与kruskal算法分析比较
相关文档
- 数学建模-最小生成树-kruskal算法及各种代码
- 算法合集之《最小生成树算法及其应用》
- 最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)
- Kruskal算法求最小生成树(java)
- 一种基于二进制编码的最小生成树算法
- 最小生成树算法
- 最小生成树及其算法
- 最小生成树经典算法
- c语言实现最小生成树算法
- 改进的最小生成树算法.
- 最小生成树算法(一)
- 最小生成树算法
- 几种求解最小生成树的算法 (论文)
- 经典最小生成树prim与kruskal算法分析比较
- 最小生成树算法讲解分解
- 图的最小生成树_prim算法
- 最小生成树算法详解.ppt
- 数据结构课程设计报告最小生成树Kruskal算法[1]4545
- 数学建模-最小生成树-kruskal算法及各种代码
- 最小生成树算法详解