*영* 스토어

*영*

개인

팔로워0 팔로우

소개

등록된 소개글이 없습니다.

전문분야 등록된 전문분야가 없습니다.

판매자 정보

학교정보

입력된 정보가 없습니다.

직장정보

입력된 정보가 없습니다.

자격증

입력된 정보가 없습니다.

판매지수

판매중 자료수

2개
전체 판매량

5개
최근 3개월 판매량

0개
자료후기 점수

평균B
자료문의 응답률

-

전체자료 2개

[알고리즘] [c 언어]집합 커버링 알고리즘 분석

{설명- skills(기술 항목을 저장), players(선수집합,부분집합), covering(집합 커버에 참여한 부분집합) 구조체 선언- skills_arrays[](기술항목을 저장할 배열), subids_arrays[](선수 번호를 저장할 배열)을 선언한다- 선수번호(players_array[].key)와 그 선수의 기술항목(players_array[].set)을 저장할 연결리스트형 배열(players_array[])을 선언한다- skills 연결 리스트(기술 항목을 저장)를 초기화 한다- retval(cover() 함수의 정상 수행 여부를 판단할 때 사용)을 선언한다Main() 함수관련 구조체 및 호출 함수{{{{{메모리 맵{skillssizeMatchdestroyheadtail{player_array0sizeMatchkeydestroyheadtail1sizeMatchkeydestroyheadtail::::::7keysizeMatchdestroyheadtail{skills_array01234567891011{subids_array01234567{coveringsizeMatchdestroyheadtail{playerssizeMatchdestroyheadtail< 구조체 및 배열을 선언 >{skillssize0Matchmatch_skilldestroynullheadnulltailnull< skills 연결 리스트를 초기화 >{설명- skills_array[](기술 항목을 저장할 배열)에 a'∼'l'까지 값을 할당하여 기술 항목을 만든다(skills_array[]의 각 값들( a'∼'l')은 skills 연결리스트의 data 값으로 할당된다)- skills_array[]의 값을 skills 연결리스트 항목으로 추가한다(set_is_member() 함수에 의해 집합(skills 연결 리스트) 내에 동일한 항목이 존재하는지 검사를 하고, 존재하지않는다면 set_ins_next() 함수에 의해 연결 리스트의 tail부분에 새로운 항목을 추가한다)Main() 함수 소 만든다Main() 함수 소스관련 구조체 및 호출 함수{(중간 생략){{{메모리 맵{{{keyset'1'size0Matchmatch_skilldestroynullheadtail{listElmtlistElmtlistElmtlistElmtdatadatadatadatanextnextnextnext'a''b''c''d'{keyset'2'size0Matchmatch_skilldestroynullheadtail{listElmtlistElmtlistElmtlistElmtlistElmtdatadatadatadatadatanextnextnextnextnext'e''f''g''h''i'{keyset'8'size0Matchmatch_skilldestroynullheadtail{listElmtdatanext'l'{subids_array0'1'1'2'2'3'3'4'4'5'5'6'6'7'7'8'{{< (player_array[i].key = &subids_array[i])와 switch()문의 실행_중간생략 >{playerssize0Matchmatch_keydestroynullheadtail{listElmtlistElmtlistElmtdatadatadatanextnextnext{설명- print_players() 함수에 의해 players 연결 리스트(각 선수별 기술 항목을 저장)을 출력한다(print_players() 함수는 선수번호를 출력한 후, print_skill() 함수를 호출하여 그 선수의 기술항목을 출력한다)- cover() 함수를 호출하여 covering을 수행한다(cover() 함수는 다음장에 별도로 설명)- print_players() 함수에 의해 covering 결과를 출력한다- 각 선수별 기술 항목을 저장하고 있는 player_array[].set 연결 리스트의 항목들을 삭제한다.- 기술 항목을 저장하고 있는 skills 연결 리스트의 항목들을 삭제한다Main() 함수 소스관련 구조체 및 호출 함수{{{메모리 맵{{< 각 선수별 기술을 출력 > < covering같이 한다면, 0 을 반환하여야 그 이하 문장을 수행할 수 있게 되므로, 결국 skills 연결 리스트의 항목과 player_array[i].set의 항목이 동일한 것이 없는 것으로 되어 공집합을 반환하게 된다. 그러면 max_size가 0 이므로 다음 명령문에서 프로그램을 종료하게 된다)- max_member의 값을 subset에 저장하고 이 subset의 값을 covering 연결 리스트의 항목으로 추가한다- for 문에서 covering 연결 리스트에 추가된 항목의 기술을 skills 연결 리스트의 항목에서 삭제한다- set_remove() 함수에 의해 covering 연결 리스트에 추가 된 players 연결 리스트의 항목을 삭제한다cover() 함수 소스관련 구조체 및 호출 함수{{{{{playerssize8Matchmatch_keydestroynullheadtail{listElmtlistElmtlistElmtlistElmtlistElmtlistElmtlistElmtlistElmtdatadatadatadatadatadatadatadatanextnextnextnextnextnextnextnext'1''2''3''4''5''6''7''8'{메모리 맵 => while 문의 첫 번째 루프 수행{{{max_member{{subids_array0'1'1'2'2'3'3'4'4'5'5'6'6'7'7'8'{listElmtlistElmtlistElmtlistElmtlistElmtlistElmtdatadatadatadatadatadatanextnextnextnextnextnext'c''d''g''h''k''l'{keyset'6'size6Matchmatch_skilldestroynullheadtail{{{(for 문에 의해 players 연결 리스트의 항목 중 6번 항목이 선택됨){listElmtlistElmtlistElmtlistElmtlistElmtlistElmtdatadatadatadatadatadatanextnextnextnextnextnext'c''d''g''h'맵 => while 문의 두 번째 루프 수행{{{{{{{{{{{{{{{{max_member{subids_array0'1'1'2'2'3'3'4'4'5'5'6'6'7'7'8'{keyset'2'size5Matchmatch_skilldestroynullheadtail{{listElmtlistElmtlistElmtlistElmtlistElmtdatadatadatadatadatanextnextnextnextnext'e''f''g''h''i'{{(for 문에 의해 players 연결 리스트의 항목 중 2번 항목이 선택됨){intersectionsize3Matchmatch_skilldestroynullheadtail{max_size3{{{{{{{listElmtlistElmtlistElmtdatadatadatanextnextnext'e''f''i'{{{{{{( skills{a, b, e, f, I, j} ∩ 2번{e, f, g, h, i} = intersection{e, f, i} 이므로,skills 연결리스트와 player_array[].set의 교집합 size는 2번이 가장 크다. 교집합의 결과를의 결과를 intersection 연결리스트의 항목으로 추가하고, 이 size를 max_size로 한다{{coveringsize2Matchmatch_keydestroynullheadtail{{listElmtlistElmtdatadatanextnext'6''2'{{{{intersection 연결 리스트의 항목을 삭제하고 다음 루프에 입력받을 준비를 한다 ){subset{(covering 연결 리스트에 subset의 값을 항목으로 추가){listElmtlistElmtlistElmtlistElmtlistElmtlistElmtdatadatadatadatadatadatanextnextnextnextnextnext'a''b''c''d''e''f'listElmtlistElmtlistElmtlistElmtlistElmtlistElmtdatadatadatadatadatadatanextnextnexElmtlistElmtdatadatadatanextnextnext'6''2''1'{subset(covering 연결 리스트에 subset의 값을 항목으로 추가){listElmtlistElmtlistElmtlistElmtlistElmtlistElmtdatadatadatadatadatadatanextnextnextnextnextnext'a''b''c''d''e''f'listElmtlistElmtlistElmtlistElmtlistElmtlistElmtdatadatadatadatadatadatanextnextnextnextnextnext'l''k''j''i''h''g'{{{{{{{{{{{{{{{skillssize1Matchmatch_skilldestroynullheadtail{{{{{{{{{(covering 연결 리스트에 추가된 선수의 기술항목을 skills 연결 리스트의 항목에 삭제){playerssize5Matchmatch_keydestroynullheadtail{{listElmtlistElmtlistElmtlistElmtlistElmtlistElmtlistElmtlistElmtdatadatadatadatadatadatadatadatanextnextnextnextnextnextnextnext'1''2''3''4''5''6''7''8'(covering 연결 리스트에 추가된 players 연결 리스트의 항목을 삭제){playerssize5Matchmatch_keydestroynullheadtail{listElmtlistElmtlistElmtlistElmtlistElmtlistElmtlistElmtlistElmtdatadatadatadatadatadatadatadatanextnextnextnextnextnextnextnext'1''2''3''4''5''6''7''8'{메모리 맵 => while 문의 네 번째 루프 수행{{{{{{{{{{{{{{{{{{max_member{subids_array0'1'1'2'2'3'3'4'4'5'5'6'6'7'7'8'{keyset'3'si 종료)

자연과학| 2004.05.14| 11페이지| 1,000원| 조회(562)

알고리즘, 집합, C/C++, cover, 커버링

미리보기

닫기
[운영체제] Linux System Call 추가 평가B괜찮아요

< 문제의 이해 >1. 문제 : Linux 커널을 변경하는 여러 가지 커널 프로그래밍 중에서 시스템 호출을 구현한다.Linux 커널에 새로운 시스템 호출을 구현하는 것은 커널 수정과 새로운 시스템 호출을 이용하는사용자 수준 응용 프로그램의 작성이라는 두 가지 작업이 수행되어야 한다.2. 주요 개념 이해1) Linux 커널 구조{Application levelprocess 1process 2process 3System Calls IntefaceFile systemTask Managerex2fs, xiafs, procminix, nfs, msdosiso9660contextschedulersignalsloadable modulesMemory ManagerKernel levelBuffer Cachevirtual memorypage fault handingswappingDevice ManagerNetwork Managerblockcharacteripv4ethernet.........hd, cdrom, isdnnetwork, scsi, pciMachine Inteface (Interrupt)Hardware levelDeviceMemoryCPU그림 2.1 Linux 커널 내부 구조{가) Linux 커널은 크게 태스크 관리자, 메모리 관리자, 파일 시스템, 네트윅 관리자 그리고 디바이스 드라이버의 5가지 부분으로 구성된다.a) 태스크 관리자 : 태스크의 생성, 실행, 상태 전이, 스케줄링, 시그널 처리, 프로세스간 통신, 모듈등의 서비스를 제공한다.b) 메모리 관리자 : 가상 메모리, 주소 변환, 페이지 부재 결함 처리 등의 서비스를 제공한다.c) 파일 시스템 : 파일의 생성, 접근 제어, inode 관리, 디렉토리 관리, 수퍼 블록 관리, 버퍼 캐쉬 관리 등의 서비스를 제공한다.d) 네트윅 관리자 : 소켓 인터페이스, TCP/IP 같은 통신 프로토콜 등의 서비스를 제공한다.e) 디바이스 드라이버 : 디스크나 터미널, CD, 네트윅 카드 등과 같은 주변 장치를 구동하는 드라 소멸, 프로그램의 실행,스케줄링, 시그널 처리 등의 기능이 이 디렉토리에 구현되어 있다.b) arch 디렉토리 : Linux 커널 기능 중 하드웨어 종속적인 부분들이 구현된 디렉토리이다.이 디렉토리는 CPU의 타입에 따라 하위 디렉토리로 다시 구분된다. 대표적인 하위 디렉토리에는 인텔 처리기를 구현한 arch/i386 디렉토리, 모토롤라 68XXX 계열 처리기를 구현한 arch/m68k 들이 있다.arch/i386 디렉토리는 다시 5개의 하위 디렉토리로 구분되어 있다. arch/i386/boot디렉토리에는 시스템의 초기화 때 사용되는 부트스트랩 코드가 구현되어 있으며,커널 소스를 컴파일하면 그 결과로 만들어지는 Linux 커널인 vmlinuz 파일도 여기에 생성된다. 한편 arch/i386/kernel에는 태스크 관리자 중에서 문맥 교환이나 쓰레드 관리 같은 하드웨어 종속적인 부분이 구현되어 있으며, arch/i386/mm에는 메모리 관리자 중에서 페이지 부재 결함 처리 같은 하드웨어 종속적인 부분이 구현되어있다.arch/i386/lib에는 커널이 사용하는 라이브러리 함수가 구현되어 있으며, arch/i386/math-emu에는 FPU(Floating Ping Unit)에 대한 에뮬레이터가 구현되어 있다.c) fs 디렉토리 : Linux에서 지원하는 다양한 파일시스템과 open(), read(), write() 등의 시스템 호출이 구현된 디렉토리이다. 각 파일시스템은 이 디렉토리의 하위 디렉토리에 구현되어있으며, 대표적인 파일시스템으로는 ext2, nfs, ufs, msdos, ntfs, proc, coda 등이있다. 한편 다양한 파일시스템을 사용자가 일관된 인터페이스로 접근할 수 있도록 하기 위하여 Linux는 시스템 호출과 각 파일시스템 사이에 추상화된 한 층을 넣었으며,이것이 VFS(Virtual File System)이다.d) mm 디렉토리 : 메모리 관리자가 구현된 디렉토리이다. 가상 메모리(virtual memory), 태스크마다할당되는 메모리 객렉토리에 구현되어 있다.예를 들어, 인텔 처리기일 경우 include/asm-i386라는 디렉토리에 헤더 파일들이 구현되어 있다.j) doc 디렉토리 : Linux 커널 및 명령어들에 대한 자세한 문서 파일들이 존재한다.k) lib 디렉토리 : 커널 라이브러리 함수들이 구현되어 있다.l) modules 디렉토리 : 컴파일된 모듈 함수들이 존재한다.m) scripts 디렉토리 : 커널 구성 및 컴파일할 때 이용되는 스크립터들이 존재한다.2) 시스템 호출 : 사용자 수준 응용들에게 커널이 자신의 서비스를 제공하는 인터페이스이다.따라서 사용자가 운영체제의 기능이나 모듈을 활용하기 위해서는 반드시 시스템 호출을 사용해야 한다. Linux 커널은 각 시스템 호출을 함수(System Call handler)로 구현해 놓고,각 시스템 호출이 요청되었을 때 대응되는 함수를 호출하여 서비스를 제공한다.{{user taskENTRY(system_call) /* arch/i386/kernel/entry.S */main()SAVE_ALL{IDT..........0x0divide_error()call *SYMBOL_NAME(sys_call_table)(,%eax,4)fork()debug()....}nmi()ret_from_sys_call(schedule, signal, bh_active,......nested interrupt handling)libc.a.....fork()sys_call_table{.....1sys_exit()sys_fork()movl 2, %eax2sys_fork()/* arch/i386/kernel/process.c */int $0x800x80system_call()3sys_read()/* kernel/fork.c */............4sys_write()}..........그림 2.4 시스템 호출 처리 과정의 예그림 2.4는 사용자 수준 응용이 fork()라는 시스템 호출을 요청했을 때의 처리 과정이다.먼저 /usr/lib/libc.a라는 이름의 표준 C과정{a) WOW Linux 7.3을 설치할 가상 머신을 WOWlinux7.3라는 이름으로 추가한다.{{{{{{{{{{{새로운 가상 머신 WOWlinux7.3가 설치된 화면이다. VMware 화면에는 메모리와 하드디스크 및 기타여러 가지 가상 머신의 시스템 사양이 나오는데, 현재 사용하고 있는 컴퓨터의 자원을 사용하도록 구성된다. 메모리, CD-ROM과 플로피 드라이버, 네트워크 카드 등이 가상 머신이 사용할 수 있는 시스템 자원으로 인식되어 있는 것으로 볼 수 있다. 가상 머신을 구동하려면 구동시킬 가상 머신을 선택한 후 Power ON 스위치를 클릭하면 된다.(시스템 자원은 VMware의 메뉴를 통해 추가할 수 있고, 메모리 용량 또한 증가시킬 수 있다.)2) 가상 머신 WOWlinux7.3에 WOW Linux 7.3을 설치한다.{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{2. Linux 커널에 새로운 시스템 호출을 구현하는 것은 커널 수정과 새로운 시스템 호출을 이용하는 사용자 수준 응용의 작성이라는 두 가지 작업으로 구성된다. 그리고 각 작업은 다음과 같은 세부 단계로 이루어진다.1) 커널 수정가) 시스템 호출 번호 할당 : Linux 커널이 제공하는 모든 시스템 호출은 각각 고유한 번호를 갖는다.그러므로, 우선적으로 시스템 호출 번호를 할당해야 한다.나) 시스템 호출 테이블 등록 : Linux 커널이 제공하는 모든 시스템 호출 처리 함수는 sys_call_table이라는 테이블에 등록이 되어야 하므로, 새로운 시스템 호출 함수를 시스템 호출 테이블에 등록해야 한다.다) 시스템 호출 처리 함수 구현 : 새로운 시스템 호출 함수를 등록하고 나면, 시스템 호출 처리 함수를구현해야 한다. 시스템 호출 처리 함수들 중에서 태스크 관리자와 관련된 함수들은 Linux 커널 소스 트리 중에서 kernel/ 디렉토리에, 파일 시스템과 관련된 함수들은 fs/ 디렉토리에 구현하는 것이 일반적이다.새로운 함수가 커널 컴파일 시에 포함될 수 있도록는 put_user()라는 매크로를 사용하였다. 이 매크로는 usr/src/linux-2.4.18-4/include/asm-i386/uaccess.h에 정의되어 있다.put_user()를 사용하기 전에 res라는 사용자 공간에 쓰기가 가능한지 확인하기 위해 verify_area()라는커널 내부 함수를 사용하였다.asmlinkage" 라는 키워드는 C로 구현된 함수가 어셈블리 언어로 구현된 함수에서 호출될 때 사용하는키워드이다. 커널 수준에서는 사용자 수준에서 수행되는 표준 라이브러리를 사용할 수 없으므로, 따라{서, printf()와 비슷한 일을 수행하는 printk()라는 커널 라이브러리를 사용하였다.usr/src/linux-2.4.18-4/kernel/Makefile을 수정하여 커널 컴파일 시에 test_syscall.c가 컴파일 될 수 있{록 한다.2. 커널 컴파일 및 리부팅1) 커널 구성"make menuconfig" 명령을 이용해서 새로 만들어질 Linux 커널에게 현재 시스템에 존재하는 하드웨어{특성, 커널 구성 요소, 네트윅 특성 등의 정보를 알려주는 과정을 수행한다.make menuconfig"를 실행하고, 우리가 질문에 답할 준비가 되면, 보통 y'(yes) 또는 n'(no)으로 대답하면 된다. 그 중에서 장치 드라이버들은 보통 m' 옵션을 가지고 있다. 이것은 module'을 뜻하며, 시스템이 컴파일 할 때 직접 커널에 집어넣지 않고 적재 가능 모듈로 만드는 것을 말한다.2) 커널 컴파일{"make dep 명령어를 이용해서 모든 오브젝트 파일과 구 버전에 남겨 놓은 의존성을 제거한다.{make clean" 명령을 이용해서 과거의 오브젝트 파일이나 구 버전 소스 파일 등을 지우는 일을 한다.make bzImage" 명령을 이용해서 커널 컴파일을 수행한다.수행된 결과로 /usr/src/linux-2.4.18-4/arch/i386/boot/에 bzImage"라는 새로 압축된 커널을 남긴다.{3) 커널 인스톨make modules", make mod티{

자연과학| 2004.05.14| 20페이지| 1,000원| 조회(1,970)

운영체제, 리눅스, Linux, 시스템콜, syscall call

미리보기

닫기