软件体系结构经典问题——KWIC的分析和解决

KWIC作为一个早年间在ACM的Paper提出的一个问题,被全世界各个大学的软件设计课程奉为课堂讲义或者作业的经典。(From Wiki,FYI,D. L. Parnas uses a KWIC Index as an example on how to perform modular design in his paper "On the Criteria To Be Used in Decomposing Systems into Modules" - Available as ACM Classic Paper)

问题陈述:KWIC(Key Word In Context),Parnas (1972)
      KWIC索引系统接受一些行,每行有若干字,每个字由若干字符组成;每行都可以循环移位,亦即重复地把第一个字删除,然后接到行末; KWIC把所有行的各种移位情况按照字母表顺序输出
 软件体系结构经典问题——KWIC的分析和解决
?目的:考察不同的体系结构对变化的适应能力(modifiability)
?评价准则
处理算法的改变:例如,行的移位可在每行读入后、在所有行读入后、或当排序要求一组移位的行时執行;
数据表示的改变:例如,行、字、字符可以不同的方式存储;类似地,循环移位后的行可以显式或隐式存储(索引和偏移量);
系统功能的增强:例如,限制以某些“修饰词”(a, an, and等)打头的移位结果;支持交互,允许用户从原始输入表中删除一些行等;
效率:时间和空间;
复用:构件被复用的潜力。
 
Solution 1
Main Program/Subroutine with Shared Data
Elements of Main/Subroutine Architectural style are:
  • Components: Functions
  • Interactions: Function calls
  • Pattern: Main function controls the calling sequence
This is the primary organization of many software systems. This style reflects structural/procedural programming language (e.g. C programming language) in which these system are written.
 
 
?Decompose the overall processing into a sequence of processing steps.
Read lines; Make shifts; Alphabetize; Print results
?Each step transforms the data completely.
每一步完全转换数据
?Intermediate data stored in shared memory.
Arrays of characters with indexes
带索引的字符数组
Relies on sequential processing
串行处理
 
软件体系结构经典问题——KWIC的分析和解决
Solution 1Modularization
?Module 1: Input
Reads data lines and stores them in core.
Storage format: 4 chars/machine word; array of pointers to start of each line.
?Module 2: Circular Shift
Called after Input is done.
Reads line storage to produce new array of pairs: (index of 1st char of each circular shift, index of original line)
?Module 3: Alphabetize
Called after Circular Shift.
Reads the two arrays and produces new index.
 
?Module 4: Output
Called after alphabetization and prints nicely formatted output of shifts
Reads arrays produced by Modules 1 & 3
?Module 5: Master Control
Handles sequencing of the first 4 modules
Handles errors
 
Properties of Solution 1
?Batch sequential processing.
?Uses shared data to get good performance.
用共享数据获得性能
?Processing phases handled by control module.
So has some characteristics of main program – subroutine organization.
Depends critically on single thread of control.
?Shared data structures exposed as inter-module knowledge.
共享数据的结构是所有模块必须知道的
Design of these structures must be worked out before work can begin on those modules.
数据结构的设计必须在其他模块设计开始之前进行
 
方案优缺点:
+系统自然分解,符合人的处理习惯
+数据共享,处理效率高
+
–难以适应数据存储格式和整体处理算法的变化——爲什麽?
–系统构件难以支持复用——爲什麽?
 
仔细参考:

软件体系结构经典问题——KWIC的分析和解决

上一篇:@SpringBootApplication包含的三个注解及其含义


下一篇:ThreadGroup其实比ExecutorService更好